Diophantine equations using Euclidean algorithm

Question

I solved two systems of Diophantine equations using the Euclidean algorithm and I can't figure out where I went wrong because the solutions I test aren't working but I have rechecked my work several times.

a) $56x+72y=40$

using the algorithm:

$72=1*56+16$

$56=3*16+$

$16=2*8+$

so $\gcd(56, 72)=8$. Then,

$8=56-3*16$

$=56-3(72-56)$

$=-3(72)+4(56)$

since $c/\gcd=40/8=5$, $x_0=4(5)=20$ and $y_0=-3(5)=-15$ so all solutions should be $(20+9t,-15+7t)$ since $9=b/\gcd$ and $7=a/\gcd$. Everything looks right to me and matches my notes and all the equations seem to make sense, but when I try solutions with different values of t, the only one that works and actually $=40$ is when $t=0$. I have the same problem with the next system:

b) $101x+40y=1$

using the algorithm the same way as above, I find $\gcd(101,40)=1$, and

$1= 2-1(1)= 2-(19-9*2)= 10(2)-19$

$= 10(21-19)-19 = 10(21)-11(19)$

$= 10(101-40*2)-11(40-21)$

$= 10(101)-20(40)-11(40)+11(101-40*2) = 101(21)+40(-53)$

since $\gcd=1$, $x_0=21$ and $y_0=-53$ so the set of all equations is $(21+40t,-53+101t)$

Answer 1

Let $d = \gcd(a, b)$. The linear Diophantine equation $ax + by = c$ has a solution if and only if $d \mid c$. If $(x_0, y_0)$ is a particular solution of the equation $ax + by = c$, then the general solution is $$x = x_0 + \frac{b}{d}t \qquad y = y_0 - \frac{a}{d}t$$ where $t \in \mathbb{Z}$.

In both problems, you incorrectly set $y = y_0 \color{red}{+} \dfrac{a}{d}t$.

$56x + 72y = 40$

You correctly found the particular solution $(20, -15)$. Let's see what happens when we substitute your general solution $(20 + 9t, -15 + 7t)$ into the equation $56x + 72y = 40$.
\begin{align*} 56x + 72y & = 56(20 + 9t) + 72(-15 + 7t)\\ & = 1120 + 504t - 1008 + 504t\\ & = 40 + 1008t \end{align*} which only yields a correct solution when $t = 0$. We want the $504t$ terms to cancel, which we can achieve by changing the sign of $7t$ to obtain the general solution $(20 + 9t, -15 - 7t)$.

A recommendation: Divide by $\gcd(56, 72, 40) = 8$ first to obtain the equivalent equation $7x + 9y = 5$.

Apply the extended Euclidean algorithm. \begin{align*} 9 & = 1 \cdot 7 + 2\\ 7 & = 3 \cdot 2 + 1\\ 2 & = 2 \cdot 1 \end{align*} Working backwards, we obtain \begin{align*} 1 & = 7 - 3 \cdot 2\\ & = 7 - 3(9 - 7)\\ & = 4 \cdot 7 - 3 \cdot 9 \end{align*} Multiplying both sides of the equation $4 \cdot 7 - 3 \cdot 9 = 1$ by $5$ yields $20 \cdot 7 - 15 \cdot 9 = 5$. Hence, a particular solution of the equation is $(20, -15)$, as you found above.

We have $a = 9$, $b = 7$, $x_0 = 20$, $y_0 = -15$, and $d = \gcd(a, b) = \gcd(9, 7) = 1$, so the general solution is \begin{align*} x & = x_0 + \frac{b}{d}t & y & = y_0 - \frac{a}{d}t\\ & = 20 + \frac{9}{1}t & & = -15 - \frac{7}{1}t\\ & = 20 + 9t & & = -15 - 7t \end{align*} which you can verify by substituting $20 + 9t$ for $x$ and $-15 - 7t$ for $y$ in the equation $56x + 72y = 40$.

$101x + 40y = 1$

You correctly found that $(21, -53)$ is a particular solution. If you correct the sign error in the formula for the general solution, you should obtain $(21 + 40t, -53 - 101t)$.

Answer 2

Okay. First of all your solution is correct till finding the first solution.

You've gone wrong here $(20+9t,-15+7t)$ .Why do you think the solution set is $(20+9t,-15+7t)$. You're adding $t$s to both the sides. You ought to subtract from one side. So the solution becomes $(20+9t,-15-7t)$. Do you realize why? Because $9t \cdot 56 + (-7t) \cdot 72 = 0$.

Try this for the other yourself. :)

Answer 3

Why not make first the obvious $$56x+72y=40\iff 7x+9y=5$$ for which your correct solution $(x,y)=(20,-15)$ stays valid $\large ?$

Now you have $$\begin{cases}7x+9y=5\\7\cdot20+9(-15)=5\end{cases}\Rightarrow7(x-20)+9(y+15)=0\Rightarrow x-20=9t;\space y+15=7t$$ Hence $$(x,y)=(20+9t,-15+7t)$$