Question

HCF of 657 & 963 is expressible in the form of 657x+963y*-(15)

Answer 1

Hi!

Here is the proof to your query.

Among 657 and 963; 963 > 657

Since 963 > 657, we apply the division lemma to 963 and 657 to obtain

963 = 657 × 1 + 306 … Step 1

Since remainder 306 ≠ 0, we apply the division lemma to 657 and 306 to obtain

657 = 306 × 2 + 45 … Step 2

Since remainder 45 ≠ 0, we apply the division lemma to 306 and 45 to obtain

306 = 45 × 6 + 36 … Step 3

Since remainder 3 ≠ 0, we apply the division lemma to 45 and 36 to obtain

45 = 36 × 1 + 9 … Step 4

Since remainder 9 ≠ 0, we apply the division lemma to 36 and 9 to obtain

36 = 9 × 4 + 0 … Step 5

In this step the remainder is zero. Thus, the divisor i.e. 9 in this step is the H.C.F. of the given numbers

The H.C.F. of 657 and 963 is 9.

From Step 4:

9 = 45 – 36 × 1 … Step 6

From Step 3:

36 = 306 – 45 × 6

Thus, from step 6, it is obtained

9 = 45 – (306 – 45 × 6) × 1

= 45 × 7 – 306 × 1

From step 2, we get

9 = (657 – 306 × 2) × 7 – 306 × 1

= 657 × 7 – 306 × 15

From step 1, we get

9 = 657 × 7 – (963 – 657 × 1) × 15

= 657 × 22 – 963 × 15

⇒ HCF of 657 and 963 = 657 × 22 – 963 × 15

∴ HCF, 9 can be expressed as linear combination of 657 and 963 as 9 = 657x + 963y, where x and y are not unique.

In the above linear combination, x = 22 and y = –15

Cheers!