# Proof: a natural number n is a prime if b^(n−1) = 1 (mod n) for every integer b between 1 and n-1

Prove or disprove: A natural number n ≥ 2 is a prime if ${b}^{n-1}\equiv 1\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n\right)$ for every integer b between 1 and n − 1.

## Proof

Suppose not. Suppose that there is a natural number $n\ge 2$, which is a not prime but ${b}^{n-1}\equiv 1\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n\right)$ for all $1\le b\le n-1$.

Because n is not a prime, there must be integers r and s both greater than 1 such that $n=rs$. Because $1, it follows that ${r}^{n-1}\equiv 1\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n\right)$ by our assumption. By the definition of congruence modulo n, there exists k such that ${r}^{n-1}-1=kn$. Thus, ${r}^{n-1}-kn=1$ and $1={r}^{n-1}-krs=r\left({r}^{n-2}-ks\right)$. But this is impossible since $r>1$. Thus, our supposition is false, and any natural number $n\ge 2$ such that ${b}^{n-1}\equiv 1\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n\right)$ for all $1\le b\le n-1$ is a prime. Q.E.D.

## Related Theorems

In my failed attempts to prove this statement, I accidentally proved the following two theorems. Since the results are pretty nice, I’ll include it here.

### Cancellation Law in Modular Arithmetic

If k, r, and s are integers, n is a prime, and k is not divisible by n and $kr\equiv ks\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n\right)$, then $r\equiv s\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n\right)$.

Proof: Let k, r, s, and n be integers such that $gcd\left(n,k\right)=1$ and $kr\equiv ks\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n\right)$. By the definition of congruence modulo n, $n\mid \left(kr-ks\right)$ or that $n\mid k\left(r-s\right)$. By Euclid’s lemma (for all integers a, b, and c, if $gcd\left(a,c\right)=1$ and $a|bc$, then $a|b$), $n\mid \left(r-s\right)$ since $gcd\left(n,k\right)=1$. Thus by the definition of congruence modulo n, $r\equiv s\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n\right)$. Q.E.D.

### Fermat’s Little Theorem

If a is an integer and b is a prime, then ${a}^{b-1}\equiv 1\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}b\right)$.

Proof: Let a be any integer and b be any prime. Then a ≠ 0 because otherwise $gcd\left(a,b\right)=b$.

Consider a set $P=\left\{a,2a,3a,\dots \left(b-1\right)a\right\}$. Suppose $ka\equiv ma\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}b\right)$ for some integers k and m such that 1 ≤ k < m ≤ b. Since $gcd\left(a,b\right)=1$, $latexk\equiv m\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}b\right)$ by the cancellation law. By the definition of congruence modulo b, $b|\left(k-m\right)$. But this is impossible since $0. Thus, every element in P belongs to a distinct equivalence class defined by congruence modulo b.

Now let us define a function F from P to a $Q=\left\{1,2,3,\dots \left(b-1\right)\right\}$ defined as $F\left(p\right)=p\phantom{\rule{thinmathspace}{0ex}}mod\phantom{\rule{thinmathspace}{0ex}}b$. Then F is one-to-one because every element in P belongs to a distinct equivalence class defined by congruence modulo b, and Q is simply a set of the class representatives. Furthermore, F is onto because because F is one-to-one and P and Q have the same cardinality.

Thus, ${a}^{b-1}\left(b-1\right)!\equiv {a}^{b-1}\prod _{i=1}^{b-1}i\equiv \prod _{i=1}^{b-1}i\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}b\right)$ by the commutative law of modular arithmetic. Because b is a prime, $gcd\left(\prod _{i=1}^{b-1}i,b\right)=1$. Applying the cancellation law yields: ${a}^{b-1}\equiv 1\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}b\right)$ as desired. Q.E.D.

## References

Fermat’s Little Theorem - Wikipedia, the free encyclopedia

Epp., S. S. (2004). Discrete Mathematics with Applications. Cengage Learning.