Question

use Euclid division Lemma algorithm to find HCF of 726 and 275

Answer 1

Answer:

For every single point of integers a and b there exists a unique integer Q and r such that a = bq + r

Where 0 ≤ r < b and here a > b.

We always divide the smaller number by the larger number.

Proceeding with Euclid division we have:

726/275 = 2 rem 99

726 = 275 × 2 + 176

275/176 = 1 rem 99

275 = 176 × 1 + 99

176/99 = 1 rem 77

176 = 99 × 1 + 77

99/77 = 1 rem 22

99 = 77 × 1 +22

77/2 = 3 rem 11

77 = 22 × 3 + 11

22/11 = 2 rem 0

22 = 11 ×2 +0

HCF = 11 Since here the remainder is zero.

We want to write it in the form :

726m + 275n = 11

We find the relationship of 726 and 275 in terms of ratio.

726/275 =66:25

66+25=91 = total ratio.

Meaning :

726/91 + 275/91 = 11

726m = 726/91

m = 1/91

275n =275/91

n = 1/91

So :

n = m = 1/91