Modular Mathematics, Fermat's Little Theorem

Fermat's Little Theorem

Fermat (biography) is generally considered to be the father of number theory. By developing modular mathematics, he took Euclid's work to new heights. Despite its name, his "little" theorem is one of the most important. The only thing little about it is its proof, which is startlingly beautiful.

If u is a unit mod m, and there are t units total, then u^t = 1 mod m. If the product of all the units is z, replace each unit with u times that unit. This permutes the units about, but doesn't change the product. The answer is still z. The introduction of t copies of u hasn't changed a thing, hence u^t = 1.

Remember that t is, by definition, φ(n).

There are 12 units mod 15; verify that 2¹² = 4096 = 1 mod 15.

When p is prime, x^p-1 = 1 mod p.