Show that there are infinitely many positive integers $n$ such that $p$ divides $2^{n}-n$

Question

Let $p$ be a prime. Show that there are infinitely many positive integers $n$ such that $p$ divides $2^{n}-n$

Proof:

If $p=2, p$ divides $2^{n}-n$ for every even positive integer $n$.

We assume that $p$ is odd. By Fermat's little theorem, $2^{p-1} \equiv 1(\bmod p)$.

It follows that $ 2^{(p-1)^{2 k}} \equiv 1 \equiv(p-1)^{2 k} \quad(\bmod p) $ that is, $p$ divides $2^{n}-n$ for $n=(p-1)^{2 k}$

now i want to clarify two things

1) How by FLT they concluded that

$ 2^{(p-1)^{2 k}} \equiv 1 \quad(\bmod p) $

i mean by taking both sides $2k$ power we should get $ 2^{(p-1){2 k}} \equiv 1 \quad(\bmod p) $ ???

2)My proof -

instead of taking both sides $2k$ power as the author did i take both sides $k$ power and obtained

$ 2^{(p-1){k}} \equiv 1 \quad(\bmod p) $

now i put $ {(p-1){k}} \equiv 1 \quad(\bmod p) $

which implies {$k=p-1,2p-1,3p-1,........$}

so hence our infinite set is $n=${$(p-1)(p-1),(p-1)(2p-1),(p-1)(3p-1).........$}

Is this correct???

thankyou

Answer 1

As lulu said in the comments, $$\forall m,\quad 2^{(p-1)m}\equiv 1\pmod p.$$ The author then took $m=(p-1)^{2k-1}$.

But your proof is indeed correct, and a bit more general: it suffices to take $m$ such that $(p-1)m\equiv-m\equiv 1\pmod p$, and this is precisely your infinite set.

Answer 2

There's probably a theorem that makes quick work of the problem, but an easy way to see things is to look at the exponent $(p-1)^{2k}$ and rewrite it as $(p-1)^{2k-1}(p-1)$. Call this exponent $m(p-1)$. Now $2^{(p-1)^{2k}}=2^{m(p-1)}=(2^m)^{p-1}\equiv 1 \bmod p$

Answer 3

Yes, as you say $n=(kp-1)(p-1)$, then $$ \begin{align} 2^n-n &=\overbrace{2^{(kp-1)(p-1)}}^{2^{p-1}\equiv1\pmod{p}}-\overbrace{\vphantom{2^1}(kp-1)(p-1)}^{\equiv1\pmod{p}}\\ &\equiv0\pmod{p} \end{align} $$