How much money to add on a Metrocard

[Thomas Klemm]

If you have an HP-42S you can use this program:

u: how much you should add
v: the remaining value on your card

1.05 u + v ≡ 0 (2.5)
gcd(1.05, 2.5) = 0.05
Thus we multiply the equation by 20.

w = 20 v (here we assume that w is an integer)
21 u + w ≡ 0 (50)
21 u ≡ -1w ≡ 49w (50)

21 ENTER
49 ENTER
50 XEQ 'CONG'
19


u ≡ 19 w (50)
u ≡ 19 × 20 v (50)

Here's how you can solve it manually.

We use the Euclidean algorithm to calculate the gcd(1.05, 2.5):

Code:

2.5 ÷ 1.05  = 2;  r = 0.4
1.05 ÷ 0.4  = 2;  r = 0.25
0.4 ÷ 0.25  = 1;  r = 0.15
0.25 ÷ 0.15 = 1;  r = 0.1
0.15 ÷ 0.1  = 1;  r = 0.05
0.1 ÷ 0.05  = 2;  r = 0

Thus gcd(1.05, 2.5) = 0.05.

We know it can be expressed in this manner: 0.05 = 2.5 x + 1.05 y

In this table we're keeping track of the multipliers x and y:

Code:

                               x     y
2.5   = 2.5                    1     0
1.05  =            1.05        0     1
0.4   = 2.5  - 2 × 1.05        1    -2
0.25  = 1.05 - 2 × 0.4        -2     5
0.15  = 0.4  -     0.25        3    -7
0.1   = 0.25 -     0.15       -5    12
0.05  = 0.15 -     0.1         8   -19

And indeed:
2.5 × 8 - 1.05 × 19 = 0.05

or

2.5 × 8 = 1.05 × 19 + 0.05

For each 0.05 we have to add 19 × 1.05 to end up at an integer multiple of 2.5.
But we never have to add more than 50 × 0.05 = 2.5.

Thus we divide the remaining value on your card by 0.05 (or multiply by 20) and multiply that by 19 which is 380 altogether.
From this we take the remainder after division by 50.

Cheers
Thomas