Question

Find the H.C.F of 592 and 252 and express it as a linear combination.

Answer 1

Solution : 

Step:1 Since 592 > 252 divide 592 by 252

592 = 252 * 2 + 88 

Step:2 Since 88 ≠ 0, divide 252 by 88

252 = 88 * 2 + 76

Step:3 Since 76 ≠ 0, divide 88 by 76

88 = 76 * 1 + 12

Step:4 Since 12 ≠ 0, divide 76 by 12

76 = 12 * 6 + 4

Step:5 Since 4 ≠ 0, divide 12 by 4

12 = 4 * 3 + 0

The remainder has now become zero, so we stop here. Since the divisor at this Step is 4, the HCF of 592 and 252 is 4. 

Answer 2

Let us first use Euclid division algorithm to find the HCF of 592 and 252

Step 1 => 592 = 252 × 2 + 88

Step 2 => 252 = 88 × 2 + 76

Step 3 => 88 = 76 × 1 + 12

Step 4 => 76 = 12 × 6 + 4

Step 5 => 12 = 4 × 3 + 0

HCF (592,252) = 4

To express the HCF as linear combination of the two given number we start from Step 4 (where there is a non - zero remainder) and successively eliminate the remainder in previous steps under :-

Step 4 => 4 = 76 - 12 × 6

= 76 - (88 - 76 × 1) × 6 (From step 3)

= 76 - 88 × 6 + 76 × 6

= 7 × 76 - 88 × 6

= 7 × (252 - 88 × 2) - 88 × 6 (From step 3)

= 7 × 252 - 14 × 88 - 88 × 6

= 7 × 252 - 20 × 88

= 7 × 252 - 20 × [592 - 252 × 2] [From step 3]

= 7 × 252 - 20 × 592 + 40 × 252

Hence,

4 = 47 × 252 - 20 × 592