Home Page > > Details

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.

Contact Us(Ghostwriter Service)

- QQ：99515681
- WeChat：codinghelp
- Email：99515681@qq.com
- Work Time：8:00-23:00

- Tele9754help With ,Help With Python，C... 2023-11-23
- Comp2005jhelp With ,Help With Python，... 2023-11-23
- Help With Comp228,Help With Python，Ja... 2023-11-23
- Help With Com661,Help With Java,Python... 2023-11-23
- Help With Program,Help With Java Progr... 2023-10-10
- Help With Math36031,Help With Matlab P... 2023-10-10
- Help With Data Programming,Help With P... 2023-10-10
- Isye 6767Help With ,C/C++，Python Prog... 2023-10-10
- Comp 10183Help With ,Help With Java Pr... 2023-10-10
- Help With Program,Java Programminghelp... 2023-10-10
- Help With Elec2103,Matlab Programmingh... 2023-10-10
- Help With Prolog|Help With R Programmi... 2023-10-10
- Help With Comp3670,Python Programmingh... 2023-10-10
- Help With Python Programming|Help With... 2023-10-09
- Csc3150help With ,Help With C/C++ Prog... 2023-10-09
- Comp10002help With ,Help With C/C++ Pr... 2023-10-09
- Help With Cisc 360,Python，C/C++ Progr... 2023-10-08
- Help With Info1113,Java Programminghel... 2023-10-08
- Cmpe 330Help With ,Java，C/C++ Program... 2023-10-08
- Comp2400help With ,R Programminghelp W... 2023-10-08

Contact Us - Email：99515681@qq.com WeChat：codinghelp

© 2021 www.asgnhelp.com

Programming Assignment Help！