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

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.