a) Show that multiplication is a well-defined binary operation on the set Zn of con-
gruence classes of integers modulo n.
b) Given an integer n > 1, let Z∗n be the set of elements x in Zn such that there exists
y in Zn with xy = 1. Show that Z∗n with the operation of multiplication is a group.
gruence classes of integers modulo n.
b) Given an integer n > 1, let Z∗n be the set of elements x in Zn such that there exists
y in Zn with xy = 1. Show that Z∗n with the operation of multiplication is a group.
-
a) what does it mean for multiplication to be "well-defined"?
well, normally "an integer modulo n" isn't just "one number", but an equivalence class on the integers. so instead of 13 "just being 13", what we really mean is the "equivalence class of 13 modulo n":
[13] = {13,13+n,13-n,13+2n,13-2n,.....etc.}
so to define an operation on the integers mod n, let's say:
[a]*[b] = [ab]
we ned to know that if a' is congruent to a mod n, and b' is congruent to b mod n, then a'b' is still congruent to ab mod n (otherwise, we "can't trust our definition", it's ill-defined).
but what does it mean for a' to be congruent mod n (that is [a] = [a'])?
it means that a - a' is a multiple of n:
a - a' = sn.
similarly, b - b' = tn, if b' is congruent to b.
we can re-write this as:
a' = a - sn
b' = b - tn.
then: a'b' = (a - sn)(b - tn) = ab - atn - bsn + stn^2
= ab - (at + bs - stn)n. we can re-arrange THIS as:
ab - a'b' = (at + bs - stn)n, which shows that
ab - a'b' is indeed a multiple of n, so [ab] = [a'b'].
b) fortunately for us, Zn is finite, so any subset of Zn is finite.
so to show that the subset:
U(Zn) = {x in Zn: there exists y in Zn with xy = 1}
is a group, we only need to show closure.
so if we have x in U(Zn), and w in U(Zn), we need to show that:
xw is also in U(Zn).
by supposition, we have y in Zn, with xy = 1
well, normally "an integer modulo n" isn't just "one number", but an equivalence class on the integers. so instead of 13 "just being 13", what we really mean is the "equivalence class of 13 modulo n":
[13] = {13,13+n,13-n,13+2n,13-2n,.....etc.}
so to define an operation on the integers mod n, let's say:
[a]*[b] = [ab]
we ned to know that if a' is congruent to a mod n, and b' is congruent to b mod n, then a'b' is still congruent to ab mod n (otherwise, we "can't trust our definition", it's ill-defined).
but what does it mean for a' to be congruent mod n (that is [a] = [a'])?
it means that a - a' is a multiple of n:
a - a' = sn.
similarly, b - b' = tn, if b' is congruent to b.
we can re-write this as:
a' = a - sn
b' = b - tn.
then: a'b' = (a - sn)(b - tn) = ab - atn - bsn + stn^2
= ab - (at + bs - stn)n. we can re-arrange THIS as:
ab - a'b' = (at + bs - stn)n, which shows that
ab - a'b' is indeed a multiple of n, so [ab] = [a'b'].
b) fortunately for us, Zn is finite, so any subset of Zn is finite.
so to show that the subset:
U(Zn) = {x in Zn: there exists y in Zn with xy = 1}
is a group, we only need to show closure.
so if we have x in U(Zn), and w in U(Zn), we need to show that:
xw is also in U(Zn).
by supposition, we have y in Zn, with xy = 1
12
keywords: group,theory,Multiplication,Multiplication group theory