HCF of 372, 496, 474 using Euclid's algorithm

Below detailed show work will make you learn how to find HCF of 372,496,474 using the Euclidean division algorithm. So, follow the step by step explanation & check the answer for HCF(372,496,474).

Here 496 is greater than 372

Now, consider the largest number as 'a' from the given number ie., 496 and 372 satisfy Euclid's division lemma statement a = bq + r where 0 ≤ r < b

Step 1: Since 496 > 372, we apply the division lemma to 496 and 372, to get

496 = 372 x 1 + 124

Step 2: Since the reminder 372 ≠ 0, we apply division lemma to 124 and 372, to get

372 = 124 x 3 + 0

The remainder has now become zero, so our procedure stops. Since the divisor at this stage is 124, the HCF of 372 and 496 is 124

Notice that 124 = HCF(372,124) = HCF(496,372) .

We can take hcf of as 1st numbers and next number as another number to apply in Euclidean lemma

Here 474 is greater than 124

Now, consider the largest number as 'a' from the given number ie., 474 and 124 satisfy Euclid's division lemma statement a = bq + r where 0 ≤ r < b

Step 1: Since 474 > 124, we apply the division lemma to 474 and 124, to get

474 = 124 x 3 + 102

Step 2: Since the reminder 124 ≠ 0, we apply division lemma to 102 and 124, to get

124 = 102 x 1 + 22

Step 3: We consider the new divisor 102 and the new remainder 22, and apply the division lemma to get

102 = 22 x 4 + 14

We consider the new divisor 22 and the new remainder 14,and apply the division lemma to get

22 = 14 x 1 + 8

We consider the new divisor 14 and the new remainder 8,and apply the division lemma to get

14 = 8 x 1 + 6

We consider the new divisor 8 and the new remainder 6,and apply the division lemma to get

8 = 6 x 1 + 2

We consider the new divisor 6 and the new remainder 2,and apply the division lemma to get

6 = 2 x 3 + 0

The remainder has now become zero, so our procedure stops. Since the divisor at this stage is 2, the HCF of 124 and 474 is 2

Notice that 2 = HCF(6,2) = HCF(8,6) = HCF(14,8) = HCF(22,14) = HCF(102,22) = HCF(124,102) = HCF(474,124) .

Therefore, HCF of 372,496,474 using Euclid's division lemma is 2.