Fermat Pseudoprime/Base 3/Examples/91

From ProofWiki
Jump to navigation Jump to search

Theorem

The smallest Fermat pseudoprime to base $3$ is $91$:

$3^{91} \equiv 3 \pmod {91}$

despite the fact that $91$ is not prime:

$91 = 7 \times 13$


Proof

We have that:

\(\displaystyle 3^{91}\) \(=\) \(\displaystyle 26 \, 183 \, 890 \, 704 \, 263 \, 137 \, 277 \, 674 \, 192 \, 438 \, 430 \, 182 \, 020 \, 124 \, 347\)
\(\displaystyle \) \(=\) \(\displaystyle 26 \, 183 \, 890 \, 704 \, 263 \, 137 \, 277 \, 674 \, 192 \, 438 \, 430 \, 182 \, 020 \, 124 \, 344 + 3\)
\(\displaystyle \) \(=\) \(\displaystyle 91 \times 287 \, 735 \, 062 \, 684 \, 210 \, 299 \, 754 \, 661 \, 455 \, 367 \, 364 \, 637 \, 583 \, 784 + 3\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle 3^{91}\) \(\equiv\) \(\displaystyle 3 \pmod {91}\)



Sources