MATH 135 Fall 2021: Written Assignment 6
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.
2021-11-04