MATH3301 NUMBER THEORY AND CRYPTOGRAPHY: ASSIGNMENT 1
DUE: FRIDAY, 18/08/2023, 6:00PM.
In all the questions below, you must justify your answers.
(1) Extended Euclidean Algorithm (9 marks). Use the Extended Euclidean algorithm to find an integer solution
to each of the following equations, or explain why no such solution exists.
(a) 179x+ 57y = 1.
(b) 1111x+ 111y = 11.
(c) 81x? 12708y = 6.
(2) Reducing numbers modulo m (12 marks).
(a) Find the last digit of 3 · 711 ? 13 · 29 + 8.
(b) Reduce 217
5
modulo 5.
(c) Find the last two digits of 1! + 2! + 3! + · · ·+ 2023!, where n! = 1 · 2 · 3 · · · · · n.
(3) Divisibility (6 marks). Is 100! a square of an integer?
(4) Modular arithmetic.
(a) (5 marks) Find a digit-wise test for divisibility by 41.
(b) (5 marks) Prove that the sum of two consecutive squares of integers is congruent to 1 modulo 4.
(c) (6 marks) Find all primes p such that p+ 10 and p+ 14 are also prime.
(d) (6 marks) Find all primes p such that 2p2 + 3 and 3p2 + 8 are also prime.
(e) (8 marks) Let a, b, and c be integers satisfying a2 + b2 = c2. Prove that at least one of a, b, or c is
divisible (i) by 3; (ii) by 4; (iii) by 5.
(5) Congruence equations (12 marks). Find all congruence classes satisfying the congruence relations below, or
explain why there are no such classes.
(a) 6x ≡ 15 mod 21;
(b) 4x? 3 ≡ 2? x mod 13;
(c) 5x? 1 ≡ x? 4 mod 18.
(6) Recurrence and divisibility (24 marks). Let us consider the sequence of numbers {an} defined by the recurrence
relation:
an+1 = 2an + an?1,
with a1 = 1 and a2 = 1.
(a) Prove that an and an+1 are coprime for all n ≥ 1.
(b) For what values of n is an divisible by 3?
Hint. Start with computing an mod 3 for n = 1, 2, 3, . . . and find the pattern.
(c) Prove that an is not divisible by 5 for all n ≥ 1.
(d) Prove that an and an+3 are coprime for all n ≥ 1.
(7) Number of prime divisors (7 marks). Let c(n) be the number of distinct prime divisors of number n. For
example, c(14) = 2 (primes 2 and 7), and c(9) = 1 (prime 3).
Let us look at the pairs of integer numbers (a, b) such that c(a+ b) = c(a)+ c(b). Prove there are infinitely
many such pairs.