Fermat's Little Theorem

Fermat's Little Theorem.  If p is prime and  a is not a multiple of p then   [Graphics:../Images/Fermat_gr_31.gif]

Questions.
Based on this theorem what can you say if you are given the following information?

1.        1997  is a prime             Therefore,  [Graphics:../Images/Fermat_gr_32.gif]

2.        [Graphics:../Images/Fermat_gr_33.gif] (mod 6557)       Therefore,  __________?_____

3.       [Graphics:../Images/Fermat_gr_34.gif]        Therefore,  _______?_______

Calculations, some relating to the questions above.

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]
[Graphics:../Images/Fermat_gr_36.gif]

We could predict that 6557 is not prime by the contrapositive of Fermat's Little Theorem

[Graphics:../Images/Fermat_gr_37.gif]
[Graphics:../Images/Fermat_gr_38.gif]

The converse of Fermat's Little Theorem is false.  If [Graphics:../Images/Fermat_gr_39.gif]   then we can't conclude that p is prime.  Numbers that illustrate this fact are called psuedoprimes.

[Graphics:../Images/Fermat_gr_40.gif]
[Graphics:../Images/Fermat_gr_41.gif]

[Graphics:../Images/Fermat_gr_42.gif] is a psuedoprime to the base 2, but not to the base 7.

[Graphics:../Images/Fermat_gr_43.gif]
[Graphics:../Images/Fermat_gr_44.gif]

[Graphics:../Images/Fermat_gr_45.gif] is a pseudoprime to a surprising number of bases.  

[Graphics:../Images/Fermat_gr_46.gif]
[Graphics:../Images/Fermat_gr_47.gif]

In fact, 29341 is a pseudoprime to every prime base other than its prime divisors.  Such a number is called a Carmichael number


Converted by Mathematica      April 24, 2000