# Find all the primes that satisfy $p \mid 2^p - 1$

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.

• Why do you have that 1 is equivalent to $0$ mod p? – Michael Burr Apr 20 '15 at 2:05
• 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) – Dude Apr 20 '15 at 2:08
• any comment @MichaelBurr? – Dude Apr 20 '15 at 2:12
• It's what I get for posting from my phone. The proof looks good. – Michael Burr Apr 20 '15 at 2:14
• Looks good to me too. Now write it down properly. – Hans Engler Apr 20 '15 at 2:16

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).