I'd like to solve this question using Diophantine equations:
We have an unknown number of coins. If you make 77 strings of them, you are 50 coins short; but if you make 78 strings, it is exact. How many coins are there? [Hint: If $N$ is the number of coins, then $N=77x+27=78y$].
I already have the following, but somewhere I'm going wrong.
- Need to solve: $77x+27=78y$. This gives the Diophantine equation: $77x+(-78)y=-27$ (so $ax+by=c$ with $a=77$, $b=-78$ and $c=-27$).
- Next step: $\gcd(a,b)=\gcd(77,-78)=1=(-1)(77)+(-1)(-78)$.
- Multiply by $-27$ to get the Diophantine equation: $-27=27(77)+27(-78)$. So $x_0=27$ and $y_0=27$ (this is already one solution).
- All other solutions are then given by: $x=x_0+bt=27-78t$ and $y=y_0-at=27-77t$.
- $x,y\geq0$ and integer, so $27-78t\geq0$ and $27-77t\geq0$. So $t\leq0$.
At this point I'm stuck. According to this, all integers $t\leq0$ should suffice, but only $t=0$ suffices. Can anyone find my mistake? Thanks in advance!