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.

  • 1
    $\begingroup$ Is that the canonical definition of pseudoprime? $2^{29}-1$ has three distinct prime factors: $233, 1103, 2089$. $\endgroup$ – Jack D'Aurizio May 30 '17 at 20:06
  • 1
    $\begingroup$ 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}.$$ $\endgroup$ – Jack D'Aurizio May 30 '17 at 20:07

For $2)$ we have just to use correctly factorization formula.

Here is the key lemma :

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 !


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.