Extended Euclidean Algorithm Check

[perplexityy]

Hi,

I'd just like someone to help me with these questions because I don't know where I went wrong, my answer is way off the mark.



1. "Use the Euclidean algorithm to find the greatest common divisor of 633 and 255"

633 = 2 x 255 + 123
255 = 2 x 123 + 9
123 = 13 x 9 + 6
9 = 1 x 6 + 3
6 = 2 x 3 + 0
Therefore gcd is 3.

2. "Find integers x and y such that 633x + 255y = 6, or explain why none exist."

3 = 9 - (1 x 6)
3 = 9 - (1 x (123 - 13 x 9)) = -1 x 123 + 14 x 9
3 = -1 x 123 + 14 x (255 - 2 x 123) = 14 x 255 - 29 x 123
3 = 14 x 255 - 29 x (633 - 2 x 255) = -29 x 633 - 17 x 255
3 = (-29 x 633) - (17 x 255)
6 = -58 x 633 - 34 x 255

 

[Deleted member 4993]

Hi,

I'd just like someone to help me with these questions because I don't know where I went wrong, my answer is way off the mark.



1. "Use the Euclidean algorithm to find the greatest common divisor of 633 and 255"

633 = 2 x 255 + 123
255 = 2 x 123 + 9
123 = 13 x 9 + 6
9 = 1 x 6 + 3
6 = 2 x 3 + 0
Therefore gcd is 3. ← This is correct

2. "Find integers x and y such that 633x + 255y = 6, or explain why none exist."

3 = 9 - (1 x 6)
3 = 9 - (1 x (123 - 13 x 9)) = -1 x 123 + 14 x 9
3 = -1 x 123 + 14 x (255 - 2 x 123) = 14 x 255 - 29 x 123
3 = 14 x 255 - 29 x (633 - 2 x 255) = -29 x 633 - 17 x 255 ← This should be -29*633 + 72*255
3 = (-29 x 633) - (17 x 255)
6 = -58 x 633 - 34 x 255

.