Diophantine Equations are equations that require Integer solutions to the unknown variables. There are many different ways to solve them, I am most comfortable with using an Algebraic approach to solving these equations.
First degree Diophantine Equations with two variables (aX + bY = c) must have c divisible by the GCD(a,b). When a and b are relatively prime, the GCD(a,b) = 1, and divides c. Plus all variables are members of the Integers.
| 37X + 23Y | = | 1 | |||
| 23Y | = | -37X + 1 | |||
| Y | = | -X + (1 -14X)/23 | |||
| Y | = | -X + A, | A | = | 1 -14X 23 |
| 23A | = | 1 -14X | |||
| 14X | = | -23A + 1 | |||
| X | = | -A + (1 -9A)/14 | |||
| X | = | -A + B, | B | = | 1 -9A 14 |
| 14B | = | 1 -9A | |||
| 9A | = | -14B + 1 | |||
| A | = | -B + (1 -5B)/9 | |||
| A | = | -B + C, | C | = | 1 -5B 9 |
| 9C | = | 1 -5B | |||
| 5B | = | -9C + 1 | |||
| B | = | -C + (1 -4C)/5 | |||
| B | = | -C + D, | D | = | 1 -4C 5 |
| 5D | = | 1 -4C | |||
| 4C | = | -5D + 1 | |||
| C | = | -D + (1 -D)/4 | |||
| C | = | -D + E, | E | = | 1 -D 4 |
| 4E | = | 1 -D | |||
| D | = | -4E + 1 |
At this point we have a single variable in terms of another variable. What is left to do is to substitute all the variables until we get an X and Y.
| D | = | -4E + 1, | ||||||
| C | = | -D + E, | C | = | -(-4E + 1) + E, | C | = | 5E - 1 |
| B | = | -C + D, | B | = | -(5E - 1) + (-4E + 1), | B | = | -9E + 2 |
| A | = | -B + C, | A | = | -(-9E + 2) + (5E - 1), | A | = | 14E - 3 |
| X | = | -A + B, | X | = | -(14E - 3) + (-9E + 2), | X | = | -23E + 5 |
| Y | = | -X + A, | Y | = | -(-23E + 5) + (14E - 3), | Y | = | 37E -8 |
Now that X and Y are in terms of E, the solutions are when E ranges through the Integers.
| E | = | -1, | 37(-23(-1)+5) + 23(37(-1)-8) | = | 1, | 37(28) + 23(-45) | = | 1, | 1036 + -1035 | = | 1 |
| E | = | 0, | 37(-23(0)+5) + 23(37(0)-8) | = | 1, | 37(5) + 23(-8) | = | 1, | 185 + -184 | = | 1 |
| E | = | 1, | 37(-23(1)+5) + 23(37(1)-8) | = | 1, | 37(-18) + 23(29) | = | 1, | -666 + 667 | = | 1 |