1. First apply the Euclidean Algorithm to 221 and 91 to find gcd(221, 91).
221 |
= |
91 · 2 + 39 | (equation 1) |
| 91 | = | 39 · 2 + 13 | (equation 2) |
| 39 | = | 13 · 3 + 0 | (equation 3) |
Thus, gcd(221, 91) = 13. Since 13 | 676, we know that a solution exists to the linear Diophantine equation 91x + 221y = 676.
Now work backwards through the equations of the Euclidean Algorithm to find a solution.
From equation 2 we see that:
| 13 | = | 91 - 39 · 2 | |
| = | 91 - [221 - 91 · 2] · 2 | (from equation 1) | |
| = | 91 · 5 - 221 · 2 |
Therefore, 91(5) + 221(-2) = 13. So we multiply both sides of the equation by 52 to get: 91(260) + 221(-104) = 676.
Hence x = 260 and y = -104 is one solution to the linear Diophantine equation 91x + 221y = 676.