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}\not\equiv 1\left(\mathrm{mod}m\right)$ 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