\[ \begin{array}{l} \text{1. Choose an integer } n \text{ that we want to test.} \\ \text{2. Choose an integer } a \text{ such that } 1 < a < n - 1. \\ \text{3. Compute } a^{n - 1} \mod n. \\ \text{4. If } a^{n - 1} \not\equiv 1 \mod n, \text{ then } n \text{ is composite.} \\ \text{5. If } a^{n - 1} \equiv 1 \mod n, \text{ then } n \text{ is probably prime.} \end{array} \]
\[ a^p-1 \mod p \equiv 1 \]