Prove or disprove: A natural number n ≥ 2 is a prime if $$b^{n-1}\equiv 1(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}n)$$, then $$r\equiv s(\mathrm{mod}n)$$.

Proof: Let k, r, s, and n be integers such that $$gcd(n,k)=1$$ and $$kr\equiv ks(\mathrm{mod}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(\mathrm{mod}n)$$. Q.E.D.

Fermat’s Little Theorem

If a is an integer and b is a prime, then $$a^{b-1}\equiv 1(\mathrm{mod}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(\mathrm{mod}b)$$ for some integers k and m such that 1 ≤ k < m ≤ b. Since $$gcd(a,b)=1$$, $$latexk\equiv m(\mathrm{mod}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)=pmodb$$. 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(\mathrm{mod}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(\mathrm{mod}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.