Question

Use the Euclidean Algorithm to decide whether the equation below is solvable in integers x and y.

637x + 259y = 357

Answer 1

To use the Euclidean Algorithm, we need to find the greatest common divisor (GCD) of 637 and 259.

First, we divide 637 by 259 and get a remainder of 119:
637 = 259 * 2 + 119

Then, we divide 259 by 119 and get a remainder of 21:
259 = 119 * 2 + 21

Next, we divide 119 by 21 and get a remainder of 16:
119 = 21 * 5 + 16

Then, we divide 21 by 16 and get a remainder of 5:
21 = 16 * 1 + 5

Finally, we divide 16 by 5 and get a remainder of 1:
16 = 5 * 3 + 1

Since the last remainder is 1, we know that the GCD of 637 and 259 is 1. Therefore, the equation 637x + 259y = 357 is solvable in integers x and y.