Question

Can you please give me a mathematical proof of the Euclid's Division Algorith to find the HCF? I mean to say that a proof to show why it works?

Answer 1

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.