Find the HCF of 72 & 96 by Euclid division algorithm and express it in form 96 m+72 n where m and n are some integers.

According to Euclid’s Division Lemma, if a and b are any two positive integers then there exist two unique whole numbers q and r such that

a = b q + r,

where 0 ≤ r < b

Here, a is called the dividend,

b is called the divisor,

q is called the quotient and

r is called the remainder.

So, apply the lemma on 96 and 72.

We get,

96 = (72 × 1) + 24 …(i)

Since the remainder is not zero.

Apply the lemma again on 72 and 24.

We get,

72 = (24 × 3) + 0

We have finally got remainder as 0.

⇒ HCF (96, 72) = 24

Now, we need to express the HCF in the form 96m + 72n, where m and n are integers.

So, take equation (i),

96 = (72 × 1) + 24

⇒ 24 = 96 – (72 × 1)

⇒ 24 = 96 (1) – 72 (1)

⇒ 24 = 96 (1) + 72 (-1)

Thus, 24 is expressed as

24 = 96 (1) + 72 (-1)

Where, m = 1 & n = -1 are integers.