1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

You didn't make a mistake. If $(x,y)$ is asolution then clearly $(x+78,y+77)$ is another.

$\endgroup$
  • $\begingroup$ Now I see it. While checking whether $t<0$ would also suffice, I interchanged 77 and 78... So my statement that only $t=0$ suffices, is simply not true. All values for $t\leq0$ suffice. Thanks! $\endgroup$ – user95864 Apr 6 '15 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.