If $a$ and $b$ are positive integers, then $a = bq + r$, $0 \leq r < b$, where $q$ is a whole number. Prove that $\text{HCF}(a, b) = \text{HCF}(b, r)$.
I have proceeded as follows:
Let $\text{HCF}(a, b) = h$. So, $b = mh$ and $r = nh$ where $m$ and $h$ are co-primes. What to do next?
$$\gcd(a,b) = \gcd(bq+r, b) = \gcd(bq+r-bq, b) = \gcd(b,r)$$
You have to use the property that $\gcd(a,b) = \gcd(a, b+ka)$