Since the key to whether Z_n is a field is law 8, the existence of multiplicative inverses, we next consider when numbers have an inverse mod n. The applet below will let you see the multiplication table for Z₂ through Z₁₅ with the entries color-coded red for invertible and blue for not invertible.

Several patterns are clear after looking at these tables.

• Numbers that divide n are not invertible (mod n)
• Numbers that share a common factor with n are not invertible (mod n).
• The rows (or columns) of non-invertible numbers repeat.
• The rows (or columns) of non-invertible numbers have more than one 0.
• Any product of a non-invertible number is a non-invertible number.
• There are other patterns you should try to find.

Looking at these patterns, we are led to conjecture (as answer to homework problem 5) that numbers have inverses (mod n) if and only if they have no common factor with n (other than 1 which is a factor of everything of course). We write the greatest common divisor of a and n as gcd(a,n). With this notation, we conjecture that a has an inverse (mod n) if and only if gcd(a,n)=1.

This conjecture has two parts. The first is that if a and n share a common factor, then a is not invertible (mod n). The second is that if a and n don’t share a common factor then a is invertible (mod n). We will start with a proof of the first part. We will prove several lemmas as stepping-stones on the way to the proof.

Lemma: In any algebraic structure satisfying field laws 1-5, 7 and 9 (such a structure is called a ring with identity), a ´ 0 = 0.

Proof:

b + 0 = b	Additive Identity (law 3)
a ´ (b + 0) = a ´ b	Multiplying both sides of the equation by b
(a ´ b) + (a ´ 0) = a ´ b	Distributive Law (law 9)
-(a ´ b) + [(a ´ b) + (a ´ 0)] = -(a ´ b) + (a ´ b)	Adding the same quantity to both sides of an equation
[-(a ´ b) + (a ´ b)] + a ´ 0 = -(a ´ b) + (a ´ b)	Associative Law (law 1)
0 + a ´ 0 = 0	Additive Inverses (law 4)
a ´ 0 = 0	Additive Identity (law 3)

Lemma: In any ring, if a ´ b = 0, with b ¹ 0 then a is not invertible.

Proof: Suppose a is invertible, so a^-1 ´ a = 1. Then

a ´ b = 0	By hypothesis
a-1 ´ (a ´ b) = a-1 ´ 0	Multiplying both sides of the equation by a-1
(a-1 ´ a) ´ b = 0	Associative Law on the left (law 5) Previous Lemma on the right
1 ´ b = 0	By definition of a-1
b = 0	Multiplicative identity (law 6)

But this contradicts the given that b ¹ 0, hence a must not be invertible.

Lemma (the first pattern): If a divides n (notation: a | n), then a is not invertible (mod n).

Proof: By definition, a divides n means n = a ´ b for some b ¹ 0. But then a ´ b º 0 (mod n), so a is not invertible by the previous lemma.

Lemma (the fifth pattern): In any ring with identity, if a is not invertible then a ´ b is not invertible (no matter what choice you make for b).

Proof: Suppose a ´ b is invertible, so there is a c with (a ´ b) ´ c = 1. Then by the associative law, a ´ (b ´ c) = 1 and (b ´ c) is the multiplicative inverse for a. Since a is not invertible, this is impossible so a ´ b must not be invertible.

Theorem: If gcd(a,n) = d > 1 (i.e. if a and n share a common factor), then a doesn’t have an inverse (mod n).

Proof: Since d is a common factor of a and n, we can write a = r ´ d and n = s ´ d for some r and s, neither equal to 0. Then by the third lemma, d is not invertible (mod n). Then by the fourth lemma, a is also not invertible (mod n), since a = r ´ d.

This theorem now justifies half our conjecture in response to homework problem 2 that Z_n is a field if and only if n is prime. If n is not prime, then it has proper divisors, n = p ´  q, with 1 < p, q < n. In this case, neither p nor q can have an inverse so not all elements have multiplicative inverses and Z_n is not a field. To show the other half of our conjecture holds, that Z_p is a field if p is prime, we have to show the other half of our conjecture above, that if gcd(a,n)=1 then a has an inverse (mod n). If p is prime, then gcd(a,p)=1 for all 1 £ a £ p-1, so all the non-zero elements of Z_p have an inverse and Z_p is a field. We will do that in the next lecture, by giving an old algorithm (due to Euclid) that allows us to find the inverse (mod n) of any number with gcd(a,n)=1.