If $a=qb+r$ then $a,b$ and $b,r$ have exactly the same common divisors, so $\gcd (a,b)=\gcd (b,r)$

Let $a,b,q,r\in \mathbb{Z}$ satisfy

$a=qb+r\mathrm{.}$

Then an integer $d$ is a common divisor of $a$ and $b$ if and only if it is a common divisor of $b$ and $r$ (Divisibility in $\mathbb{Z}$: $d\mid a$ when $a=dq$ for some integer $q$); the two sets of common divisors are equal. Consequently

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

(Common divisor, and the greatest common divisor $\gcd (a,b)$, with the convention $\gcd (0,0):=0$).

No inequality on $r$ is assumed: the identity $a=qb+r$ alone is what is used, so the lemma applies to any decomposition of $a$, not only to the one produced by division with remainder.

• This is the whole content of the Euclidean algorithm; everything else in The Euclidean algorithm: for $a\in \mathbb{Z}$ and $b>0$ the remainder descent from $(a,b)$ terminates, and the last nonzero remainder is $\gcd (a,b)$ is bookkeeping about termination. Each division replaces a pair by a strictly smaller one without changing the set of common divisors, so the invariant is not merely the value $\gcd$ but the set $D$ itself.

• The absence of a constraint on $r$ matters. Applying the lemma with $q=1$ and no inequality is exactly what identifies $\gcd (F_{n+2},F_{n+1})$ with $\gcd (F_{n+1},F_n)$ for consecutive Fibonacci numbers, where $F_{n+2}=F_{n+1}+F_n$ is given by the recursion and not by a division.