To answer this, we turn to another result visible in our modular power graphic.

Again, Fermat's Little Theorem is the right-hand column. What's that pattern in the middle?

What is the use for us of this theorem? Imagine we are testing \(n\) for primality, but \[a^{(n-1)/2}\not\equiv \pm 1\text{ mod }(n)\; ,\] then that number is definitely not prime.

Let's try this on our pesky Carmichael number, once again starting with base \(a=2\).

Not again! Try another base - maybe \(a=3\)?

Phew! So this does help us test at least a little better.

A slightly stronger variant of this test is called Miller's test base \(a\) for primality.

• Start by taking \(n-1\), dividing by two, and checking the power \[a^{(n-1)/2}\text{ mod }(n)\; .\] If \(n\) actually is prime, then this will be \(\pm 1\). If the result is \(-1\) we say it passes for sure.
• If it hasn't passed yet, but the result of the power is \(+1\), continue dividing the power itself by two and then taking \(a\) to that power. If \(n\) is actually prime, then the result will be \(\pm 1\), and again we say \(n\) passes if the result is \(-1\).
• Continue – divide the power by two, check the result.
• If we have divided \(n-1\) by all possible powers of two, then we say \(n\) passes as long as \(a\) to the final result is \(\pm 1\); certainly this will be true if \(n\) is prime and we haven't already had \(n\) pass yet.