Why do remainders show cyclic pattern?

Solution 1:

First, let me address a simpler question: why is there a pattern to the remainders at all?

Suppose I have any positive integer $b$ (in your case $b=7$). Then remainders respect multiplication: if $x, x'$ are positive integers which yield the same remainder when divded by $b$, and $y, y'$ are positive integers which yield the same remainder when divded by $b$, then $xy$ and $x'y'$ yield the same remainder when divided by $b$.

This is modular arithmetic: for a positive integer $b$, we can develop arithmetic on the set $R_b=\{0, 1, 2, . . . , b-1\}$ by interpreting elements of $R_b$ as remainders. For instance, any time I multiply two even numbers I get an even number; this is represented as $$0\times 0=0 \quad \mbox{(in $R_2$)}.$$ Because remainders respect multiplication, this makes sense and works the way we want it to.

So what does this have to do with powers? Well, fix $b$, and consider the sequence $a, a^2, a^3, . . .$. Since $R_b$ is finite there are some $m<n$ such that $a^m$ and $a^n$ leave the same remainder when divided by $b$. Once this happens, the remainders will repeat: the remainder of $a^{n+1}$ when divided by $b$ will be the same as the remainder of $a^{m+1}$ when divided by $b$, etc. So the sequence of remainders of powers of some number will always be eventually repeating.

Note that "eventually" is crucial here: consider $a=3$, $b=27$. Then the sequence of remainders is $3, 9, 0, 0, 0, 0, . . .$. Similarly, if we take $a=2$ and $b=12$ we get $2, 4, 8, 4, 8, 4, 8, . . .$ This happens because $a$ and $b$ share prime factors. Euler's theorem says that if, by contrast, $a$ and $b$ are coprime (have no factors besides $1$ in common), then this pattern is just repeating, full stop, and in fact tells us how long it will take to repeat.