how to determine the modulo rules?

Question

I´m repeating some old math exercises and could`t remember the following modulo rule: I have to find the smallest natural $k>0$ $mod(3^k,7)=1$

the solution seems straight forward. But I dont remember why:

$mod(3^1,7)=(3,7)=3$

$mod(3^2,7)=mod(3 \cdot 3,7)=2$

$mod(3^3,7)=mod(2 \cdot 3,7)=6$

$mod(3^4,7)= mod(6 \cdot 3,7)=4$

$mod(3^5,7)=mod(4 \cdot 3,7)=5$

$mod(3^6,7)= mod(5 \cdot 3,7)=1$

Its prety clear that the rest has been included into the next following term. What I dont understand is why. Could somebody provide a nice explanation...Thx

Answer 1

What you seem to be referring to is this:

If $a,b$ are integers and $a\equiv c\pmod{n}$ for some integers $n\ne 0$ and $c,$ then $ab\equiv cb\pmod{n}$.

To see why, recall that $a\equiv c\pmod{n}$ means that $a=kn+c$ for some integer $k,$ so that $$ab=(kn+c)b=bkn+cb.$$ Since $bk$ is an integer, this means that $$ab\equiv cb\pmod{n},$$ as desired.

Answer 2

I personally don't like your notation for modulus. I will simply use the equal sing and (by convention) here we will be always dealing with modulo 7:

$3^1 = 3$

$3^2 = 3 \times 3 = 2$

$3^3 = 3 \times 3^2 = 3 \times 2 = 6$, as $3^2 = 2$ by the previous result

...

$3^k = 3 \times 3^{k-1}$ and you can substitute the $3^{k-1}$ by the previous value

Just like in plain old math the definition of exponentiation is the same and you can apply the results you have previously obtained.

Answer 3

One could use Fermat's Little Theorem. Knowing that $7 \nmid 3$, that is $7$ does not divide $3$ and given the fact that $7$ is a prime number, we know that $$ 3^{7-1}=3^6\equiv 1 \mod 7 $$

A bit larger scope than your question asks: Modular arithmetic forms a group under addition and 'nearly' under multiplication (if one looks at the residue classes, $\overline{0}$ does not have an inverse). Moreover, we know that in such a group any element relatively prime to the number being modded by will generate the group, since $\text{gcd}(3,7)=1$, then $3^k$ will generate all of the possible remainders $\mod 7$ if we run through and $7$ consecutive $k$'s.

$3^1=3 \mod 7$. This gives us the element $\overline{3}$. Multiplying by $3$ again yields $9\equiv 2 \mod 7$. So now we have $\overline{2}$. Again, multiplication by $3$ gives $6$, so that's $\overline{6}$. Next we have $18\equiv 4 \mod 7$, that's $\overline{4}$. Then $4\cdot 3=12\equiv 5 \mod 7$, and we have $\overline{5}$. Finally, we have $5\cdot 3=15\equiv 1 \mod 7$ and we have the identity element $\overline{1}$. So the inverse of $3$, that is $\overline{3}$ in the group of residues $\mod 7$ is $5$, that is $\overline{5}$ since $\overline{3} \cdot \overline{5} \equiv \overline{1} \mod 7$. Notice what this implies when the original gcd is \emph{not} $1$!

Answer 4

The recursion is this: multiply the prior line $\rm\,b^n\equiv a\,$ times $\rm\,b,\,$ to obtain $\rm\,b^{n+1},\,$ i.e.

$$\begin{eqnarray}\rm \color{#0a0}{b^n} &\equiv\,&\rm \color{#c00}a\\ \rm\Rightarrow\ b^{n+1}\! =\, b \color{#0a0}{b^n}&\equiv\,&\rm b\color{#c00}a \end{eqnarray}\qquad\qquad\qquad\ \ $$

We substituted the argument $\rm\color{#0a0}{b^n}$ of a product $\rm\,b\color{#0a0}{b^n}$ by a congruent integer $\rm\color{#c00}a,\,$ i.e. we used

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}\ \ \ $ QED

There are also analogous sum and power rules

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

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

Congruence Power Rule $\rm\quad\ A\equiv a\ \Rightarrow\ 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\, A^{n+1}\equiv a^{n+1},\,$ by the Product Rule, so the result follows by induction on $\,n.$

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,\,$ when it reduces to and inductive application of the Product Rule).