$n$ is an 18-digit number, while $n/5$, $(n-1)/2$, $(n-2)/3$, $(n-3)/4$ are all primes. Find $n$.
Is there a theorem that can solve this kind of problem?
For example, The Chinese Remainder Theorem could solve issues that if one knows the remainders of the Euclidean division of an integer $n$ by several integers, then one can determine uniquely the remainder of the division of $n$ by the product of these integers, under the condition that the divisors are pairwise coprime.
However, this question is one step further, constraints are not only on the remainder but also on quotients.
So, are there related theorems, or such kind of questions are to be solved by brute force?
Best Answer
This looks more like a programming exercise rather than a number theory problem. It's very easy to conclude that all possible values of $n$ are of the form:
$$n=35k+60$$
The first such number with 18 digits is $100\ 000\ 000\ 000\ 000\ 055$. We just have to find one that produces four primes. It looks like a very difficult job but actually the following code managed to generate a dozen of solutions in less than a minute:
This function prints:
So it's mostly brute force all the way, except in the first step. It's also amazing to see how fast Mathematica's $PrimeQ$ function is for 18 digit numbers.