What number has a remainder of 9 when divided by 10, a remainder of 8 when divided by 9, a remainder of 7 when divided by 8 and so on until a remainder of 0 when divided by 1?
Solution
The first idea that comes to mind for a problem like this is chinese remainder, which solves a concurrent modular relation like stated here. The problem however is that all modules need to be co-prime. Of course, we could skip mod 1, since the result is always zero for natural numbers. We could also skip divisor 2, since we already know that we're looking for odd numbers by the other constraints. We could continue on that and try to remove every duplicate prime factor. However, there is a much easier solution to this problem.
How do you normally calculate the integer solution plus rest of \(\frac{x}{y} \in\mathbb{Q} \)? You first search the next smaller number \(x^-\) which is divisible by \(y\) and calculate the rest like this
\[x-x^-=x\mod y\]
You can also go the other way round and search the next greater number \(x^+\) which is divisible by \(y\). The rest is the difference of \(x\) and \(x^+\) plus \(y\):
\[x-x^++y=x\mod y\]
We know from the problem statement that the rest of every division is always one smaller than the divisor \(y\), from which follows that
\[x-x^++y = y - 1\]
We can simplify and solve for \(x\):
\[x = x^+ - 1\]
This result states that the number \(x\) we're looking for is just a number which is divisible by all \(y\) and then reduced by one. In order to get a number that is divisible by all stated divisors and is minimal, we calculate the least common multiple (LCM):
\[x^+ = lcm(1, 2, ..., 10) = 2520\]
And okay, calculating \(x\) from the derived equation should be simple now:
\[x = 2520 - 1 = 2519\]