2
$\begingroup$

I just want somebody to verify that my work is correct.

Find all prime numbers $p$ such that $p \mid 2^p - 1$.

My claim is that there no such prime that satisfies this.

If $pk = 2^p - 1$, we must have $2^p - 1 \equiv 0 \pmod{p}$. By using Fermat's little theorem we can deduce that $2^p \equiv 2 \pmod{p}$, and so we must also have $2^p - 1 \equiv 2 - 1 \equiv 1 \equiv 0 \pmod{p}$. But $p$ is prime, so $p$ can't divide $1$, and consequently there is no no prime $p$ that will satisfy the above.

$\endgroup$
  • $\begingroup$ Why do you have that 1 is equivalent to $0$ mod p? $\endgroup$ – Michael Burr Apr 20 '15 at 2:05
  • $\begingroup$ since we have $2^p - 1$ $\equiv$ 0 (mod p) but $2^p$ $\equiv$ 2 so we have $2^p$ - 1 $\equiv$ 1 $\equiv$ 0 (mod p) $\endgroup$ – Dude Apr 20 '15 at 2:08
  • $\begingroup$ any comment @MichaelBurr? $\endgroup$ – Dude Apr 20 '15 at 2:12
  • $\begingroup$ It's what I get for posting from my phone. The proof looks good. $\endgroup$ – Michael Burr Apr 20 '15 at 2:14
  • $\begingroup$ Looks good to me too. Now write it down properly. $\endgroup$ – Hans Engler Apr 20 '15 at 2:16
1
$\begingroup$

Your argument is correct. $\,n\nmid 2^n-1\,$ for $\,n>1\,$ more generally, by the following

Theorem $\,\ \ \ m,n>1,\,\ m\mid 2^{\large n}-1\,\Rightarrow\, \ell(m) > \ell(n),\ \ $ $\ell(x) =\,$ least prime factor of $\,x $

Proof $\quad\ \, {\rm mod}\,\ p = \ell(m)\!:\,\ 2^{\large n}\equiv 1\equiv\, 2^{\large\color{}{ p-1}}\,$ $\Rightarrow$ $\,\ \ell(m) = p > {\rm ord}\,2\color{#80f}{ \ge \ell(n)}$

Remark $\,\ $ The $ $ key dea $ $ is: $\ 2^n\equiv 1,\,\ \color{#0a0}{2\not\equiv 1}\,$ implies the order of $\,2\,$ is $\,\color{#80f}{\ge\ {\rm least\ prime}\,\ q\mid n},\ $ since the order must divide $\,n,\,$ and is $\color{}{\neq \color{#c00}1}\,$ (else $\,\color{#0a0}{2^{\color{#c00}{\large 1}}\equiv 1}),\,$ i.e. the least nontrivial divisor of $\,n\,$ is its least prime factor (by uniqueness of prime factorizations).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.