MATH10101 Foundations of Pure Mathematics A
Mock assessment
1. (i) Write down the negation of the statement
∀n ∈ Z, if 3n+ 2 is odd , then n is odd .
Prove that the statement is true.
(ii) Use mathematical induction to prove that for all n ∈ N, 3 divides
4n + 2.
(10 marks)
2. (i) Let A,B,C and D be sets. Prove that
(A\C)× (B\D) ⊆ (A×B)\(C ×D).
Give an example where (A\C)× (B\D) 6= (A×B)\(C ×D).
(In this question you may assume that if S = ∅ or T = ∅, then
S × T = ∅.)
(ii) Let A be a denumerable set and f : R → A be a function. Prove
that f is not injective.
(10 marks)
3. (i) Let f : N → N be defined by f(n) = n2 − n + 1. Show that f is
injective. Is f surjective? Explain your answer.
(ii) Explain why the set of even integers and the set {k2 : k ∈ Z} are
equipotent. (You may state without proof any results from the lecture
notes.)
(10 marks)
4. (i) Let R be a relation defined on a set X. We define Rc to be the
relation where
xRcy ⇐⇒ (x, y) /∈ R.
Prove that R is symmetric =⇒ Rc is symmetric.
(ii) If R is an equivalence relation, must Rc be an equivalence relation?
Give a proof or counterexample. If you give a counterexample, also
determine whether Rc is reflexive, symmetric, or transitive for your
counterexample.
(10 marks)
5. (i) Let p be a prime. Prove that if x2 ≡ 1 mod p then either x ≡ 1
mod p or x ≡ −1 mod p. You may use results from the course
provided they are explicitly stated.
(ii) Let p be a prime. How many congruence classes [x]p are there such
that [x2]p = [1]p?
(iii) Let m ≥ 2 be an integer. If x2 ≡ 1 mod m must x ≡ ±1 mod m?
Give a proof or counterexample.
(10 marks)
6. (i) Find all solutions x ∈ Z to the linear congruence
7x ≡ 21 mod 42,
by reducing the problem to a linear Diophantine equation in two un-
knowns. You may use results from the course provided they are ex-
plicitly stated.
(ii) Find a multiplicative inverse for 5 modulo 42, you do not need to
explain your method.
(iii) Hence or otherwise find all x ∈ Z such that
5x ≡ 21 mod 42.
(10 marks)
7. (i) Let n ≥ 2 be an integer. Show that
φ(n2)
n
= φ(n),
where φ is Euler’s phi-function. You may use results from the course
provided they are explicitly stated, including the formula for φ(n).
(ii) Is there an integer n with φ(n) = 11? Justify your answer.
(10 marks)
8. (i) Use Fermat’s Little Theorem or Euler’s Theorem to calculate the
remainder of 1012 on division by 7.
(ii) Calculate the remainder of 1012 on division by 28, showing your work-
ing.
(10 marks)
Solutions
1. (i) The negation is ∃n ∈ Z, 3n+ 2 is odd and n is even. (1 mark)
We prove the original statement using proof by contradiction. Assume
the negation is true. Since n is even we can write n = 2k for some
k ∈ Z. Then 3n+2 = 6k+2 = 2(3k+1) is even because 3k+1 ∈ Z.
This contradicts our assumption that 3n + 2 is odd. Therefore the
statement is true. (4 marks)
(ii) Let P (n) be the statement 3 divides 4n + 2.
Base case: P (1) is true because 3 divides 41 + 2 = 6.
Inductive step: Let k ∈ N and assume P (k) is true, ie. 3 divides
4k + 2. Then 4k + 2 = 3m for some m ∈ Z. We have 4k+1 + 2 =
4.4k + 2 = 4(3m − 2) + 2 = 3(4m − 2) and this is divisible by 3
because 4m− 2 ∈ Z. Therefore P (k + 1) is true.
By induction, P (n) is true for all n ∈ N. (5 marks)
2. (i) Let (x, y) ∈ (A\C) × (B\D). Then x ∈ A\C and y ∈ B\D.
Therefore (x, y) ∈ A × B and (x, y) /∈ C × D. Hence (x, y) ∈
(A×B)\(C ×D) and (A\C)× (B\D) ⊆ (A×B)\(C ×D).
(5 marks)
If A = {1, 2}, B = {3, 4}, C = {1}, D = {3} we have
(A\C)×(B\D) = {(2, 4)},(A×B)\(C×D) = {(1, 4), (2, 3), (2, 4)}.
(1 mark)
(ii) Let A be a denumerable set and f : R → A be a function. Assume
that f is injective. Let g : R → Imf be defined by g(x) = f(x)
for all x ∈ R. Then g is surjective and injective and so g is a
bijection. Therefore R is equipotent with the image of f . Since
A is denumerable Imf is countable. his contradicts the fact that R
is uncountable. Therefore f is not injective. (4 marks)
3. (i) Assume n,m ∈ N. We have
f(n) = f(m)
⇒ n2 − n+ 1 = m2 −m+ 1
⇒ n2 −m2 = n−m
⇒ (n−m)(n+m) = n−m.
Therefore n = m or n + m = 1. Since n,m ∈ N we can’t have
n+m = 1. Hence n = m and f is injective. (4 marks)
We can see that f is not surjective because f(1) = 1, f(2) = 3 and
f(n) > n2 + 1 > 4 for all n > 2. Therefore 2 is not in the image of
f . (2 marks)
(ii) To show the sets are equipotent we need to find a bijection between
them. Let A = {2k : k ∈ Z} and B = {k2 : k ∈ Z}. A and B are
infinite subsets of the denumerable set Z and therefore they are both
denumerable. Hence there exist bijections f : N→ A and g : N→ B.
The inverse of f is also a bijection. The map g ◦ f−1 : A → B is
the composite of two bijections and therefore it is a bijection. By
definition A and B are equipotent. (4 marks)
4. (i) We need to show xRcy =⇒ yRcx. So assuming xRcy we have
(x, y) /∈ R by definition. SinceR is symmetric we must have (y, x) /∈
R. Then by definition we have yRcx, as required. (5 marks)
(ii) A counterexample is when R is the equivalence relation = on Z.
Then Rc is precisely the relation 6=. Now 1 = 1 and so we do not
have 1 6= 1, so 6= is not reflexive. We have already shown that 6= is
symmetric because = is. Finally, 6= is not transitive because 1 6= 2,
2 6= 1, but it is not the case that 1 6= 1. (5 marks)
5. (i) We observe x2 − 1 ≡ 0 mod p and therefore p divides x2 − 1 =
(x− 1)(x+1). Euclid’s property of primes states that if p divides ab
then either p divides a or p divides b. Therefore p divides (x− 1) or
p divides (x+1). Therefore x− 1 ≡ 0 mod p or x+1 ≡ 0 mod p.
Rearranging these congruences, we obtain the result required. (5
marks)
(ii) If p = 2 then there is only one congruence class namely [1]2. If p ≥ 3
is prime then there are two congruence classes [1]p and [−1]p by the
previous part. (2 marks)
(iii) A counterexample is m = 8 and x = 3, we observe that x2 = 9 ≡ 1
mod 8 but x is not congruence to either 1 or −1. (3 marks)
6. (i) We have 7x ≡ 21 mod 42 if and only if 7x + 42k = 21 for some
k ∈ Z, so this is the linear Diophantine equation we wish to solve.
We may divide throughout by 7 and obtain x+ 6k = 3. A particular
solution is (3, 0). The greatest common divisor of 1 and 6 is 1.
We may now use the theorem from the course that states that if a
particular solution to ax+bk = c is (x0, k0) then the general solution
to ax+ bk = c is
(x0 +
b
gcd(a, b)
t, k0 − a
gcd(a, b)
t).
Hence the general solution for our equation is (3 + 6t,−t), and so
x = 3 + 6t, t ∈ Z, is the solution. (6 marks)
(ii) 17 is a multiplicative inverse for 5 modulo 42, remember to actually
check this (1 mark)
(iii) Multiplying the congruence 5x ≡ 21 mod 42 by 17 we obtain x ≡
17 × 21 mod 42. We observe that 17 × 21 = 357, which has re-
mainder 21 on division by 42, hence x ≡ 21 mod 42. Therefore the
integers x satisfying the linear congruence are x = 21 + 42t, t ∈ Z.
(3 marks)
7. (i) The first result we need is that any integer n ≥ 2 can be written as a
product of primes. We can write this in the following equivalent way.
We have
n =
k∏
i=1
prii ,
where each ri ≥ 1 and the p1, . . . , pk are distinct primes. Then it is
clear that
n2 =
k∏
i=1
p2rii .
Another result we need from the course is that
φ(n) = φ(
k∏
i=1
prii ) =
k∏
i=1
(pi − 1)pri−1i ,
we may also use this formula for φ(n2), observe:
φ(n2) = φ(
k∏
i=1
p2rii ) =
k∏
i=1
(pi − 1)p2ri−1i .
At this point we divide φ(n2) by n, express this in terms of primes,
then we observe that it is equal to φ(n) (actually write it out and
check this in an exam). (5 marks)
(ii) If
φ(n) = φ(
k∏
i=1
prii ) =
k∏
i=1
(pi − 1)pri−1i = 11,
then since 11 is prime, precisely one of the (pi−1)pri−1i terms is equal
to 11. Now 11 is prime therefore either (pi − 1) = 11 or pri−1i = 11.
Now we rule out each case by a contradiction. If (pi − 1) = 11 then
pi = 12, which isn’t prime, a contradiction. If p
ri−1
i = 11 then ri = 2
and pi = 11, but then φ(n) will be divisible by φ(11
2) = 10 × 11,
which is too large to be 11, which is again a contradiction. The
conclusion is that there is no integer with φ(n) = 11. (5 marks)
8. (i) 7 is prime and so Fermat’s Little Theorem will tell us that when 7
does not divide n then n7−1 = n6 will be congruent to 1 modulo 7.
Therefore 1012 = 1006 will have remainder 1 on division by 7, because
7 does not divide 100. (5 marks)
(ii) (We cannot use Fermat because 28 is not prime, and we cannot use
Euler because 10 is not coprime to 28.) We can use the method of
successive squaring. 102 = 100 ≡ 16 mod 28, 104 ≡ 162 = 256 ≡
−24 ≡ 4 mod 28, 108 ≡ 42 = 16 mod 28. Thus 1012 ≡ 4× 16 =
64 ≡ 8 mod 28. (5 marks)