Why gcd(a,b) is the same as solving for gcd(b,a-b) in the Euclidean algorithm

Question

I am a number theory hobbyist, and have recently started to read the book Excursions in Number Theory. I am at a point where the author is trying to reason why Euclid's algorithm for finding the gcd of 2 numbers work. I am unable to get my head around the fact that gcd(a,b) is the same as solving for gcd(b,a-b). Is there some way I can intuitively understand why this is so? I have gone through several explanations where they use modular arithmetic and Euclid's division algorithm to explain it and I am afraid I dont get it.

Answer 1

Enlarge the problem: what is actually true is that the set of common divisors $D(a,b)$ of $a$ and $b$ is the same as $D(b, a-b)$ – and also the same as $D(b,a\bmod b)$.

Indeed a number which divides both $a$ and $b$, also divides $a-b$: this proves $D(a,b)\subseteq D(b,a-b)$.

Conversely, a number which divides $b$ and $a-b$ also divides $b+(a-b)=a$, whence the reverse inclusion.