# Does $2^n \bmod n$ ever repeat?

Title basically says it all, but...

Is it known whether the sequence generated by $$2^n \bmod n$$ is periodic as $$n$$ traverses the natural numbers?

Just for some flavor, the first 50 elements:

{0, 0, 2, 0, 2, 4, 2, 0, 8, 4,
2, 4, 2, 4, 8, 0, 2, 10, 2, 16,
8, 4, 2, 16, 7, 4, 26, 16, 2, 4,
2, 0, 8, 4, 18, 28, 2, 4, 8, 16,
2, 22, 2, 16, 17, 4, 2, 16, 30, 24,
...}

• I don’t know, but I would guess no, because I would expect the sequence to be unbounded. – Joe Aug 26 at 12:28
• This sequence appear on the list of integer sequences as oeis.org/A015910. It is conjectured that this sequence takes on every value but $1$. The much weaker statement that it takes on arbitrarily high values would be enough to disprove periodicity. – quarague Aug 26 at 12:33

$$a_n=0$$ iff $$n$$ is a power of $$2$$. This is obviously not periodic.

• All that means is that the eventual period, if one exists, must be a power of 2, right? – Connor Harris Aug 26 at 13:04
• The gap between zeroes gets twice as long every time they occur. So there will never be a period. – Matthew Daly Aug 26 at 13:07
• Right, iff not if. – Connor Harris Aug 26 at 13:50
• Several good answers, but I gotta go with this one. Duh. – Trevor Aug 26 at 17:18

If the sequence be periodic, there should exist $$M$$ s.t. $$\forall n,2^n\,mod\,n.

Choose $$k$$ s.t. $$2^k>M$$. Choose big prime $$p>2^k$$.

Let $$n=pk$$ then $$2^n\equiv 2^k$$ mod $$p$$. Thus, $$2^n\,mod\,n\ge 2^k$$. (contradiction)

It's easy to prove that $$2^{3^n} \equiv 3^n-1 mod(3^n)$$. So if you consider the sequence $$x_{n}=(2^{3^n} \equiv 3^n-1 mod(3^n))$$ it's divergent to infinity, and assumes infinite distinct values. So the sequence can't be periodic.