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 [Graphics:../Images/Fermat_gr_48.gif] a prime?

m=8453305711931797;
PowerMod[5,m-1,m]//Timing
[Graphics:../Images/Fermat_gr_49.gif]

The output above tells us just about instantly that [Graphics:../Images/Fermat_gr_50.gif] 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
[Graphics:../Images/Fermat_gr_51.gif]

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
[Graphics:../Images/Fermat_gr_52.gif]
The converse of Fermat's Little Theorem is False - another example


Converted by Mathematica      April 24, 2000