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 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$
1
  • $\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, 2015 at 12:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .