HCF of 595, 252 using Euclid's algorithm

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

Here 595 is greater than 252

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

Step 1: Since 595 > 252, we apply the division lemma to 595 and 252, to get

595 = 252 x 2 + 91

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

252 = 91 x 2 + 70

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

91 = 70 x 1 + 21

We consider the new divisor 70 and the new remainder 21,and apply the division lemma to get

70 = 21 x 3 + 7

We consider the new divisor 21 and the new remainder 7,and apply the division lemma to get

21 = 7 x 3 + 0

The remainder has now become zero, so our procedure stops. Since the divisor at this stage is 7, the HCF of 595 and 252 is 7

Notice that 7 = HCF(21,7) = HCF(70,21) = HCF(91,70) = HCF(252,91) = HCF(595,252) .

Therefore, HCF of 595,252 using Euclid's division lemma is 7.