Diophantine equations using Euclidean algorithm 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)$
 A: 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. :)
A: 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)$.
A: 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)$$ 
