Solution for Section G.1 Question 4

Proof (part 2) Suppose that every non-zero element of Z_p has a multiplicative inverse in Z_p. We must show that p is prime.

Then we have " [a] Î Z_p, $ [a]^-1 Î Z_p such that a × a^-1 1 (mod p). This can be rewritten as (a × a^-1) + rp = 1. Since there exist integers a^-1 and r such that this equation (a × a^-1) + rp = 1 is true, we know (from Section 3.9) that gcd(a,p) divides 1 (and hence gcd(a,p)=1). Hence " [a] Î Z_p, gcd(a,p) = 1, so p has no divisors other than one and itself. Thus p is prime.

An alternative proof (by contradiction) for this is as follows.

Suppose that p is NOT prime.
If p is not prime then we can write
p = ab where 1 < a, b < p.
So [a][b] = [ab] = [0] in Z_p.
But we know that [a]^-1 exists, and also that [b]^-1 exists. By multiplying the equation [a][b] = [0] by [a]^-1 on the left and by [b]^-1 on the right) we have
[a]^-1[a] [b] [b]^-1 = [a]^-1[0] [b]^-1
which gives [1] = [0]. This is clearly a contradiction.
Hence p must be prime.

Back to Section G.1