Gcd

not14talk

Ok im trying to do this question
1. (i) Find the greatest common divisor d of 272 and 244, and find a pair of integers x
and y such that
272x+244y = d.

and this is what I get
272 = 1 X 244 + 28
244 = 2 X 122 + 0
122 = 2 X 61 + 0
61 = 2 X 30 + 1
30 = 2 X 15 + 0
15 = 2 x 7 + 1
7 = 2 X 3 + 1
3 = 1 x 2 + 1
2 = 2??

so is it ans 2 or 2x2 = 4 ????

Pherekydes

272 = 1 X 244 + 28
244 = 8 X 28 + 20
28 = 1 X 20 + 8
20 = 2 X 8 + 4
8 = 2 X 4 + 0

...is correct. Thus 4 is the GCD of 272 and 244. I'll leave you to do the other part yourself.

not14talk

Ah it all makes sense now!! thanks

Ah how do I do the 2ed bit?


Sometimes I wish I could understand my lecturer :rolleyes: and maybe I could understand maths!!

Mary-Ellen

I used the extended euclidian algorithm described here
http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

factors of 272 are:2,2,2,2,17
factors of 244 are : 2,2,61
common ones are: 2,2
so gcd = 2*2 = 4

what you need to solve is 272x * 244y = 4
divide both sides by 4
68x+61y = 1
(1*61+7)x + 61*y = 1
61(x+y)+7x = 1
where (x1) = x+y & (y1)=x
61(x1)+7(y1) = 1

repeate steps again:
(8*7+5)(x1)+5(y1) = 1
7(8(x1)+(y1))+5(x1)= 1
where (x2) = 8(x1)+(y1)
7(x2)+5(y2) = 1

(1*5+2)(x2)+5(y2)= 1
5((x2)+(y2))+2(x2) = 1
5(x3)+2(y3) = 1

stop now because both 2 & 5 are primes

if x3 = 1
5+2(y3) = 1
therefor y3 = -2

now we need to work backward to find x&y
(y3)= -2 = (x2)
(x2)+(y2)=x3
-2+(y2)=1
y2=3 & x2 = -2

y2 = 3 = x1
8(x1)+(y1) = x2
24 + y1 = -2
y1 = -26

y1 = -26 = x
x + y = x1
-26 + y = 3
y = -29

if you work out 68(-26)+61(29)=1 it should work
therefor 272(-26)+244(29) = 4:rolleyes: