# how many number like $119$

How many 3-digits number has this property like $119$:

$119$ divided by $2$ the remainder is $1$

119 divided by $3$ the remainderis $2$

$119$ divided by $4$ the remainder is $3$

$119$ divided by $5$ the remainder is $4$

$119$ divided by $6$ the remainder is $5$

-
Hint: 59 has the same property (isn't three digits) but 29 doesn't (fails on division by 4). Worth working out for yourself. – Mark Bennet Jan 1 '13 at 13:49
Try adding multiples of $60$ to $119$. – Gerry Myerson Jan 1 '13 at 13:49
What related properties does the number $120=119+1$ have? – Hagen von Eitzen Jan 1 '13 at 13:52

Observe that $119$ leaves remainder $n-1$ when divided by $n$ where $2\le n\le 6$

So, $119+1$ is divisible by $n$ for $2\le n\le 6$

So, we numbers of the form $\operatorname{lcm}(2,3,4,5,6)m-1=60m-1$ where $m$ is any positive integer.

As the required number is of three digits $100\le 60m-1\le 999\implies 2\le m\le 16$

Hence there are $16-2+1=15$ such numbers.

-

Note that

$$x \equiv 1 \mod 2 \\ x \equiv 2 \mod 3 \\ x \equiv 3 \mod 4 \\ x \equiv 4 \mod 5 \\ x \equiv 5 \mod 6$$

is equivalent to

$$x \equiv -1 \mod 2 \\ x \equiv -1 \mod 3 \\ x \equiv -1 \mod 4 \\ x \equiv -1 \mod 5 \\ x \equiv -1 \mod 6$$

And by the Chinese Remainder Theorem, the solution to the latter is easily found to be $x \equiv -1 \mod{\mathrm{lcm}(2,3,4,5,6)}$, or $x \equiv -1 \mod 60$.

So just count the number of $3$-digit numbers $x$ satisfying $x \equiv -1 \mod 60$.

-

Exercises:

Try dividing $420 - 1$ by integers $2, 3, ..., 7$ and note the respective remainders are $1, 2, 3, 4, 5, 6$.

Then note that $420 = \textrm{lcm}\,(2, 3, 4, 5, 6, 7)$

Any $n = k\cdot 420 - 1$, $k\in \mathbb{Z}$, will yield the same remainders when divided by $2, 3, ..., 7$.

Try dividing $840 - 1 = 839\,$ by $\,2,\, 3, \,4, \,5, \,6, \,7,\,8\,$ $\implies$ respective remainders of $\;$...?...

Then note that $840 = \textrm{lcm}\,(2, 3, 4, 5, 6, 7, 8)$.

So the same respective remainders are obtained, when $k\cdot 840 - 1$ is divided by each of $\{2, 3, ..., 8\}$.

Now: What\s the least positive number, that when divided by each of $\{2, 3, 4, 5, 6, 7, 8, 9\}$ gives a corresponding remainder of $\{1, 2, 3, 4, 5, 6, 7, 8\}$?

Find the $\text{lcm}\,(2, 3, 4, 5, 6, 7, 8, 9\} = 2^3\cdot 3^2\cdot 5 \cdot 7 = 840\cdot 3 = 2520.\;$

Subtract $1:\;\;$ $2520 - 1 = 2519 = n_9$.

Test by dividing $n_9$ by each of $2, 3, 4, 5, 6, 7, 8, 9$, to confirm...

There you go.

-

You seek numbers which, when divided by $k$ (for $k=2,3,4,5,6$) gives a remainder of $k-1$. Thus the numbers you seek are precisely those which are one less than a multiple of $k$ for each of these values of $k$. To find all such numbers, consider the lowest common multiple of $2$, $3$, $4$, $5$ and $6$, and count how many multiples of this have three digits.

-

A brute force solution in python:

    >>> def check_remainders(three_digit_number):
...     return all(three_digit_number % n == n -1
...         for n in (2, 3, 4, 5, 6))
...
>>> # Filter a list of all 3-digit numbers with the above function
... all_numbers = filter(check_remainders, range(100, 1000))
>>> print(all_numbers)
[119, 179, 239, 299, 359, 419, 479, 539, 599, 659, 719, 779, 839, 899, 959]
>>>
>>> # "Try adding multiples of 60 to 119", Gerry Myerson said.
... [119 + (i * 60) for i in range(15)]
[119, 179, 239, 299, 359, 419, 479, 539, 599, 659, 719, 779, 839, 899, 959]
>>>
>>> # so how many numbers like these are there?
... print(len(all_numbers))
15

-