# High school level proof for Euclid's GCD theorem

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.

• Why don't you try with Euclid's algorithm to find HCF. Commented Sep 19, 2021 at 11:48

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.
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)$$