2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ The author raised the left hand side to the power $(p-1)^{2k-1}$, I think. In either case, $1$ stays equal to $1$. $\endgroup$
    – Isaac Ren
    Commented May 19, 2020 at 16:40
  • 2
    $\begingroup$ 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}$. $\endgroup$
    – lulu
    Commented May 19, 2020 at 16:41
  • $\begingroup$ @lulu thanks ,a little mistake ,m cannot be integer it has to be positive intger. $\endgroup$
    – Ishan
    Commented May 19, 2020 at 17:21

3 Answers 3

2
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ ahh,i missed it ,thanks.. $\endgroup$
    – Ishan
    Commented May 19, 2020 at 17:23
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .