Question

use euclid's division lemma to find the h.c.f of 858 , 325 . express it in the form of 858x+325y.

Answer 1

substitution of the required values should be from the direction as described.

Answer 2

The HCF of 858, 325 is 13 and it can be written as 858 x 11 + 325 x (-29).

• HCF of given numbers is the highest common factor of given numbers.
• Finding HCF using Euclid's Division Algorithm:
• Statement: If there are two positive integers a, b then there exists two unique integers q and r such that

                         a = bq + r (0 ≤ r < b)

PROBLEM:

Given numbers are 858, 325

858 = 325 x 2 + 208   ---------------(1)

325 = 208 x 1 + 117      ---------------(2)

208 = 117 x 1 + 91        ----------------(3)

117 = 91 x 1 + 26          -----------------(4)

91 = 26 x 3 + 13            ----------------(5)

26 = 13 x 2 + 0            

∴ HCF of 858, 325 is 13.

Expressing 13 in the form of 858x + 325y:

13 = 91 - 26 x 3                                  [From (5)]

13 = 91 - (117 - 91 x 1) x 3                    [From (4)]

13 = 91 - 117 x 3 + 91 x 3

13 = 91 x 4 - 117 x 3

13 = (208 - 117 x 1) x 4 - 117 x 3          [From (3)]

13 = 208 x 4 - 117 x 4 - 117 x 3

13 = 208 x 4 - 117 x 7

13 = 208 x 4 - (325 - 208) x 7            [From (2)]

13 = 208 x 4 - 325 x 7 + 208 x 7

13 = 208 x 11 - 325 x 7

13 = (858 - 325 x 2) x 11 - 325 x 7       [From (1)]

13 = 858 x 11 - 325 x 22 - 325 x 7

13 = 858 x 11 + 325 x (-29)