Euclid Division Lemma
For any pair of positive integers a and b (a＞b), there exist a unique pair "q and r" such that
a=bq+r, 0≤ r ＜b
Dividend(a)= Divisor(b) x Quotient(q) + Remainder(r)
This is known as Euclid Division Algorithm
For example:
Two positive integers 24 and 9
9 ) 24 (2
18
----------
06
----------
∴ 24 = 9 x 2 + 6
One more example:
Two numbers 34 and 6
6 ) 34 (5
30
----------
04
----------
∴ 34 = 6 x 5 + 4
✶Euclid division algorithm is used to find HCF of two numbers
✶ HCF of two consecutive numbers is 1.
✶ HCF of two consecutive odd numbers is 1.
✶ HCF of two Prime numbers is 1.
✶ HCF of two consecutive Even numbers is 2.
Process to find HCF by Euclid Division Algorithm:
1. Apply Euclid's division algorithm to a and b, to find the values of q and r
a=bq+r
2. If r = 0, "b"(Divisor) is the HCF of Given a and b
3. If r ≠ 0, Apply Euclid's division algorithm to b and r
4. If r = 0, Divisor(r) is the HCF of Given a and b
5. If r ≠ 0, Apply Euclid's division algorithm to divisor and remainder
6. Continue the process till the remainder is Zero
7. Divisor at last stage, will be the HCF of Given numbers
Ex.1: Finding HCF of 96 and 72
Solution:
Apply division algorithm to 96 and 72
72 ) 96 (1
72
----------
24
----------
∴ 96 = 72 x 1 + 24
Apply division algorithm to 72 and 24
24 ) 72 (3
72
----------
00
----------
∴ 72 = 24 x 3 + 0
Remainder is Zero
So divisor(24) is the HCF
∴ HCF of 96 and 72 is 24
Ex.2: Finding HCF of 145 and 30
Solution:
Apply division algorithm to 145 and 30
30 ) 145 (4
120
----------
025
----------
∴ 145 = 30 x 4 + 25
Apply division algorithm to 30 and 25
25 ) 30 (1
25
----------
05
----------
∴ 30 = 25 x 1 + 5
Apply division algorithm to 25 and 5
5 ) 25 (5
25
----------
00
----------
∴ 25 = 5 x 5 + 0
Remainder is Zero
So divisor(5) is the HCF
∴ HCF of 145 and 30 is 5
Text Book Question:
Finding HCF of 900 and 270
Solution:
Apply division algorithm to 900 and 270
270) 900 (3
810
----------
090
----------
∴ 900 = 270 x 3 + 90
Apply division algorithm to 270 and 90
90) 270 (3
270
----------
000
----------
∴ 270 = 90 x 3 + 0
Remainder is Zero
So divisor(90) is the HCF
∴ HCF of 900 and 270 is 90
Find HCF of following by using Euclid Division Algorithm.
1. 240 and 100
2. 350 and 250
3. 680 and 500
4. 175 and 120
5. 144 and 108