Suppose a, b, n ∈ N. Use the Euclidean algorithm to prove that gcd(na, nb) = n gcd(a, b)

Question

I had this for homework before, and I wrote:

There exists s,t, that are elements of integers, such that gcd(a,b) = sa + tb, so ngcd(a,b) = n(sa + tb) = s(na) + t(nb)

but I got it wrong.

How do I write a rigorous formal proof to answer this?

Answer 1

The existence of integers $x$ and $y$ such that $ax + by = c$ only guarantees that $\gcd(a, b)$ divides $c$. Thus, you only showed that $\gcd(an, bn)$ divides $n \gcd(a, b)$. One way to get the converse would be to note that $n \gcd(a, b)$ divides both $na$ and $nb$ (because $\gcd(a,b)$ divides both $a$ and $b$) so, because $\gcd$ is the largest common divisor, $\gcd(an, bn) \ge n \gcd(a, b)$, so they are equal.

But this line of proof doesn't use the Euclidean algorithm at all. To use the Euclidean algorithm, write $$a = q_1 b + r_1,\quad 0 < r_1 < b$$ $$b = q_2 r_1 + r_2,\quad 0 < r_2 < r_1$$ $$r_1 = q_3 r_2 + r_3,\quad 0 < r_3 < r_2$$ $$\vdots$$ $$\quad\quad\quad\quad\quad r_{k-2} = q_k r_{k-1} + r_k,\quad 0 < r_k = \gcd(a,b) < r_{k-1}$$ $$r_{k-1} = q_{k+1} r_k + r_{k+1},\quad r_{k+1} = 0.\quad\quad$$ This shows the Euclidean algorithm proceeding through $(k+1)$ steps, where at the $(k+1)$th step we find the remainder to be zero, so the previous step's remainder is the $\gcd$ of $a$ and $b$. Now multiply all the steps and inequalities by $n$. The equality $r_{k+1} = 0$ implies $n r_{k+1} = 0$, so the previous step's remainder, $n r_k = n\gcd(a,b)$, is the $\gcd$ of $an$ and $bn$.