Use Buclid\'s algorithm to find the greatest common factor of the following pair

Question

Use Buclid's algorithm to find the greatest common factor of the following pairs ofintegers, aand b (a) 3745 and 1172(b 192876 and 192918 Look back at your calculations for the previous exercise. Use those to help decide whether there are pairs of integers x and y which satisfy the following equations. If so, use the method ofback substitution or othermethod, with those calculations to find an integer-pair solution [x, yl (a) 3745 x + 1172 y-5 (b) 192876 x + 1929 18 y = 10 In those cases where you think that nopair can exist, give a dear reason why not

Explanation / Answer

Using Eulid's algorithm to find g.c.d of

a) 3745 and 1172

since 3745=1172*3+229

1172=229*5+27

229=27*8+13

27=13*2+1

13=13*1+0

therfore

g.c.d(3745,1172)=1

Now

1=27-(13*2)

=27-(229-27*8)*2

=27-(229*2)+27*16

=27*17-229*2

=(1172-229*5)*17-229*2

=1172*17-229*85-229*2

=1172*17-229*87

=1172*17-(3745-1172*3)*87

=1172*17-3745*87+1172*261

=1172(278)+3745(-87)

therfore Here x=-87 and y=278 only if

g.c.d(3745,1172)=1

therfore there is no pair of x and y such that 3745x+1172y=5

b) to find g.c.d of 192876 and 192918

since

192918=192876*1+42

192876=42*4592+12

42=12*3+6

12=6*2+0

therfore g.c.d(192876,192918)=6

Back substitution

6=42-(12*3)

42-(192876-42*4592)*3

42-(192876*3+42*13776

=42*13777-192876*3

=(192918-192876*1)*1377-192876*3

=192918*13777-192876*1377-192876*3

6=192918(13777)-192876(13780)

x=13777 and y=13780

since g.c.d is 6 therfore there is no pais such that  

192876x+192918y=10

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.