Fermat's "Little" Theorem

Evidence for Fermat's Little Theorem

For a given prime p, consider the positive powers of a, 0 ≤ a < p.  Each value of (a^k)is congruent to a number from 0 to p-1.  Look for patterns.

p=11:   Powers in  the ring (Subscript[ℤ, 11])

p=17   Powers in  the ring (Subscript[ℤ, 17])

One of the patterns that you might have noticed is indeed a theorem

Fermat's Little Theorem

Fermat's Little Theorem.  If p is prime and  a is not a multiple of p then   (a^(p - 1)) ≡ 1 (mod p)

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

1.        1997  is a prime     		Therefore,  (25^1996) ≡ _?_  (mod 1997)

2.        (13^6556) ≡  1780 (mod 6557)   	Therefore,  __________?_____ 

3.       (5^29340) ≡ 1 (mod 29341)    	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

PowerMod[25, 1996, 1997]

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

FactorInteger[6557]

The converse of Fermat's Little Theorem is false.  If (a^(p - 1)) ≡ 1 (mod p)   then we can't conclude that p is prime.  Numbers that illustrate this fact are called psuedoprimes.

PowerMod[2, 340, 341]

341 = 11×31 is a psuedoprime to the base 2, but not to the base 7.

PowerMod[7, 340, 341]

29341 = 13×37×61 is a pseudoprime to a surprising number of bases.

Map[PowerMod[#, 29340, 29341] &, {2, 3, 5, 7, 11}]

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

Some bigger numbers

In spite of its name, Fermat's Little Theorem is very powerful.  With it we can identify that certain large integers are composite without actually finding a factorization.  For example, is m  = 8453305711931797 a prime?

m=8453305711931797;
PowerMod[5,m-1,m]//Timing

The output above tells us just about instantly that (5^(m - 1)) ≢ 1 (mod m) and so m is composite.  If we insisted on determining whether m is prime by direct factorization we would use a measurable amount time.

FactorInteger[m]//Timing

To determine whether an integer is prime, Mathematica uses a test based on Fermat's theorem as a start and if the test is inconclusive it preceeds to more sophisticated tests.  Here's a much bigger number - 101 digits long - and we can see that it must be composite too.

m=10^100 + 37;
PowerMod[5,m-1,m]//Timing

The converse of Fermat's Little Theorem is False - another example

Which of the odd numbers from 547 to 567 are prime?

Select[Range[547, 567], PrimeQ]

Mathematica Code

<< NumberTheory`Master`

powertable[p_]:=Map[PowerMod[First[#],Last[#],p]&,Outer[List,Range[0,p-1],Range[1,p]],{2}]//
Prepend[#,Map[(a^#)&,Range[1,p]]]&//
TableForm[#,TableSpacing->Map[1&,Range[p]]]&

powertable[7]