Originally Posted by

**Demandeur** Prove that if $\displaystyle a = qb+r$ for $\displaystyle q, b, r \in \mathbb{Z}$, then $\displaystyle \gcd(a, b) = \gcd(b, r)$.

Let $\displaystyle n$ be any common divisor of $\displaystyle a$ and $\displaystyle b$. Then we have $\displaystyle n\mid{a}$ and $\displaystyle n\mid{b}$ therefore $\displaystyle n\mid{a-qb} \Rightarrow n\mid{r}.$ Similarly, let $\displaystyle m$ be any common divisor of $\displaystyle b$ and $\displaystyle r$. Then we have $\displaystyle m\mid{b}$ and $\displaystyle m\mid{r}$ therefore $\displaystyle m\mid{qb+r} \Rightarrow m\mid{a}.$ How does it follow that $\displaystyle a, b$ and $\displaystyle b, r$ have the same common divisors?