0

If $a \equiv b\mod n$ then $a^m \equiv x \mod n$. Please express $x$ in terms of $a,b,n,m$. Also please provide an explanation, if possible.

TMM
  • 9,976
  • 2
    You already wrote the answer: $x\equiv a^m\equiv b^m\mod n$. – Ragnar Feb 16 '14 at 16:14
  • actually the question was to find the remainder when 3^51 is divided by 7 so 3^3 = -1(mod 7) Now by taking power 17 on both sides.. What will happen to remainder? –  Feb 16 '14 at 16:16
  • If $a\equiv b\mod n$, it follows for any $m\in \mathbb N$ that $a^m\equiv b^m\mod n$. – Ragnar Feb 16 '14 at 16:17
  • Does your notation $\ a\equiv b\ {\rm mod}\ n\ $ mean that $b$ is the remainder of $a$ divided by $n$, or does it denote a congruence, i.e. $,n\mid a-b,?\ \ $ – Bill Dubuque Feb 16 '14 at 16:17
  • @Bill the notation means that a-b is divisible by n –  Feb 16 '14 at 16:24

2 Answers2

2

It is better to work with congruences rather than remainder (or mod) operations. Recall that $\,a\equiv b\pmod n\,$ means precisely that $\,n\mid a-b.\,$ Then we have an arithmetic of congruences highly analogous to ordinary integer arithmetic - see the fundamental rules below.

Let's consider your real question (in comments). Working mod $7$, by the $\rm\color{#0a0}{Power\ Rule\ (PR)}$ $$\,\color{#c00}{3^3\equiv -1}\,\overset{\large\rm\color{#0a0}{(PR)}}\Rightarrow\, (\color{#c00}{3^3})^{17}\equiv (\color{#c00}{-1})^{17}\,\Rightarrow\, 3^{51}\equiv -1\pmod 7$$

Therefore $\ 3^{51} = -1 + 7k,\ $ so $\, -1\equiv 6\,$ is the remainder left when $\,3^{51}$ is divided by $\,7$.

Congruence Sum Rule $\rm\qquad\quad A\equiv a,\quad B\equiv b\ \Rightarrow\ \color{#c0f}{A+B\,\equiv\, a+b}\ \ \ (mod\ m)$

Proof $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a) + (B\!-\!b)\ =\ \color{#c0f}{A+B - (a+b)} $

Congruence Product Rule $\rm\quad\ A\equiv a,\ \ and \ \ B\equiv b\ \Rightarrow\ \color{blue}{AB\equiv ab}\ \ \ (mod\ m)$

Proof $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a)\ B + a\ (B\!-\!b)\ =\ \color{blue}{AB - ab} $

Congruence $\,\rm\color{#0a0}{Power\ Rule}$ $\rm\qquad\ \, \color{}{A\equiv a}\ \Rightarrow\ \color{#c00}{A^n\equiv a^n}\ \ (mod\ m)$

Proof $\ $ It is true for $\rm\,n=1\,$ and $\rm\,A\equiv a,\ A^n\equiv a^n \Rightarrow\, \color{#c00}{A^{n+1}\equiv a^{n+1}},\,$ by the Product Rule, so the result follows by induction on $\,n.$

Polynomial Congruence Rule $\ $ If $\,f(x)\,$ is polynomial with integer coefficients then $\ A\equiv a\ \Rightarrow\ f(A)\equiv f(a)\,\pmod m.$

Proof $\ $ By induction on $\, n = $ degree $f.\,$ Clear if $\, n = 0.\,$ Else $\,f(x) = f(0) + x\,g(x)\,$ for $\,g(x)\,$ a polynomial with integer coefficients of degree $< n.\,$ By induction $\,g(A)\equiv g(a)\,$ so $\, A g(A)\equiv a g(A)\,$ by the Product Rule. Hence $\,f(A) = f(0)+Ag(A)\equiv f(0)+ag(a) = f(a)\,$ by the Sum Rule.

Beware $ $ that such rules need not hold true for other operations, e.g. the exponential analog of above $\rm A^B\equiv a^b$ is not generally true (unless $\rm B = b,\,$ so it reduces to the Power Rule, so follows by inductively applying $\,\rm b\,$ times the Product Rule).

Bill Dubuque
  • 272,048
0

Let's say $S = (|a-b|\,/\,n \times m\,/\,n )$. Then $x = (S-\lfloor S \rfloor)\times n; x \in \{0,1,2,...,n-1\}$

Explanation: $r = |a-b|\,/n$ is a remainder of $a$ divided by $n$ (whole positive number). $r\times m$ is the accumulated remainder of $a^m$. $S = r\times m\,/n$ is a fraction whose decimal part represents $x/n$. So $x/n = S-\lfloor S \rfloor$ where $\lfloor S \rfloor$ stands for $floor(S)$.

addingKofi
  • 1
  • 1