Paper 4, Section I, E

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

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

*Typos? Please submit corrections to this page on GitHub.*