Solve the following Diophantine equations for general solutions, if possible:
(a) $101x + 600y= 1001$
(b) $181x + 232y= −100$
(a) Here $\gcd(101, 600) = 1$, which divides 1001. This means the equation has integer solutions.
Because the coefficients are large, we won't use trial and error to find a solution. We'll use Euclid's Algorithm.
$ 600 = 5(101) + 95 $
$ 101 = 1(95) + 6 $
$ 95 = 15(6) + 5 $
$ 6 = 1(5) + 1 $
$ 5 = 5(1) + 0$
Re-arranging
$ 1 = 6 -5 $
$ 1 = 6 - (95 - 15(6)) = -95 + 16(6)$
$ 1 = -95 + 16(101 - 95) $
$ 1 = -17(95) +16(101) $
$ 1 = -17(600 - 5(101)) +16(101) $
$ 1 = -17(600) + 101(101) $
So a solution of $101x + 600y =1$ is $x=101, y=-17$.
Multiplying through by 1001, gives us $101(101\times 1001) + 600(-17 \times 1001) =1001$.
This means a solution of $101x + 600y= 1001$ is
$$x_0=101101, \quad y_0=-17017$$
A general solution is
$$ x = 101101 + 600t, \quad y = -17017 - 101t$$
for any integer $t$.
(b) Here $\gcd(181,232)=1$, which divides -100. This means the equation has integer solutions.
Because the coefficients are large, we won't use trial and error to find a solution. We'll use Euclid's Algorithm.
$ 232 = 1(181) + 51 $
$ 181 = 3(51) + 28 $
$ 51 = 1(28) + 23 $
$ 28 = 1(23) + 5 $
$ 23 = 4(5) + 3 $
$ 5 = 1(3) + 2 $
$ 3 = 1(2) + 1 $
$ 2 = 2(1) + 0 $
Re-arranging
$1 = 3 - 2 = (23 - 4(5)) - (5 - 3)$
$ 1= 23 - 5(5) + 3 = 23 - 5(5) + (23 - 4(5)) = 2(23) - 9(5)$
$ 1 = 2(23) - 9(28-23) = 11(23) -9(28) = 11(51 - 28) - 9(28) = 11(51) -20(28) $
$ 1 = 11(232 - 181) - 20(181 -3(51)) = 11(232) -31(181) + 60(51)$
$ 1 = 11(232) -31(181) + 60(232-181) = 71(232) - 91(181) $
So a solution of $181x + 232y= 1$ is $x=-91, y = 71$.
Multiplying through by -100, gives us $181(-91 \times -100) + 232(71 \times -100) = -100$.
This means a solution of $181x + 232y= −100$ is
$$ x_0 = 9100, \quad y_0 = -7100 $$
A general solution is
$$ x = 9100 + 232t, \quad y = -7100 - 181t$$
for any integer $t$.