Different Remainders of Three Digit Numbers

Question

I have come across an Olympic Maths style of question. At first glance, the question seemed simple. After going deeper into the question, I couldn't find any shortcut or simple formula to calculate it except for trial and error. The question is as follows:

Some 3-digit numbers have different remainders when dividing by 2, 3, 4, 5 and 6. What is the sum of the smallest two before-mentioned numbers?

Let's ignore that "sum of the smallest two" part, and work out an equation to find out these numbers first.

I found a couple of numbers, like 155 and 118.

Scenario 1

$155 \div 2 = 77 \frac 1 2$ (remainder of 1)

$155\div 3 = 51 \frac 2 3$ (remainder of 2)

$155 \div 4 = 38 \frac 3 4$ (remainder of 3)

$155 \div 5 = 31$ (remainder of 0)

$155 \div 6 = 25 \frac 5 6$ (remainder of 5)

Scenario 2

$118 \div 2 = 59$ (remainder of 0)

$118 \div 3 = 39 \frac 1 3$ (remainder of 1)

$118 \div 4 = 29 \frac 2 4$ (remainder of 2)

$118 \div 5 = 23$ (remainder of 0)

$118 \div 6 = 25 \frac 5 6$ (remainder of 5)

These 2 numbers have different remainders when divided by 2, 3, 4, 5, and 6. but I used trial and error, which takes a long time and is inefficient. To check if 118 was the smallest 3 digit number with this rule, I would have to test every number from 100 to 117. Therefore, a formula or equation is required to do this problem quickly.

I have made up two basic rules to help me with eliminating some of the numbers.

1. The number cannot be a multiple of 4. If the number is a multiple of 4, it is also a multiple of 2, so the remainders for 2 and 4 will be the same, at 0.
2. The number may also not be a multiple of 6. It will also be a multiple of 3 and 2, where 3 remainders will be 0. These two rules eliminate most of the even numbers.

Although this is a quicker process, this still needs time. I am looking for an easy to calculate formula that can help me with this problem. If there isn't a fixed equation, a rule which eliminates most of the numbers is also helpful. Thanks in advance!

Answer 1

The least common multiple of $2,3,4,5,6$ is $60$. If some integer $n$ has the property of having different remainders when divided by $2,3,4,5,6$ then so does $n+60$ and $n-60$.

This means we can restrict our search space to $60$ convenient numbers - say $0$ through to $59$, because all the examples we are looking for will have a counterpart in such a range.

You can also restrict more numbers than you have done already. What happens if $n$ leaves remainder $1$ when divided by $4$ or by $6$?

Also what can the remainders be? There are only $6$ candidates - $0,1,2,3,4,5$, and $5$ can only be a remainder on division by $6$

If you explore these observations you will be able to conclude quite quickly.

Answer 2

You could use the sieve of eratosthenes kind of method. Make a simple table. Rows will be the numbers from 100 the columns represent the remainders. Remainders will be easy to fill. The remainders of 2 will go. 0, 1, 0, 1, 0.. the remainders of 3 will go 1, 2, 0, 1, 2... The remainders of 4 will go 0, 1, 2, 3, 0, 1, 2... The remainders of 5 will go 0, 1, 2, 3, 4, 0, 1, 2, 3, 4.. 6: 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2 Then look at all the columns and the numbers where the values for remainders are all different are the numbers you are looking for.

Answer 3

First convince yourself that each number is either

• $10 \bmod 12 $ and also $3 \bmod 5$

Or

• $11 \bmod 12$ and also $0 \bmod 5$

Or

• $11 \bmod 12$ and also $4 \bmod 5$

then it should be easy.