High school level proof for Euclid's GCD theorem

Question

I have noticed that in various high school math books, there is no proof given for the Euclid's GCD property of:

If $a \ge b$ then $\mathrm{gcd}(a,b)=\mathrm{gcd}(b,a-b),$ where $a,b\in \mathbb N^*.$

I would be very much interested in finding out about proofs that are accessible to high school students. Proofs by induction are also welcome.

---

My idea for a simple proof

(but I am not sure whether it is complete)

Suppose $x:=\mathrm{gcd}(a,b),$ then \begin{align} a&=x a' \tag{1}\\ b&=xb'. \tag{2} \end{align}

With $(1)$ and $(2)$ we can rewrite the difference of $a$ and $b$ as: $$a-b=x(a'-b').\tag{3}$$

Therefore, with $(3):$ \begin{align} \mathrm{gcd}(b,a-b)&= \mathrm{gcd}(xb',x(a'-b'))\\ &= x. \end{align}

What I am unsure of, is whether the last step truly implies $x$ is the gcd or could $x$ just be a common divisor and not necessarily the greatest.

Answer 1

Well your Arguments up to the last equation show that $x$ is a Common divisor. Not necessarily the gcd. What is missing is the following argument: Assume that $y $ divides $b$ and $a-b$, i.e. $b=cy$ and $$dy=a-b=a-cy$$ Then we deduce from the last equation that $a=(d+c)y$, so also $y$ divides $a$ and $b$ therefore $y\leq x$ as $x $ is already the gcd. Combining with the fact you showed that $x$ divides $b$ and $a-b$, we see that $x$ must be the gcd.

Answer 2

You've only shown that $x$ divides $a-b$, so that every common divisor of $a$ and $b$ also divides $b$ and $a-b$. Hence we have $\gcd(a,b)\leq \gcd(b, a-b)$. Then you shown the inequality the other way.

Indeed note that $\gcd(b,a-b)$ divides $b$ and $b+(a-b)=a,$ so every common divisor of $b$ and $a-b$ also divides $a$ and $b$. So we also have $\gcd (b, a-b) \leq \gcd (a,b),$ and thus

$$\gcd(a,b)=\gcd(b, a-b)$$