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

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

• The author raised the left hand side to the power $(p-1)^{2k-1}$, I think. In either case, $1$ stays equal to $1$. Commented May 19, 2020 at 16:40
• Since $2^{p-1}\equiv 1\pmod p$ we have $2^{(p-1)m}\equiv 1 \pmod p$ for all integers $m$, so just take $m=(p-1)^{2k-1}$.
– lulu
Commented May 19, 2020 at 16:41
• @lulu thanks ,a little mistake ,m cannot be integer it has to be positive intger. Commented May 19, 2020 at 17:21

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$$
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}
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.