Nearly divisible by all

Number Theory Level 3

Find a positive integer less than 3000 which satisfy the conditions below.

When divided by 1, it leaves a remainder of 0.
When divided by 2, it leaves a remainder of 1.
When divided by 3, it leaves a remainder of 2.
$\ldots$
When divided by 9, it leaves a remainder of 8.
When divided by 10, it leaves a remainder of 9.

The answer is 2519.

1 solution

Mathh Mathh
May 13, 2015

$1,2,3,4,5,6,7,8,9,10\mid x+1\iff \text{lcm}(1,2,3,4,5,6,7,8,9,10)\mid x+1$

$\iff 2^3\cdot 3^2\cdot 5\cdot 7\mid x+1\iff 2520\mid x+1$

with $0\le x<3000$ gives $x=\boxed{2519}$ .

Moderator note:

Nice. Bonus question: Would there be any solution if I added another constraint: "When divided by 11, it leaves a remainder of 10."?

Challenger Master: It would be equivalent to finding $x$ such that

$2^3\cdot 3^2\cdot 5\cdot 7\cdot 11\mid x+1\iff 27\, 720\mid x+1$ , which with $0\le x<3000$ is impossible. Least nonnegative such $x$ is $27\, 719$ .

mathh mathh - 6 years, 1 month ago

Its perfect

Vraj Mistry - 6 years, 1 month ago

Nearly divisible by all

The answer is 2519.

1 solution

Moderator note:

0 pending reports