Examiners’ commentaries 2015 Mock

Examiners’ commentary 2015 Mock

MT2116 Abstract Mathematics Mock Examination

Specific comments on questions Zone B

Candidates should answer SIX of the following EIGHT questions: THREE from Section A and
THREE from Section B. All questions carry equal marks.

Section A

Question 1

a) Let p, q and r be statements. Prove, using a truth table or otherwise, that if

S1 is the statement
(p ∨ q) ∧ (q ∨ r) ∧ (r ∨ p)
and if S2 is the statement

(p ∧ q) ∨ (q ∧ r) ∨ (r ∧ p),

then S1 and S2 are logically equivalent.

All of Question 1 builds on the material of Chapter 1 of the subject guide.
We have the following truth table.
p q r p∨q q∨r r∨p S1 p∧q q∧r r∧p S2
T T T T T T T T T T T
T T F T T T T T F F T
T F T T T T T F F T T
F T T T T T T F T F T
T F F T F T F F F F F
F T F T T F F F F F F
F F T F T T F F F F F
F F F F F F F F F F F
As can be seen from the table, the two statements S1 and S2 are logically equivalent.

b) In this part of the question, n denotes an integer and S is the following

statement.

S: If n2 − (n − 2)2 is not divisible by 8, then n is even.

(i) Write down the contrapositive of S. Prove that the contrapositive of S is
true.
(ii) Is statement S true? Why?
(iii) Write down the converse of S. Is it true? If so, prove it. If not, write down a
counterexample.
(i) The contrapositive of a statement p =⇒ q is ¬q =⇒ ¬p. So the contrapositive is:

If n is not even, then n2 − (n − 2)2 is divisible by 8.

1
MT2116 Abstract Mathematics Mock Examination

Equivalently, it is:

If n is odd, then n2 − (n − 2)2 is divisible by 8.

This is true. For, suppose that n is odd, so that, for some integer k, n = 2k + 1. We have

n2 − (n − 2)2 = n2 − (n2 − 4n + 4) = 4n − 4 = 4(n − 1) = 8k,

which is an integer multiple of 8. Therefore n2 − (n − 2)2 is divisible by 8.

(ii) Statement S is true because its contrapositive is true and any statement is logically
equivalent to its contrapositive. This is all we need to do here: there is no need to prove S is
true, since we have already proved its contrapositive is true.
(iii) The converse of a statement p =⇒ q is q =⇒ p. So the converse is:

If n is even, n2 − (n − 2)2 is not divisible by 8.

This is true. We can see this as follows. Suppose that n is even, so that n = 2k for some
integer k. Then n2 − (n − 2)2 = 4(n − 1) = 8k − 4, which has remainder 4 on division by 8,
so it is not divisible by 8.

c) Let T be the following statement:

there are infinitely many natural numbers a, b, c
solving the equation a2 + b2 = c2 .
Show that T is true by proving that there are infinitely many solutions in which,
for some x, b = x and c = x + 1.
With b = x and c = x + 1, the equation a2 + b2 = c2 is

a2 + x2 = (x + 1)2

which gives a2 = 2x + 1. So x = (a2 − 1)/2. Now, we want x to be a natural number (so

that a, b, c are all then natural numbers). Therefore, we need a2 − 1 to be even. Since
a2 − 1 = (a − 1)(a + 1), this will certainly be the case whenever a is odd, for in this case
a − 1 and a + 1 are even. So there are infinitely many solutions in natural numbers: for any
odd number a, a solution is given by

(a, b, c) = (a, x, x + 1)

where a = (a2 − 1)/2; that is,

a2 − 1 a2 + 1
 
(a, b, c) = a, , .
2 2

Question 2

a) The sequence (xn ) is defined recursively as follows: x1 = 5, x2 = 9 and, for

n ≥ 3,
xn = 2xn−1 + 3xn−2 − 4.
Prove, by induction, that the value of xn is given by the formula
 n
3 if n is even
xn =
3n + 2 if n is odd

Proof by induction is discussed in Chapter 3 of the subject guide. It is clear that the result
holds when n = 1 and n = 2. For, when n = 1, we have x1 = 5 = 31 + 2 and when n = 2, we
have x2 = 9 = 32 .

2
 Examiners’ commentaries 2015 Mock

Now we use strong induction to establish the result for all n. Suppose that n is some
positive integer and that, for all k ≤ n, we have
 k
3 if k is even
xk =
3k + 2 if k is odd

We now want to show the required result holds for xn+1 . We consider separately the case in
which n is even and the case in which it is odd.
First, suppose n is even. Then n − 1 is odd and so

xn+1 = 2xn + 3xn−1 − 4 = 2(3n ) + 3(3n−1 + 2) − 4 = 3n+1 − 4,

which is as required.
If, instead, n is odd, then n − 1 is even and

xn+1 = 2xn + 3xn−1 − 4 = 2(3n + 2) + 3(3n−1 ) − 4 = 3n+1 ,

as required.
It follows that the result is true for all n.

b) Use the method of induction to prove that the following statement is true for
all natural numbers n:
n  2
X 1
r3 = n(n + 1) .
r=1
2

The base case n = 1 is easily seen to be true since both sides of the expression are 1 in this
case. Suppose the result is true for a positive integer n, so that
n  2
X 1
r3 = n(n + 1) .
r=1
2

Then
n+1
X n
X
r3 = (n + 1)3 + r3
r=1 r=1
 2
1
= (n + 1)3 + n(n + 1)
2
1
= (n + 1)3 + n2 (n + 1)2
4
1
(n + 1)2 4(n + 1) + n2
 
=
4
1
(n + 1)2 n2 + 4n + 4
 
=
4
1
= (n + 1)2 (n + 2)2
4
 2
1
= (n + 1)((n + 1) + 1) ,
2

which establishes that the result is true for n + 1. By induction, therefore, the result holds
for all n.

c) Let the relation R be defined on the set of integers by: aRb if and only if
a2 ≡ b2 (mod 5). Prove that R is an equivalence relation. How many equivalence
classes are there?
Equivalence relations are discussed in Chapter 5 of the subject guide. Recall what it means
to say that a relation R on a set A is an equivalence relation. It means three things:
R is reflexive: for all x ∈ A, x R x.

3
MT2116 Abstract Mathematics Mock Examination

R is symmetric: for all x, y ∈ A, x R y implies y R x .

R is transitive: for all x, y, z ∈ A, whenever x R y and y R z, we also have x R z; that is,
(x R y) ∧ (y R z) =⇒ xRz.
Since, for any x, x2 ≡ x2 (mod 5), it follows that xRx and hence R is reflexive.
If we have xRy then x2 ≡ y 2 (mod 5) and so y 2 ≡ x2 (mod 5), showing that yRx and that R
is symmetric.
Suppose that x R y and y R z. Then x2 ≡ y 2 (mod 5) and y 2 ≡ z 2 (mod 5), so
x2 ≡ z 2 (mod 5), which means that xRz. Hence R is transitive.
To determine the equivalence classes, we simply need to consider the different possible
values of a2 modulo 5 as a runs through the numbers 0, 1, 2, 3, 4. The values of a2 (modulo
5) are 0, 1, 4, 9 ≡ 4, 16 ≡ 1. So there are three equivalence classes: these are
{x : x ≡ 0}, {x : x ≡ 1 or x ≡ 4}, {x : x ≡ 2 or x ≡ 3},
where the congruences are all modulo 5.

Question 3

a) Find the greatest common divisor of 2009 and 615, and express it in the form
2009x + 615y for integers x and y.
This is a standard, easy, question. We use the Euclidean Algorithm (of Chapter 6 of the
subject guide).
We use the Euclidean Algorithm. To find gcd(2009, 615), we consecutively find divisors and
remainders as follows :
2009 = 3 × 615 + 164;
615 = 3 × 164 + 123;
164 = 1 × 123 + 41;
123 = 3 × 41 + 0.
As the final line ends in 0, we have found the greatest common divisor: gcd(2009, 615) = 41.
Going backwards through the steps in the algorithm, we see
41 = 164 − 123
= 164 − (615 − 3 × 164) = 4 × 164 − 615
= 4 × (2009 − 3 × 615) − 615 = 4 × 2009 − 13 × 615.
In summary: 41 = 4 × 2009 − 13 × 615; in other words, x = 4 and y = −13.
This is not the only possible solution. In general, if (x, y) is a solution to xa + yb = d, then
so is (x − kb, y + ka) for any integer k.

b) Find all solutions in Z6 to the following system of equations:

2x + y = 2
x + 2y = 4.

The relevant background material can be found in Chapter 7 of the subject guide.
Multiplying the second equation by 2 gives 2 x + 4 y = 8 = 2 in Z6 . Subtracting the first
equation from this leads to 3 y = 0.
It is very tempting to conclude immediately that this must mean y = 0. But remember that
we can’t just “cancel the 3” in 3 × y = 3 × 0. This has solutions y = 0, y = 2 and y = 4.
Substituting y = 0 in the original second equation gives x + 0 = 4, hence x = 4 in Z6 . In the
same way we find that for y = 2 we must take x = 0. And for y = 4 we have x + 8 = 4,
hence x = −4 = 2 in Z6 .
So all possible solutions are x = 4, y = 0; x = 0, y = 2; and x = 2, y = 4. In fact, we only
know for sure that these values satisfy the second equation ( that is how we found the
x-values ); we also must check these pairs in the first equation. They do indeed all work.

4
 Examiners’ commentaries 2015 Mock

c) Suppose that a, b ∈ N and that a > b. Let d = gcd(a, b) and D = gcd(a + b, a − b).
Prove that d | D and D | 2d.
(You may use the fact that for any m, n ∈ Z, there are integers x, y such that
mx + ny = gcd(m, n).)
Hence show that D = d or D = 2d.
Show, with specific values of a, b, that it is possible to have D = d and it is also
possible to have D = 2d.
The relevant background material can be found in Chapter 6 of the subject guide. This is
quite a challenging question, and it is a good idea to make use of the hint given in the
question, namely the fact that for any m, n ∈ Z, there are integers x, y such that
mx + ny = gcd(m, n).
There are integers x, y, z, t such that

d = ax + by, D = (a + b)z + (a − b)t.

Since d | a and d | b, we have d | (a + b) and d | (a − b). So d | D = (a + b)z + (a − b)t. Also,

D | (a + b) and D | (a − b), so D | ((a + b) + (a − b)) = 2a and D | ((a + b) − (a − b)) = 2b.
So, since 2d = (2a)x + (2b)y, we have D | 2d.
Since d | D and D | 2d, there are positive integers k, l such that D = kd and 2d = lD. But
this means 2D = k(2d) = klD, so kl = 2. So, either k = 1 and l = 2 (in which case D = d)
or k = 2 and l = 1 (in which case D = 2d).
We have, for instance, gcd(2 + 1, 2 − 1) = 1 = gcd(2, 1) and gcd(3 + 1, 3 − 1) = 2 = 2 gcd(3, 1).

Question 4

a) Express the recurring decimal 0.10765 as a rational number p/q, where p and q
are integers.
See Chapter 8 of the subject guide for a discussion of how to solve questions like this. Let’s
write 0.10765 = 0.1 + x, where x = 0.00765 is the repeating part. We should see
immediately that 0.1 = 1/10. For x we write 1000 x = 7.65765, hence
765
999 x = 1000 x − x = 7.65765 − 0.00765 = 7.65 = .
100
This leads to
765 765
x= = .
100 × 999 99900
And so we obtain
1 765 9990 + 765 10755
0.10765 = 0.1 + 0.00765 = + = = .
10 99900 99900 99900

b) DeMoivre’s formula tells us that

(cos θ + i sin θ)3 = cos(3θ) + i sin(3θ).

By expanding the left hand-side of this equation, and by using sin2 θ + cos2 θ = 1,
prove that
cos(3θ) = 4 cos3 θ − 3 cos θ.
(Here, as usual, i is the complex number satisfying i2 = −1.)
For this, and the next, part of the question, see the discussion of complex numbers in
Chapter 8 of the subject guide.
By DeMoivre’s theorem,

(cos θ + i sin θ)3 = cos(3θ) + i sin(3θ).

5
MT2116 Abstract Mathematics Mock Examination

Now,

(cos θ + i sin θ)3

= (cos θ)3 + 3(cos θ)2 (i sin θ) + 3 cos θ(i sin θ)2 + (i sin θ)3
= cos3 θ + 3i cos2 θ sin θ + 3i2 cos θ sin2 θ + i3 sin3 θ
= cos3 θ + 3i cos2 θ sin θ − 3 cos θ sin2 θ − i sin3 θ
= (cos3 θ − 3 cos θ sin2 θ) + i(3 cos2 θ sin θ − sin3 θ).

So, equating the real parts,

cos(3θ) = cos3 θ − 3 cos θ sin2 θ = cos3 θ − 3 cos θ(1 − cos2 θ) = 4 cos3 θ − 3 cos θ.

c) Consider the polynomial P (z) = z 4 + z 2 − 2z + 6.

Show that z = 1 + i is a solution of P (z) = 0.
Hence find all the solutions of P (z) = 0. (State clearly any results you use.)
To verify that z = 1 + i is a root, we simply need to evaluate P (1 + i). For this, note that
(1 + i)2 = 2i and that (1 + i)4 = (2i)2 = −4. Now we can check that

P (1 + i) = (1 + i)4 + (1 + i)2 − 2(1 + i) + 6 = −4 + 2i − 2 − 2i + 6 = 0.

The polynomial P (z) has degree 4, so it will have 4 complex roots ( possibly including
repeated roots ). We are given one of them for free, but actually we know even more: as
P (z) is a real-coefficient polynomial, the complex roots come in conjugate pairs, and
therefore z = 1 + i = 1 − i is also a root of P (z).
We know that z − (1 + i) and z − (1 − i) are both factors of P (z). The next step is to divide
these out, i.e., to find a polynomial Q(z) with P (z) = [z − (1 + i)][z − (1 − i)]Q(z). For this,
it makes things much easier if you first calculate that
[z − (1 + i)][z − (1 − i)] = (z − 1)2 + 1 = z 2 − 2z + 2. This is a real-coefficient polynomial
( which, as you can probably see, is not an accident ). We can find Q(z) by a process of long
division: Q(z) = z 2 + 2z + 3. Alternatively, we can see that if Q(z) = az 2 + bz + c then,
because we need
z 4 + z 2 − 2z + 6 = (z 2 − 2z + 2)(az 2 + bz + c),
we must have a = 1 and c = 3 and then, looking at the z 3 terms, 0 = b − 2a, so b = 2a = 2.
√ √
We find the roots of Q(z) using the quadratic formula: z = −1 + i 2 and z = −1 − i 2.

Question 5

a) What does it mean to say that a sequence (an ) is convergent ? Use this
definition to show that if an → L, then an+1 → L.
See Chapter 10 of the subject guide for the background material to this part of the question.
A sequence (an )n≥1 is convergent if there is L ∈ R so that for every  > 0 there is N such
that for all n > N we have |an − L| < . Suppose that n > N 0 = N − 1. Then n + 1 > N
and |an+1 − L| < . Therefore, (an+1 )n≥1 is also convergent and lim an = lim an+1 = L.
n→∞ n→∞

b) Let b ∈ (2, 3) be arbitrary but fixed number. We define a sequence (bn ) by

b1 = b, and
bn+1 = b2n − 4bn + 6 for every n ∈ N.

Show that 2 < bn < 3 for every n ∈ N.

Prove that (bn ) is a monotonic sequence.

6
 Examiners’ commentaries 2015 Mock

Explain why lim bn exists and find its value.

n→∞
Let S = {bn | n ∈ N}. Find sup S, inf S, max S, min S. Justify your answers !
We proceed by induction on n. For n = 1, we have 2 < b = b1 < 3. Suppose that. for n = k,
we have 2 < bk < 3. Then, for n = k + 1, we obtain

bk+1 − 2 = b2k − 4bk + 4 = (bk − 2)2 > 0,

as bk > 2. Hence, bk+1 > 2. Similarly,

3 − bk+1 = 3 − (b2k − 4bk + 6) = −b2k + 4bk − 3 = (3 − bk )(bk − 1) > 0,

as 3 > bk > 2. Hence, bk+1 < 3.

Next, for all natural numbers n, we have

bn+1 − bn = b2n − 4bn + 6 − bn = b2n − 5bn + 6 = (bn − 2)(bn − 3).

From the above, we have bn − 2 > 0 and bn − 3 < 0, hence bn+1 − bn < 0 and (bn )n≥1 is a
decreasing sequence.
The above analysis shows that (bn ) is a bounded, monotone sequence. Therefore, by a
standard theorem from the course (Theorem 10.9 in the subject guide), its limit
lim bn = B exists. By part (a) of this question, lim bn+1 = B as well. Hence
n→∞ n→∞

B = lim bn+1 = lim b2n − 4bn + 6 = B 2 − 4B + 6,

n→∞ n→∞

where we have applied the known results about the algebra of limits. The above quadratic
equation has solutions B = 2 and B = 3.
However, since (bn )n≥1 is a decreasing sequence, we have bn ≤ bn−1 ≤ · · · ≤ b1 = b < 3 for
all natural numbers n. We know that in this case, B = lim bn ≤ b < 3. Hence B = 2.
n→∞
max S = sup S = b1 = b, inf S = B = 2, and min S does not exist because 2 < bn for all
n ∈ N and, therefore, inf S = 2 6∈ S.

Question 6

a) What does it mean that a function f : R → R is continuous at a point c ∈ R ?

What does it mean that a function f : R → R is continuous on the interval
[a, b] ⊂ R ? State the Intermediate Value Theorem.
See Chapter 11 of the subject guide for background material on limits of functions and
continuity.
A function f : R → R is continuous at a point c ∈ R if for every  > 0 there exists δ > 0 such
that for every x, |x − c| < δ, we have |f (x) − f (c)| < . A function f : R → R is continuous
on the interval [a, b] ⊂ R if it is continuous at c for every c ∈ (a, b), lim+ f (x) = f (a) and
x→a
lim f (x) = f (b).
x→b−
The Intermediate Value Theorem states the following: Let f be a function continuous on
[a, b]. Suppose that y is such that f (a) < y < f (b). Then there exists c ∈ [a, b] so that
f (c) = y.

b) Suppose that a function f : R → R is positive and continuous on R. Suppose

that there exists two real numbers x and y such that
4
f (x) = .
f (y)

Prove that there exists c ∈ R such that f (c) = 2.

7
MT2116 Abstract Mathematics Mock Examination

Suppose there exist two real numbers x and y such that

4
f (x) = , that is, f (x)f (y) = 4.
f (y)

If x = y, then f (x)2 = 4 and, since f is positive on R, we get f (x) = 2.

By symmetry, we may assume x < y. If f (x) = 2, we are done. Assume that f (x) < 2, then
f (y) = 4/f (x) > 4/2 = 2. f is continuous on [x, y] and f (x) < 2 < f (y). By the
Intermediate Value Theorem, there is c ∈ [x, y] so that f (c) = 2. The case when f (x) > 2 is
handled in the same way.

c) Let f : R → R be a function such that f (x) tends to infinity as x tends to 1.

Suppose that g : R → R is a function such that g(x) > 1/2011 for every x ∈ R.
Prove that f (x)g(x) tends to infinity as x tends to 1.
f (x) → ∞ as x → 1 means that for every K there exists δ > 0 such that

0 < |x − 1| < δ ⇒ f (x) > K.

For a given K, let δ > 0 be such that

0 < |x − 1| < δ ⇒ f (x) > 2011K.

Then, for 0 < |x − 1| < δ,

1
f (x)g(x) > 2011K · = K.
2011
Hence, f (x)g(x) → ∞ as x → 1.

Question 7

a) Let S = {q ∈ Q | q 6= 1}. For two rational numbers a, b ∈ Q we define

a ∗ b = a + b − ab.
Show that (S, ∗) is a group.
Recall, from Chapter 12 of the subject guide, that (S, ∗) is a group if and only if the
following properties hold:
∀x, y ∈ S, x ∗ y ∈ S [closure property]
∀x, y, z ∈ S, (x ∗ y) ∗ z = x ∗ (y ∗ z) [associativity property]
∃e ∈ S such that ∀x ∈ S, e ∗ x = x ∗ e = x [identity property]
∀x ∈ S, ∃x−1 ∈ S such that x ∗ x−1 = x−1 ∗ x = e [inverse property]
First, we establish closure. For any two rational numbers a and b, a ∗ b = a + b − ab is also a
rational number, therefore, we only need to show that if a, b ∈ S, then a ∗ b 6= 1.
To the contrary, suppose that
a ∗ b = a + b − ab = 1
for some a, b ∈ S. But then 0 = a + b − ab − 1 = (a − 1)(1 − b), which is a contradiction
because a, b 6= 1 (see the definition of S). A number of candidates overlooked the fact that
to show a ∗ b ∈ S, we need to show not only that it is rational, but that it is not equal to 1.
Next, we prove associativity. For every a, b, c ∈ S, we have

(a ∗ b) ∗ c = (a ∗ b) + c − (a ∗ b)c
= a + b − ab + c − (a + b − ab)c
= a + b + c − ab − ac − bc + abc

8
 Examiners’ commentaries 2015 Mock

and

a ∗ (b ∗ c) = a ∗ (b + c − bc)
= a + (b + c − bc) − a(b + c − bc)
= a + b + c − ab − ac − bc + abc.

Hence (a ∗ b) ∗ c = a ∗ (b ∗ c).
Next, we show that there is an identity. 0 ∈ S is an identity element because for all a ∈ S,

a ∗ 0 = a + 0 − a0 = a + 0 − 0 = a

and
0 ∗ a = 0 + a − 0a = 0 + a − 0 = a.
−a
Next, we show that inverses exist. Note first that for every a ∈ S, 1−a 6= 1 and, thus,
−a
1−a ∈ S.
Second,

−a −a −a −a + a(1 − a) + a2
∗a = +a− ·a=
1−a 1−a 1−a 1−a
−a + a − a2 + a2
= =0
1−a
and
−a −a −a a(1 − a) − a + a2
a∗ = a+ −a· =
1−a 1−a 1−a 1−a
a − a2 − a + a2
= = 0.
1−a
−a −a
Consequently, a ∗ 1−a =0= 1−a ∗ a.
(You might well ask where we got −a/(1 − a) from. Well, we’re looking for an inverse b to a,
so we must have a ∗ b = 0, because 0 is the identity. That means a + b − ab = 0 which, if we
solve for b, gives exactly b = −a/(1 − a). So we can know what the inverse will be working
backwards in this way.)

b) Consider a group (G, ·). Prove that for any two elements a, b of G, the
equation x · a = b has exactly one solution.
Clearly (b · a−1 ) · a = b · (a−1 · a) = b · e = b, and so x = b · a−1 is a solution to x · a = b.
If there are two solutions, say x1 and x2 , then x1 · a = b = x2 · a. Hence

x1 = x1 · e = x1 · (a · a−1 ) = (x1 · a) · a−1 = (x2 · a) · a−1 = x2 · (a · a−1 ) = x2 · e = x2 .

It follows that x1 = x2 . Hence x · a = b has the unique solution x = b · a−1 .

c) Let (G, ?) be an Abelian group. Prove that the set H = {g 3 | g ∈ G} is a

subgroup of G.
Subgroups are discussed in Chapter 13 of the subject guide. H is a subgroup of G if it is
nonempty and
(1) x, y ∈ H =⇒ xy ∈ H, and
(2) x ∈ H =⇒ x−1 ∈ H.
We have, e = e3 and e ∈ G, so H is nonempty.
If G is Abelian, then a ? b = b ? a. We notice that
(a ? b)2 = (a ? b) ? (b ? a) = a ? (b ? b) ? a = a ? (b2 ? a) = (a ? a) ? b2 = a2 ? b2 .
Hence, (a ? b)3 = (a ? b)2 ? (b ? a) = (a2 ? b2 ) ? (b ? a) = a2 ? (b2 ? b) ? a = a2 ? (b3 ? a) =
a2 ? (a ? b3 ) = (a2 ? a) ? b3 = a3 ? b3 .

9
MT2116 Abstract Mathematics Mock Examination

Hence, if a3 , b3 ∈ H for some a, b ∈ G, then a3 ? b3 = (a ? b)3 ∈ H because a ? b ∈ G.

If a3 ∈ H for some a ∈ G, then (a3 )−1 = a−3 = (a−1 )3 and (a3 )−1 ∈ H because a−1 ∈ G.
Hence a−1 ∈ H.
It follows that H is indeed a subgroup.

Question 8

a) Suppose that (G, ?) and (H, ◦) are groups. What is meant by a

homomorphism θ : G → H ? Define the kernel ker θ of θ.
Given that θ : G → H is a homomorphism, prove that, for every a ∈ G and for
every n ∈ N, θ(an ) = θ(a)n .
See Chapter 14 of the subject guide for relevant material.
A mapping θ : G → H is a homomorphism if for every a, b ∈ G, we have θ(a ? b) = θ(a) ◦ θ(b).
The kernel of θ is defined by ker θ = {a ∈ G | θ(a) = eH }, where eH is the identity element
of H.
For the next part, we proceed by induction: For n = 1, we have θ(a1 ) = θ(a) = θ(a)1 .
Then, making the inductive assumption that θ(an ) = θ(a)n , we have

θ(an+1 ) = θ(an ? a) = θ(an ) ◦ θ(a) = θ(a)n ◦ θ(a) = θ(a)n+1 .

The result follows.

b) What is meant by the order of a group element in a group (G, ?) ?

Let (G, ?) and (H, ◦) be finite groups. Suppose that e is the identity element for
G and that θ : G → H is a homomorphism such that ker θ = {e}. Prove that for
every element a ∈ G, a and θ(a) have the same order.
Let (G, ?) be a group with identity e. We say that a ∈ G has finite order if there is a natural
number n such that an = e. Otherwise, we say that a has infinite order. If a has a finite
order, the order of a is min{n ∈ N|an = e}. (See Chapter 13 of the subject guide.)
As G, H are finite, we know that, for any a ∈ G, both a and θ(a) have finite orders. Let n
be the order of a in G and m be the order of θ(a) in H.
By part (a), we have
θ(a)n = θ(an ) = θ(e) = eH .
Here we used the fact that any homomorphism from G to H maps the identity in G to the
identity in H. Hence, m ≤ n.
We also have
θ(e) = eH = θ(a)m = θ(am ).
Thus am ∈ ker θ. Since ker θ = {e}, we must have e = am . Hence, n ≤ m.

c) State Lagrange’s theorem.

Let G be a finite group of order n > 2. Prove that G cannot have a subgroup of
order n − 1.
Lagrange’s Theorem (see Chapter 14 of the subject guide) says the following. Let G be a
finite group, and let H be a subgroup of G. Then |H| divides |G|.
If |G| = n > 2 and H is a subgroup of G such that |H| = n − 1, then, by the above theorem,
then n − 1 divides n. However, for n > 2,

n − 1 < n < 2(n − 1),

hence, this is impossible.

10