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

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


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.