Question: Show that every composite Fermat number $F_m=2^{2^m}+1$ is a pseudoprime base 2.

Hint: Raise the congruence $2^{2^m}\equiv-1($mod $F_m)$ to the $2^{2^m-m}$th power.

Even with the hint, I'm fairly lost. I understand that $2^{2^m}+1\equiv0($mod $ F_m)$, so clearly it follows that $2^{2^m}\equiv-1($mod $F_m)$. I also know that for a positive integer $b$, if $n$ is a composite positive integer and $b^n\equiv b($mod $n)$ then $n$ is called a pseudoprime to the base $b$.

So, we want to show that $2^{F_m}\equiv2($mod $F_m)$ I don't understand how the hint helps us do this.

Thank you for your help, I'm happy to answer any questions that come up.

  • 1
    $\begingroup$ Well, what do you get when you raise both sides to that power? Try writing it out. $\endgroup$ – Bob Jones Mar 8 '17 at 3:45
  • $\begingroup$ @BobJones would I get $2^{2^{m^{2^{2^m-m}}}}\equiv-1^{2^{2^m-m}}($mod $F_m)$? The only sense that I can make out of that is that $-1^2=1$, and that $2^{2^2}=16$. $\endgroup$ – Ephraim Mar 8 '17 at 3:52
  • 2
    $\begingroup$ You do not take the first $m$ to the power. You know the rule $(a^b)^c=a^{b\cdot c}$, right? Let $a=2, b=2^m, c=2^{2^m-m}$. $\endgroup$ – Bob Jones Mar 8 '17 at 3:55
  • $\begingroup$ @BobJones Thank you, that was helpful. I believe that leaves us with $2^{2^{2^m}}=16^m\equiv1^{2^m-m}($mod $F_m$). $\endgroup$ – Ephraim Mar 8 '17 at 4:07

$F_m=2^{2^m}+1$ implies $2^{2^m}+1\equiv0($mod $ F_m)$, and it follows that $2^{2^m}\equiv-1($mod $F_m)$.

Raising both sides by $2^{2^m-m}$ gives us

$2^{2^m*2^{2^m-m}}=2^{2^{m+{2^m-m}}}=2^{2^{2^m}}\equiv-1^{2^{2^m-m}}=1^{2^m-m}=1^{2^m}/1^m=1^m/1^m=1($mod $F_m)$


$2^{2^{2^m}}\equiv1($ mod $F_m)$

multiplying both sides by $2$ leaves us with:

$2^{2^{2^m}+1}\equiv2($ mod $F_m)$ as was to be shown.

Thanks to Bob Jones for his help!

  • 1
    $\begingroup$ The left side is unfortunately not $2^{F_m}$ as you need. Instead of adding $1$, you need to multiply by $2$. But it works out the same. $\endgroup$ – Bob Jones Mar 8 '17 at 4:46

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.