Fermat 's little theorem states that if p is prime and , then 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 .
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 .