MAT 301 Antonelli College Jackson Short Math Questions

Description

Please follow the instructions. I want good grades for this assignment.

2 attachmentsSlide 1 of 2attachment_1attachment_1attachment_2attachment_2

Unformatted Attachment Preview

MAT301 ASSIGNMENT 1
DUE BY FRIDAY MAY 22, 2020, 11:59 PM.
Each question is worth 5 marks.
Question 1. Define the following relation on R:
For each x, y ∈ R, x ∼ y ⇔ x − y ∈ Z.
(a) Prove that this
is
an equivalence relation on R.
(b) Compute [1], 21 , [π] (justify your answer).
Question 2. Let G be a group with order n < ∞. If n ≥ 2, prove that G has an element of prime order. Question 3. Fix an integer n > 2. If |G| = n < ∞, prove that G has no subgroup of order n − 1. Question 4 Prove that no group can have exactly two elements of order 2. Question 5. Suppose H and K are two non-trivial subgroups of Q (under addition). Prove that H ∩ K 6= {0}. 1 University of Toronto Mississauga Department of Mathematical and Computational Sciences Groups and Symmetries Second Edition Ali Mousavidehshikh c 2018 Ali Mousavidehshikh, All rights reserved. Dedicated to my parents Zahra and Seyedalizaman, my brother and sister Mahmoud and Maryam, and our cats Blitz, Shireen, and Susan. Contents Preface 3 1 Preliminaries 5 1.1 Well Ordering Principle and Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.4 Maps and Well Defined Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.5 Well Defined Operations and Modular Arithmetic . . . . . . . . . . . . . . . . . . . . 19 1.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.7 Challenging Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2 Groups 27 2.1 Definition and Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.2 Order of a Group, Order of an Element . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.3 Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.4 Cayley Table for Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.6 Challenging Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3 Generators, Relations, and Cyclic Groups 47 3.1 Definition of Generators and Relations . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.2 Cyclic Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.3 Subgroup Lattice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.5 Challenging Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4 Dihedral, Symmetric, and Alternating Groups 61 4.1 Dihedral Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.2 Symmetric Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.3 Alternating Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.5 Challenging Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5 Group Homomorphisms and Isomorphisms 1 77 5.1 Homomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 5.2 Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 5.3 Automorphisms, Inner Automorphisms . . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.4 Cayley’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 5.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.6 Challenging Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 6 Cosets and Lagrange’s Theorem 90 6.1 Definition and Properties of Cosets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 6.2 Lagrange’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 6.4 Challenging Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 7 Normal Subgroups and Factor Groups 102 7.1 Definition and Properties of Normal Subgroups . . . . . . . . . . . . . . . . . . . . . 102 7.2 Factor (Quotient) Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 7.3 Isomorphism Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 7.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 7.5 Challenging Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 8 Direct Products and Sums 117 8.1 External Direct Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 8.2 Internal Direct Sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 8.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 8.4 Challenging Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 2 Preface This book was written with the intention of introducing students to the wonderful world of Algebra. More specifically, the book introduces students to the notion of groups, and how these abstract sets can be used to describe the movements of certain geometric objects. This book is my attempt to make groups and their applications (mathematically speaking) lovable. Every chapter ends with two Exercise sections. The first section contains simple to mediocre level exercises, and the second section contains challenging questions (some open). I believe doing the exercises is the only way to learn mathematics. Serge Lang set the following exercise on page 105 of his book, Algebra (with a little paraphrasing): Take any book in Algebra and prove all the theorems without looking at the proofs given in the book. Taken literally, the statement of the exercise is absurd. But its spirit is absolutely accurate; the subject only appears difficult, but once broken down and understood, it is actually quite beautiful. I would like to thank my colleagues Peter Crooks, Payman Eskandari, and Tyler Holden for reading through this book, spotting several errors and misprints, and for making useful suggestions on improving the book. Please keep in mind that this book is still under development. Students, instructors, and mathematicians are encouraged to contact me with comments, suggestions, and any errors found in the book. Ali Mousavidehshikh ali.mousavidehshikh@utoronto.ca University of Toronto, Mississauga Campus 3 4 1 Preliminaries 1.1 Well Ordering Principle and Divisibility In this section, we state and prove some of the properties of the integers. We will be using the following standard notations: N = {1, 2, 3, . . . , } Z = {0, ±1, ±2, . . . , } na o Q = : a ∈ Z, b ∈ N b R = all the real numbers Natural numbers Integers Rational numbers Real numbers We start with an important and useful property of the natural numbers. Well Ordering Principle Axiom 1.1. Every non-empty set of positive integers contains a smallest member. The Well Ordering Principle can be taken as an axiom or as a theorem. This is because the Well Ordering Principle cannot be proved from the usual properties of arithmetic. However, those with a strong background in set theory or analysis can argue (and rightly so) that it should be a theorem. In set theory one can use the notion of inductive sets, and in analysis one can use the completeness property of the real numbers to prove the Well Ordering Principle. This is one of very few occasions in this book where we are less concerned with proving a mathematical result than with applying it. Divisibility Given integers m and n, we say m divides n, and write m|n, if there exist an integer u such that n = mu. If m does not divide n, we write m - n. If m|n, we say m is a divisor of n. We now stablish a fundamental property of the integers that will be used frequently. Division Algorithm Theorem 1.2. Let a, b ∈ Z with b > 0. Then there exist unique integers q, r such that
a = bq + r, where 0 ≤ r < b. We call r the remainder and q the quotient. Proof. Fix a, b ∈ Z with b > 0. First we prove there exist q and r such that a = bq+r, where 0 ≤ r < b. Then we prove that q and r are unique. Let S(a, b) = {c : c ≥ 0 and c = a − bk for some k ∈ Z}. We claim that S(a, b) 6= ∅. To see this we consider three cases for a: Case 1. If a = 0, take k = −b, Case 2. If a > 0, take k = 0,
Case 3. If a < 0, take k = a. 5 If 0 ∈ S(a, b), there exist k ∈ Z such that a − bk = 0 ⇒ a = bk ⇒ b|a, and we can take k = (a/b) and r = 0. If 0 ∈ / S(a, b), then a 6= 0 and S(a, b) ⊆ N. By the Well Ordering Principle, there exist a smallest element in S(a, b), call it r. Then, r = a − bk for some k ∈ Z. It follows that a = bk + r and r > 0
(since every element of S(a, b) is positive). If r ≥ b, then
a − b(k + 1) = a − bk − b = r − b ≥ 0 ⇒ a − b(k + 1) ∈ S(a, b).
However,
a − b(k + 1) = a − bk − b |{z}
< a − bk = r, since b>0
contradicting the minimality of r. Hence, 0 < r < b and letting q = k establishes existence. For uniqueness, suppose bq + r = a = bq 0 + r0 with 0 ≤ r < b, 0 ≤ r0 < b. Note that r0 ≤ r or r ≤ r0 . Without loss of generality, we assume r ≤ r0 . Then b(q − q 0 ) = r0 − r, which implies that b|(r0 − r). Since 0 ≤ r0 − r ≤ r0 < b, we have r0 − r = 0. Hence, r0 = r, from which we get q 0 = q, completing the proof. For example, if a = 57 and b = 14, then 57 = 14(4) + 1. So, q = 4 and r = 1 (notice that 0 ≤ r < 14). Greatest Common Divisor Given a, b ∈ Z with at least one of a, b non-zero, the greatest common divisor of a and b is the largest integer that divides both a and b, and is denoted by gcd(a, b). More precisely, gcd(a, b) = d if and only if the following two conditions are satisfied; (1) d|a and d|b, and (2) If d0 |a and d0 |b, then d0 ≤ d. We now state some of the facts about the gcd of two integers a and b (at least one of them non-zero): (1) gcd(a, b) = gcd(b, a). (2) gcd(a, b) ≥ 1. (3) gcd(0, b) = |b| for any b ∈ Z − {0}. We say two integers a and b are relatively prime if gcd(a, b) = 1. For example, note that 4 and 7 are relatively prime, i.e., gcd(4, 7) = 1. Similarly, 15 and 22 are relatively prime. However, 10 and 45 are not relatively prime (as gcd(10, 45) = 5). The following proposition tells us the relationship between the greatest common divisor of two numbers and the two numbers themselves. Proposition 1.3. Given a, b ∈ Z with at least one of a or b non-zero, there exist s, t ∈ Z such that gcd(a, b) = as + bt. Moreover, gcd(a, b) is the smallest positive integer of the form as + bt. 6 Proof. Fix a, b ∈ Z with at least one of a or b non-zero. Let S(a, b) = {am+bn > 0 : m, n ∈ Z}. Note
that am + bn is non-zero for some choice of m and n. If am + bn is positive for this choice of m and
n, then S(a, b) is non-empty. If am + bn is negative for this choice of m and n, then a(−m) + b(−n)
is positive and S(a, b) is again non-empty. It follows that S(a, b) is non-empty in all cases.
By the Well Ordering Principle, S(a, b) has a smallest element, say d = as+bt. We claim d = gcd(a, b).
By the Division Algorithm, there exist unique integers q and r such that a = dq + r, where 0 ≤ r < d. If r > 0, then
r = a − dq = a − (as + bt)q = a − asq − btq = a(1 − sq) + b(−tq),
from which it follows that r ∈ S(a, b), contradicting the minimality of d. Hence, r = 0, and d|a. A
similar proof shows that d|b.
Now suppose e|a and e|b. Then, a = el and b = ek for some l, k ∈ Z. In particular,
d = as + bt = els + ekt = e(ls + kt) ⇒ e|d ⇒ e ≤ d,
completing the proof.
For example, if a = 24 and b = 132, then gcd(24, 132) = 12. Moreover, 24(−5) + 132(1) = 12. In the
proof of the previous proposition, we have proven the following two useful corollaries.
Corollary 1.4. Suppose gcd(a, b) = d. If e|a and e|b, then e|d.
Corollary 1.5. gcd(a, b) = 1 if and only if there exist integers s and t such that as + bt = 1.
Proposition 1.3 tells us that gcd(a, b) = as + bt for some integers s and t. On the other hand,
Corollary 1.5 tells us that if we can find s and t with as + bt = 1, then gcd(a, b) = 1, in essence
giving a sort of converse of Proposition 1.3. One should be careful here. It is not true in general
that if as + bt = n for n > 1, then n = gcd(a, b). Take a = 2 and b = 4, then 2(3) + 4(5) = 26, but
gcd(2, 4) 6= 26. So why is this the case when n = 1? Answer: In this case, note that 1 is the smallest
positive integer of the form as + bt, and it then follows by Proposition 1.3 that gcd(a, b) = 1.
Recall that a prime number p is a natural number greater than 1 whose only divisors are ±1 and ±p.
We are now in position to prove one of the most important properties of prime numbers.
Corollary 1.6. Given integers a and b, if p is a prime number and p|(ab), then p|a or p|b.
Proof. Suppose p divides ab, i.e., ab = pn for some n ∈ Z. If p|a, there is nothing to prove. If p – a,
then gcd(p, a) = 1 (since p is prime). By Corollary 1.5, there exist integers s and t such that
1 = as + pt ⇒ b = asb + ptb = pns + ptb = p(ns + tb) ⇒ p | b,
completing the proof.
The fact that p is prime in the previous corollary is very important. For example 6|(9 × 4), however,
6 does not divide 9 nor does it divide 4. The previous corollary says this cannot happen for a prime
number.
7
Least Common Multiple
The least common multiple of two non-zero integers a and b is the smallest positive integer
that is a multiple of both a and b, denoted by lcm(a, b).
For example, lcm(6, 15) = 30 and lcm(12, 30) = 60.
1.2
Induction
In this section, we state two forms of proof that are equivalent to the Well Ordering Principle. In
fact, the following are equivalent;
(a) Well Ordering Principle,
(b) Mathematical Induction (ordinary induction),
(c) Mathematical Induction (strong induction),
(d) Axiom of Choice,
(e) Zorn’s Lemma.
The Axiom of Choice and Zorn’s Lemma are some other fundamental axioms that are often used in
mathematics but are outside the scope of this course.
A mathematical statement is a sentence that can be either true or false (not both). For example, “if
x is a real number, then x2 ≥ 0” is a mathematical statement. However, “2+3” is not a mathematical
statement.
Principle of Mathematical Induction (Ordinary Induction)
Theorem 1.7. Let a ∈ Z and P (a), P (a + 1), P (a + 2), . . . be an infinite sequence of mathematical statements. Suppose this sequence satisfies the following two properties:
(1) P (a) is true, and
(2) for each integer k ≥ a, P (k) ⇒ P (k + 1).
Then, P (n) is true for all integers n ≥ a.
The fact that this is equivalent to the Well Ordering Principle is left as an exercise (see Exercise
1.29). In Step (1) of Mathematical Induction is called the base case. In step (2), P (k) is called the
induction hypothesis. We now give examples of proofs which are done via ordinary induction.
Example 1.8. Prove that
n
X
i=1
i=
n(n + 1)
for all natural numbers n.
2
8
Solution. For each natural number n, we can think of P (n) as being the statement
n
X
i=
i=1
n(n + 1)
.
2
We use mathematical induction to prove P (n) is true for all natural numbers n. Since the natural
numbers start at 1, we first show that P (1) is true. This follows from the fact that
1
X
i=1=
i=1
1(1 + 1)
.
2
Next is our induction hypothesis: let k be a natural number and suppose P (k) is true. Then,
k+1
X
i=
i=1
k
X
i + (k + 1) =
i=1
k(k + 1)
k(k + 1) + 2(k + 1)
(k + 1)(k + 2)
+ (k + 1) =
=
.
2
2
2
In particular, P (k + 1) is true. By Mathematical Induction, P (n) is true for all natural numbers n.♣
When P (n) is clear from content, we will usually omit it.
Example 1.9. Prove that
n
X
i=0
i2 =
n(n + 1)(2n + 1)
for all non-negative integers.
6
Solution. The base case follows from the fact that
0
X
i=0
i2 = 0 =
0(0 + 0)(2(0) + 1)
.
6
Assume the result is true for n = k, where k ∈ N. Then,
k+1
X
i=0
2
i =
k
X
i2 + (k + 1)2 =
i=0
=
=
=
=
=
k(k + 1)(2k + 1)
+ (k + 1)2
6
by the induction hypothesis
k(k + 1)(2k + 1) + 6(k + 1)2
6
(k + 1)(k(2k + 1) + 6(k + 1))
6
2
(k + 1)(2k + 7k + 6)
6
(k + 1)(k + 2)(2k + 3)
6
(k + 1)((k + 1) + 1)(2(k + 1) + 1)
.
6
So the result is true for n = k + 1, and by Mathematical Induction,
n
X
i=1
non-negative integers.
9
i2 =
n(n + 1)(2n + 1)
for all
6
♣
Notice that (n + 1)2 ≥ 2n for 1 ≤ n ≤ 5. However, (n + 1)2 = n2 + 2n + 1 is a polynomial and 2n is
an exponential function, and exponential functions eventually dominate polynomials (calculus).
Example 1.10. Prove that
(n + 1)2 < 2n for all natural numbers n ≥ 6. Solution. The base case, which is n = 6, follows from the fact that 49 < 64. Assume the result is true for n = k, where k is natural number greater than or equal to 6. Then, 2k+1 = 2(2k ) > 2(k + 1)2 = 2k 2 + 4k + 2 = k 2 + 4k + 4 + k 2 − 2 > k 2 + 4k + 4 = (k + 2)2 .
♣
The result follows by Mathematical Induction.
We now give another version of the Principle of Mathematical Induction, most commonly called
Strong Induction.
Principle of Mathematical Induction (Strong Induction)
Theorem 1.11. Let a ∈ Z and P (a), P (a + 1), P (a + 2), . . . be an infinite sequence of mathematical statements. Suppose this sequence satisfies the following two properties:
(1) P (a) is true, and
(2) for each k ≥ a, (P (a) ∧ P (a + 1) ∧ . . . ∧ P (k)) ⇒ P (k + 1).
Then, P (n) is true for all integers n ≥ a.
Again, step (1) is called the base case. The difference between induction and strong induction is
in the induction hypothesis. The induction hypothesis in strong induction is as follows: assume
P (a), P (a + 1), . . . , P (k) are true. This is where strong induction gets its name from. The induction
hypothesis in strong induction is much stronger than induction. After all, in induction we only
assume P (k) is true. In strong induction we assume that P (a), P (a + 1), . . . P (k) are all true.
Example 1.12. Prove that every natural number n can be written in the form 2a b where a is
a non-negative integer and b is a positive odd integer.
Solution. We prove this by strong induction. The base case follows from the fact that 1 = 20 (1)
(that is, take a = 0 and b = 1). Assume the result is true for n = 1, 2, . . . , k. If k + 1 is odd, then
take a = 0 and b = k + 1 (for this part we do not need induction nor strong induction). If k + 1 is
even, then k + 1 = 2m for some integer 1 ≤ m ≤ k. By the induction hypothesis, m = 2c d for some
non-negative integer c and positive odd integer d. Then,
k + 1 = 2m = 2(2c d) = 2c+1 d.
So we can take a = c + 1 and b = d. That is, the result holds for n = k + 1, and by Strong Induction
the result holds for all natural numbers.
♣
To see the necessity for strong induction (rather than induction) in the previous example, one should
notice that m is some integer between 1 and k (inclusive). But, we have no idea where m is. More
10
specifically, if we only used induction, the hypothesis would only tell us the result holds for k.
However, m is almost never equal to k. In fact, m = k gives k + 1 = 2k, which is equivalent to k = 1.
So our induction hypothesis would be useless for every k 6= 1.
We now prove one of the most important theorems in arithmetic.
Fundamental Theorem of Arithmetic (Part 1)
Theorem 1.13. Every natural n ≥ 2 is a prime or product of primes.
Proof. The proof is by strong induction on n. Our base case is n = 2, which is prime. So the base
case holds. Assume the result holds for n = 2, 3, . . . , k. If k + 1 is prime, the result holds. If k + 1
is not prime, then k + 1 = ab for some natural numbers a and b with 2 ≤ a ≤ k and 2 ≤ b ≤ k. By
induction, a and b can both be written as product of primes, say a = p1 p2 . . . pm and b = q1 q2 . . . qr .
So k + 1 = ab = p1 p2 . . . pm q1 q2 . . . qr , which is a product of primes. By strong induction, the result
holds for all natural numbers greater than or equal to 2.
Notice that the Fundamental Theorem of Arithmetic tells us that if n is a natural number greater
than or equal to 2, then n has a prime factor. Of course if n is prime, it has only one prime factor,
namely, itself.
One of the consequences of the Fundamental Theorem of Arithmetic is that there are infinitely many
primes, a very famous theorem proved by Euclid.
Infinitely Many Primes
Theorem 1.14. There are infinitely many prime numbers.
Proof. Suppose there are finitely many primes. Then we can enumerate them in ascending
order.
!
n
Y
Let p1 < p2 < . . . < pn be the list of all primes in ascending order. Set a = pi + 1. Notice i=1 ! n Y that a > pn . Moreover, 1 = a −
pi . If pi | a for some i, then pi | 1 (see Exercise 1.2), a
i=1
contradiction. In particular, a is not divisible by any prime number, contradicting the Fundamental
Theorem of Arithmetic.
By the Fundamental Theorem of Arithmetic, every natural number n ≥ 2 can be factored into primes.
The natural question is: Is the factorization unique? For example,
105 = 3 × 5 × 7 = 3 × 7 × 5 = 7 × 3 × 5 = 7 × 5 × 3 = 5 × 3 × 7 = 5 × 7 × 3.
If we don’t care about the order in which the primes are written, 105 has one prime factorization.
That is, the prime factorization is unique up to reordering the primes. The following theorem tells
us up to reordering the prime factors, there is only one prime factorization for all natural numbers
n ≥ 2. That is, once we have factored a number into primes, the primes used never changes in any
factorization of that number, and the number of times each prime is used never changes. The only
thing that can change is the order in which we write the primes.
11
Fundamental Theorem of Arithmetic (Part 2)
Theorem 1.15. The product in Theorem 1.13 is unique up to reordering.
Proof. The proof is left as an exercise (see Exercise 1.9).
Corollary 1.16. Given non-zero integers a, b, and c, prove that gcd(a, bc) = 1 if and only if
gcd(a, b) = 1 = gcd(a, c).
Proof. Let d = gcd(a, b), e = gcd(a, c), f = gcd(a, bc). Suppose f = 1. Since d | b, we have d|(bc).
In particular, d|f (by Corollary 1.4). Thus d = 1. A similar proof shows that e = 1.
Conversely, suppose d = e = 1 and f > 1. By Theorem 1.13, f = p1 p2 …pk (pi -prime). Since f | a
and f | bc we have p1 | a and p1 | bc. Thus p1 | b or p1 | c (by Corollary 1.6). If p1 | b, then p1 | d (by
Corollary 1.4), consequently, p1 |1, a contradiction. If p1 | c, a similar argument gives a contradiction.
Hence, f = 1.
There is a very nice relationship between the least common multiple of two numbers and their greatest
common divisor.
Corollary 1.17. Given two non-zero integers a and b, prove that
lcm(a, b) =
ab
.
gcd(a, b)
Proof. The proof is left as an exercise (see Exercise 1.13).
1.3
Equivalence Relations
In high school we are taught about similar triangles. More specifically, two triangle are similar if
their corresponding angles are congruent and the corresponding sides are in proportion. In other
words, similar triangles are the same shape, but not necessarily the same size. The notion of similar
triangles extends (or generalizes) the notion of equality on triangles. Of course, equal triangles are
similar, but not vice versa.
In general, the notion of equality in mathematics is extremely strict. When we say two things are
equal, we mean they are the same in every possible way (mathematically speaking). In this chapter
we introduce a notion, called an equivalence relation, which aims to generalize the notion of equality.
Or if you like, loosen the definition of equality. For example, we can think of similar triangles as
being equivalent.
We begin with the formal definition of an equivalence relation.
12
Equivalence Relation
An equivalence relation on a set S is a set R ⊆ S × S satisfying the following three properties:
1. (a, a) ∈ R for all a ∈ S (reflexive).
2. If (a, b) ∈ R, then (b, a) ∈ R (symmetric).
3. If (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R (transitive).
If R is an equivalence relation on S, the following all mean the same thing: (a, b) ∈ R, a ∼ b,
a ≡ b. Moreover, when R is an equivalence relation and (a, b) ∈ R, we say a and b are
equivalent.
Notice that an equivalence relation R on a set S is a subset of S × S. In practice, it is helpful to
think of (a, b) ∈ R as meaning that “a is related to b”. One can think of the reflexive property as
saying: every element in our set is related to itself. The symmetric property says that if a is related
to b, then b is related to a. The transitive property is telling us that if a is related to b and b is
related to c, then a is related to c.
Example 1.18. Which one of the following relations is an equivalence relation?
(a) Define the following relation on the integers: a ∼ b ⇔ a < b. (b) Let S be the set of all polynomials with real coefficients. Define the following relation on S: f ∼ g if and only if f 0 = g 0 (the first derivative). (c) Let S = Z and n ∈ N with n ≥ 2. Define a ≡ b (mod n) if and only if n|(b − a). Another notation frequently used for a ≡ b (mod n) is a mod n = b mod n. Solution. (a) This is not an equivalence relation (reflexivity and symmetry both fail, but transitivity holds). (b) This is an equivalence relation. The reflexive and symmetric property are straightforward. If f ∼ g and g ∼ h, then f 0 = g 0 = h0 . Hence, the relation is also transitive. (c) This is an equivalence relation. Fix an integer n ≥ 2. For any integer a, n|(a − a), so a ≡ a (mod n). If a ≡ b (mod n), then n|(a − b), which in turn implies n|(b − a). Thus b ≡ a (mod n). If a ≡ b (mod n) and b ≡ c (mod n), then n|(a − b) and n|(b − c). In particular, there exist integers m and k such that a − b = nm and b − c = nk. So a − c = (a − b) + (b − c) = n(m + k). That is, n|(a − c) and a ≡ c (mod n). ♣ Equivalence Classes When ∼ is an equivalence relation on a set S, for any a ∈ S, [a] = {x ∈ S : x ∼ a} is called the equivalence class of a in S, and a is called a representative for [a]. Notice that the equivalence class of a consists of all elements which are equivalent to a under the relation ∼. 13 Example 1.19. In Example 1.18 we showed that parts (b) and (c) defined an equivalence relation. For part (b), find the equivalence class of each polynomial. For part (c), if n = 5, find the equivalence classes of [1] and [2]. Solution. For part (b), the equivalence class of a polynomial f is [f ] = {f + c : c a constant} (as two functions Rhave the same derivative if and only if they differ by a constant). For those familiar with calculus, f 0 = [f ]. For part (c), if we let n = 5, then [1] = {m ∈ Z : m ≡ 1(mod 5)} = = = = {m ∈ Z : 5|(m − 1)} {m ∈ Z : m − 1 = 5k, k ∈ Z} {m ∈ Z : m = 5k + 1, k ∈ Z} {5k + 1 : k ∈ Z} Similarly, [2] = {5k + 2 : k ∈ Z}. ♣ Partition A partition of a set S is a collection of non-empty disjoint subsets of S whose union is S. The set {[0, ∞), (−∞, 0)} is a partition for R. However, the set {[0, ∞), (−∞, 0]} is not a partition for R (both sets contain zero, thus they are not disjoint). Many students are familiar with the union (or intersection) of two sets. We now extend these notions to arbitrary unions (or intersections) of sets. Arbitrary Union and Intersection Let I be a set (finite or infinite), and suppose Ai is a set (finite or infinite) for each i ∈ I. We define the arbitrary union and intersection as follows: [ Ai = {x : x ∈ Ai for some i ∈ I} (union), i∈I Ai = {x : x ∈ Ai for all i ∈ I} (intersection). i∈I The set I is called an index set. When the set I in the previous definition is the set of the natural numbers, we use the following notation: [ i∈I Ai = ∞ [ i=1 Ai and i∈I Ai = ∞ Ai . i=1 Proposition 1.20. The equivalence classes of an equivalence relation on a set S constitute a partition of S. Conversely, for any partition P of S, there is an equivalence relation on S whose equivalence classes are the elements of P . 14 Proof. Let ∼ be an equivalence relation on S. For any a ∈ S, a ∈ [a] (by reflexivity). In particular, [ S= [a]. a∈S We claim that for all a, b ∈ S, either [a] = [b] or [a] ∩ [b] = ∅. Suppose [a] ∩ [b] 6= ∅. We show that [a] = [b]. Since [a] ∩ [b] is not empty, there exist a c ∈ [a] ∩ [b]. In particular, a ∼ c and c ∼ b. By transitivity, a ∼ b. If x ∈ [a], then x ∼ a and a ∼ b, which gives x ∼ b, thus x ∈ [b]. Hence, [a] ⊆ [b]. Similarly, if x ∈ [b], then x ∼ b and b ∼ a, which gives x ∼ a, thus x ∈ [a]. Hence, [b] ⊆ [a]. Now we show that any partition P of a set S corresponds to an equivalence relation on S whose equivalence classes are the elements of P . Suppose P = {Pi : i ∈ I}, where I is an index set. Define a ∼ b if and only if there exist a j ∈ I such that a, b ∈ Pj (notice that each element is exactly in one Pi ). A routine check shows that this defines an equivalence relation on S and by construction the equivalence classes are precisely the elements of P . It should not come as any surprise that finite sets are much easier to work with then infinite sets. We now give an example that shows that equivalence relations can be used to go from an infinite set to a finite set. Example 1.21. Fix an integer n ≥ 2. Define Zn = {[a]| a ∈ Z}, where [a] is the equivalence class of a under the relation in Example 1.18(c). Prove that Zn = {[0], [1], ..., [n − 1]}. Solution. Notice that {[0], [1], ..., [n − 1]} ⊆ Zn . If [a] ∈ Zn , by the Division Algorithm there exist unique q and r such that a = nq + r with 0 ≤ r < n. Therefore, n|(a − r) ⇒ a ≡ r (mod n) ⇒ [a] = [r] (by Proposition 1.20). We have established the inclusion Zn ⊆ {[0], [1], . . . , [n]}. Hence, Zn = {[0], [1], ..., [n − 1]}. The proof of the fact that these equivalence classes are distinct is left to the reader. ♣ 1.4 Maps and Well Defined Functions A map f from a set√A to a set B is a rule that assigns to each element a ∈ A element(s) in B. For example, f (x) = ± x is a map from the non-negative real numbers to the real numbers; √ f (0) = 0, f (1) = ±1, f (2) = ± 2, f (4) = ±2, f (25) = ±5. Well Defined Functions A well defined function from a set A to a set B is a map that assigns to each element a ∈ A a unique element f (a) ∈ B, called the image of a under f . When a map is a well defined function f from A to B, we write f : A → B or A → B, and simply say f is a function. One should notice that the only difference between a map and a function between two sets is that a map can have multiple outputs for a given input. However, a function has only one output for each √ input. So all functions√are maps but not vice versa; f (x) = ± x is a map but not a function, and we say that f (x) = ± x is not well-defined. All of the following are functions from R to R: 15 (a) f (x) = 2, (b) f (x) = x + 4, (c) f (x) = x2 + 4x + 3. There is another useful notation used to illustrate the rule of a function. If f : A → B is a function and f (a) = b, we write a 7→ b. This sometimes allows us to describe the rule of the function. For example, if f : R → R is the function f (x) = x2 , we describe the rule of this function as follows: let f : R → R be defined via x 7→ x2 . Domain/Co-domain/Image of A Function If f : A → B is a function, the set A is called the domain of f and B is called the co-domain of f . The image of a function, denoted by f (A) or Im(f ), is the set of all points that are actually realized as outputs of f . That is, f (A) = {f (a) : a ∈ A}. If C ⊆ A, we define f (C) = {f (x) : x ∈ C}. Example 1.22. Find the image of the following functions. (a) f : R → R defined via x 7→ x2 . (b) g : N → N defined via n 7→ n + 1. Solution. (a) Since the square of every real number is non-negative, f (R) ⊆ [0, ∞). Conversely, √ √ √ given y ∈ [0, ∞), y ∈ R and y = ( y)2 = f ( y) ∈ f (R). That is, [0, ∞) ⊆ f (R). Hence, the image of f is [0, ∞). (b) A similar argument to the one given in part (a) shows that f (N) = {2, 3, 4, . . .}. Example 1.23. Let f : N×N → N be defined by f (a, b) = ♣. a(a + 1)b . Find f ({1, 2, 4}×{3, 5}). 2 Solution. Notice that {1, 2, 4} × {3, 5} = {(1, 3), (1, 5), (2, 3), (2, 5), (4, 3), (4, 5)}. Moreover, f (1, 3) = 3, f (1, 5) = 5, f (2, 3) = 9, f (2, 5) = 15, f (4, 3) = 30, f (4, 5) = 50. Hence, f ({1, 2, 4} × {3, 5}) = {3, 5, 9, 15, 30, 50}. ♣ One should notice that a function comes with three pieces of data; its domain, co-domain, and rule. So for two functions to be equal, we need all these things to be the same. We make this into a formal definition. Equality of Functions Let f : A → B and g : C → D be functions. We say that f and g are equal if and only if A = C, B = D, and f (a) = g(a) for all a ∈ A. When two functions f and g are equal, we write f = g. 16 In our definition, A = C tells us that the domain of the two functions are equal. Similarly, B = D tells us that the co-domains are equal. The fact that f (a) = g(a) for all a ∈ A tells us that the rule of the two functions are the same. Consider the functions f : R → R defined via x 7→ x2 and g : R → [0, ∞) defined via x 7→ x2 . It is very tempting to say that these two functions are equal. While it is true that these two functions have the same domain and rule, they do not have the same co-domain. Hence, they are not equal. Composition of Functions Let f : A → B and g : B → C. The composition g ◦ f is the function from A to C defined by (g ◦ f )(a) = g(f (a)). When there is no confusion with function multiplication, we write gf instead of g ◦ f . For example, if f, g : R → R via f (x) = x2 and g(x) = x + 1, then both f g and gf are defined. Moreover, (f g)(x) = f (g(x)) = f (x + 1) = (x + 1)2 = x2 + 2x + 1 and (gf )(x) = g(f (x)) = g(x2 ) = x2 + 1. This shows that f g does not have to equal gf (as (f g)(1) = 4, but (gf )(1) = 2). One should be very careful with composition. The composition gf is defined if and only co-domain of f is equal to the domain of g, and the composition f g is defined if and only co-domain of g is equal to the domain of f . Given two functions f and g, it is possible for one compositions to be defined but not the other. For example, if f : R → Z is defined via x 7→ g : R → R is defined via x 7→ 1, then f g is defined, but gf is not defined. if the if the of the 1 and Notice that function composition is associative; that is, if f : A → B, g : B → C, and h : C → D, then h(gf ) = (hg)f. The proof of this fact is left to the reader. Injection/Surjection/Bijection Let f : A → B be a function. (a) f is called one-to-one (or injective) if and only if, for any x, y ∈ A, f (x) = f (y) ⇒ x = y. (b) f is called surjective (or onto) if and only if, for all b ∈ B, there exist a ∈ A such that f (a) = b. (c) f is called a bijection if and only if it is one-to-one and surjective. In this case, define g : B → A via f (a) = b ⇔ g(b) = a. The function g is called the inverse of f , and is denoted by f −1 . 17 The fact that the map g in part (c) of the previous definition is a function is a direct consequence of f being a bijection. In fact, a function is a bijection if and only if g = f −1 is a function (the proof is left to the reader). Proposition 1.24. Let f : A → B and g : B → C. (a) If f and g are injective, prove that their composition gf is injective. (b) If f and g are surjective, prove that their composition gf is surjective. (c) If f and g are bijections, prove that their composition gf is a bijection, and also that (gf )−1 = f −1 g −1 . Proof. Notice that gf : A → C. (a) If (gf )(a) = (gf )(b) where a, b ∈ A, then g(f (a)) = g(f (b)). Since g is injective, f (a) = f (b), and injectivity of f implies that a = b. Hence, gf is injective. (b) Given c ∈ C, there exist b ∈ B such that g(b) = c (as g is surjective). Since f is surjective, there exist an a ∈ A such that f (a) = b. In particular, (gf )(a) = g(f (a)) = g(b) = c. Hence, gf is surjective. (c) If f and g are bijections, then they are both injective and surjective. By parts (a) and (b), gf is both injective and surjective, and thus a bijection. Now we prove the second part of the statement. First notice that (gf )−1 : C → A and f −1 g −1 : C → A. So the domains and co-domains of the two functions are equal. Given c ∈ C, we show that (gf )−1 (c) = (f −1 g −1 )(c). Let (gf )−1 (c) = a. It follows that c = (gf )(a) = g(f (a)). Let f (a) = b. Then g(b) = c and (f −1 g −1 )(c) = = = = f −1 (g −1 (c)) f −1 (b) a (gf )−1 (c). since g(b) = c since f (a) = b Hence, f −1 g −1 = (gf )−1 . The previous Theorem says that the composition of two injective functions is injective, the composition of two surjective functions is surjective, and the composition of two bijections is a bijection. Example 1.25. Define f : N → N via n 7→ n + 1. Is f injective? Is f surjective? Is f a bijection? Solution. Given natural numbers n and m, if f (n) = f (m), then n + 1 = m + 1 ⇒ n = m. Thus f is injective. Furthermore, Im(f ) = {2, 3, 4, . . .} 6= N. Hence, f is not surjective. It follows that f is not a bijection. ♣ 18 1.5 Well Defined Operations and Modular Arithmetic Operation on a Set Given a set S, we say · is an operation on S if there exist a set A such that a · b ∈ A for any a, b ∈ S. Equivalently, · : S × S → A is a map that sends (a, b) to a · b. For example, addition is an operation on the integers (in fact, on all the real numbers). Using the notation in the preceding definition, S = Z = A. Given any two integers a and b, a + b ∈ Z. Another example is the operation of division on the natural numbers. In this case, S = N, and we can take A = Q (one can also take A to be the set of the positive rational numbers). For most students, it is taken for granted that an operation on a given set is well defined. For example, if somebody asks you to compute 2 + 3 (where + is understood to be normal addition), most people (if not all) would answer 5, and they would be correct. The whole idea here is that there is no ambiguity about the numbers 2 and 3, nor about the operation of addition on the integers. So the answer is obvious to most people. We say such an operation is well defined (shortly we will define this more precisely). Now one might ask; “when is this not the case?” Let S = {A, B}, where A = {1, 3, 5} and B = {2, 4, 6}. Define the operation · on S as follows; A · B = a + b where a ∈ A, b ∈ B, and a + b is normal addition. As it stands, we are allowed to pick any element in a ∈ A and any element in b ∈ B and A · B = a + b. But if this is the case, then A · B has multiple answers. For example, we can take a = 1 and b = 2, which gives A · B = 3. However, we can also take a = 1 and b = 4, which gives A · B = 5. This shows that the way the operation is defined, A · B has multiple answers. When this occurs, we say the operation · is not well defined. One might argue and say we should put more restrictions on how we pick the element a ∈ A and the element b ∈ B. For example, suppose we alter the definition of · as follows; A · B = a + b where a is the first element in A and b is the first element in B. While this is now more restrictive than before, the problem that arises now is that the same set can be written in many different ways (as long as it has more than one element). In our example, A · B = {1, 3, 5} · {2, 4, 6} = 1 + 2 = 3, A · B = {3, 1, 5} · {2, 4, 6} = 3 + 2 = 5. While the second definition makes more precise how we pick the elements from each set, what it does not take into account is the fact that an element in S can be written in more than one way. From this example we see that for an operation to be well defined on a set, the operation cannot be vague in the way it is defined, and must take into account the possible distinct representations of the elements in the set that it is being defined on. This leads us to the following definition. Definition 1: Well Defined Operations An operation · on a set S is said to be well defined if it satisfies the following property; If x, w, y, z ∈ S with x = y and w = z, then x · w = y · z. 19 One can also think of an operation being well defined in terms of functions. For example, the operation of addition on the integers being well defined is equivalent to the map f : Z × Z → Z given by (a, b) 7→ a + b being a function (that is, each input gives a unique output). Definition 2: Well Defined Operations Suppose · is an operation on a set S such that there exist a set A with the property that a · b ∈ A for any a, b ∈ S. We say that · is well defined if and only if the map f : S × S → A given by (a, b) 7→ a · b is a function. We now turn our attention to modular arithmetic. Given an integer n ≥ 2, let ≡ be the relation on the integers defined in Example 1.18(c). As shown in that example, this is an equivalence relation. The equivalence class of an element a ∈ Z is [a] = {b ∈ Z : a ≡ b (mod n)} We say [a] is the equivalence class of a mod n. Since equivalence classes partition a set, [a] = [b] if and only if a ≡ b (mod n), and this in turn is equivalent to a − b = nk for some integer k. We first define operations on Zn (n ≥ 2), and show that they are well defined. Proposition 1.26. For a fixed integer n ≥ 2, the two operations [a] + [b] = [a + b] [a] · [b] = [ab] addition, multiplication, on Zn are well defined. Proof. Suppose [a] = [c] and [b] = [d]. Since [a] = [c] and [b] = [d], there exist integers u and v such that a − c = nu and b − d = nv. Then, (a + b) − (c + d) = (a − c) + (b − d) = nu + nv = n(u + v), and (ab) − (cd) = ab − bc + bc − cd = b(a − c) + c(b − d) = bnu + cnv = n(bu + cv). This shows that [a] + [b] = [a + b] = [c + d] = [c] + [d], [a] · [b] = [ab] = [cd] = [c] · [d], and the result follows. The previous proposition generalizes from the case of two element [a] and [b] to the case of finitely many [a1 ], [a2 ], . . . , [ak ] (induction). We usually write [a][b] instead of [a] · [b]. These operations are called addition and multiplication mod n, respectively. Notice that the proof of Proposition 1.26 shows that if a ≡ c (mod n) and b ≡ d (mod n), then a + b ≡ c + d (mod n) and ab ≡ cd (mod n). This is a very powerful property of modular arithmetic. 20 Example 1.27. Compute the following in Z8 . (a) [4] + [7]. (b) [4] · [7]. (c) [2]1000 . (d) [3]501 . (e) 25([5]) = [5] + [5] + . . . + [5]. | {z } 25 terms Solution. By Example 1.21, Z8 = {[0], [1], [2], [3], [4], [5], [6], [7]}. (a) [4] + [7] = [11] = [3] (since 11 ≡ 3 (mod 8)). (b) [4] · [7] = [28] = [4] (since 28 ≡ 4 (mod 8)). (c) Observe that 23 ≡ 8 mod 8 = 0 mod 8. So [2]3 = [0], and [2]1000 = [2]999 [2] = ([2]3 )333 [2] = [0][2] = [0]. (d) Observe that [3]2 = [9] = [1]. Hence, [3]501 = [3]500 [3] = ([3]2 )250 [3] = [1][3] = [3]. (e) 25([5]) = 24([5]) + [5] = 12([5] + [5]) + [5] = 12([2]) + [5] = = = = 3([2] + [2] + [2] + [2]) + [5] 3([0]) + [5] [0] + [5] [5]. ♣ Example 1.28. Define f : Z2 → Z2 via [a] 7→ [a]2 + [a] and g : Z2 7→ Z2 via [a] 7→ [0]. Prove that f = g. Solution. It suffice to show that f ([a]) = g([a]) for all [a] ∈ Z2 (since the domains and co-domains of the two functions are equal). Observe that f ([0]) = [0]2 + [0] = [0] = g([0]), and f ([1]) = [1]2 + [1] = [2] = [0] = g([1]). ♣ Hence, f = g. 21 1.6 Exercises Exercise 1.1. Let a, b ∈ Z (with at least one of a, b non-zero) with d = gcd(a, b). Prove that a b gcd , = 1. d d Exercise 1.2. Suppose a|b and a|c. Prove that a|(mb + nc) for any integers m and n. Exercise 1.3. Prove or disprove. Let a, b, c ∈ Z. If gcd(a, b) = 1 and c|(ab), then c|a or c|b. Exercise 1.4. (a) Let a, b, c ∈ Z. If a|c, b|c, and gcd(a, b) = 1, prove that (ab)|c. (b) Show, by example, that part (a) is false if one removes the assumption gcd(a, b) = 1. Exercise 1.5. Suppose a, b ∈ Z with at least one of them non-zero. Prove that gcd(a − kb, b) = gcd(a, b) for any integer k. Exercise 1.6. (Euclidean Algorithm) Let a, b ∈ Z such that 0 < b ≤ a. By the Division Algorithm there exist unique integers q and r1 such that a = bq + r1 with 0 ≤ r1 < b. Now apply the Division Algorithm to b and r1 to obtain integers q2 and r2 such that b = r1 q2 +r2 with 0 ≤ r2 < r1 . Continuing in this fashion we obtain the following: 0 ≤ r1 < b 0 ≤ r2 < r1 0 ≤ r3 < r2 a = bq + r1 b = r1 q2 + r2 r1 = r2 q3 + r3 .. . This gives us the following sequence of non-negative integers: b > r1 > r2 > r3 > . . . .
(1.1)
(a) Prove that the sequence in (1.1) must stop at zero. That is, there exist a natural number k such
that rk = 0.
(b) If k = 1, prove that gcd(a, b) = b. If k > 1, prove that gcd(a, b) = rk−1 . Hint. Use Exercise 1.5.
Exercise 1.7. (a) Let a = 228 and b = 58. Use the Euclidean Algorithm to compute gcd(a, b).
Moreover, find integers u and v such that au + bv = gcd(a, b). Hint. Look closely at the numbers
you get in the Euclidean Algorithm.
(b) Let a = 124256 and b = 1210. Use the Euclidean Algorithm to compute gcd(a, b). Moreover, find
integers u and v such that au + bv = gcd(a, b).
(c) Let a = 560 and b = 10240. Use the Euclidean Algorithm to compute gcd(a, b). Moreover, find
integers u and v such that au + bv = gcd(a, b).
Exercise 1.8. Use induction to prove the following identities for all natural numbers n.
(a) Prove that
n
X
i=1
(b) Prove that
n
X
i=1
(2i − 1)2 =
4n3 − n
.
3
1
k
=
.
i(i + 1)
k+1
22
(c) Prove that
n
X
i ≤ n2 .
i=1
(d) Prove that
√
n
X
√
1
√ ≤ 2 n.
n≤
i
i=1
(e) Let 0 < a < 1. Prove that √ n X √ 1 √ ≤ 2 n. n≤ i i=1 (f) Prove that n3 + 2n is divisible by 3. (g) Prove that 42n − 1 is divisible by 5. Exercise 1.9. Prove Theorem 1.15. Hint. Use strong induction. Exercise 1.10. Let a ∈ Z and P (a), P (a + 1), P (a + 2), . . . be an infinite sequence of mathematical statements. Use Mathematical induction to prove the following (these are variations of mathematical induction). (a) Suppose m is an even integer greater than or equal to a, (1) P (m) is true, and (2) for each k ≥ m, P (k) ⇒ P (k + 2). Prove that P (n) is true for every even integer n ≥ m. (b) Suppose m is an odd integer greater than or equal to a, (1) P (m) is true, and (2) for each k ≥ m, P (k) ⇒ P (k + 2). Prove that P (n) is true for every odd integer n ≥ m. (c) Suppose m is an odd integer greater than or equal to a, (1) P (m) and P (m + 1) are true, and (2) for each k ≥ m, P (k) ⇒ P (k + 2). Prove that P (n) is true for every integer n ≥ m. Exercise 1.11. (a) Prove that 23n−1 + 5 · 3n is divisible by 11 for all even natural numbers. (b) Is part (a) true if we replace even by odd? Explain. Exercise 1.12. For each integer n ≥ 2, prove that there are n consecutive numbers none of which are prime (that is, they are all composite). Exercise 1.13. Prove Corollary 1.17. Hint. Use the Fundamental Theorem of Arithmetic. Exercise 1.14. Define the following relation on the integers: a ∼ b ⇔ a − b is even. Prove that this is an equivalence relation on the integers. List all the distinct equivalence classes. 23 Exercise 1.15. Define the following relation on the real numbers: a ∼ b ⇔ |a| = |b|. Prove that this is an equivalence relation on the real numbers. Find the equivalence classes of [0], [1], [π], [−1], [−π]. Exercise 1.16. Define the following relation on Z − {0}: a ∼ b ⇔ gcd(a, b) = 1. Determine whether this relation is reflexive? symmetric? transitive? Is this an equivalence relation? Justify your answer. Exercise 1.17. Let S be a non-empty set, A be the set of all functions from S to S, and B be the set of all bijective functions from S to S. Define the following relation on A: f ∼ g ⇔ ∃ h ∈ B such thatf h = g. Is this an equivalence relation on A? Justify your answer. Exercise 1.18. Suppose A and B are finite sets, and A ⊆ B. Let |A| and |B| be the number of elements in A and B, respectively. Prove that if |A| = |B|, then A = B. Exercise 1.19. (a) Let A and B be two finite sets with |A| = |B|, and f : A → B a function. Prove that f injective if and only if surjective. (b) Give an example showing that part (a) is false if we remove the hypothesis that A and B are finite sets. Exercise 1.20. Let A be the set of all finite non-empty subsets of the natural numbers (this set is countable). Determine which of the following maps from A to Z are functions. (a) f (A) is the sum of all the elements in A, where A ∈ A. For example, f ({1, 2, 4}) = 1 + 2 + 4 = 7. (b) f (A) is the product of all the elements in A, where A ∈ A. (c) Given A ∈ A, ( 1 if |A| = 1, 2 f (A) = the sum of any three elements in A if |A| ≥ 3. Exercise 1.21. Find the image of the following functions. Justify your answers. (a) f : N × N → N defined via (a, b) 7→ a + b. (b) f : N × N → R defined via (a, b) 7→ a − b. (c) f : Z × Z → R defined via (a, b) 7→ a(a + 1)b . 2 (d) f : N × N → R defined via (a, b) 7→ a(a + 1)b . 2 24 (e) f : Z × Z → R defined via (a, b) 7→ (f) f : R → R defined via x 7→ (g) f : R → R defined via x 7→ a+b . 2 x . |x| + 1 x2 x . +1 (h) f : (0, ∞) → R defined via x 7→ 4x + 1. x+3 Exercise 1.22. For each part of Exercise 1.21, determine if the function is injective/surjective/bijective. Exercise 1.23. Define f : R × R → R via (a, b) 7→ a − b. (a) Find f ([−1, 1] × (0, 4)). (b) Find f ((0, 3) × {4}). (c) Find f ((1, 5) × [1, 5)). Exercise 1.24. Fix an integer n ≥ 2. Define the following operation on Zn : [a] + [b] = a + b, where + on the right of the equality is usual addition. Is this operation well defined? Justify your answer. Exercise 1.25. (a) What digit does the number 3237 end in? (b) What digit does the number 21020 end in? Exercise 1.26. (a) Prove that two natural numbers a and a + 1 are prime if and only if a = 2. (b) Suppose p is a natural number with p, p + 2, and p + 4 all prime. Prove that p = 3. Exercise 1.27. (a) Given an integer a, prove that a2 ≡ 0 or 1 (mod 4). (b) Given three integers a, b, and c, prove that a2 + b2 + c2 is not a perfect square. Note: An integer n is called a perfect square if there exist an integer m such that n = m2 . (c) Prove that the equation a2 + b2 = 3c2 has no solutions in non-zero integers a, b, and c. Exercise 1.28. Prove that an integer n is divisible by 3 if and only if the sum of its digits is divisible by 3. 1.7 Challenging Exercises Exercise 1.29. Prove that the Well Ordering Axiom and Principle of Mathematical Induction (ordinary or strong) are equivalent. Exercise 1.30. Let F1 = 1 = F2 , and Fn = Fn−1 + Fn−2 for all integers n ≥ 3. Prove that Fn = Φn − φn √ , 5 √ √ 1+ 5 1− 5 where Φ = and φ = . Hint. First show that 1 + Φ = Φ2 and 1 + φ = φ2 . 2 2 25 Exercise 1.31. Fix an integer n ≥ 1. Given non-negative real numbers x1 , x2 , . . . , xn , prove that (x1 + x2 + . . . + xn )1/n ≤ x1 + x2 + . . . + xn . n Exercise 1.32. Given seven distinct integers a1 , a2 , . . . a7 , prove that 10|(ai − aj ) or 10|(ai + aj ) for some i 6= j, i, j ∈ {1, 2, 3, 4, 5, 6, 7}. Exercise 1.33. (Open question) Given a natural number p, p and p + 2 are called twin primes if they are both prime. How many twin primes are there? It is conjectured that there are infinitely many. 26 2 Groups 2.1 Definition and Properties In this section, we introduce the basic algebraic structure to be studied in this course, called a group. We then prove some of the properties enjoyed by groups. Binary Operation Given a non-empty set G, a binary operation on G is a function from G × G → G. Usual addition (or multiplication) on the integers (or real numbers) is a binary operation. Division is not a binary operation on the natural numbers, nor is it a binary operation on the integers. Group Let G be a set together with a binary operation ·, that assigns to (a, b) ∈ G × G an element a · b (usually written as ab). We say (G, ·) is a group if it satisfies the following three properties: 1. Associativity; (ab)c = a(bc) for all a, b, c ∈ G. 2. Identity; there exist an element e ∈ G such that ae = a = ea for all a ∈ G. The element e is called the identity element in G. 3. Inverses; for all a ∈ G, there exist b ∈ G such ab = e = ba. We denote b by a−1 and call it the inverse of a. Associativity allows us to drop the brackets. In particular, instead of writing (ab)c we simply write abc, and this can be extended to any finite number of elements in G (induction). We will shortly prove that the identity element and inverses in a group are unique. Example 2.1. Which one of the following is a group? (a) (Z, +), where + is usual addition. (b) (Z, ×), where × is usual multiplication. (c) (N, +), where + is usual addition. Solution. (a) Since the sum of two integers is an integer, the operation of addition as binary. Moreover, addition on the integers is associative. The identity element in this set is the number zero. For any a ∈ Z, a + (−a) = 0, so a−1 = −a ∈ Z. Hence, the integers are a group under addition. (b) This is not a group. To see this, notice that 1 is the identity element in Z under the operation of multiplication. However, there does not exist an integer b such that 2b = 1, i.e., 2−1 does not exist. (c) This is not a group. This set has no identity element (notice that 0 ∈ / N). Also, inverses do not exist. ♣ Unless otherwise stated when we say Z is a group we assume the operation is usual addition. 27 Abelian Group A group G is called Abelian (or commutative) if ab = ba for all a, b ∈ G. Example 2.2. Which one of the groups in example 2.1 are Abelian? Solution. (Z, +) is an Abelian group. The other two are not groups. ♣ We now state some of the properties of a group. Properties of A Group Theorem 2.3. Let G be a group, e the identity element in G, and a, b ∈ G. Then, (1) e is unique, i.e., e is the unique element of G satisfying ea = a = ae for all a ∈ G. (2) If ab = ac, then b = c. Similarly, if ba = ca, then b = c. (3) a−1 is unique, i.e., a−1 is the unique element of G satisfying aa−1 = e = a−1 a. (4) (ab)−1 = b−1 a−1 . (5) (a−1 )−1 = a. Proof. (1) Suppose e and f are both identity elements of G. Then, ae = a = ea and af = a = f a for all a ∈ G. In particular, e = ef = f . (2) If ab = ac, then a−1 (ab) = a−1 (ac) ⇒ (a−1 a)b = (a−1 a)c ⇒ eb = ec ⇒ b = c. A similar argument shows that if ba = ca, then b = c. (3) Suppose b and c are both inverses of a. Then, ba = e = ca, and by part (2), b = c. (4) Notice that (ab)(b−1 a−1 ) = a(bb−1 )a−1 = aea−1 = aa−1 = e. Similarly, (b−1 a−1 )(ab) = e. Hence, (ab)−1 = b−1 a−1 . (5) This follows from the fact that aa−1 = e = a−1 a. One of the consequences of part (2) of the previous proposition is that if a ∈ G with ab = e or ba = e, then b = a−1 , i.e., we do not have to show both equations hold. Also, if for some b ∈ G, ab = a (or ba = a), then b must be the identity, i.e., we do not have to check bx = xb = x for all x ∈ G. The rest of this section consists of examples of groups. The Abelian Group Zn Example 2.4. Given an integer n ≥ 2, Zn is an Abelian group under the operation [a] + [b] = [a + b]. Solution. Given [a], [b] ∈ Zn , [a]+[b] = [a+b] ∈ Zn , so the operation is binary. For any [a], [b], [c] ∈ Zn , [a] + ([b] + [c]) = [a] + [b + c] = [a + (b + c)] = [(a + b) + c] = [a + b] + [c] = ([a] + [b]) + [c]. 28 We have just shown associativity. Since [a] + [0] = [a] = [0] + [a] for all [a] ∈ Zn , the identity element in Zn is [0]. Moreover, [a] + [−a] = [a − a] = [0] = [−a + a] = [−a] + [a]. That is, [a]−1 = [−a] ∈ Zn . Hence, Zn is a group. Furthermore, [a] + [b] = [a + b] = [b + a] = [b] + [a] for any [a], [b] ∈ Zn . ♣ The Abelian Group U (n) Example 2.5. Given an integer n ≥ 2, define U (n) = {[a] ∈ Zn : [ax] = [1] for some integer x}. Show that U (n) is an Abelian group under the operation [a][b] = [ab]. Solution. Given [a], [b] ∈ U (n), there exist integers x and y such that [ax] = [1] = [by]. This is equivalent to ax + nt = 1 and by + ns = 1, for some integers t and s. By Corollary 1.5, gcd(a, n) = 1 = gcd(b, n), and by Corollary 1.16, gcd(ab, n) = 1. Using Corollary 1.5 we get (ab)u + nv = 1 for some integers u and v, and this in turn is equivalent to [(ab)u] = [1]. Hence, [a][b] = [ab] ∈ U (n), which implies that the operation is binary. For any [a], [b], [c] ∈ U (n), [a]([b][c]) = [a][bc] = [a(bc)] = [(ab)c] = [ab][c] = ([a][b])[c]. We have just shown associativity. The identity element in this group is [1] (as [a][1] = [a] = [1][a] for all [a] ∈ U (n)). Moreover, given [a] ∈ U (n), there exist an integer b such that [a][b] = [ab] = [1] = [ba] = [b][a]. Notice that [b] ∈ U (n) (as [ba] = [ab] = [1]). So [a]−1 = [b] ∈ U (n). Hence, U (n) is a group and [a][b] = [ab] = [ba] = [b][a] for all [a], [b] ∈ U (n). ♣ The students should check that the set U (n) can also be written as follows: U (n) = {[a] ∈ Zn : gcd(a, n) = 1}. Unless otherwise stated the operations on Zn and U (n) are the operations defined in the preceding two examples, respectively. Moreover, we abuse notation and write a instead of [a] in these groups. It should be understood that the elements in these groups are not integers (they are equivalence classes mod n). For example, Z4 = {0, 1, 2, 3} and U (10) = {1, 3, 7, 9}. The operations in Zn and U (n) are called addition mod n and multiplication mod n, respectively. Example 2.6. Let G= 2a 2a 2a 2a : a ∈ R, a 6= 0 . Prove that G is an Abelian group under the usual matrix multiplication. 29 Solution. From linear algebra we know matrix multiplication is associative. Moreover, 2a 2a 2b 2b 8ab 8ab 2(4ab) 2(4ab) = = ∈G 2a 2a 2b 2b 8ab 8ab 2(4ab) 2(4ab) Notice that we have used that fact that a, b 6= 0 implies that 4ab 6= 0. We have just proven the operation is binary. Since 1 1 1 1 2a 2a 2a 2a 2a 2a 2 2 = = 21 21 , 1 1 2a 2a 2a 2a 2a 2a 2 2 2 2 1 1 1 2 4 2 14 = 21 21 . Furthermore, the identity element in G is 2 41 2 14 2 2 −1 1 1 1 1 2 16a a a 2 16a 8a 8a ∈G = 1 1 = 1 1 a a 2 2 8a 8a 16a 16a Therefore, G is a group under matrix multiplication. Also, 2a 2a 2b 2b 8ab 8ab 2b 2b 2a 2a = = . 2a 2a 2b 2b 8ab 8ab 2b 2b 2a 2a ♣ Hence, G is Abelian. The previous example seems to contradict what many of us learned in linear algebra: an n × n matrix A has an inverse if and only if det A 6= 0. All the matrices in the previous example have determinant zero. So what is happening here? How is it possible that these matrices have inverses? The answer while simple is very subtle. The theorems in linear algebra are based on the fact that the entries in our matrices is the set of all real numbers with no relation between the entries themselves. However, in the previous example, the restriction on the matrices is much more severe: every entry must be the same. This condition changes the identity element in this set, which in turn changes the notion of inverses. So theorems that we knew from linear algebra do not apply in the previous example. ab (where ab is the usual product of the 2 rational numbers). Show that (G, ∗) is an Abelian group. Example 2.7. Let G = Q − {0}, and define a ∗ b = p c pc , b = where p, q, c, d ∈ Z − {0}. Then, a ∗ b = ∈ G. q d 2qd Moreover, for any a, b, c ∈ G, we have Solution. Given a, b ∈ G, let a = a ∗ (b ∗ c) = a ∗ bc a(bc) (ab)c (a ∗ b)c = = = = (a ∗ b) ∗ c. 2 4 4 2 For any a ∈ G, we have a(2) 2a =a= =2∗a 2 2 4 4 4 Hence, the identity element in G is 2. Furthermore, ∈ G (since a ∈ G) and a ∗ = 2 = ∗ a. a a a 4 −1 That is, a = . Hence, (G, ∗) is a group. Also, a ab ba a∗b= = = b ∗ a for any a, b ∈ G, 2 2 a∗2= 30 ♣ showing that G is Abelian. Example 2.8. Let G = R − {−1}, and define x ∗ y = x + y + xy (the operations on the right of the equality are normal addition and multiplication). Prove (G, ∗) is an Abelian group. Solution. Given x, y ∈ G, x ∗ y ∈ R (since R is closed under addition and multiplication). Moreover, if x ∗ y = −1, then x + y + xy = −1 ⇒ ⇒ ⇒ ⇒ x + y + xy + 1 = 0 x(1 + y) + 1 + y = 0 (x + 1)(y + 1) = 0 x = −1 or y = −1, a contradiction. Therefore, ∗ is a binary operation on G. For any x, y, z ∈ G, (x ∗ y) ∗ z = (x + y + xy) ∗ z = x + y + xy + z + z(x + y + xy) = x + y + xy + z + zx + zy + zxy, and x ∗ (y ∗ z) = x ∗ (y + z + yz) = x + y + z + yz + x(y + z + yz) = x + y + z + yz + xy + xz + xyz. In particular, (x ∗ y) ∗ z = x ∗ (y ∗ z). Hence, ∗ is an associative operation on G. For any x ∈ G, we have x ∗ 0 = x = 0 ∗ x. Thus the identity element in G is 0. Moreover, by solving the equation x ∗ y = 0 for y we get x−1 = y = −x 1+x (notice that x 6= −1). We need to show y ∈ G, i.e., y 6= −1. If y = −1, then −(1 + x) = −x, which in turn gives −1 = 0, a contradiction. Hence, (G, ∗) is a group. Moreover, x ∗ y = x + y + xy = y + x + yx = y ∗ x, ♣ showing that G is Abelian. Example 2.9. Let a b G= : a + d = b + c, a, b, c, d ∈ R c d Show that G is an Abelian group under (the usual) matrix addition. Solution. From linear algebra we know matrix addition is associative. Given A, B ∈ G, let x y x1 y1 A= , B= , z w z1 w1 31 where x, y, z, w, x1 , y1 , z1 , w1 ∈ R, and x + w = y + z, x1 + w1 = y1 + z1 ⇒ (x + x1 ) + (w + w1 ) = (y + y1 ) + (z + z1 ) In particular, A+B = x y x1 y1 x + x1 y + y 1 + = ∈G z w z1 w1 z + z1 w + w1 This proves the operation is binary. Let E= 0 0 0 0 ∈ G. Notice that A + E = A = E + A for all A ∈ G. Hence, E is the identity element of G. Moreover, if x y A= ∈ G, where x, y, z, w ∈ R, x + w = y + z, z w then −x − w = −y − z. Thus −A ∈ G, and A−1 = −A (as A + (−A) = E = (−A) + A). Hence, G is a group under matrix addition. This group is Abelian: x y x1 + x y 1 + y x1 y1 x + x1 y + y 1 x y x1 y 1 + , = = = + z1 w1 z w z + z1 w + w1 z1 + z w1 + w z1 w1 z w ♣ showing that G is Abelian. The next example gives a necessary and sufficient condition for a group to be Abelian. Example 2.10. Let G be a group. Then, G is Abelian if and only if (ab)−1 = a−1 b−1 for all a, b ∈ G. Solution. If G is Abelian, then all the elements in G commute with each other. Combining this with Theorem 2.3(4), for any a, b ∈ G we have (ab)−1 = b−1 a−1 = a−1 b−1 . Conversely, suppose (ab)−1 = a−1 b−1 for all a, b ∈ G. Given x, y ∈ G, xy = = = = (x−1 )−1 (y −1 )−1 (x−1 y −1 )−1 (y −1 )−1 (x−1 )−1 yx by Theorem 2.3(5) by our assumption by Theorem 2.3(4) by Theorem 2.3(5), ♣ showing that G is Abelian 0 If g ∈ G, we define g = e, and for any natural number n, we define g n = g · g · · · · · g and g −n = g −1 · g −1 · · · · · g −1 . {z } | {z } | n−times n−times It should be noted that in a group we do not permit non-integer exponents. Notice that when the operation in your group is addition, the preceding notation translates to g m = mg for any g ∈ G and m ∈ Z. Moreover, if a, b ∈ G and the operation is addition, then ab−1 = a − b. 32 Example 2.11. Let G be a group. Suppose that x2 = e for all x ∈ G. Prove that G is Abelian. Solution. Given a, b ∈ G, we have a = a−1 , b = b−1 , and ab = (ab)−1 . Hence, ab = (ab)−1 = b−1 a−1 by Theorem 2.3(4) = ba, ♣ showing that G is an Abelian group. 2.2 Order of a Group, Order of an Element In this section, we introduce the notion of order for a group and its elements. Order of A Group If G is a group, the number of elements in G is called the order of G. The order of a group G is denoted by |G|. If G has infinitely many elements, countable or not, we write |G| = ∞. For example, the integers under addition are an infinite group (i.e., |Z| = ∞). Whereas the group U (6) = {1, 5} is a group of order 2 (i.e., |U (6)| = 2). Order of An Element Given an element g in a group G, the order of g is the smallest positive integer n such that g n = e. If no such n exist, we say that g has infinite order. The order of an element g ∈ G is denoted by |g|. A few quick facts that follow from the definition of the order of an element g in a group G are: (1) |g| = 1 if and only if g = e. (2) |g| = ∞ is equivalent to the following statement: g n = e if and only if n = 0. (3) |g| = n is equivalent to: (i) g n = e, and (ii) if g m = e for some natural number m, then n ≤ m. Example 2.12. List the elements in U (10). Find the order of U (10) and every element in it. Solution. The group U (10) = {1, 3, 7, 9}. So |U (10)| = 4. The identity element in U (10) is 1. Notice that 71 72 73 74 = = = = 7 6= 1, 49 = 9 6= 1, 7 · 72 = 7 · 9 = 63 = 3 6= 1, 72 · 72 = 9 · 9 = 81 = 1. Hence, |7| = 4. A similar computation shows that |1| = 1, |3| = 4, |9| = 2. 33 ♣ Example 2.13. List the element in Z8 and find the order of every element. Solution. The group Z8 = {0, 1, 2, 3, 4, 5, 6, 7}. The identity element in Z8 is 0. Notice that 21 22 23 24 = = = = 2, 2 + 2 = 4, 2 + 2 + 2 = 6, 2 + 2 + 2 + 2 = 8 = 0. Hence, |2| = 4. Similar computations show that |0| |1| |4| |6| = = = = 1 8 = |3| = |5| = |7| 2 4 ♣ Example 2.14. Find the order of every element in Z. Solution. As we mentioned at the beginning of this section, the integers are an infinite group under addition. Since zero is the identity element, |0| = 1. If n 6= 0, we show that |n| = ∞. Assume to the contrary, say |n| = m. Then mn = nm = 0. This implies that n = 0 or m = 0, a contradiction. Hence, every non-identity element in Z has infinite order. ♣ Example 2.15. Let a, b ∈ G with |a| = 4, |b| = 2, and a3 b = ba. Find |ab|. Solution. We do this by process of elimination. If |ab| = 1, then ab = e, equivalently a = b−1 . By Exercise 2.19, |a| = |b|, a contradiction. Thus |ab| ≥ 2. Since (ab)2 = (ab)(ab) = a(ba)b = a(a3 b)b = a4 b2 = ee = e, we get |ab| = 2. ♣ Example 2.16. Let a, b ∈ G with |a| = 2, b 6= e, |ab| = 2, and aba = b2 . Determine |b|. Solution. Since b 6= e, |b| ≥ 2. Notice that |a| = 2 implies that a = a−1 . If |b| = 2, then e = b2 = aba ⇒ b = a−1 a−1 = a2 = e, a contradiction. Thus |b| ≥ 3. Since b3 = b2 b = (aba)b = (ab)2 = e, we get |b| = 3. ♣ The following corollary gives us a necessary and sufficient condition for ak = e whenever a has finite order. 34 Corollary 2.17. Given a ∈ G with |a| = n < ∞, ak = e if and only if n|k. In other words, ak = e if and only if k is an integer multiple of n. Proof. If n|k, then k = nm for some integer m. In particular, ak = anm = (an )m = em = e. Conversely, if ak = e, by the Division Algorithm, there exist unique integers q and r such that k = nq + r with 0 ≤ r < n. It follows that ar = ak−nq = ak (an )−q = ee−q = e. Minimality of n implies that r = 0, and the result follows. Example 2.18. Suppose x is an element of a group G and xn = e = xm for some integers n, m (not both zero). Prove that |x| |d, where d = gcd(n, m). Solution. Notice that |x| is finite, as xn = e (can also use xm = e). By Proposition 1.3, there exist integers u and v such that d = mu + nv. In particular, xd = xmu+nv = (xm )u (xn )v = eu ev = e. ♣ The result now follows by Corollary 2.17. 2.3 Subgroups The set of even integers E is a group under addition (proof of this is left to the reader). This set is also a subset of a bigger set which is also a group under addition, namely, the integers. Of course, the integers are also a subset of the rationals, which is also a group under addition. One can extend this to the real numbers; that is, we have the following chain of groups ordered by inclusion: E ⊆ Z ⊆ Q ⊆ R. This situation arises so often that we introduce a special term to describe it. Subgroup A subset H of a group G is called a subgroup of G, if H itself is a group under the binary operation of G. If H is a subgroup of G, we write H G. If H G, then it must have an identity element, and thus it must be non-empty. Moreover, the identity element of G is also the identity element of H. To see this, since H is not empty, there exist an a ∈ H. Since H is a subgroup, a−1 ∈ H. Since our operation is binary, e = aa−1 ∈ H, and the uniqueness of the identity element proves the result. It is very easy to prove that {e} G for any group G. This is called the trivial subgroup of G. In particular, for any group G, the sets {e} and G are subgroups of G. If H is a subgroup of G but is not equal to G itself, we write H ≺ G. Such a subgroup is called a proper subgroup of G. For example, the set of even integers is a proper subgroup of the integers, the integers are a proper subgroup of the rationals, and the rationals are a proper subgroup of the reals. 35 Example 2.19. Is the set of odd integers a subgroup of the integers under addition? Solution. No. The sum of two odd integers is even. Thus the operation is not binary. One can also use the fact that there is no identity element in the set of odd integers. ♣ Example 2.20. Is the set H = (R − Q) ∪ {1} a subgroup of G = R − {0} under multiplication? Solution. This is not a subgroup. To see this, notice that is, the operation is not binary. √ √ √ 2 ∈ H, however, 2 2 = 2 ∈ / H. That ♣ Given a group G, the relation on subgroups of G is a reflexive and transitive relation. However, it is almost never a symmetric relation. The only time it is a symmetric relation is when G = {e}. Proposition 2.21. Let G be a group and ∅ = 6 H ⊆ G. If H satisfies the following property: a, b ∈ H ⇒ ab−1 ∈ H, then H G. Proof. Then, a = e, get xy Associativity follows from the fact that H ⊆ G. Since H is non-empty, there exist an x ∈ H. e = xx−1 ∈ H (by taking a = x = b). If x ∈ H, then x−1 = ex−1 ∈ H (by taking b = x). Suppose x, y ∈ H. By our preceding argument y −1 ∈ H. Taking a = x, b = y −1 we = x(y −1 )−1 ∈ H. Hence, H is a group, showing that H G. Example 2.22. Let G be an Abelian group and define H = {x ∈ G| x2 = e}. Prove that H G. Solution. By definition H ⊆ G. Moreover, e = e2 ∈ H, showing that H is not empty. Given x, y ∈ H, we have x = x−1 and y = y −1 . This gives (xy −1 )2 = xy −1 xy −1 = = = = x2 (y −1 )2 as G is Abelian x2 y 2 ee e. Hence, xy −1 ∈ H, and the result follows by Proposition 2.21. ♣ The following example shows that the intersection of two subgroups is again a subgroup. Example 2.23. Suppose H, K G. Prove that H ∩ K G. Solution. Notice that H ∩ K ⊆ H ⊆ G. Moreover, e ∈ H ∩ K (as e ∈ H and e ∈ K). Thus H ∩ K is not empty. Given x, y ∈ H ∩ K, the elements x and y are in H and in K. Since H and K are subgroups of G, we have xy −1 is in H and K. That is, xy −1 ∈ H ∩ K. By Proposition 2.21, H ∩ K G. ♣ 36 It is not true that the union of two subgroups has to be a subgroup (see Exercise 2.25). Proposition 2.24. Let G be a group and let H be a non-empty subset of G. If H satisfies the following two properties: 1. a, b ∈ H ⇒ ab ∈ H (H is closed under multiplication), and 2. a ∈ H ⇒ a−1 ∈ H (H is closed under inverses), then H G. Proof. Suppose a, b ∈ H. Since H is closed under inverses, b−1 ∈ H. Since H is closed under multiplication we have ab−1 ∈ H, and the result follows by Proposition 2.21. Example 2.25. Suppose G is an Abelian group and H, K G. Prove that HK = {hk : h ∈ H, k ∈ K} G. Solution. Notice that e = ee ∈ HK and HK ⊆ G (since the operation in G is binary). Given a, b ∈ HK, then a = xy and b = zw for some x, z ∈ H and y, w ∈ K. Since G is Abelian and H and K are subgroup of G, ab = xyzw = (xz)(yw) ∈ HK, and a = (xy)−1 = y −1 x−1 = x−1 y −1 ∈ HK. −1 By Proposition 2.24, HK G. ♣ Example 2.26. Let H be a subgroup of a group G, and for each g ∈ G, define gHg −1 = {ghg −1 : h ∈ H}. Prove that gHg −1 G for all g ∈ G. Solution. Given g ∈ G, e = geg −1 ∈ gHg −1 (thus gHg −1 is not empty). Since the operation in G is binary, gHg −1 ⊆ G. Given a, b ∈ gHg −1 , a = ghg −1 and b = gh1 g −1 for some h, h1 ∈ H. It follows that ab = (ghg −1 )(gh1 g −1 ) = g(hh1 )g −1 ∈ gHg −1 , and a−1 = (ghg −1 )−1 = (g −1 )−1 h−1 g −1 = gh−1 g −1 ∈ gHg −1 . By Proposition 2.24, gHg −1 G. ♣ The following sets (which we will show are subgroups) play a crucial role in group theory. 37 Center/Centralizer/Normalizer Let G be a group. • The center of G, denoted by Z(G), is the set of all elements in G that commute with every element of G; Z(G) = {g ∈ G : gx = xg ∀x ∈ G}. • Given an element a ∈ G, the centralizer of a ∈ G, denoted by CG (a), is the set of elements in G that commute with a; CG (a) = {g ∈ G : ga = ag}. • If H G, the centralizer of H in G, denoted by CG (H), is the set of elements in G that commute with every element in H; CG (H) = {g ∈ G : gh = hg ∀h ∈ H}. • If H G, the normalizer of H in G is the set NG (H) = {g ∈ G : gHg −1 = H}. It follows by definition that G is Abelian if and only if Z(G) = G. Moreover, CG (G) = Z(G). Theorem 2.27. Let G be a group. Then, 1. Z(G) CG (a) G for all a ∈ G. 2. Z(G) CG (H) NG (H) G for all H G. 3. G is Abelian if and only if Z(G) = CG (a) for all a ∈ G. 4. Z(G) = CG (a). a∈G Proof. The proofs of (2), (3), and (4) are left as an exercise (see Exercise 2.18). The elements of the center of a group commute with every element in the group. In particular, given a ∈ G, g ∈ Z(G), we have ga = ag. This is equivalent to g ∈ CG (a). Since a ∈ G and g ∈ Z(G) were chosen arbitrarily, we have Z(G) ⊆ CG (a) for any a ∈ G. It now suffices to show that Z(G) G and CG (a) G. Since ea = ae for all a ∈ G, i.e., e ∈ Z(G). Given x, y ∈ Z(G), for any a ∈ G, (xy)a = x(ya) = x(ay) = (xa)y = (ax)y = a(xy). Thus xy ∈ Z(G). Moreover, xa = ax for all a ∈ G ⇔ x−1 (xa)x−1 = x−1 (ax)x−1 for all a ∈ G ⇔ ax−1 = x−1 a for all a ∈ G. That is, x−1 ∈ Z(G), and the result follows by Proposition 2.24, Z(G) G. 38 We now show CG (a) G for all a ∈ G. Given a ∈ G, the identity element e is in CG (a) (as ea = ae). So CG (a) 6= ∅. Moreover, given x, y ∈ CG (a), (xy)a = x(ya) = x(ay) = (xa)y = (ax)y = a(xy) ⇒ xy ∈ CG (a), and xa = ax ⇔ x−1 (xa)x−1 = x−1 (ax)x−1 ⇔ ax−1 = x−1 a ⇔ x−1 ∈ CG (a). By Proposition 2.24, CG (a) G. Example 2.28. Let GL(2, R) = a b : a, b, c, d ∈ R, ad − bc 6= 0 . c d This usual matrix set is a group under multiplication (see Exercise 2.1(b)). Find the centralizer 1 1 1 1 of , i.e., CGL(2,R) . 1 0 1 0 Solution. CGL(2,R) 1 1 1 0 = = = = a b a b 1 1 1 1 a b ∈ GL(2, R) : = c d c d 1 0 1 0 c d a b a+b a a+c b+d ∈ GL(2, R) : = a b c d c+d c a b ∈ GL(2, R) : a = b + d, b = c c d b+d b 2 : b, d ∈ R, (b + d)d 6= b . b d ♣ Example 2.29. Let SL(2, R) = a b : a, b, c, d ∈ R, ad − bc = 1 . c d This set is a group under usual matrix multiplication (see Exercise 2.30). Find the center of SL(2, R), i.e., Z(SL(2, R)). Solution. We need to find all matrices that commute with every element in Z(SL(2, R)). Suppose a b ∈ Z(SL(2, R)). Then, c d a b 0 1 0 1 a b a b a b = ⇒ a = d and c = −b ⇒ = . c d −1 0 −1 0 c d c d −b a Furthermore, a b −b a 1 1 −1 0 = 1 1 −1 0 39 a b −b a ⇒ b = 0. a b a 0 Hence, = with a2 = 1 (as our matrix must be an element of SL(2, R)). This proves c d 0 a a 0 2 Z(SL(2, R)) ⊆ : a ∈ R, a = 1 . 0 a The reverse inclusion is obtained by noticing a 0 x y ax ay x y a 0 = = . 0 a z w az aw z w 0 a Hence, Z(SL(2, R)) = a 0 1 0 −1 0 2 : a ∈ R, a = 1 = , . 0 a 0 1 0 −1 ♣ Example 2.30. Suppose x, y ∈ G with xy ∈ Z(G). Prove that xy = yx. Solution. Since xy ∈ Z(G) it commutes with every element in G. Hence, (xy)x−1 = x−1 (xy) = (x−1 x)y = y ⇒ xy = yx. ♣ Proposition 2.31. Suppose H is a non-empty subset of a group G and |H| < ∞. If H is closed under the operation of G (i.e., the operation on G defines a binary operation on H) then H G. Proof. We only need to show that H is closed under inverses. Let a ∈ H. If a = e, then a−1 = e−1 = e = a ∈ H. If a 6= e, consider the sequence a, a2 , a3 , .... Since H is closed under the operation, these are all in H. Since H is finite, not all of these elements are distinct. In particular, ai = aj for some i 6= j. Without loss of generality we can assume i > j. Then ai−j = e. Since a 6= e, we have i − j > 1.
Thus, a(ai−j−1 ) = e ⇒ a−1 = ai−j−1 ∈ H. Hence, H G. Remark. The condition that H is finite
is a necessary one (see Exercise 2.14).
2.4
Cayley Table for Groups
If G is a finite group under the operation ·, a very nice way to arrange a · b for all a, b ∈ G is via
a table, called a Cayley table. The entry a · b appears in the box corresponding to the row a and
column b and the entry b · a appears in the box corresponding to the row b and column a. Note that
a · b may not equal to b · a. For example, if G = {e, a, b, c} is a group under the operation ·, then its
Cayley table is
·
e
e
e
a a·e
b b·e
c c·e
a
b
e·a e·b
a·a a·b
b·a b·b
c·a c·b
40
c
e·c
a·c
b·c
c·c
Example 2.32. Give the Cayley table for Z4 .
Solution.
+
0
1
2
3
0
0
1
2
3
1
1
2
3
0
2
2
3
0
1
3
3
0
1
2
♣
Example 2.33. Give the Cayley table for U (10).
Solution.
·
1
3
7
9
1
1
3
7
9
3
3
9
1
7
7
7
1
9
3
9
9
7
3
1
♣
Example 2.34. Give the Cayley table for U (7).
Solution.
·
1
2
3
4
5
6
1
1
2
3
4
5
6
2
2
4
6
1
3
5
3
3
6
2
5
1
4
4
4
1
5
2
6
3
5
5
3
1
6
4
2
6
6
5
4
3
2
1
♣
41
2.5
Exercises
Unless otherwise stated G is a group.
Exercise 2.1. Determine which of the following are groups under the defined operation.
(a) The set of 2 × 2 matrices with entries in R under matrix addition.

a b
(b) The set GL(2, R) =
: det A = ad − bc 6= 0, a, b, c, d ∈ R under usual matrix mulc d
tiplication. This group is called the General Linear Group.
(c) The set R× = R − {0} under usual multiplication.
(d) The set R>0 = {x ∈ R : x > 0} under usual multiplication.
(e) The set Q>0 = {x ∈ Q : x > 0} under usual multiplication.
(f) The set Z × Z under the operation (a, b)(c, d) = (ad + bc, bd).
(g) The set Q under the operation a · b =
addition.
a+b
, where addition on the right of the equality is usual
7
Exercise 2.2. Determine which groups in Exercise 2.1 are Abelian.
Exercise 2.3. Is the set of the integers under the operation a · b = a + b − 2 a group? Justify your
answer. If yes, is it Abelian? Justify your answer.
Exercise 2.4. Is the set of the integers under the operation a · b = a − b + 1 a group? Justify your
answer. If yes, is it Abelian? Justify your answer.
Exercise 2.5. Let G be the set of odd integers. Is this set a group under addition? Justify your
answer.

a b
Exercise 2.6. Let G =
: a, b, c, d ∈ R, bc = 0 . Is G a group under matrix addition?
c d
Justify your answer.
Exercise 2.7. Let

a b
G=
: a, b, c, d ∈ R, ad = 0 .
c d
Is G a group under usual matrix addition? Justify your answer.
Exercise 2.8. Find the inverse and order of every element in U (7)? Do the same for U (10).
Exercise 2.9. Is Z6 a group under the operation [a][b] = [ab]? Justify your answer.
Exercise 2.10. Let M2×2 (R) be the set of all 2 × 2 matrices with entries from R. The trace of a
2 × 2 matrix A, denoted tr(A), is defined to be the sum of its main diagonal. That is,

a b
tr(A) = a + d where A =
.
c d
Let G = {A ∈ M2×2 (R) : tr(A) = 0}. Is G a group under usual matrix addition (justify your answer)? If yes, is it an Abelian Group (justify your answer)?
42
Exercise 2.11. Is the set G in Exercise 2.10 a group under matrix multiplication? Justify your
answer.
Exercise 2.12. Let

G=

a b
: a, b, c ∈ R .
c a
Is G a group under usual matrix addition (justify your answer)? If yes, is it an Abelian Group (justify
your answer)?
Exercise 2.13. Let G = {5, 15, 25, 35}. Prove that G is a group under multiplication modulo 40.
Find the order of each element in this group.
Exercise 2.14. Give an example of a non-empty subset H of a group G that is closed under the
operation of G but is not a subgroup of G.
Exercise 2.15. (a) Find the order of A, B ∈ GL(2, R), where

0
1
0 −1
A=
, and B =
.
−1 −1
1 0
(b) Find the order of |AB|. Is |AB| = |A| |B|?
Exercise 2.16. Find the order of all the elements in Z10 and U (20).
Exercise 2.17. (a) Suppose a ∈ G with |a| = 9. Prove that there exist x ∈ G such that x5 = a2 .
(b) Suppose a ∈ G with |a| = 11. Prove that there exist x ∈ G such that x6 = a.
Exercise 2.18. Prove the rest of Theorem 2.27.
Exercise 2.19. Show that |a| = |a−1 | for all a ∈ G.
Exercise 2.20. Let g ∈ G such that |g| = n < ∞. (a) Prove that if n = 2k + 1 for some integer k ≥ 0, then xi 6= x−i for all i = 1, 2, . . . , n − 1. (b) Prove that if n = 2k for some integer k ≥ 1 and 1 ≤ i < n, then xi = x−i if and only if i = k. Exercise 2.21. Suppose a, b ∈ G such that |a| = 2, |b| ≥ 2, and b = ab2 a. Determine |b|. Exercise 2.22. (a) Prove that CG (a) = CG (a−1 ) for all a ∈ G. (b) Suppose a ∈ G with |a| = n, and k is an integer with gcd(n, k) = 1. Prove that CG (a) = CG (ak ). Exercise 2.23. Suppose H and K are subgroups of G. Prove that HK is a subgroup of G if and only if HK = KH. Exercise 2.24. Suppose H is a subgroup of G. Prove that HZ(G) is a subgroup of G. Exercise 2.25. (a) Give an example of a group G with subgroups H and K such that H ∪ K is not a subgroup of G. (b) Suppose H1 , H2 , H3 , . . . is an infinite collection of subgroups of a group G such that Hi ⊆ Hi+1 for all i ∈ N. Prove that ∞ [ Hi i=1 is a subgroup of G. 43 Exercise 2.26. Suppose H1 , H2 , H3 , . . . is an infinite collection of subgroups of a group G. Prove that ∞ Hi i=1 is a subgroup of G. Exercise 2.27. Let H G and define a relation ∼ on G by a ∼ b ⇔ b−1 a ∈ H. Prove that ∼ is an equivalence relation on G. Exercise 2.28. Define the following operation on R2 = {(x, y) : x, y ∈ R}: (a, b) + (c, d) = (a + c, b + d). (a) Prove that (R2 , +) is a group. (b) Let H = {(x, y) ∈ R2 : xy ≥ 0}. Is H a subgroup of R2 ? (c) Let K = {(x, y) ∈ R2 : x2 + y 2 = 1}. Is K a subgroup of R2 ? Justify your answer. Exercise 2.29. Suppose G is an Abelian group. Prove that H = {g 2 : g ∈ G} is a subgroup of G (see Exercise 4.25). Exercise 2.30. Let SL(2, R) = a b : a, b, c, d ∈ R, ad − bc = 1 . c d This is called the special linear group. Show that SL(2, R) is a group under matrix multiplication and it is a subset of GL(2, R). Conclude that SL(2, R) GL(2, R). Exercise 2.31. Show that the set Q× = Q − {0} is a subgroup of R× Exercise 2.32. Show that the set Q>0 = {x ∈ Q : x > 0} is a subgroup R>0 .
Exercise 2.33. Let G be an Abelian group and n a fixed positive integer.
(a) Prove that
H = {g ∈ G : g n = e} G.
(b) Prove that
K = {g n : g ∈ G} G.
Exercise 2.34. Suppose G is a group of order n ≥ 3. Prove that G does not have a subgroup of
order n − 1.
Exercise 2.35. Let H and K be subgroups of G. Prove that H ∪ K is a subgroup if and only if
either H ⊆ K or K ⊆ H.
44
Exercise 2.36. Suppose x, y ∈ G with |x| = |y| = |xy| = 2. Prove that x and y commute with each
other, i.e., xy = yx.
Exercise 2.37. Prove or disprove. If |a3 | = |b3 |, then |a| = |b|.
Exercise 2.38. Prove that G is Abelian if and only if (xy)2 = x2 y 2 for all x, y ∈ G.
Exercise 2.39. Suppose G is a finite group with even order. Prove that G must have an element of
order 2.
Exercise 2.40. Prove that H CG (H) if and only if H is an Abelian subgroup of G.
Exercise 2.41. (a) Find Z(GL(2, R)).

0 −1
(b) Find CGL(2,R)
.
−1 1

1 −1
(c) Find CGL(2,R)
.
−1 0
Exercise 2.42. (a) Suppose that the table shown below is a Cayley table for a group G. Fill in the
blank entries.
· e
e e
a
b
c
d
a
b
c
d
d
c
e
a
e
a
(b) Use the table to compute the following.
(1) CG (b).
(2) Z(G).
(3) CG (d).
(4) a(bc).
(5) b2 ac2 d.
(6) (ab)2 .
(7) The order of every element in G.
(8) |abcd|.
45
2.6
Challenging Exercises
×
Exercise 2.43. Fix an integer n ≥ 2. Let Z×
n = Zn − {0}, and define the following operation on Zn :
×
[a][b] = [ab]. Prove that Zn is a group under this operation if and only if n is prime.
Exercise 2.44. Fix an integer n ≥ 2. Let
Gn = {f : Z → Z : f is a bijection and f (i + n) = f (i) + n ∀i ∈ Z}, and
Hn = {f ∈ Gn : f (i) ≡ i(mod n) for all i ∈ Z}.
(a) Prove that Gn is a group under function composition.
(b) Prove that Hn Gn .
Exercise 2.45. Suppose a, b ∈ G such that |a| = 2k + 1 for some integer k ≥ 0, and ab = b−1 a.
Show that b = b−1 .
Exercise 2.46. In this exercise we give an example of an infinite Abelian group with every element
having finite order. Let G = {x ∈ Q : 0 ≤ x < 1}. (a) Prove that G is an infinite Abelian group under the operation ( a+b if 0 ≤ a + b < 1 a·b= a + b − 1 if 1 ≤ a + b < 2. (b) Prove that every element in G has finite order. Exercise 2.47. (a) Prove that the set of rational numbers Q under addition is a group. (b) Suppose H is a subgroup of Q (under addition) with the following property: 1 ∈ H for every non-zero x ∈ H. x Prove that H = {0} or H = Q. Exercise 2.48. Let G be an Abelian group and H = {x ∈ G : |x| = 2k + 1 for some k ≥ 0}. Prove that H G. Exercise 2.49. Fix an integer n ≥ 1. Suppose G is a finite group such that an bn = bn an for all a, b ∈ G. Let H = {x ∈ G : gcd(|x|, n) = 1}. Prove that H is an Abelian subgroup. Hint. First show that H is Abelian, then show its a subgroup. Note: this does not say G is Abelian when n ≥ 2. 46 3 Generators, Relations, and Cyclic Groups 3.1 Definition of Generators and Relations Recall that the integers under addition are a group, and every integer is a power of 1 under this operation, i.e., n = 1n . We say that the integers are generated by 1 under addition, and say 1 is a generator for the integers. Notice that the integers are also generated by −1 (as n = (−1)−n ). This shows that it is possible for two different elements to generate the same group. Moreover, most groups are generated by more than one element (see Dihedral Groups). In this sense, the integers are very special. We begin with the formal definition of generators. Generators Let A be a non-empty. Define hAi = {an1 1 an2 2 · · · anmm : m ∈ N, ai ∈ A, ni ∈ Z}. We call the elements of A generators, and say hAi is the set generated by A. In the previous definition, the ai ’s in an1 1 an2 2 · · · anmm need not be distinct. Combining exercises 2.26 and 3.5 proves that if A is a non-empty subset of a group G, then hAi is a subgroup of G. When A is a finite set {a1 , a2 , . . . , an }, we write ha1 , a2 , . . . , an i for the subgroup generated by A instead of h{a1 , a2 , . . . , an }i. In this course we are mostly interested in the case when A is a finite non-empty subset of a group G. Expressions of the form an1 1 an2 2 · · · anmm are called words in the elements of A. The set A can be finite or infinite (countable or uncountable). For example, if A = {a, b, c}, then some of the elements of this group are: acb, a2 b2 ca3 , ac3 b2 , abcacbcab, a2 cbcaba3 . If A is a set consisting of a single element a, then hAi = hai = {an : n ∈ Z}. Example 3.1. Find the subgroup generated by A = {12, 18} in Z. Find the subgroup h6i. Is there any relation between h12, 18i and h6i? Solution. Since Z is an Abelian group, h12, 18i = {12n + 18m : n, m ∈ Z} and h6i = {6n : n ∈ Z}. We now prove that these two sets are in fact equal. To see this, notice that 6 = 12(−1) + 18(1). So 6 ∈ h12, 18i. Since h12, 18i is a subgroup of Z (in particular, the operation is binary), we have h6i ⊆ h12, 18i. Conversely, 12, 18 ∈ h6i (as 12 = 6 × 2 and 18 = 6 × 3). Since h6i is a subgroup of Z, any integer linear combination of 12 and 18 will be in h6i. That is, h12, 18i ⊆ h6i, completing the proof. ♣ Now we turn our attention to the notion of relations. It is possible that in a group elements interact with each other in a certain way. For example, it is possible that ab = ba for two elements a and b 47 in a group G. Also, it is possible that ab2 = b2 a−1 in a group. The relations between the elements of a non-empty subset A of a group G play an important role in the subgroup they generate. If there is no relation between the elements in A, we write the subgroup generated by A as hAi (as we did above). However, if there are relations between the elements in A, we write the set generated by A as follows; hA : Ri where R is the set of relations between the ai ’s in A. For example, suppose a is an element of a group G such that |a| = 4. We write the subgroup generated by a in G as ha : |a| = 4i. When there is no confusion about the order of a, we simply write hai. If A contains more than one element and there are relations, then we always write the subgroup generated by A as hA : Ri. For example, suppose A = {a, b, c}, where |a| = 2 = |b|, |c| = 3, ab = ba, and bc = cb. We write the group generated by A as follows: ha, b, c : |a| = 2 = |b|, |c| = 3, ab = ba, bc = cbi It is then understood that the elements in this subgroup are strings (or words) consisting only of the letters a, b, and c (and any power of them) obeying the relations stated. Some of the elements of this group are: (abc2 )(cba) = abc3 ba = ab2 a = a2 = e (abac)(bac) = a2 bcbac = bcbac = b2 cac = cac (c2 ab)(cba) = c2 acb2 a = c2 aca. As mentioned in the beginning of this section, if A is a non-empty subset of a group G, combining Exercises 2.26 and 3.5 proves that hAi is a subgroup of G. We now give an alternate proof of this fact when A = {a}. hai is a subgroup Proposition 3.2. For all a ∈ G we have hai G. Proof. Since a ∈ hai, hai is not empty. Since the operation in G is binary, hai ⊆ G. Given x, y ∈ hai, then x = am and y = an for some integers m, n ∈ Z. Then, xy −1 = am (an )−1 = am−n ∈ hai. By Proposition 2.21, hai G. We now show that the order of an element in a group is the same as the order of the subgroup that element generates in the group. Theorem 3.3. Let a ∈ G. 1. If |a| = ∞ then, ai = aj if and only if i = j. 2. If |a| = n then, ai = aj if and only if n|(i − j). Moreover, hai = {e, a, a2 , a3 , . . . , an−1 }. 48 Proof. (1) Notice that |a| = ∞ is equivalent to am = e if and only if m = 0. It follows that ai = aj ⇔ ai−j = e ⇔ i − j = 0 ⇔ i = j. (2) We first prove ai = aj if and only if n|(i − j). If n|(i − j), then i − j = nk for some integer k, and ai = ank+j = ank aj = (an )k aj = eaj = aj . Conversely, if ai = aj , then ai−j = e. By Corollary 2.17, n|(i − j). From the definition we have {e, a, a2 , a3 , . . . , an−1 } ⊆ hai. Conversely, given ak ∈ hai, by the Division Algorithm there exist unique integers q and r such that k = nq + r with 0 ≤ r < n. In particular, ak = anq+r = (an )q ar = ar ∈ {e, a, a2 , a3 , . . . , an−1 }, showing that hai ⊆ {e, a, a2 , a3 , . . . , an−1 }, completing the proof. Corollary 3.4. |a| = |hai|. Proof. This follows from Theorem 3.3. Combining Corollary 3.4 and Proposition 3.2 gives |a| ≤ |G|. The subgroup hai is called the cyclic subgroup of G generated by a. For example, in Z, h2i is the set of even integers, h3i is the set of all multiples of 3, and Z = h1i = h−1i. In Z8 , h4i = {0, 4}, h2i = {0, 2, 4, 6}, and h1i = h3i = h5i = h7i = Z8 . 3.2 Cyclic Groups In this section, we turn our attention to groups which can be generated by a single element. If G = hai for some a ∈ G, we say that G is a cyclic group and a is a generator for G. To see where the name comes from, assume G = hai such that |a| = 5. By Corollary 3.4, |G| = 5. By Theorem 3.3(2), G = {e, a1 , a2 , a3 , a4 }. We can draw this group as follows; a5 a4 a1 a3 a2 49 Where a5 = e. In general, when |a| = n and G = hai, we can think of G geometrically as a cycle starting at a and going clockwise (rotating by 360/n each time), increasing the power of a one at time. The cycle completes with an = e connecting back to a. Below we draw the cycle for G = hai where |a| = 7: a6 a7 a5 a1 a4 a2 a3 If the order of a is infinite, the cycle never gets completed. The next example illustrates, a cyclic group may have many different generators. Example 3.5. Show that U (10) is cyclic and find all the elements that generate U (10). Solution. Notice that U (10) = {1, 3, 7, 9}. Moreover U (10) = h3i = h7i. Hence, U (10) is a cyclic group and 3 and 7 are generators for it. Notice that h9i = {1, 9} = 6 U (10), so 9 is not a generator for U (10). ♣ A group G is cyclic if and only if there exist an element a ∈ G such that G = hai. In particular, to show that a group is not cyclic, it suffices to show that G 6= hai for any a ∈ G. Example 3.6. U (8) is not cyclic. Solution. Notice that U (8) = {1, 3, 5, 7}, and |1| = 1, |3| = |5| = |7| = 2. Since |U (8)| = 4, we have U (8) 6= hai for any a ∈ U (8). Hence, U (8) is not cyclic. ♣ Smallest Subgroup Let H be a subgroup of a group G and A a subset of G. We say that H is the smallest subgroup of G containing A if it has the following property: (K G and A ⊆ K ⊆ H) ⇒ K = H. If H is a subgroup of G and a ∈ H, every power of a is an element of H (since the operation is binary). In particular, hai ⊆ H. This shows that hai is the smallest subgroup of G containing a (or 50 more precisely, {a}). A similar proof shows that hAi is the smallest subgroup of G containing A (see Exercise 3.5). The next few results focus on the order of elements in subgroups generated by a single element. Proposition 3.7. Suppose a ∈ G with |a| = n < ∞. Given a natural number k, hak i = hagcd(k,n) i and |ak | = n . gcd(k, n) Proof. Set d = gcd(k, n). Then k = dm for some integer m. By Proposition 1.3, there exist integers u and v such that d = ku + nv. If b ∈ hak i, there exist an integer s such that b = (ak )s = aks = adms = (ad )ms ∈ had i. Conversely, suppose b ∈ had i. Then b = (ad )z for some integer z. Therefore, b = adz = akuz+nvz = (ak )uz (an )vz = (ak )uz ∈ hak i. Hence, hak i = had i. This completes the proof of the first part of the proposition. Notice that if l|n, then (al )n/l = an = e ⇒ |al | ≤ (n/l). In particular, if i < (n/l), then (al )i 6= e (by the minimality of n, since li < n). Hence, |al | = (n/l). n Now we prove the second part of the proposition: |ak | = |hak i| = |had i| = |ad | = . d Corollary 3.8. Suppose G is a finite cyclic group of order n. Then |a| |n for all a ∈ G. Proof. Let G = hgi with n = |G| = |g|. Given a ∈ G, we have a = g k for some integer k, and by n n n = gcd(k, n). Proposition 3.7, = k = n |a| |g | gcd(k,n) The following corollary characterizes when two cyclic groups are equal. Corollary 3.9. Let |a| = n < ∞. Then, (1) hai i = haj i if and only if gcd(i, n) = gcd(j, n). (2) |ai | = |aj | if and only if gcd(i, n) = gcd(j, n). (3) hai = haj i if and only if gcd(j, n) = 1. (4) |a| = |aj | if and only if gcd(j, n) = 1. Proof. We prove (1) and (2). The proofs of (3) and (4) follow from (1) and (2), respectively (by letting i = 1). (1) Suppose gcd(i, n) = gcd(j, n). By Proposition 3.7, hai i = hagcd(i,n) i = hagcd(j,n) i = haj i. 51 Conversely, if hai i = haj i, then Corollary 3.4 and Proposition 3.7 imply that n n = |ai | = |hai i| = |haj i| = |aj | = , gcd(i, n) gcd(j, n) and the result follows. (2) By Proposition 3.7, gcd(i, n) = gcd(j, n) ⇔ n n = ⇔ |ai | = |aj |. gcd(i, n) gcd(j, n) Given n ≥ 2, Zn is a cyclic group with Zn = h1i. Since |1| = n, the preceding corollary tells us that every number relatively prime to n generates Zn . For examples, Z8 is generated by 1, 3, 5, and 7. Fundamental Theorem of Cyclic Groups Theorem 3.10. 1. Every subgroup of a cyclic group is cyclic. 2. If |hai| = n and H hai, then |H| | n. 3. Suppose |a| = n. For each k ∈ N with k|n, the group hai has exactly one subgroup of order k, namely han/k i. Notice that this theorem tells us how many subgroups a finite cyclic group has and how to find them (they correspond to the divisors of the order of the group). Proof. (1) Let G = hai for some a ∈ G and suppose H G. We show that H is cyclic. If H is the trivial subgroup, then H = {e} = hei. Suppose H 6= {e}. Then there exist a non-identity element x ∈ H. Since a is a generator for G, x = ab for some non-zero integer b. Notice that x−b ∈ H, and either b or −b > 0. Let m be the smallest positive integer such that am ∈ H (Well Ordering Principle
guarantees the existence of such an m). Since H is a subgroup of G and am ∈ H, ham i ⊆ H. Now
we show the reverse inclusion, which will complete the proof. If h ∈ H ⊆ G = hai, then h = aα for
some α ∈ Z. By the Division Algorithm, there exist unique integers q and r such that α = mq + r
with 0 ≤ r < m. Thus aα = amq+r = amq ar ⇒ ar = a−mq aα = (am )−q h ∈ H. Minimality of m implies that r = 0. Hence, α = mq ⇒ h = aα = (am )q ∈ ham i. (2) If H is a subgroup of hai, then H is cyclic and H = ham i, where m is the smallest positive integer such that am ∈ H (by part (1)). Hence, |H| = |ham i| = |am | = n ⇒ |H| |n. gcd(m, n) (3) If k|n, then han/k i hai, and |han/k i| = n n = = k. gcd(n, n/k) n/k 52 We will show that this is the only subgroup of order k. Suppose H hai with |H| = k. By part (1) H = ham i, where m is the smallest positive integer such that am ∈ H. By the Division Algorithm, there exist unique integers q and r such that n = mq + r with 0 ≤ r < m. Thus ar = a−mq an = a−mq ∈ H, and minimality of m implies that r = 0. That is, m|n. Hence, m|n ⇒ m = gcd(m, n) ⇒ k = |H| = |ham i| = |agcd(n,m) | = ⇒ m= n n = gcd(n, m) m n ⇒ H = ham i = han/k i. k Corollary 3.11. For each positive divisor k of n, the set hn/ki is the unique subgroup of Zn of order k. Moreover, these are the only subgroups of Zn . Proof. The group Zn is cyclic, and the result follows by Theorem 3.10. For example, consider the group Z15 . The subgroups of Z15 are as follows: h15/15i h15/5i h15/3i h15/1i = = = = Z15 , h3i, h5i, h0i, order 15, order 5, order 3, order 1, and these are all the subgroups of Z15 . Example 3.12. Suppose G is a finite cyclic group and has three subgroups: G itself, {e} and a subgroup of order 5. What is |G|? Solution. Let |G| = n. Since G has three distinct subgroups,... Purchase answer to see full attachment Tags: integer equivalence relation contradiction Reflexive rule symmetric rule User generated content is uploaded by users for the purposes of learning and should be used following Studypool's honor code & terms of service.