HCF of 78902,89765,12345 is 1 the largest number which exactly divides all the numbers i.e. where the remainder is zero. Let us get into the working of this example.
HCF of 78902, 89765, 12345 using Euclid’s algorithm
Consider we have three numbers 78902, 89765,12345 and we need to find the HCF of three of these numbers. To do so, we need to choose the largest integer first i.e. 89765 and then as per Euclid’s Division Lemma a = bq + r where 0 ≤ r ≤ b
Step 1: As 89765 > 78902 on applying division lemma to these numbers we get
89765 = 78902 x 1 + 10863
As the remainder is not zero, in this case, we should proceed with the division lemma procedure by considering 78902 as the divisor and the remainder 10863
Step 2: On applying division lemma to numbers 78902 and 10863 we get as such
78902= 10863 x 7 + 2861
Step 3: Following the same procedure again until we get a remainder zero
10863 = 2861 x 3 + 2280
2861 = 2280 x 1 + 581
2280 = 581 x 3 + 537
581 = 537 x 1 + 44
537 = 44 x 12 + 9
44 = 9 x 4 + 8
9 = 8 x 1 + 1
8 = 1 x 8 + 0
As we see the remainder has become zero, proceeding further isn’t possible and hence HCF is the divisor b left before the remainder zero arrived Which in this case is 1. Thus, we can ay HCF of numbers 78902 and 89765 is 1.
Notice that 1 = HCF(8,1) = HCF(9,8) = HCF(44,9) = HCF(537,44) = HCF(581,537) = HCF(2280,581) = HCF(2861,2280) = HCF(10863,2861) = HCF(78902,10863) = HCF(89765,78902).
Let us take the HCF of 1st two numbers and another number in the list as the next number to apply the Euclidean lemma.
Step 1: As 12345 is greater than 1 on applying the Euclidean Lemma we get it as such
12345 = 1 x 12345 + 0
As the remainder becomes zero, we cannot proceed further. According to the algorithm, in this case, the divisor is 1 and hence, the HCF of 12345 and 1 is 1.
FAQs on HCF using Euclid’s Algorithm
1. What is the Euclid division algorithm?
Euclid’s Division Algorithm is a technique to compute the Highest Common Factor (HCF) of given positive integers.
2. What is the HCF of 78902,89765,12345?
HCF of 78902,89765,12345 is 1 the largest number that divides all the numbers leaving a remainder zero.
3. How to find HCF of 78902,89765,12345 using Euclid’s Algorithm?
For arbitrary numbers 78902,89765,12345 apply Euclid’s Division Lemma in succession until you obtain a remainder zero. HCF is the remainder in the last but one step.