45, there is no solution to the
linear Diophantine equation 354a + 258b = 45. 1. First apply the Euclidean Algorithm to 21 and 15 to find gcd(21, 15).
21 |
= |
15 · 1 + 6 | (equation 1) |
| 15 | = | 6 · 2 + 3 | (equation 2) |
| 6 | = | 3 · 2 + 0 | (equation 3) |
Thus, gcd(21, 15) = 3. Since 3 | 9, we know that a solution exists to the linear Diophantine equation 21x + 15y = 9.
Now work backwards through the equations of the Euclidean Algorithm to find a solution.
From equation 2 we see that:
| 3 | = | 15 - 6 · 2 |
| = | 15 - [21 - 15 · 1] · 2 (from equation 1) | |
| = | 15 · 3 - 21 · 2 |
Therefore, 21(-2) + 15(3) = 3. So 21(-6) + 15(9) = 9.
Hence x = - 6 and y = 9 is one solution to the linear Diophantine equation 21x + 15y = 9.
2. First apply the Euclidean Algorithm to 158 and 57 to find gcd(158, 57).
158 |
= |
57 · 2 + 44 | (equation 1) |
| 57 | = | 44 · 1 + 13 | (equation 2) |
| 44 | = | 13 · 3 + 5 | (equation 3) |
| 13 | = | 5 · 2 + 3 | (equation 4) |
| 5 | = | 3 · 1 + 2 | (equation 5) |
| 3 | = | 2 · 1 + 1 | (equation 6) |
| 2 | = | 1 · 2 + 0 | (equation 7) |
Thus, gcd(158, 57) = 1. Since 1 | 20000, we know that a solution exists to the linear Diophantine equation 158m + 57n = 20000.
Now work backwards through the equations of the Euclidean Algorithm to find a solution.
From equation 6 we see that:
| 1 | = | 3 - 2 · 1 | |
| = | 3 - [5 - 3 · 1] · 1 | (from equation 5) | |
| = | 3 · 2 - 5 · 1 | ||
| = | [13 - 5 · 2] · 2 - 5 · 1 | (from equation 4) | |
| = | 13 · 2 - 5 · 5 | ||
| = | 13 · 2 - [44 - 13 · 3] · 5 | (from equation 3) | |
| = | 13 · 17 - 44 · 5 | ||
| = | [57 - 44 · 1] · 17 - 44 · 5 | (from equation 2) | |
| = | 57 · 17 - 44 · 22 | ||
| = | 57 · 17 - [158 - 57 · 2] · 22 | (from equation 1) | |
| = | 57 · 61 - 158 · 22 |
Therefore, 158(-22) + 57(61) = 1. So we multiply both sides of the equation by 20000 to get: 158(-440 000) + 57(1 220 000) = 20 000.
Hence m = -440 000 and n = 1 220 000 is one solution to the linear Diophantine equation 158m + 57n = 20 000.
3. First apply the Euclidean Algorithm to 354 and 258 to find gcd(354, 258).
354 |
= |
258 · 1 + 96 | (equation 1) |
| 258 | = | 96 · 2 + 66 | (equation 2) |
| 96 | = | 66 · 1 + 30 | (equation 3) |
| 66 | = | 30 · 2 + 6 | (equation 4) |
| 30 | = | 6 · 5 + 0 | (equation 5) |
Thus, gcd(354, 258) = 6. Since 645, there is no solution to the
linear Diophantine equation 354a + 258b = 45.