Question 2

Use the Euclidean Algorithm to calculate d = gcd(30135,7110) and express d as an

integral linear combination of 30135 and 7110.

(7 marks)

Suppose that m, n are positive integers each greater than 1 such that

lcm(n, m) + gcd(n, m) = n+m. Show that either m divides n or n divides m.

(8 marks)

(a)

(b)