Original: If we want to test if p is prime, then we can pick random a's in the interval and see if the equality holds.
Simplified: Fermat's little theorem states that if p is prime and . If we want to test if n is prime, then we can pick random a's in the interval and see if the equation above holds.