Given two integers $m$ and $n$, thre greatest common divisor (GCD) is the largest positive integer that divides both $m$ and $n$. If the greatest common divisor is $1$, we say the two integers are relatively prime. If either integer is zero, the greatest common divisor is the absolute value of the other integer.

Algorithm X.1(a): Greatest common divisor of two non-negative integers

Input: two non-negative integers $m \ge 0$ and $n \ge 0$.
Output: a non-negative integer.

In secondary school, you learned Euclid's algorithm for calculating the greatest common divisor. Describe this algorithm.

Now, what does your algorithm say is the greatest common divisor of $0$ and $0$? Is it $0$?

Algorithm X.1: Greatest common divisor of two integers

Input: two integers $m$ and $n$.
Output: a non-negative integer.

Describe an algorithm for finding the greatest common divisor of two integers. As any negative number is less than any positive number, the greatest common divisor must be positive, even if $m$ or $n$ or both are negative.

The algorithm for calculating the least common multiple is actually very straight-forward, as it uses an algorithm that we have already discussed:

${\rm lcm}(m, n) = \frac{ |mn| }{ \gcd(m, n) }$.

Algorithm X.2: Least common multiple

Input: two integers $m$ and $n$.
Output: a non-negative integer.

Describe an algorithm for calculating the least common multiple of two integers $m$ and $n$. As with the GCD, the least common multiple must be positive.