# 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}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n)$$ 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}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n)$$ 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<r<n$$, it follows that $${r}^{n-1}\equiv 1\phantom{\rule{1em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n)$$ 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({r}^{n-2}-ks)$$. 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}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n)$$ 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}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n)$$, then $$r\equiv s\phantom{\rule{1em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}n)$$.

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

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

Consider a set $$P=\{a,2a,3a,\dots (b-1)a\}$$. Suppose $$ka\equiv ma\phantom{\rule{1em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}b)$$ for some integers k and m such that 1 ≤ k < m ≤ b. Since $$gcd(a,b)=1$$, $$latexk\equiv m\phantom{\rule{1em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}b)$$ by the cancellation law. By the definition of congruence modulo b, $$b|(k-m)$$. But this is impossible since $$0<k-m<b$$. 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=\{1,2,3,\dots (b-1)\}$$ defined as $$F(p)=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}(b-1)!\equiv {a}^{b-1}\prod _{i=1}^{b-1}i\equiv \prod _{i=1}^{b-1}i\phantom{\rule{1em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}b)$$ by the commutative law of modular arithmetic. Because b is a prime, $$gcd(\prod _{i=1}^{b-1}i,b)=1$$. Applying the cancellation law yields: $${a}^{b-1}\equiv 1\phantom{\rule{1em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}b)$$ as desired. Q.E.D.

## References

Fermat’s Little Theorem - Wikipedia, the free encyclopedia

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