Fermat primality test

Question

Is the following a correct statement for the Fermat primality test?

For all $b$ if

1. $n$ is prime and
2. $(b,n)=1$

then $b^{n-1} \equiv 1 \bmod{n}$.

The contrapositive is if $b^{n-1} \not \equiv 1 \bmod{n}$ then condition (1) and/or (2) is false (they are equivalent --both attest to $n$ not being prime).

Answer 1

If you don't require the test to be definitive, then, well, um, maybe.

For it to be practical, however, I would change "all $b$" to "all $1 < b < n$". Obviously $n^{n - 1} \equiv 0 \bmod n$. Since this test involves exponentiation, I would want to avoid having to do more multiplications than necessary.

Let's try $n = 341$. Clearly 341 is an odd number. Either Wolfram Mathematica or Wolfram Alpha readily tells us that $2^{340} \equiv 1 \bmod 341$. Likewise we see that with a base 10 digital root of 8, 341 is not divisible by 3 but $3^{340} \equiv 56 \bmod 341$. Indeed $341 = 11 \times 31$. Looks like the test works.

But let's not be satisfied with one successful run. How about $n = 561$? I'm not pulling that number out of a hat. It came from one of the comments.

Okay, so 561 is also odd, and we see that $2^{560} \equiv 1 \bmod 561$. With a digit sum of 12, we see that 561 is divisible by 3, so we skip 3 and move on to 4. We see that $4^{560} \equiv 1 \bmod 561$ which means that the...

Hey, wait a minute! If 561 is divisible by 3, can it be prime? No, it's composite. Indeed $3^{560} \equiv 375 \bmod 561$. But you will find that if $b$ is not divisible by 3, 11 or 17, then $b^{560} \equiv 1 \bmod 561$.

This is why 341 is called a pseudoprime to base 2 and a few others, and 561 is called a pseudoprime to bases 2, 4, 5, 7, 8, 10, 13, 14, etc.

This means that the Fermat primality test is by itself not reliable, it gives a lot of small false positives. However, if for a largish odd number you can rule out a lot of small primes (like 3, 11, 17) as prime factors with trial division, and it's a pseudoprime to a lot of small bases, that might be a good enough indication of primality for your purposes.

By the way, PrimeQ in Wolfram Mathematica is not definitive either. But no one has found a false positive yet, maybe no one ever will.

Answer 2

No, it's not, it's a correct statement of the test that tests whether $n$ is a prime number or a Carmichael number. That's a subtly different thing.

From a theoretical point of view, it doesn't matter if $b < n$ or not. For example, $$b^{n - 1} \equiv (n + b)^{n - 1} \pmod n.$$ The same goes for $2n + b$, $3n + b$, etc.

From a practical point of view, you need to be able to tell your algorithm to stop somewhere. $n - 1$ might not be the optimal point to stop, but it's much better than the largest number you can handle, e.g., to test $561$ it's better to stop at $560$ than at $2^{31} - 1$.

Then your algorithm is going to test each $b$ from $2$ to $n - 1$. However, you have the condition of $(b, n) = 1$ as of this writing. So if $n$ is composite, then the test as you originally wrote it requires us to skip $b$ such that $\gcd(b, n) > 1$ even if $b < n$.

Nor did you say to skip $b$ known to be composite, at least not in the original statement of your question.

Therefore, what you have is a test that returns true if $n$ is prime or a Carmichael number (see Sloane's OEIS).

But since the Carmichael numbers are relatively rare, if a large number (like a prime close to the largest known Mersenne prime) is a Fermat pseudoprime to a lot of small $b$, it might be a prime number after all.