# Difference between revisions of "Probable prime"

Given an integer n, choose some integer a coprime to n and calculate an $a^n \equiv 1$ modulo n. If the result is different from 1, n is composite. If it is 1, n may or may not be prime; n is then called a (weak) probable prime to base a.