 # Problem of the Week Problem E and Solution Number Crunching

## Problem

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$$? ## Solution

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$$.