# Proof verification: if $p$ is an odd prime, then any divisor of a Mersenne number is of the form $2kp+1$.

I've proved that if $p$ is an odd prime, then any divisor of a Mersenne number is of the form $2kp + 1$.

Proof:

If $q$ is a prime divisor of $M_p$, then $qk = 2^p - 1 \rightarrow 2^p \equiv 1 \pmod{q}$.

Then $\gcd(2,q) = 1$. We know $q$ can't be two since $2^p - 1$ is always odd, so its prime divisor can't be even; in particular it can't be $2$, so $q \neq 2$.

Since $2^p \equiv 1 \pmod{q}$, we know $\text{ord}_q(2) \mid p \rightarrow p = \text{ord}_q(2)$, because $p$ is prime. By Fermat's little theorem, $2^{q - 1} \equiv 1 \pmod{q} \rightarrow \text{ord}_q(2) \mid q - 1$, and hence $q - 1 = 2kp$.

However what bothers me in my proof is that I didn't use $p$ being an odd prime anywhere! If someone could check my proof that would be great.

## 2 Answers

Towards the end, you have reached the fact that the order of $2$ divides $q-1$. So $p$ divides $q-1$, and therefore $q=mp+1$ for some integer $m$.

But $q$ is odd. Since $p$ is odd, $m$ must be even. Let $m=2k$.

If I have understood your question correctly, you wish to know why your proof appears to work for $p=2$ when it shouldn't.

Your last line shows that $p\mid q-1$. You can conclude that $2p\mid q-1$ provided $p\ne2$, but this is not a valid deduction when $p=2$.