90.1k views
3 votes
Use the Euclidean Algorithm to decide whether the equation below is solvable in integers x and y.

637x + 259y = 357

User Surasak
by
8.4k points

1 Answer

4 votes
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.
User Blub
by
8.5k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.