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

Question

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.

Answer 1

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$