NUMBER THEORY AND CRYPTOGRAPHY 2023: ASSIGNMENT 2
DUE FRIDAY 1 SEPTEMBER AT 6 PM
The total number of marks is counted by the formula min(total mark, 100), i.e. you cannot
get more than 100 marks. The challenge question is a bonus question which allows you to get
extra marks. You must justify all your answers below.
(1) An Application of Number Theory to magpies counting (6 marks). There are many
magpies nesting on a huge gum tree in the middle of Limestone Avenue. Every time
a group of cyclists passes by, all the magpies split into teams of the same size, so that
each cyclist is swooped by exactly one team. Any remaining magpies stay on the tree
and observe.
When a group of 15 cyclists passed by, there were 6 birds remaining on the tree.
When a group of 16 cyclists passed by, 7 birds stayed on the tree. When a group of
17 cyclists passed by, only one bird stayed on the tree. What is the total number of
magpies nesting on the gum tree if it is known that there should be less than 2000?
(2) System of congruence relations (20 marks).
(a) (6 marks) Find the least positive even integer a such that a+ 1 is divisible by 3,
a+ 2 is divisible by 5, and a+ 3 is divisible by 7.
(b) (3 marks) Prove that [5]63 is a unique congruence class modulo 63 which solves
the system of equations:
{
x ≡ 5 mod 7
x ≡ 5 mod 9.
(c) (4 marks) Let a and b be coprime positive integers. Prove that x ≡ 1 mod ab if
and only if x ≡ 1 mod a and x ≡ 1 mod b.
(d) (7 marks) Find 744 + 1066 mod 70.
Hint. Think of Euler’s function φ.
(3) Life without a calculator (28 marks). Carry out the following calculations by hand.
You must show your work to receive full credit.
(a) Reduce 303! mod 307.
(b) Reduce (45!)(57!) mod 101.
(c) Reduce 72023 mod 23.
(d) Determine the last 3 digits of 997907807.
(4) A curious congruence (16 marks).
(a) Prove that for all positive integers n, n5 − n is a multiple of 30.
(b) Prove that for all positive integers n, 202n + 162n − 32n − 1 is a multiple of 323.
(5) Euler’s function and r.r.s (16 marks).
(a) (3 marks) Find all positive integers a such that φ(7a) = 294.
(b) (3 marks) Find all integer a and b such that φ(3a5b) = 600.
1
2(c) (5 marks) Find all positive integers n such that φ(n) = 2.
Hint. Prove first that n should be of the form 2a3b with a, b ≥ 0. Then find the
possible values of a and b.
(d) (5 marks) Let n be a positive integer such that the set {1, 5} is an r.r.s. modulo
n. Find all the possible values of n.
(6) Diophantine equations (14 marks). In this question, we will prove that the equation
6x2 + 5x+ 1 = 0
has no integer solutions whereas the congruence relation
6x2 + 5x+ 1 ≡ 0 mod m
has a solution for all positive integers m.
(a) (2 marks) Prove that the equation 6x2 + 5x+ 1 = 0 has no integer solutions.
(b) (3 mark) Prove that the equation 2x + 1 ≡ 0 mod m has a solution for all odd
positive integers m.
(c) (3 mark) Prove that the equation 3x+1 ≡ 0 mod m has a solution for all positive
integers m of the form m = 2k, k a positive integer.
(d) (6 marks) Prove that the equation 6x2+5x+1 ≡ 0 mod m has a solution for all
positive integers m.
Hint. Use that m can be written as a product 2k ·m′ where k ≥ 0 and m′ is an
odd number; conclude by using the Chinese Remainder Theorem.
(7) A challenge question for extra 6 marks. Assume we try to send a message which
consists of n2 digits, which are 0s and 1s. Let us write it in the form of the square
table n × n. Let us add to each row one more entry with a sum of all numbers in
this row modulo 2. We will get an extra column of size n. For example, if our initial
message is the following table of size 2× 2,
0 1
1 1
then we get the additional row on the right as follows.
0 1 1
1 1 0
Now we have n rows and n+ 1 columns. Similarly, we will add one entry below to
each of the n + 1 columns with the sum of numbers in this column modulo 2. In our
example, we will get
0 1 1
1 1 0
1 0 1
Prove that if there arises one error while transmitting the table (n+1)× (n+1) as
a message, it will be possible to detect it and correct it.