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
We could predict that 6557 is not prime by the contrapositive of Fermat's Little Theorem
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.
is a psuedoprime to the base 2, but not to the base 7.
is a pseudoprime to a surprising number of bases.
In fact, 29341 is a pseudoprime to every prime base other than its prime divisors. Such a number is called a Carmichael number