# For every prime $p$ exists infinitely many integers $n$ such that $p \mid 2^n-n$.

Prove that for every prime $p$ exists infinitely many integers $n$ such that $p \mid 2^n-n$.

I have no idea how to prove that.

• If you can find one solution you can find an infinite number, since $2^{n + p \cdot (p-1)} \equiv n + p \cdot (p-1) \pmod p$. – Dan Brumleve Jan 7 '15 at 18:21
• @DanBrumleve: Don't you need further specification/fixes for your equation? I don't think it is true for all n, p etc. I tested it for $n = p = 3$ and didn't work. (I hope, I didn't a calculation error in my head) – Imago Jan 7 '15 at 18:45
• Another way of thinking about it: you want to find an $n$ such that $2^n \equiv_p n$. Then by Dan's comment, you have infinitely many. – dalastboss Jan 7 '15 at 18:45
• I don't doubt, it works for infinity many cases :) just that one might need specification for n and p; – Imago Jan 7 '15 at 18:48
• The specification is that $p \mid 2^n - n$. When $n = p = 3$ this is saying that $3 \mid 5$ which is not true, which is why that case does not work. – dalastboss Jan 7 '15 at 18:53

Let $$o:=\operatorname{ord}(2,p)$$ be the smallest positive number with $$2^o\equiv 1\pmod p$$
Then we have for every natural number $$k$$ : $$2^{ok}\equiv 1\pmod p$$
Because of $$1 < o < p$$ there exists $$q$$ with $$oq\equiv 1\pmod p$$
So we have $$2^{oq}\equiv oq\equiv 1\pmod p$$