2519, and the Shift That Turns Nine Congruences Into One

Find the smallest positive whole number that leaves remainder 1 when divided by 2, remainder 2 when divided by 3, remainder 3 when divided by 4, and so on all the way to remainder 9 when divided by 10.

Nine conditions, and every one of them is a genuine constraint. Written out as a system of congruences the problem looks like an afternoon of work, and the standard tool for such systems does not even apply here. The answer is 2519, and there is a route to it that fits on one line.

Read the nine lines before solving them

The nine conditions are

and they all say the same thing. In each line the remainder is one less than the divisor. A number that leaves remainder 9 on division by 10 is one short of a multiple of 10. A number that leaves remainder 3 on division by 4 is one short of a multiple of 4. So add one to $x$ and every line collapses.

Nine separate congruences have become one sentence: $x + 1$ is divisible by every integer from 2 to 10. The nine unknown remainders are gone, and so is any need to combine anything.

The smallest such shift

A number divisible by all of $2, 3, \dots, 10$ is a common multiple of them, and the smallest positive one is by definition their least common multiple. To build it, take the highest power of each prime that appears anywhere in the list. The 8 in the list forces $2^3$ and the 9 forces $3^2$:

And minimality comes free. The smallest positive $x$ corresponds to the smallest positive value of $x + 1$, which is the least common multiple by definition. No separate argument is needed, which is another way of saying that the shift did not just find a solution, it found the solution set.

The slow route works, which is why it is dangerous

Nothing above is a proof that grinding out the nine congruences fails. It does not fail. Merge them two at a time in any order and you arrive at $x \equiv 2519 \pmod{2520}$, correctly. It takes a few minutes rather than a few seconds, and it takes care, because the moduli are not pairwise coprime and merging in that setting has a condition on it.

The Chinese remainder theorem in its usual form asks for pairwise coprime moduli, and $2, 3, \dots, 10$ are anything but: 2 divides 4, 6, 8 and 10, and 3 divides 6 and 9. Two congruences $x \equiv a \pmod{m}$ and $x \equiv b \pmod{n}$ with a shared factor are solvable exactly when

and when they are, the merged modulus is $\operatorname{lcm}(m,n)$ rather than $mn$. Here condition (5) holds at every step, which is not luck: all nine congruences are shadows of the single statement $2520 \mid x+1$, so they cannot contradict each other. Redundancy is the reason the system is easy and also the reason it looks hard.

The tempting wrong number

The near miss to know about is 209. It comes from multiplying the primes below 11 and forgetting the powers: $2 \cdot 3 \cdot 5 \cdot 7 = 210$, so $209$. It is a good near miss because it satisfies six of the nine conditions, all the ones whose divisor is squarefree. It fails at 4, 8 and 9. Checking the first one is enough: $209 = 52 \cdot 4 + 1$, so it leaves remainder 1 where 3 was required.

The same problem with different lists

The structure survives any upper limit. Asking for remainders $1, 2, \dots, n-1$ against divisors $2, 3, \dots, n$ gives $x = \operatorname{lcm}(2,\dots,n) - 1$. Extending our list by one more line, up to remainder 10 on division by 11, gives $\operatorname{lcm}(2,\dots,11) = 27720$ and so $x = 27719$. These least common multiples grow fast, roughly like $e^{n}$, because every new prime multiplies the answer. Running the list to 20 gives $\operatorname{lcm}(2,\dots,20) = 232{,}792{,}560$, so the same puzzle phrased with nineteen conditions has an answer just under a quarter of a billion, and it is still one subtraction away.

The word "positive" in the question is also doing something. Take $k = 0$ in the solution set and you get $x = -1$, which satisfies all nine conditions perfectly well in the integers: dividing $-1$ by 4 gives quotient $-1$ and remainder 3, as required, and the same happens at every divisor. So $-1$ is the real centre of this problem, and 2519 is only the first solution that happens to be positive. Seeing that is another way of noticing the shift: the whole solution set is the multiples of 2520, moved back by one.

The shift also works whenever the remainders are a constant amount below their divisors, not only one. If every condition read "remainder $d - 3$ on division by $d$", then $x + 3$ is the common multiple and $x = 2520 - 3 = 2517$, valid as long as each remainder stays non-negative, which here means $d \ge 3$.

Where the trick stops

Change one remainder and the structure is gone. Ask for remainder 1 on division by 2, remainder 2 on division by 3, and then remainder 2 on division by 4, and no shift lines the conditions up, because the offsets are now 1, 1 and 2. Worse, that particular system has no solution at all: remainder 2 modulo 4 forces $x$ even, while remainder 1 modulo 2 forces it odd. Condition (5) is what detects this, with $\gcd(2,4) = 2$ and $1 \not\equiv 2 \pmod 2$.

That is the real lesson of the problem. The elegant route exists because the nine lines are one line in disguise, and the first thing to do with a wall of congruences is to look for the disguise. When there is not one, the grind is what you have, and the coprimality caveat is what keeps it honest.

Sources and further reading

• The quantity in equation (3) — Least common multiple
• The theorem that does not quite apply, and its general form — Chinese remainder theorem
• The notation in equation (1) — Modular arithmetic

The answer and its minimality were both checked by exhaustive search over every integer up to 20,000, since no identity can establish minimality on its own. The pairwise merge was also run in both directions and returns 2519 modulo 2520, so the slow route is verified to work rather than merely assumed to.