A particularly simple example of a probabilistic test is the Fermat primality test, which relies on the fact (Fermat's little theorem) that np≡n (mod p) for any n if p is a prime number.
What does the Fermat primality test depend upon?
np≡n (mod p)