# MATH3301Help With ,Help With Python，Java Programming

MATH3301 NUMBER THEORY AND CRYPTOGRAPHY: ASSIGNMENT 1
DUE: FRIDAY, 18/08/2023, 6:00PM.
(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.