Week 2 fun problem - Stanford University

Mathematics Department Stanford University
Math 51H Week 2 Fun Problem
Do not hand in
The aim of this problem is to show that Z/(pZ) is a field when p is a prime.
To set this up, we should first discuss Z/(nZ) for all n ∈ Z, n ≥ 2. As a set, Z/(nZ) can be identified
with the set of integers {0, 1, . . . , n − 1}. Then addition and multiplication are done modulo n, i.e. to
calculate the product of the two elements in this representation, one multiplies them as integers, and
then adds the correct multiple of n to obtain an integer in {0, 1, . . . , n − 1} (i.e. this is the remainder,
when dividing by n, of the product regarded as the product of integers). For example, in Z/(5Z), 3 · 3 is
4, since 9 = 1 · 5 + 4. However, it is useful to have a more conceptual picture.
In general, if S is a set, a partition of S is a collection C of subsets of S such that every element of S is
in exactly one of the elements of the collection C. As an example, fixing some n > 0, with S = Z, we can
take the subsets S0 , . . . , Sn−1 where Sk , k = 0, 1, . . . , n − 1, consists of integers of the form na + k, a ∈ Z.
Thus, x ∈ Sk if and only if the remainder of dividing x by n is k. One also says that x ≡ k modulo n, or
x ≡ k mod n.
Whenever one has a partition of a set, one can introduce an equivalence relation: two elements are
equivalent if they lie in the same subset. So in the above example, x, y are equivalent if there are a, b, k
integers such that x = na + k, y = nb + k. Equivalently, this means that x − y is an integer multiple of n,
i.e. x − y ∈ nZ. One then says that Z/(nZ) consists of the set of equivalence classes of integers, relative to
this notion of equivalence; namely the equivalence classes are S0 , . . . , Sn−1 . A typical short-hand notation
for Sk is [k].
We claim that addition and multiplication of equivalence classes is well-defined, as induced from Z. That
is, if one takes two equivalence classes, Sk and Sm , one would like to define Sk +Sm by taking any element
x of Sk and any element y of Sm and letting Sk + Sm be the equivalence class containing x + y. For this
to be well-defined, we must check that the equivalence class of x + y is independent of the choice of the
representatives x, y of the original equivalence classes, i.e. if x 0 ∈ Sk , y 0 ∈ Sm as well, then x+y and x 0 +y 0
are in the same class. But this means exactly that (x + y) − (x 0 + y 0) ∈ nZ, i.e. (x + y) − (x 0 + y 0) = nc
for some integer c. On the other hand, x, x 0, resp. y, y 0 being in the same equivalence class means that
x − x 0 = na, y − y 0 = nb for some a, b. Thus, (x + y) − (x 0 + y 0) = (x − x 0) + (y − y 0) = n(a + b) ∈ nZ as
desired, so addition is well defined.
Problem 1 Check that multiplication of equivalence classes is also well-defined.
While this setup involved extra work compared to the original description of Z/(nZ) by choosing the
remainders after dividing by n, there are significant conceptual advantages. For instance, the algebraic
properties are very easy to check. To see associativity, for example, note that ([x]+[y])+[z] = [x]+([y]+[z])
since the left hand side is, by definition, the equivalence class of (x + y) + z, while the right hand side is
that of x+(y +z), and the two are equal by the associativity of addition in Z. (In order to appreciate this,
try to write down a proof of associativity of multiplication using the hands-on definition of the second
paragraph!)
To complete the algebraic set-up, we define a commutative ring to be a set R with two operations
+, · : R × R → R satisfying all the properties in the definition of a field, except that non-zero elements
are not required to have multiplicative inverses, and that 1 6= 0 is not assumed. That is,
Definition 1 A ring (or ring with a unit) (R, +, ·) is a set R with two maps +, · : R × R → R such that
• (R, +) is a commutative group, with additive unit 0,
• (R, ·) is a semigroup, with multiplicative unit 1,
• the distributive law holds: for all x, y, z ∈ R, (x + y) · z = x · z + y · z and x · (y + z) = x · y + x · z.
A commutative ring is a ring such that (R, ·) is a commutative semigroup.
Note that we had two distributive laws, since we did not assume that multiplication was commutative.
Note that if 0 = 1 then for any x ∈ R, x = 1 · x = 0 · x = 0, since any multiple of 0 is necessarily 0. (Same
proof as in the fields case in the Basic algebra handout.) Thus, the only ring one gains by allowing 0 = 1
is the zero ring with only one element, 0.
Then we can proceed as above to check that Z/(nZ) is such a commutative ring.
Problem 2 Show that for n ≥ 2, Z/(nZ) is a commutative ring and 1 6= 0.
What remains to check is the field property. We already saw that when n is a composite number, i.e.
n = mk where m, k ≥ 2 integers, then Z/(nZ) is not a field: indeed, [m][k] = [0], [m], [k] are non-zero as
m, k are not multiples of n, while in a field the product of non-zero elements is necessarily non-zero.
So from now on consider Z/(pZ), p ≥ 2 a prime.
Problem 3 Show that for p ≥ 2 prime, every non-zero element of Z/(pZ) has a multiplicative inverse,
and thus Z/(pZ) is a field. (Hint: Let a ∈ {1, . . . , p − 1}. We need to find b ∈ Z such that [a][b] = [1],
i.e. such that ab − 1 ∈ pZ. To do so, consider the p − 1 integers, 1 · a, 2 · a, . . . (p − 1)a. Note that none of
these is a multiple of p (since p is a prime, and 1 ≤ a ≤ p − 1), so none of these lies in [0]. Since there
are exactly p − 1 non-zero equivalence classes, there are two cases: either no two of these p − 1 numbers
lies in the same class (i.e. they all lie in different classes), or two lie in the same class, i.e. for some
b, c ∈ {1, . . . , p − 1}, b 6= c, ba − ca is a multiple of p. Show that the latter cannot happen, and use this
to conclude that there exists b such that [ab] = [1].)
While this is not very constructive for finding the inverse of a non-zero element, one can in fact show
that for any a which is not a multiple of p, ap−1 ≡ 1 mod p. (This is Fermat’s little theorem.) Thus,
the multiplicative inverse of [a] in Z/(pZ) is ap−2 since a · ap−2 = ap−1 .
Let’s apply now some linear algebra we learned.
Problem 4 In the set of integers Z, solve the system of equations
2x + y = 2
mod 5, 3x − 2y = 0
mod 5.
(Hint: Use Gaussian elimination in Z/(5Z).)
Note that in this case if we tried to solve the equations in the set of real numbers (dropping the mod 5),
we would get x = 4/7, y = 6/7, which certainly does not give integers!

Download Report