Euler-Fermat Theory and Prime-testing

As mentioned in the last post, Euler-Fermat's Theory states that for any element m in a group:

$m^{\varphi(n)} = 1 \text{ mod } n$

where $\varphi(n)$ is the totient of n.
The totient of a number is simply the number of Integers that are smaller, and coprime (i.e. no common factors).

This allows us to come up with a simple (though not foolproof) test for prime numbers.
If n is a prime number p, then the number of smaller Integers that are coprime, are all of them. Thus $\varphi(p) = p-1$ for a prime number, and $m^{(p-1)} = 1 \text{ mod } p$ should be true for all the numbers m, smaller than p.

It turns out that just randomly choosing one number m, smaller than p, and discovering $m^{(p-1)} = 1 \text{ mod } p$ means that it's a ½ chance that the number p is prime. If it doesn't give us 1 mod p, then the number is definitely composite.

Which brings us to a very interesting definition of a mathematical proof. We can't prove a number is prime with 100% certainty using this method, but we can keep testing different values of m (which are referred to as witnesses) to achieve a probably prime number.
If we successfully test one witness, P(composite) = $\frac{1}{2}$. Two witnesses, P(composite) = $\frac{1}{4}$ etc. etc.

We can keep testing witnesses until we achieve a likelihood of a prime number with as large a probability as we care to keep calculating …

Except there is a special group of numbers called the Carmichael numbers that will pass this test, and are still composite. Thankfully these numbers are somewhat rare.