Prove that n is an odd pseudoprime number, then m=(2^n) - 1 is an odd pseudoprime number.

Printable View

- Apr 27th 2009, 09:02 AMjboitePseudoprimes
Prove that n is an odd pseudoprime number, then m=(2^n) - 1 is an odd pseudoprime number.

- Apr 30th 2009, 01:58 PMThePerfectHacker
Since $\displaystyle n$ is an odd pseudoprime it means $\displaystyle 2^n\equiv 2(\bmod n)$, hence $\displaystyle 2^n - 2 = kn$ for some $\displaystyle k\in \mathbb{Z}$.

Now $\displaystyle m=2^n - 1$ is not prime since $\displaystyle n$ is not prime, so it sufficies to show $\displaystyle 2^m\equiv 2(\bmod m)$. Note that $\displaystyle 2^{m-1} = 2^{2^n - 2} = 2^{kn}$. Therefore, $\displaystyle 2^{m-1} - 1$ is divisible by $\displaystyle 2^n - 1=m$ since $\displaystyle n|(m-1)$. Thus, $\displaystyle 2^{m-1} \equiv 1(\bmod m) \implies 2^m \equiv 2(\bmod m)$.