Jump to

**Find the HCF of the following pair of integers and express it as a linear combination of them,**

**(i) 963 and 657**

**(ii) 592 and 252**

**(iii) 506 and 1155**

**(iv) 1288 and 575**

Answer:

By applying Euclid’s division lemma on 963 and 657, we get 963 = 657 x 1 + 306… ......... (1)

As the remainder ≠ 0, apply division lemma on divisor 657 and remainder 306 657 = 306 x 2 + 45…............ (2)

As the remainder ≠ 0, apply division lemma on divisor 306 and remainder 45 306 = 45 x 6 + 36… ............ (3)

As the remainder ≠ 0, apply division lemma on divisor 45 and remainder 36

45 = 36 x 1 + 9… ............... (4)

As the remainder ≠ 0, apply division lemma on divisor 36 and remainder 9

36 = 9 x 4 + 0… ................ (5)

Thus, we can conclude the H.C.F. = 9.

Now, in order to express the found HCF as a linear combination of 963 and 657, we perform 9 = 45 – 36 x 1 [from (5)]

= 45 – [306 – 45 x 6] x 1 = 45 – 306 x 1 + 45 x 6 [from (3)]

= 45 x 7 – 306 x 1 = [657 -306 x 2] x 7 – 306 x 1 [from (2)]

= 657 x 7 – 306 x 14 – 306 x 1

= 657 x 7 – 306 x 15

= 657 x 7 – [963 – 657 x 1] x 15 [from (1)]

= 657 x 7 – 963 x 15 + 657 x 15

= 657 x 22 – 963 x 15.

**(ii) 592 and 252**

By applying Euclid’s division lemma on 592 and 252, we get

592 = 252 x 2 + 88…....... (1)

As the remainder ≠ 0, apply division lemma on divisor 252 and remainder 88 252 = 88 x 2 + 76… ........ (2)

As the remainder ≠ 0, apply division lemma on divisor 88 and remainder 76 88 = 76 x 1 + 12… ........... (3)

As the remainder ≠ 0, apply division lemma on divisor 76 and remainder 12

76 = 12 x 6 + 4… ............. (4)

Since the remainder ≠ 0, apply division lemma on divisor 12 and remainder 4 12 = 4 x 3 + 0… ................ (5)

Thus, we can conclude the H.C.F. = 4.

Now, in order to express the found HCF as a linear combination of 592 and 252, we perform 4 = 76 – 12 x 6 [from (4)]

= 76 – [88 – 76 x 1] x 6 [from (3)]

= 76 – 88 x 6 + 76 x 6

= 76 x 7 – 88 x 6

= [252 – 88 x 2] x 7 – 88 x 6 [from (2)]

= 252 x 7- 88 x 14- 88 x 6

= 252 x 7- 88 x 20

= 252 x 7 – [592 – 252 x 2] x 20 [from (1)]

= 252 x 7 – 592 x 20 + 252 x 40

= 252 x 47 – 592 x 20

= 252 x 47 + 592 x (-20)

**(iii) 506 and 1155**

By applying Euclid’s division lemma on 506 and 1155, we get 1155 = 506 x 2 + 143… ............. (1)

As the remainder ≠ 0, apply division lemma on divisor 506 and remainder 143 506 = 143 x 3 + 77…................. (2)

As the remainder ≠ 0, apply division lemma on divisor 143 and remainder 77 143 = 77 x 1 + 66… .................. (3)

Since the remainder ≠ 0, apply division lemma on divisor 77 and remainder 66

77 = 66 x 1 + 11… ..................... (4)

As the remainder ≠ 0, apply division lemma on divisor 66 and remainder 11 66 = 11 x 6 + 0… ...................... (5)

Thus, we can conclude the H.C.F. = 11.

Now, in order to express the found HCF as a linear combination of 506 and 1155, we perform 11 = 77 – 66 x 1 [from (4)]

= 77 – [143 – 77 x 1] x 1 [from (3)]

= 77 – 143 x 1 + 77 x 1

= 77 x 2 – 143 x 1

= [506 – 143 x 3] x 2 – 143 x 1 [from (2)]

= 506 x 2 – 143 x 6 – 143 x 1

= 506 x 2 – 143 x 7

= 506 x 2 – [1155 – 506 x 2] x 7 [from (1)]

= 506 x 2 – 1155 x 7+ 506 x 14

= 506 x 16 – 1155 x 7

**(iv) 1288 and 575**

By applying Euclid’s division lemma on 1288 and 575, we get

1288 = 575 x 2+ 138 ............... (1)

As the remainder ≠ 0, apply division lemma on divisor 506 and remainder 143

575 = 138 x 4 + 23 .................... (2)

As the remainder ≠ 0, apply division lemma on divisor 143 and remainder 77

138 = 23 x 6 + 0 ......................... (3)

Thus, we can conclude the H.C.F. = 23.

Now, in order to express the found HCF as a linear combination of 1288 and 575, we perform 23 = 575 – 138 x 4 [from (2)]

= 575 – [1288 – 575 x 2] x 4 [from (1)]

= 575 – 1288 x 4 + 575 x 8

= 575 x 9 – 1288 x 4

Related Questions

Was This helpful?

Exercises

Chapters

Lido

Courses

Quick Links

Terms & Policies

Terms & Policies

2022 © Quality Tutorials Pvt Ltd All rights reserved