0.
6 Exercise Set 1 THE DEFINITION OF A GROUP AND EXAMPLES
Definition: Given integers x, k we say that x is equivalent to k modulo n, written
x ” k pmod nq
if n | x ´ k. Thus x ” k pmod nq if and only if rxsn “ rksn by Corollary 0.4.3(3).
An Important Remark: Theorem 0.4.2 and Corollary 0.4.3 tell us that
r0sn , r1sn , r2sn , . . . , rn ´ 1sn
are all the sets of the form rxsn , since 0, 1, 2, . . . , n ´ 1 are all the possible remainders when n divides
into x. So every integer x is in one of these n sets above, by Corollary 0.4.3(1). Also observe that
no two sets on the list r0sn , r1sn , r2sn , . . . , rn ´ 1sn can be equal, by Corollary 0.4.3(3): if rasn “ rbsn ,
with 0 ď a, b ă n, then a “ b (why?). Thus by Corollary 0.4.3(5), any two distinct sets in the above
collection are disjoint. Thus the above collection forms a partition of Z.
Definition: We let Zn “ tr0sn , r1sn , r2sn , . . . , rn ´ 1sn u. Then Zn is called the set of integers
modulo n. Sometimes we simply write Zn “ tr0s, r1s, r2s, . . . , rn ´ 1su or Zn “ t0, 1, 2, . . . , n ´ 1u.
Some very bad people abuse notation, by writting Zn “ t0, 1, 2, . . . , n ´ 1u. We shall not abuse
notation in this course. Not on my watch!
0.6 Exercise Set
1. Prove statements 4-7 in the “Elementary Properties of Division”.
2. In Theorem 0.4.2, prove why it follows from Equation (1) that n | x ´ t if and only if n | r ´ t.
3. Prove Corollary 0.4.3(1).
4. Prove that if rasn “ rbsn , with 0 ď a, b ă n, then a “ b.
5. Show that r0sn “ rnsn , r1sn “ rn ` 1sn , r2sn “ rn ` 2sn and that, in general, rksn “ rn ` ksn
for any integer k.
Part I
Group Theory
1 The Definition of a Group and Examples
1.1 Binary Operations
Let X be a non-empty set. Suppose two elements of X (not necessarily distinct) can be combined to
form another element of X. Then we say X has a binary operation, often denoted by a symbol, e.g. ˚.
Page: 18 of 114
1.1 Binary Operations 1 THE DEFINITION OF A GROUP AND EXAMPLES
Example: On Z, a ˚ b “ a ` b is a binary operation. And so are a ˚ b “ a ´ b, a ˚ b “ ab. On
the other hand, a ˚ b “ a{b is not a binary operation on Z.
Thus, the sum, difference, and product of two integers is again an integer. On the other hand,
when one divides two integers, you may not always get an integer: 3 ˚ 2 is undefined on Z if ˚ is
division.
If X has a binary operation, say ˚, we say that X is closed under ˚. The set X, together with
a binary operation ˚, is often written as pX, ˚q.
Given pX, ˚q, we say that ˚ is associative if, for all a, b, c P X, we have pa ˚ bq ˚ c “ a ˚ pb ˚ cq.
Example: pZ, `q is associative, since pa ` bq ` c “ a ` pb ` cq @ a, b, c P Z.
Example: pZ, ´q is not associative, since 2 ´ p3 ´ 1q “ p2 ´ 3q ´ 1; LHS= 0, RHS= ´2.
Remark: When pX, ˚q is associative, it does not matter where you wish to place the parenthesis,
and hence you may ignore them completely. E.g. p2 ` 3q ` 1 and 2 ` p3 ` 1q mean the same thing,
and you may as well just write 2`3`1. On the other hand, when pX, ˚q is not associative, then you
really need the parenthesis. E.g. 2´3´1 has ambiguous meaning: is it p2´3q´1 or is it 2´p3´1q?
Given a, b P X, we say a and b commute if
a ˚ b “ b ˚ a.
We say ˚ is commutative if, for all a, b P X, a ˚ b “ b ˚ a, i.e., if any two elements commute.
Example: pZ, `q is commutative, since a ` b “ b ` a @ a, b P X.
Example: pZ, ´q is not commutative, since 2 ´ 3 “ 3 ´ 2.
An element e P X is called an identity element if for every a in X we have:
e ˚ a “ a and a ˚ e “ a.
When this is the case, we say that pX, ˚q has an identity.
Example: 0 is an identity on pZ, `q.
Example: 1 is an identity on pZ, ¨q.
Example: pZ, ´q has no identity.
Proof by Contradiction: Suppose e is an identity of pZ, ´q. Then a ˚ e “ a, hence a ´ e “ a and
so a ´ a “ e. Thus e “ 0. But e ˚ 5 “ 0 ˚ 5 “ 0 ´ 5 “ ´5 “ 5. So the only possible candidate for e
is not an identity after all! l
Page: 19 of 114
1.1 Exercise Set 1 THE DEFINITION OF A GROUP AND EXAMPLES
If pX, ˚q has an identity e, and a P X, we say that b is an inverse of a if
a ˚ b “ e and b ˚ a “ e.
When this is the case, then a is also an inverse of b, i.e., a and b are inverses of each other.
Example: In pZ, `q, 2 is an inverse of ´2.
Example: In pZ, ¨q, ´1 is an inverse of ´1.
Example: In pZ, ¨q, 2 has no inverse (why?).
Theorem 1.1.1. An identity element (if it exists) of pX, ˚q is unique.
Proof. Let e, e1 be identities of pX, ˚q. Since e is an identity, we have
e ˚ e1 “ e1 .
However, since e1 is also an identity, we have
e ˚ e1 “ e.
And hence e “ e1 . l
1.1 Exercise Set
Always justify your answers!
1. Which of the following are associative binary operations?
(a) pZ, ˚q, where a ˚ b “ pa ` bq ´ ab.
(b) pZ, ˚q, where a ˚ b “ a ` b ` 1.
(c) pQ, ˚q, where a ˚ b “ pabq{2.
(d) pR, ˚q, where a ˚ b “ |a ` b|.
(e) pR, ˚q, where a ˚ b “ |a| ` |b|.
(f) pN, ˚q, where a ˚ b “ ab .
(g) pR, ˚q, where a ˚ b “ minpa, bq.
(h) pR, ˚q, where a ˚ b “ maxpa, bq.
2. Which of the above binary operations are commutative?
3. Which of the above binary operations has an identity?
4. Suppose pX, ˚q has an identity element, say e. What is the inverse of e?
Page: 20 of 114
