Question 5

We need to prove that the highest common factor of $(a, b)$ is the same as the highest common factor of $(b, r)$.

Step 1 — Show $\text{HCF}(b, r)$ divides $a$

Let's start with $\text{HCF}(b, r)$. Let $\text{HCF}(b, r) = \mathbf{h}$. This means $\mathbf{h}$ divides $\mathbf{b}$. It also means $\mathbf{h}$ divides $\mathbf{r}$. So, we can write $\mathbf{b} = k_1 \mathbf{h}$. This is for some integer $k_1$. And $\mathbf{r} = k_2 \mathbf{h}$. This is for some integer $k_2$. We are given $a = bq + r$. Let's substitute $b$ and $r$ into this.

$a = (k_1 h)q + (k_2 h)$

We can take $\mathbf{h}$ as a common factor.

$a = h(k_1 q + k_2)$

This shows $\mathbf{h}$ divides $\mathbf{a}$. So, $\mathbf{h}$ is a common divisor of $\mathbf{a}$ and $\mathbf{b}$. $\mathbf{h}$ is the greatest common divisor of $\mathbf{b}$ and $\mathbf{r}$. Thus, $\mathbf{h}$ must be less than or equal to $\text{HCF}(a,b)$.

$\boxed{\text{HCF}(b, r) \le \text{HCF}(a, b)}$

Step 2 — Show $\text{HCF}(a, b)$ divides $r$

Now, let's consider $\text{HCF}(a, b)$. Let $\text{HCF}(a, b) = \mathbf{d}$. This means $\mathbf{d}$ divides $\mathbf{a}$. It also means $\mathbf{d}$ divides $\mathbf{b}$. So, we can write $\mathbf{a} = m \mathbf{d}$. This is for some integer $m$. And $\mathbf{b} = n \mathbf{d}$. This is for some integer $n$. We know that $a = bq + r$. Let's rearrange this equation for $r$.

$r = a - bq$

Now, substitute $a$ and $b$ into this.

$r = (m d) - (n d)q$

We can take $\mathbf{d}$ as a common factor.

$r = d(m - nq)$

This shows $\mathbf{d}$ divides $\mathbf{r}$. So, $\mathbf{d}$ is a common divisor of $\mathbf{b}$ and $\mathbf{r}$. $\mathbf{d}$ is the greatest common divisor of $\mathbf{a}$ and $\mathbf{b}$. Thus, $\mathbf{d}$ must be less than or equal to $\text{HCF}(b,r)$.

$\boxed{\text{HCF}(a, b) \le \text{HCF}(b, r)}$

Answer

From Step 1, we found $\text{HCF}(b, r) \le \text{HCF}(a, b)$. From Step 2, we found $\text{HCF}(a, b) \le \text{HCF}(b, r)$. Combining these, we conclude $\text{HCF}(a, b) = \text{HCF}(b, r)$.