Modular Mathematics, A Simple Primality Test

A Simple Primality Test

If you can factor p-1, you can prove p is prime. Of course you need to prove that the factors of p-1 are also prime, but they're smaller, so perhaps that's easier.

If p is prime it has a primitive root, lots of them. Try a couple values at random; you're sure to run into one. If g is primitive, and q is a prime dividing p-1, then g^(p-1)/q will not be 1 mod p. We haven't gone through the entire cycle. Conversely, assume g^p-1 is 1, but the exponents (p-1)/q don't produce 1. If g^k = 1 then k divides p-1, yet it doesn't divide (p-1)/q for the primes q in p-1, so k can't be a proper factor of p-1. G generates a cycle of length p-1. All the nonzero elements are units; they are all coprime to p. Hence p is prime.