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
Best Answer
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$