# Proof for Mersenne primes?

Let $M_p=2^p-1$, $p$ prime.

Show that $M_p$ is either prime or pseudoprime : $2^{n-1} \equiv1\pmod n$

My attempt:

1)Show p not prime $\Rightarrow$ $M_p$ not prime

Assume that $p$ is not prime, then write $p=n \cdot q ,\quad n,q>1$, so $$M_p=2^p-1=2^{n \cdot q}-1=\underbrace{(2^n-1)}_{>1}\underbrace{(2^{n(q-1)}+...+2^p+1)}_{>1}$$ $\Rightarrow M_p$ is prime, if $p$ is prime.

2)Show $2^{M_p-1} \equiv 1 \pmod {M_p}$

With fermat theorem: $$2^{p-1} \equiv 1 \pmod p$$ $$2^{p-1}=1+ k\cdot p ,\quad k\in \Bbb Z$$ $$\Rightarrow 2^{M_p-1} = 2^{2kp}= (2^p)^{2k}=(M_p+1)^{2k}\equiv 1 \pmod {M_p}$$

I think this is not correct, so I would appreciate any hint, thank you.

• Is that the canonical definition of pseudoprime? $2^{29}-1$ has three distinct prime factors: $233, 1103, 2089$. – Jack D'Aurizio May 30 '17 at 20:06
• Besides that, the question is trivial: by Fermat's little theorem $$2^p-1 = 2\cdot 2^{p-1}-1 \equiv 2-1 = 1\pmod{p}.$$ – Jack D'Aurizio May 30 '17 at 20:07

For $2)$ we have just to use correctly factorization formula.
Let $a\in \mathbb{Z}$ , $m,n$ integers such that $m\mid n$, then $a^m-1\mid a^n-1$.
Proof : we have the existence of $k\in \mathbb{Z}$ such that $n=km$.
So : $a^n-1=a^{km}-1=(a^{m})^{k}-1=(a^m-1)(\sum \limits_{i=0}^{k-1}a^{m^i})$. It's proved !
Here we want to prove that $2^p-1\mid 2^{{2^p}-2}-1$. So $a=2$, $m=p$ and $2^p-2=n$. Now do we have $m\mid n$ ? Yes Fermat little theorem can be applied !