Theorem: Fermat Pseudoprime/Base 3/Examples/91

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:
{{begin-eqn}}
{{eqn | l = 3^{91}
      | r = 26 \, 183 \, 890 \, 704 \, 263 \, 137 \, 277 \, 674 \, 192 \, 438 \, 430 \, 182 \, 020 \, 124 \, 347
      | c = 
}}
{{eqn | r = 26 \, 183 \, 890 \, 704 \, 263 \, 137 \, 277 \, 674 \, 192 \, 438 \, 430 \, 182 \, 020 \, 124 \, 344 + 3
      | c = 
}}
{{eqn | r = 91 \times 287 \, 735 \, 062 \, 684 \, 210 \, 299 \, 754 \, 661 \, 455 \, 367 \, 364 \, 637 \, 583 \, 784 + 3
      | c = 
}}
{{eqn | ll= \leadsto
      | l = 3^{91}
      | o = \equiv
      | r = 3 \pmod {91}
      | c = 
}}
{{end-eqn}}
Here we define Fermat pseudoprime to base $3$ to be a composite number $n$ such that (a slightly stronger result):
:$3^{n - 1} \equiv 1 \pmod n$
Otherwise we have:
:$3^6 = 729 \equiv 3 \pmod 6$
Following our definition, we see that a Fermat pseudoprime to base $3$ cannot be divisible by $3$:
{{begin-eqn}}
{{eqn | l = 3^{3 k - 1}
      | o = \equiv
      | r = 0
      | rr = \pmod 3
}}
{{eqn | o = \not \equiv
      | r = 1
      | rr = \pmod {3 k}
}}
{{end-eqn}}
neither can it be divisible by $4$:
{{begin-eqn}}
{{eqn | l = 3^{4 k}
      | r = \paren {3^{2 k} }^2
}}
{{eqn | o = \equiv
      | r = 1
      | rr = \pmod 4
      | c = Square Modulo 4
}}
{{eqn | o = \not \equiv
      | r = 3
      | rr = \pmod {4 k}
}}
{{end-eqn}}
nor $10$:
{{begin-eqn}}
{{eqn | l = 3^{10 k}
      | r = \paren {3^{5 k} }^2
}}
{{eqn | o = \equiv
      | r = \pm 1
      | rr = \pmod 5
      | c = Square Modulo 5
}}
{{eqn | o = \not \equiv
      | r = 3
      | rr = \pmod {10 k}
}}
{{end-eqn}}
Also such a number cannot be equal to twice a prime greater than $3$:
{{begin-eqn}}
{{eqn | l = 3^{2 p}
      | o = \equiv
      | r = 3^2
      | rr = \pmod p
      | c = Fermat's Little Theorem
}}
{{eqn | o = \not \equiv
      | r = 3
      | rr = \pmod p
      | c = Since $p \nmid 6 = 2 \times 3$
}}
{{eqn | ll = \leadsto
      | l = 3^{2 p}
      | o = \not \equiv
      | r = 3
      | rr = \pmod {2 p}
}}
{{end-eqn}}
nor five times a prime greater than $5$:
{{begin-eqn}}
{{eqn | l = 3^{5 p}
      | o = \equiv
      | r = 3^5
      | rr = \pmod p
      | c = Fermat's Little Theorem
}}
{{eqn | o = \not \equiv
      | r = 3
      | rr = \pmod p
      | c = Since $p \nmid 240 = 2^4 \times 3 \times 5$
}}
{{eqn | ll = \leadsto
      | l = 3^{5 p}
      | o = \not \equiv
      | r = 3
      | rr = \pmod {5 p}
}}
{{end-eqn}}
Therefore only the following numbers less than $91$ remain:
:$25, 49, 77$
and we check:
{{begin-eqn}}
{{eqn | l = 3^{25}
      | r = 847 \, 288 \, 609 \, 443
      | c = 
}}
{{eqn | r = 33 \, 891 \, 544 \, 377 \times 25 + 18
      | c = 
}}
{{eqn | ll= \leadsto
      | l = 3^{25}
      | o = \equiv
      | r = 18 \pmod {25}
      | c = 
}}
{{eqn | l = 3^{49}
      | r = 239 \, 299 \, 329 \, 230 \, 617 \, 529 \, 590 \, 083
      | c = 
}}
{{eqn | r = 4 \, 883 \, 659 \, 780 \, 216 \, 684 \, 277 \, 348 \times 49 + 31
      | c = 
}}
{{eqn | ll= \leadsto
      | l = 3^{49}
      | o = \equiv
      | r = 31 \pmod {49}
      | c = 
}}
{{eqn | l = 3^{77}
      | r = 5 \, 474 \, 401 \, 089 \, 420 \, 219 \, 382 \, 077 \, 155 \, 933 \, 569 \, 751 \, 763
      | c = 
}}
{{eqn | r = 71 \, 096 \, 118 \, 044 \, 418 \, 433 \, 533 \, 469 \, 557 \, 578 \, 827 \, 944 \times 77 + 75
      | c = 
}}
{{eqn | ll= \leadsto
      | l = 3^{77}
      | o = \equiv
      | r = 75 \pmod {77}
      | c = 
}}
{{end-eqn}}
hence the result.
{{qed}}