Fermat's Little Theorem. If p is prime and a is not a multiple of p then
Questions.
Based on this theorem what can you say if you are given the following information?
1. 1997 is a prime Therefore,
2. (mod 6557) Therefore, __________?_____
3. Therefore, _______?_______
This follows from the fact that 1997 is a prime and a direct application of Fermat's Little Theorem
![[Graphics:../Images/Fermat_gr_35.gif]](../Images/Fermat_gr_35.gif)
We could predict that 6557 is not prime by the contrapositive of Fermat's Little Theorem
![[Graphics:../Images/Fermat_gr_37.gif]](../Images/Fermat_gr_37.gif)
The converse of Fermat's Little Theorem is false. If then we can't conclude that p is prime. Numbers that illustrate this fact are called psuedoprimes.
![[Graphics:../Images/Fermat_gr_40.gif]](../Images/Fermat_gr_40.gif)
is a psuedoprime to the base 2, but not to the base 7.
![[Graphics:../Images/Fermat_gr_43.gif]](../Images/Fermat_gr_43.gif)
is a pseudoprime to a surprising number of bases.
![[Graphics:../Images/Fermat_gr_46.gif]](../Images/Fermat_gr_46.gif)
In fact, 29341 is a pseudoprime to every prime base other than its prime divisors. Such a number is called a Carmichael number