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.