Paper 4, Section I, E

Numbers and Sets | Part IA, 2013

Let mm and nn be positive integers. State what is meant by the greatest common divisor gcd(m,n)\operatorname{gcd}(m, n) of mm and nn, and show that there exist integers aa and bb such that gcd(m,n)=am+bn\operatorname{gcd}(m, n)=a m+b n. Deduce that an integer kk divides both mm and nn only if kk divides gcd(m,n)\operatorname{gcd}(m, n).

Prove (without using the Fundamental Theorem of Arithmetic) that for any positive integer k,gcd(km,kn)=kgcd(m,n)k, \operatorname{gcd}(k m, k n)=k \operatorname{gcd}(m, n).

Typos? Please submit corrections to this page on GitHub.