2
$\begingroup$

Show that if $p$ is prime and $2^p-1$ is composite, then $2^p-1$ is a pseudoprime to the base $2$.

I need to show that $2^{2^p-1}\equiv2\pmod{2^p-1}$. The way I "achieved" this was by doing the following: $2^{2^p-1}\equiv2\pmod{2^p-1},$ $2^{2^p}\equiv4\pmod{2^p-1},$ $4^{2^{p-1}}\equiv4\pmod{2^p-1},$ $2^p-1\equiv1\pmod{2^p-1}.$ Since the congruence does not hold, it must be false that $2^p-1$ is a pseudoprime to the base $2$. Is this approach correct?

  • 2
    How are you getting the last congruence? Remember that in general $a^x \equiv a^y\pmod{m}$ **does not imply** that $x\equiv y\pmod{m}$. Also, it seems like you are assuming what you are trying to prove.2012-03-14

2 Answers 2

3

We say that a composite $x$ is a (Fermat) pseudoprime to the base $a$ if $\gcd(a,x)=1$ and $a^{x-1}\equiv 1\pmod{x}$.

So you need to show that $2^{2^p-2}\equiv 1\pmod{2^p-1}$ (you are already given that $2^p-1$ is composite).

That is, you want to see whether $2^{2^p-2} - 1$ is a multiple of $2^p-1$.

Note that since $2^2-1$ is prime, we must have that $p$ is odd. Since $p$ is an odd prime, we know that $p$ divides $2^p-2$ by Fermat's Little Theorem (since $2^p\equiv 2\pmod{p}$). Thus, we can write $2^p-2$ as $kp$. So now you are trying to show that $2^p-1$ divides $2^{kp} - 1$, with $k$ an integer.

But this is easy...

1

Hint $\ $ little Fermat $\rm\Rightarrow 2^P-2\: =\: P\!\:N,\:$ so $\rm\:mod\ 2^P-1\!: \displaystyle\ 2^P\equiv 1\ \Rightarrow\ 2^{2^P-2} = (2^P)^{N}\equiv 1^N\equiv 1\ $