Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit


MATH 135 Fall 2021: Written Assignment 6


Q1. (5 marks)

(a) (3 marks) Use the Extended Euclidean Algorithm to find integers x, y and d = gcd(3366, 1785) such that

(b) (2 marks) Find integers s and t such that 3366s − 1785t = gcd(3366, −1785). Show your work.


Q2. (5 marks) Prove that, for all integers a, b and c, gcd(a, b) | gcd(a, bc).


Q3. (5 marks) A positive integer s is called squarefree if the only perfect square that divides s is 1.

Prove that every positive integer n can be written in the form n = st2 , where t is a positive integer and s is squarefree.

Hint: Let t be the largest positive integer such that t2 | n. Convince yourself that such an integer always exists!


Q4. (6 marks) For any non-negative integer r, define

(a) (3 marks) Prove that, for every positive integer n,

(b) (2 marks) Use Part (a) to prove that, for all non-negative integers i and j, with i < j, the numbers ai and aj are coprime.

Hint: Notice that ai divides 

(c) (1 mark) Use Part (b) to conclude that there are infinitely many primes.


Q5. (5 marks) Let a and b be coprime integers. Prove that there exist integers u and v such that for every integer n, gcd(an + u, bn + v) = 1.