Fermats little theorom

In many applications, such as Public key cryptography, large prime numbers are needed. The usual algorithm to generate prime numbers is to just generate a random odd number and test it for primality.

However, primality tests are slow. If the user does not require the test to be completely accurate (say, he might tolerate a 0.000000000000000001% chance a "prime" number might be composite), there are very fast algorithms, such as Fermat's Little Theorom.

Fermat's Little Theorom is so-called to differentiate it from Fermats Last Theorom.

Basically, the test states that, if p is a prime number, then for any positive number a less than p, a^p mod p = a (that is, if you take some number a, multiply it by itself p times, then divide the result by p and take the remainder, you should get back a).

Note that the opposite is not always true: if the result is a, p is not necesarily prime. However, the Contrapositive is always true, so if the result is not a, p is not prime. So, to be reasonably sure that a number is prime, test it against several a's. (It can be shown that for each a, the chance of catching a false prime is at least 3 in 4.)

In practice, exponentiation takes log-base-2 of p steps, so Fermat's test is quite fast.

Proving the Little Theorom is pretty easy: we can use Mathematical induction. Basically, I will demonstrate that the algorithm works when a = 1, then that if it works for a = some number, it works for a = some number + 1, concluding that it works for all a's less than p.

Before I start, I need to prove (sorta a sideshow) that (a + b)^n mod p

= a^n + b^n mod p when p is prime. (Does anyone know how to get superscript on this system?) The Binomial theorom tells us that (a + b)^n is a^n + b^n + a bunch of n'C'r's times a^something times b^something. n'C'r is in this case p'C'r (since we're working with p) which equals p(p-1)(p-2)(p-3) ... (r terms) all divided by r! Since r is less than p, and we're supposing p is prime, p cannot divide n!, so the whole term (n'C'r' times a^something times b^something) is a multiple of p, which means the whole term equals 0 mod p. So, (a + b)^n mod p

indeed equals a^n + b^n mod p when p is prime.

Back to the proof:

---

It's spelled "theorem."