# Why does a number like $2^n\bmod 7$ have a repeating pattern?

I am struggling with the formal understanding of why a number like $2^n\bmod7$ have a repeating pattern? $1, 2, 4, 1, 2 ,4\ldots$

The repeating pattern show up in many places of modular arithmetic, what is the primary reason for this?

Thank you

-
Finiteness.  –  Berci Feb 12 '13 at 15:30
Care to explain a bit more @Berci? :) –  Lukas Arvidsson Feb 12 '13 at 15:33
I'm sure many others will –  Berci Feb 12 '13 at 15:35

Consider a sequence $a^1, a^2, a^3,\ldots$, all taken $\mod{n}$. We only assume a finite number of values (at most $n$), and the sequence is infinite, so after at most $n+1$ many terms we have a repetition, say $a^i = a^j$ ($\mod{n}$,for some $i <j$). But this means that the sequence will repeat after $j$ again: $a^{j+1} = a^{i+1}$ and so on, till we have again $j-i$ terms, after which we are back again etc. Because you have a prime modulus in your example, $a^{n-1} = 1$, so we actually cycle back to the starting value. In general you might get a start sequence and then the repeating part (between $a^i$ and $a^j$).

-
This answer is the least focused on powers and the best at pointing out that any iteration $n, f(n), f(f(n)) \ldots$ will enter a cycle in $\pmod k$. This is very general. –  Ross Millikan Feb 12 '13 at 17:14
Thank you for the answer! I will sit down and try to map out this way of thinking. Very much apreciated! –  Lukas Arvidsson Feb 12 '13 at 19:31

Start with $2^n \pmod{7}$. It can be written as $2^{n- 3} \pmod{7} \times 2^3 \pmod{7}$ which is $2^{n- 3} \pmod{7}$.

So $2^n \equiv 2^{n- 3} \pmod 7$ for all $n$. That is why we see a repeating pattern every three terms.

-
This is the only answer here that makes sense to me. –  Pureferret Feb 12 '13 at 17:36
I have had a bit of a hard time to truly understand the other answers aswell, but this made sense to me, thank you! –  Lukas Arvidsson Feb 12 '13 at 19:34
Hmm. I understand what you were thinking (and that's all correct), but IMHO the notation here is a bit poor. You seem to be mixing congruences ($\equiv$) and binary mod (i.e. remainder operation) at leisure. That might be tolerable, but because they both use the notation $\pmod 7$, it may confuse some, and I would most certainly steer away from that. –  Jyrki Lahtonen Feb 12 '13 at 20:04
@JyrkiLahtonen Pardon, I am very bad at this. I hope everyone sees where I am getting. :-) –  Parth Kohli Feb 13 '13 at 15:08
No biggie. +1 :-) –  Jyrki Lahtonen Feb 13 '13 at 16:21

The primary reason is that

$$(a \mod n) \times (b \mod n) \mod n = ab \mod n$$

In the sense that, if you want to compute $ab \mod n$, you can first compute $a \mod n$ and $b \mod n$ and then multiply them together, and reduce $\mod n$. For example, $24 \mod 5 = 4$, but we have $24 = 4 \times 6$,

$$4 \mod 5 = 4 \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, 6 \mod 5 = 1$$

And, indeed $4 \times 1 = 4$.

To see how this applies, note that $2^{m+n} = 2^{m} \times 2^{n}$. If we have concluded that $2^{m} = 1 \mod 7$, then $2^{m+n} \mod 7 = (2^{n} \mod 7) \times 1$, and so after $m$ steps the pattern returns to where it started.

-

As 7 is a prime number, $\mathbb Z_7$ is a field. Therefore $\mathbb Z_7\setminus \{0\}$ is a (finite) group. So $z\in\mathbb Z_7\setminus\{0\}$ has finite order, therefore there exists a $k\in\mathbb N$, $z^k = 1$ (in $\mathbb Z_7$). Then for every $n\in \mathbb N$ you write $n$ as $n=g\cdot k + r, ~r<k$ and it follows that $z^n = z^r$ (again, in $\mathbb Z_7$).

This will give you the repeating pattern. Of course this works with every prime number $p$ as $\mathbb Z_p$ is a field.

-

It is a group-theoretic principle. Suppose $G$ is a finite group and that $g\in G$. Then, the mapping $n\mapsto g^n$ cannot be 1-1. You can't embed an infinite set inside of a finite one. So there are $m$ and $n$ so that $g^m = g^n$.

With no loss of generality, assume $m\le n$. Then $g^{n-m} = e$, where $e$ is the identity element of $G$. Choose the smallest positive integer $d$ so that $g^d = e$. The function $n\mapsto g^n$ will have period d. Also, it is not hard to argue, using the minimality of $d$, that $n\mapsto g^n$ is 1-1 on $\{0, 1, \cdots , d-1\}$.

-

As for non-negative integers $m,n$

$2^{m+n}\pmod7\equiv2^m\pmod7\cdot 2^n\pmod7$ and $2^3=8\equiv1\pmod 7$

Alternatively, using Euler's Totient Theorem, $a^{\phi(m)}\equiv1\pmod m$ for natural numbers $a,m$ where $(a,m)=1$

So, the values of $a^r\pmod m$ must recurs after $\phi(m)$ values for integer $r\ge0$

Using Carmichael Function, $a^{\lambda(m)}\equiv1\pmod m$ for natural numbers $a,m$ where $(a,m)=1$

So, the values of $a^r\pmod m$ must recurs after $\lambda(m)$ values for integer $r\ge0$

In fact, the period of the cycle is called the Multiplicative Order, observe here that its value is $3$

-

Hint $\rm\ mod\ 7\,$ the doubling map $\rm\, n\to 2n\,$ has inverse $\rm\, n\to 4n.\:$ Being an invertible map on a finite set the map is a permutation. Written in cycle notation the doubling permutation is $(1\, 2\, 4)\, (3\, 6\, 5).$ Here the first cycle $(1\, 2\, 4)\,$ is the orbit of $1,$ i.e. $\rm\,2^n.\,$ Thus the pure periodicity of $2^n$ is just a special case of the fact that orbits of permutations are cycles.

Remark $\$ Such pure cyclicity fails for noninvertible maps, e.g. $\rm\,mod\ 12\!:\ 2^n = 1,2,4,8,4,8,\ldots$ has the "preperiod" part $\,1,2$.

Not too infrequently students effectively "reinvent the wheel (cycle)" by overlooking this simple way of deriving cyclicity via the known cycle structure of permutations. For a less trivial example see e.g this competition problem and other posts on reinventing the wheel (cycle).

-

Let's ignore the specifics of the problem and just look at why finiteness gives the answer.

We are in a situation where we have only finitely many possible "states". The process that decides what state to go to next depends only on the current state.

These facts combined imply that the process eventually gets into a cycle that repeats indefinitely. The proof is easy:

Suppose that there are $N$ states. After $N+1$ steps, we have to have visited a particular state at least twice. Call it $S$.

Because the steps to take after you visit $S$ are fixed, the second time you visit $S$ you have to repeat all of the steps you took after the first time you visited $S$. Which means you'll visit $S$ a third time, and repeat the steps, and you'll visit $S$ a fourth time....

In this case, the state is very simple: it is just an element of the integers modulo $7$, interpreted as the "current value" of $2^n$. Advancing to the next value of $2^n$ is just multiplication by $2$ (modulo $7$), which depends only on the current state.

So when we're in the state $1$, you've computed that the next three states are $2$, $4$, and $1$. But then we're at $1$ again so the next three states are $2$, $4$, and $1$, and so forth.

This same idea works for lots of things. For example, it proves that a rational number has a repeating decimal expansion. The process you consider is long division, and the state you use is the remainder you've calculated so far. Eventually, the remainder has to repeat. Because the digits produced by long division depend entirely on the remainders, they have to repeat as well.

-
Thank your for your explanation, I think it will serve me well when trying to understand he other answers posted here. –  Lukas Arvidsson Feb 12 '13 at 19:51

$1\cdot 1=1=0\cdot7+1$

$1\cdot 2=2=0\cdot7+2$

$1\cdot 4=4=0\cdot7+4$

$2\cdot 2=4=0\cdot7+4$

$2\cdot4=8=1\cdot7+1$

$4\cdot4=16=2\cdot7+2$

-