4
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ $\frac{n-3}{4}$ will be a Sophie Germain prime and will have $17$ or $18$ digits. I don't know if there is a convenient online list of SGPs of this size. $\endgroup$ – David Apr 10 '19 at 2:03
  • $\begingroup$ Just taking a shot here, not very experienced with number theory yet: $5(\frac{n}{5}) = n$, therefore $n$ is divisible by 5, $2(\frac{n - 1}{2}) = n - 1$, therefore $n - 1$ is divisible by 2, etc. Then we can already say that $n$ ends in a 5, since it is odd (as 2 divides $n - 1$) and divisible by 5. We also know some things about what divides it. After that, I guess we can say that $n$ is of the form $p_1 \cdot 5, p_2 \cdot 2 +1, p_3 \cdot 3 + 2$, etc., where $p_n$ are prime numbers. I'll do some more thinking because this sounds fun, but hopefully the above helps even a slight amount. $\endgroup$ – kusa Apr 10 '19 at 2:22
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ good try. but 1 min only searched 2*10^8, searching 10^19 must take forever. i suspect there are something more math could help.. $\endgroup$ – athos Apr 10 '19 at 6:12
  • $\begingroup$ @athos I see no point in searching the whole $10^{17}-10^{18}$ range just to prove that the problem has millions of solutions. If we had had only a few, the problem would have been much more interesting. $\endgroup$ – Oldboy Apr 10 '19 at 8:18
  • $\begingroup$ actually the original problem has some checksum constraints to limit the solution, but probably won't speed up the search. I'm looking for some stronger math properties on prime numbers to trim more efficiently. $\endgroup$ – athos Apr 10 '19 at 8:22
  • $\begingroup$ @athos And the checksum is? $\endgroup$ – Oldboy Apr 10 '19 at 8:23
  • $\begingroup$ $n$ is a china ic number, note it as $n_{18}n_{17}...n_2n_1$, the check sum requirement is $7n_{18} + 9n_{17} + 10n_{16} +5n_{15} + 8n_{14} +4n_{13} + 2n_{12}+1n_{11}+ 6n_{10}+ 3n_9 + 7 n_8 + 9n_7 + 10 n_6 + 5 n_5 + 8 n_4 + 4 n_3 + 2 n_2 + 1n_1 = 1 (mod 11)$. link: zh.wikipedia.org/wiki/… $\endgroup$ – athos Apr 10 '19 at 8:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.