Question

use euclid algorithm to find the hcf of 858 and 325. Express it in the form 858x + 325y.

Answer 1

Hi ,
_______________
Euclid's Division algorithm:

Given positive integers ' a ' and ' b '

there exists unique integers q and r

satisfying

a = bq + r ,

0 less than or equal to ' r ' < b.

__________________________

Applying Euclid's Division algorithm

to 858 and 325 we get

858 = 325 × 2 + 208

325 = 208 × 1 + 117

208 = 117 × 1 + 91

117 = 91 × 1 + 26

91 = 26 ×3 + 13

26 = 13 × 2 + 0

Reminder becomes zero .

Therefore ,

HCF of 858 and 325 = 13

Now ,

858x + 325y = 13

I hope this helps you.

****