# Mersenne prime is a pseudoprime

Suppose $M_p=2^p-1$, where $p$ is a prime, is composite.

Work: Then $M_p = ab$ for positive integers $1 < a,b < M_p$.

I want to show

$2^{ab}=k2^{2^p-1}+2$

---> $2^{2^p-1}-2=k2^{2^p-1}$

---> $2^{2^p-1} \mid 2^{2^p-1}-2$

---> $2^{2^p-1} \equiv 2 \pmod {2^p-1}$

May I ask for help on filling my missing steps? I'm not getting this, I'm sorry. :(

## 1 Answer

The first statement is false: $2^{2^p-1}$ and $k 2^{2^p-1}$ are divisible by $4$, for example, but $2$ isn't. So I hope that's not what you want to show.

• I want to show the very last statement in my question post. That is the definition of $2^p-1$ being pseudoprime (w.r.t base $2$). Also, I must remark that your "answer" reads more like a comment. – user292908 Nov 24 '15 at 1:30
• So why are you trying to get $2^{2^p-1}$, rather than $2^p-1$, to divide $2^{2^p-1} - 2$? – Robert Israel Nov 24 '15 at 7:41