# MAT 301 Antonelli College Jackson Short Math Questions

Description

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.
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?
(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
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 =
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
Exercise 2.4. Is the set of the integers under the operation a · b = a − b + 1 a group? Justify your
Exercise 2.5. Let G be the set of odd integers. Is this set a group under addition? Justify your

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

a b
G=
: a, b, c, d ∈ R, ad = 0 .
c d
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
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
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
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.

## Reviews, comments, and love from our customers and community:

This page is having a slideshow that uses Javascript. Your browser either doesn't support Javascript or you have it turned off. To see this page as it is meant to appear please use a Javascript enabled browser. Peter M.
So far so good! It's safe and legit. My paper was finished on time...very excited! Sean O.N.
Experience was easy, prompt and timely. Awesome first experience with a site like this. Worked out well.Thank you. Angela M.J.
Good easy. I like the bidding because you can choose the writer and read reviews from other students Lee Y.
My writer had to change some ideas that she misunderstood. She was really nice and kind. Kelvin J.
I have used other writing websites and this by far as been way better thus far! =) Antony B.
I received an, "A". Definitely will reach out to her again and I highly recommend her. Thank you very much.  