Find the smallest $n > 1$ such that the $n$-th prime $p_n \equiv 330 \mod n $.

I was investigating the remainders when the $n$-th prime is divided by $n$. For every positive integer $a < 330$, I have found a prime $p_n$ such that $p_n \equiv a\mod n $. However for $a = 330$, I have not found a solution so far for $n \le 4.5 \times 10^8$. There is no reason to believe why a solution should not exist specifically for 330 so I guess there is a solution which is really large.

  • 1
    $\begingroup$ $2=p_1\equiv 330 \mod 1. $ $\endgroup$ – DanielWainfleet Apr 23 '19 at 6:00
  • 1
    $\begingroup$ @DanielWainfleet Lol yes, 1 divides everything so technically you are right. But lets look at something bigger than 1 :) $\endgroup$ – Nilotpal Kanti Sinha Apr 23 '19 at 6:06
  • $\begingroup$ No solutions $< 10^9$ $\endgroup$ – Nilotpal Kanti Sinha Apr 23 '19 at 6:28
  • $\begingroup$ Obviously you are not interested in integers modulo 1. But I couldn't resist. $\endgroup$ – DanielWainfleet Apr 23 '19 at 20:13

This answer doesn't give a solution but an explanation for why they're rare.

Since $p_n \approx n \ln n$, the remainders $p_n \bmod n$ roughly follow a saw-tooth. Between $e^a$ and $e^{a+1}$ there's only a small range where the modulus is approximately the right value, and even moduli are at a disadvantage because they can only occur when $n$ is odd and $\lfloor \frac{p_n} {n} \rfloor$ is odd. Moreover, the remainder has to be large enough, so the first few teeth are irrelevant.

Combining all these factors, up to $4.5\times 10^8$ there have only been about 20 candidates, so heuristically it's not unexpected that none of them should be successful.

  • $\begingroup$ Thanks for the nice answer. Can you add your calculation for the estimate of 20 candidates? $\endgroup$ – Nilotpal Kanti Sinha Apr 23 '19 at 7:50
  • $\begingroup$ It's very rough and ready. The range $\lfloor \frac{p_n} {n} \rfloor = 7$ is the first to be large enough for 330 to be a possible remainder; $\ln 4.5 \times 10^8 \approx 19.9$, so we're looking at ranges 7,9,11,13,15,17,19. Each of those has at least two candidates in the sense that it must have remainders which bracket the desired 330, and the third candidate is thrown in arbitrarily to account for it not being a perfect sawtooth. $\endgroup$ – Peter Taylor Apr 23 '19 at 7:56
  • $\begingroup$ What was the software that you use for computation on large prime. Sorry for asking it here, you had mentioned it in one of your comments but I am unable to find it. $\endgroup$ – Nilotpal Kanti Sinha Jan 4 at 5:51

I actaully got the answer to my own question $p_{1208198749} = 27788571557 \equiv 330 \mod(1208198749)$


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.