If and are positive integers, then you know that , , where is a whole number. Prove that . [Hint: Let . So, and , where and are coprime.]

Understand the Question Euclid's Division Lemma states that for any two positive integers and , there exist unique integers and such that , where . To prove that , we show that: 1. Every common factor of and is also a factor of , which gives . 2. Every common factor of and is also a factor of , which gives . Since both numbers are less than or equal to each other, they must be equal. Step 1 · Show that HCF(b, r) Divides a Let . Then divides both and , so we can write for some integers and . Given Substitute the values of and Since is an integer, divides . Because divides both and , is a common factor of and . Therefore, cannot exceed the highest common factor of and Step 2 · Show that HCF(a, b) Divides r Let . Then divides both and , so we can write for some integers and . Rearranging gives Substitute the values of and Since is an integer, divides . Because divides both and , is a common factor of and . Therefore, cannot exceed the highest common factor of and Answer > From and : Common Mistakes One-Way Divisibility: Proving only that divides is not sufficient; you must prove divisibility in both directions to show equality. Confusing a Common Factor with HCF: Just because a number divides and does not mean ; it only proves .

Appendix 1: Proofs in Mathematics | A1.3

Question 5

If $a$ and $b$ are positive integers, then you know that $a = bq + r$ , $0 \le r < b$ , where $q$ is a whole number. Prove that $\text{HCF}(a, b) = \text{HCF}(b, r)$ .

[Hint: Let $\text{HCF}(b, r) = h$ . So, $b = k_1 h$ and $r = k_2 h$ , where $k_1$ and $k_2$ are coprime.]

Solution

Understand the Question

Euclid's Division Lemma states that for any two positive integers $a$ and $b$ , there exist unique integers $q$ and $r$ such that $a = bq + r$ , where $0 \le r < b$ .
To prove that $\text{HCF}(a, b) = \text{HCF}(b, r)$ $HCF (a, b) = HCF (b, r)$ , we show that:
1. Every common factor of $b$ and $r$ is also a factor of $a$ , which gives $\text{HCF}(b, r) \le \text{HCF}(a, b)$ .
2. Every common factor of $a$ and $b$ is also a factor of $r$ , which gives $\text{HCF}(a, b) \le \text{HCF}(b, r)$ .
Since both numbers are less than or equal to each other, they must be equal.

Step 1 · Show that HCF(b, r) Divides a

Let $\text{HCF}(b, r) = h$ .

Then $h$ divides both $b$ and $r$ , so we can write $b = k_1 h \quad \text{and} \quad r = k_2 h$ for some integers $k_1$ and $k_2$ .

Given $a = bq + r$

Substitute the values of $b$ and $r$

\begin{aligned} a &= (k_1 h)q + (k_2 h) \\ &= h(k_1 q + k_2) \end{aligned}

Since $k_1 q + k_2$ is an integer, $h$ divides $a$ .

Because $h$ divides both $a$ and $b$ , $h$ is a common factor of $a$ and $b$ . Therefore, $h$ cannot exceed the highest common factor of $a$ and $b$ $\text{HCF}(b, r) \le \text{HCF}(a, b) \quad \dots (1)$

Step 2 · Show that HCF(a, b) Divides r

Let $\text{HCF}(a, b) = d$ .

Then $d$ divides both $a$ and $b$ , so we can write $a = md \quad \text{and} \quad b = nd$ for some integers $m$ and $n$ .

Rearranging $a = bq + r$ gives $r = a - bq$

Substitute the values of $a$ and $b$

\begin{aligned} r &= md - (nd)q \\ &= d(m - nq) \end{aligned}

Since $m - nq$ is an integer, $d$ divides $r$ .

Because $d$ divides both $b$ and $r$ , $d$ is a common factor of $b$ and $r$ . Therefore, $d$ cannot exceed the highest common factor of $b$ and $r$ $\text{HCF}(a, b) \le \text{HCF}(b, r) \quad \dots (2)$

Answer

From $(1)$ and $(2)$ : $\text{HCF}(a, b) = \text{HCF}(b, r)$

Common Mistakes

One-Way Divisibility: Proving only that $\text{HCF}(b, r)$ divides $a$ is not sufficient; you must prove divisibility in both directions to show equality.
Confusing a Common Factor with HCF: Just because a number $h$ divides $a$ and $b$ does not mean $h = \text{HCF}(a, b)$ ; it only proves $h \le \text{HCF}(a, b)$ .

Question 5

More questions in A1.3