Question

Using Euclid division Lemma find HCF of 315 and 728

Answer 1

By Euclid's Division Lemma:-

a = bq + r and 0 ≤ r <b

As 728 > 315 :-

a = 728 and b = 315

Now:-

$⇝728 = 315 \times 2 + 98 \\ ⇝315 = 98 \times 3 + 21 \\ ⇝98 = 21 \times 4 + 14 \\ ⇝21 = 14 \times 1 + 7 \\ ⇝14 = {\fbox{7}} \times 2 + 0$

$\red{\tt{(Since ~we ~obtain~ 0 ~as}}$ $\red{\tt{remainder,~our ~step }}$$\red{\tt{stops~here.)}}$

∴ HCF of 728 & 315=7