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

September 9, 2010

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)=p,mod,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}{\displaystyle \prod _{i=1}^{b-1}i\equiv {\displaystyle \prod _{i=1}^{b-1}i(\mathrm{mod}b)}}$ by the commutative law of modular arithmetic. Because b is a prime, $gcd({\displaystyle \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

% reference discrete_math -l 625-627 %

• Number Theory,
• Mathematics,
• Proof,
• Modular Arithmetic