Use Euclid’s division algorithm to find the HCF of 726 and 275

Use Euclid’s division algorithm to find the HCF of 726 and 275.

Euclid’s division lemma: The division lemma of Euclid asserts that for any two positive numbers, such as ‘a’ and ‘b,’ the condition ‘a = bq +r’, where 0 ≤ r < b always holds true. We can represent this mathematically as ‘Dividend = (Divisor*Quotient) + Remainder’. A lemma is a proposition that has already been proven to be true.

We determine the HCF of two positive integers using Euclid’s Division Algorithm by repeating division until we receive 0 as the remainder.

726 is more than 275 in the provided two numbers. Thus, we divide 726 by 275 to get

The remainder is 176, as we can see.

We can now divide 275 by 176 to get the remainder as 99, as we can see.

We can now divide 176 by 99 to get the remainder as 77.

When we divide 99 by 77, we obtain the remainder as 22.

When we divide 77 by 22, we obtain the remainder is 11 ≠ 0, as we can see.

We can now divide 22 by 11 to get the remainder as 0, as we can see.

As a result, the HCF for the numbers 726 & 275 is 11.