Problem E and Solution

Number Crunching

While waiting for the bus one day, Leo divided numbers on his calculator. He noticed that when \(44\,000\) is divided by \(18\), the remainder is \(8\). He then noticed that the remainder is also \(8\) when \(44\,000\) is divided by \(24\), and also when \(44\,000\) is divided by \(39\). Leo then set out to find other numbers that had the same remainder (not necessarily \(8\)), when divided by \(18,~24,\) and \(39\).

How many five-digit positive integers have the same remainder when divided by \(18,~24,\) and \(39\)?

Since \(18=2 \times 3 \times 3\), \(24=2 \times 2 \times 2 \times 3\), and \(39=3 \times 13\), the lowest common multiple (LCM) of \(18,~24,\) and \(39\) is LCM\((18,24,39) = 2 \times 2 \times 2 \times 3 \times 3 \times 13 = 936\).

Suppose \(n\) is a positive integer. Then the following statements are true:

Every integer of the form \(936n\)
will have a remainder of \(0\) when
divided by \(18,~24,\) and \(39\).

Every integer of the form \(936n+1\)
will have a remainder of \(1\) when
divided by \(18,~24,\) and \(39\).

Every integer of the form \(936n+2\)
will have a remainder of \(2\) when
divided by \(18,~24,\) and \(39\).

Every integer of the form \(936n+3\)
will have a remainder of \(3\) when
divided by \(18,~24,\) and \(39\).

\(\vdots\)

Every integer of the form \(936n+16\)
will have a remainder of \(16\) when
divided by \(18,~24,\) and \(39\).

Every integer of the form \(936n+17\)
will have a remainder of \(17\) when
divided by \(18,~24,\) and \(39\).

However, every integer of the form \(936n+18\) will not have the same remainder when divided by \(18,~24,\) and \(39\). The remainders will be \(0,~18,\) and \(18\), respectively. Therefore, we need to find the number of five-digit integers that have the form \(936n+r\) where \(0 \leq r \leq 17\).

The smallest five-digit integer that is a multiple of \(936\) can be found by dividing \(10\,000\) by \(936\). Since \(\frac{10\,000}{936} \approx 10.68\), the first five-digit multiple is \(936 \times 11= 10\,296\). This means the integers from \(10\,296\) to \(10\,296+17=10\,313\) have the same remainder when divided by \(18,~24,\) and \(39\).

The largest five-digit integer that is a multiple of \(936\) can be found by dividing \(100\,000\) by \(936\). Since \(\frac{100\,000}{936} \approx 106.84\), the largest five-digit multiple is \(936 \times 106= 99\,216\). This means the integers from \(99\,216\) to \(99\,216+17=99\,233\) have the same remainder when divided by \(18,~24,\) and \(39\). We also note that these are all five-digit integers.

Thus, \(936n\) is a positive five-digit integer for \(11 \leq n \leq 106\). The number of positive five-digit integers that are divisible by \(936\) is \(106 - 11 + 1 = 96\). For each of these multiples of \(936\), there are \(18\) integers that have the same remainder when divided by \(18,~24,\) and \(39\). This gives a total of \(96 \times 18 = 1728\) integers that have the same remainder when divided by \(18,~24,\) and \(39\).

However, we need to check integers near \(10\,000\). The largest multiple of \(936\) that is less than \(10\,000\) is \(936 \times 10 = 9360\). This means the integers between \(9360\) and \(9360+18=9378\) have the same remainder when divided by \(18,~24,\) and \(39\). However, none of these are five-digit integers.

Therefore, the number of five-digit positive integers that have the same remainder when divided by \(18,~24,\) and \(39\) is \(1728\).