# Demostrate: $M_p=2^p-1$

Demostrate:

If the number $M_p=2^p-1$ is Composite number, where $p$ is prime, then $M_p$ is a Pseudoprime.

This exercise was on a test and I could not do!!

Number Pseudoprime: Fermat's little theorem states that if p is prime and a is coprime to p, then ap−1 − 1 is divisible by p. For an integer a > 1, if a composite integer x divides ax−1 − 1, then x is called a Fermat pseudoprime to base a. It follows that if x is a Fermat pseudoprime to base a, then x is coprime to a. Some sources use variations of this definition, for example to only allow odd numbers to be pseudoprimes

• what is a pseudo prime? – mookid Nov 27 '14 at 16:44
• ckeck it: en.wikipedia.org/wiki/Pseudoprime – Yobani Ordoñez Nov 27 '14 at 16:45
• There are many different definitions of pseudoprime, as you can see in your Wikipedia link. Which one are you working with? – Brandon Carter Nov 27 '14 at 16:47
• o i didnt know,, im sorry!!! – Yobani Ordoñez Nov 27 '14 at 16:49
• It is pseudoprime to the base $2$. – André Nicolas Nov 27 '14 at 16:50

More precisely, $M_p$ is a pseudoprime to the base $2$. To show this we show that $$2^{M_p-1}\equiv 1\pmod{M_p}.$$ By Fermat's Theorem we have $2^{p-1}\equiv 1\pmod{p}$. Thus $2^{p-1}=1+kp$ for some integer $k$, and therefore $M_p-1=2kp$. Thus $$2^{M_p-1}=(2^p)^{2k}=(1+M_p)^{2k}\equiv 1\pmod{M_p}.$$