This is not a homework problem, but the one I've run into in real life. I have a subway card on which the remaining balance is \$2.28. One ride on the subway costs \$2.75, and when you refill the card with money, the subway company gives you an 11% bonus (so when you put in \$10, you actually get \$11.10).

I would like to find the least amount (in dollars and cents, so no sub-cent solutions) I can add to get this card to get an exact number of rides, i.e. a multiple of \$2.75.

It sounds like we have to solve $$2.28 + 1.11k = 2.75N$$ with $k,N$ whole and $k$ minimal positive. This is equivalent to $$228 + 111k = 275N$$ and you can factor the left-hand side $$3 \cdot(76 + 37k) = 275 \cdot (3n)$$ where $N=3n$ and $n$ is a positive integer.

Factoring this into primes we get $$3 \cdot \left(2^2 \cdot 19 + 37k\right) = 5^2 \cdot 11 \cdot (3n)$$ Is there a way to solve this completely without trial-and-error by computer? How would I proceed?

Thank you very much.

UPDATE From numerical simulation, I see that the smallest possible such $k$ is 102 and we end up with $$228 + 111 \cdot 102 = 11,550 = 275 \cdot 42.$$ But how would I come up with this analytically?

  • $\begingroup$ could the downvoter please explain the downvote? $\endgroup$ – gt6989b Jul 3 '17 at 10:30

You have $111k = 275N - 228$. For $k$ to be an integer, you would need $$ 275N \equiv 228\pmod{111}$$

You can find many such $N$ by inverting $275\equiv 53\pmod{111}$.

  • $\begingroup$ So you suggest I numerically try every one of $N$ and checking if it satisfies $53N \pmod{111} \equiv 0$? $\endgroup$ – gt6989b Jan 17 '17 at 21:10
  • $\begingroup$ Suppose you have a number $m$ such that $53m\equiv1\pmod{111}$. Then multiplying both sides of the equation above by $m$ gives $N\equiv 228m\pmod{111}$. $\endgroup$ – Hempelicious Jan 17 '17 at 21:16
  • $\begingroup$ You can find $m$ without trial-and-error by factoring $111=3\times37$, and then solving for those two primes, combining the results via the Chinese Remainder theorem. $\endgroup$ – Hempelicious Jan 17 '17 at 21:17
  • 2
    $\begingroup$ In particular, $m=44$, so $N\equiv44\times228\equiv42\pmod{111}$, so taking $N=42$ gives the smallest $k$, 102. $\endgroup$ – Hempelicious Jan 17 '17 at 21:21

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.