Loading....
Coupon Accepted Successfully!

 

Euclid's Division Lemma

Euclidean Algorithm :

Let a and b be positive integers with ab.
If b divides a, then (a, b) = b.
If b divides a, then apply the division algorithm repeatedly as follows:

a = b q0 + r0 with 0 r0 < b
b = r0 q1 + r1 with 0
r1 < r0
r0 = r1 q2 + r2 with 0
r2 < r1
r1 = r2 q3 + r3 with 0
r3< r2
r2 = r3 q4 +r4 with 0
 r4 < r3    ......................

This process ends when the remainder 0 is obtained. This must occur after a finite number of steps; that is, for some k
rk-2 = rk-1 qk + rk with 0
rk < rk-1
rk-1= rk qk+1 + 0
Then rk the last non zero remainder, is the greatest common divisor of a and b.

Proof
The proof follows from the property: if a = b q + r, then (a, b) = (b, r). Thus, if b divides a then a = b q + 0 and so (a, b) = (b, 0) = b. Also, as in the statement of the proposition,

(a, b) = (b, r0) = (r0, r1) = ... = (rk-2,rk-1) =(rk-1,rk) = (rk,0) = rk.
 

Find the HCF of 274170 and 17017.

274170= 17017 x 16 + 1898

Answer: 17017





Test Your Skills Now!
Take a Quiz now
Reviewer Name