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:=ord(2,p)$ be the smallest positive number with $2^o\equiv 1\ (\ mod\ p\ )$
Then we have for every natural number $k$ : $2^{ok}\equiv 1\ (\ mod\ p\ )$
Because of $1 < o < p$ there exists $q$ with $oq\equiv 1\ (\ mod\ p\ )$
So we have $2^{oq}\equiv oq\equiv 1\ (\ mod\ p\ )$