$n/5$, $(n-1)/2$, $(n-2)/3$, $(n-3)/4$ are prime numbers, what is the 18-digit $n$

number theory

$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:

find[] := Module[
   {n},
   n = 10^17 + 55;
   While[True,
    If[PrimeQ[n/5] && PrimeQ[(n - 1)/2] && PrimeQ[(n - 2)/3] && 
      PrimeQ[(n - 3) / 4], Print[n]];
    n = n + 60;
    ];
   ];

This function prints:

100000000004988815
100000000007664215
100000000022080415
100000000029160655
100000000033573415
100000000040231015
100000000041817055
100000000049727335
100000000051723295
100000000054931255
100000000060959095
100000000064312135
100000000064677535
100000000071630215
100000000071773135
100000000075327295
100000000077687455
100000000080714095
100000000082694815
100000000087186415
100000000087903535
100000000097346095
100000000099114295
100000000101532535
100000000104639695
100000000112930495
100000000114337615
100000000120137695
100000000121605295
100000000135502135
100000000138631135
100000000145064095
100000000145786255
100000000145813255
100000000146236495
100000000152464495
100000000154254535
100000000155096215
100000000160340935
100000000162088135
100000000162430015
...

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.

Related Question