Question

Why is Euclids division algorithm for finding HCF is true?

And why is the fact true that hcf(a,b) is same as hcf(b,r)?

Answer 1

We have seen that the said lemma is nothing but a restatement of the long division process which we have been using all these years. In this section, we will learn one more application of Euclids division lemma known as Euclids Division Algorithm.
An algorithm means a series of well defined steps which provide a procedure of calculation repeated successively on the results of earlier steps till the desired result is obtained.Theorem : If a and b are positive integers such that a = bq + r, then every common divisor of a and b is a common divisor of b and r, and vice-versa.
Proof : Let c be a common divisor of a and b. Then,
c| a ⇒ a = cq1 for some integer q1
c| b ⇒ b = cq2 for some integer q2.
Now, a = bq + r
⇒ r = a – bq
⇒ r = cq1 – cq2 q
⇒ r = c( q1 – q2q)
⇒ c | r
⇒ c| r and c | b
⇒ c is a common divisor of b and r.
Hence, a common divisor of a and b is a common divisor of b and r.
Euclids Division Algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers. Recall that the HCF of two positive integers a and b is the largest positive integer d that divides both a and b.
---------------------------------------------------------------------------
Let us state Euclid’s division algorithm clearly.
To obtain the HCF of two positive integers, say c and d, with c > d, follow the steps below: Step 1 : Apply Euclid’s division lemma, to c and d. So, we find whole numbers, q and r such that c = dq + r, 0 ≤ r < d.
Step 2 : If r = 0, d is the HCF of c and d. If r ≠ 0, apply the division lemma to d and r.
Step 3 : Continue the process till the remainder is zero. The divisor at this stage will be the required HCF.

This algorithm works because HCF (c, d) = HCF (d, r) where the symbol HCF (c, d) denotes the HCF of c and d, etc.
---------------------------------------------------------------------------
Examples :
1) Use Euclid’s algorithm to find the 420 and 130.

Solution :
Step:1 Since 420 > 130 we apply the division lemma to 420 and 130 to get ,
420 = 130 x 3 + 30
Step:2 Since 30 ≠ 0 , we apply the division lemma to 130 and 30 to get
130 = 30 x 4 + 10
Step:3 Since 10 ≠ 0 , we apply the division lemma to 30 and 10 to get
30 = 10 x 3 + 0
The remainder has now become zero, so our procedure stops. Since the divisor at this Step is 10, the HCF of 420 and 130 is 10.
---------------------------------------------------------------------------
2) Use Euclid’s algorithm to find the 65 and 117.

Solution :
Step:1 Since 117 > 65 we apply the division lemma to 117 and 65 to get ,
117 = 65 x 1 + 52
Step:2 Since 52 ≠ 0 , we apply the division lemma to 65 and 52 to get
65 = 52 x 1 + 13
Step:3 Since 13 ≠ 0 , we apply the division lemma to 52 and 13 to get
52 = 13 x 4 + 0
The remainder has now become zero, so our procedure stops. Since the divisor at this Step is 13, the HCF of 117 and 52 is 13.