1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ $2=p_1\equiv 330 \mod 1. $ $\endgroup$ – DanielWainfleet Apr 23 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 at 6:06
  • $\begingroup$ No solutions $< 10^9$ $\endgroup$ – Nilotpal Kanti Sinha Apr 23 at 6:28
  • $\begingroup$ Obviously you are not interested in integers modulo 1. But I couldn't resist. $\endgroup$ – DanielWainfleet Apr 23 at 20:13
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the nice answer. Can you add your calculation for the estimate of 20 candidates? $\endgroup$ – Nilotpal Kanti Sinha Apr 23 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 at 7:56
0
$\begingroup$

Here are a few sieving steps if you want to refind it.

  1. Note, n must be coprime to 330, if not, neither is the supposed prime. ($\overline{75}\%$ reduced, where the overline means repeat past a decimal place.)
  2. 330 is 0 mod 6. for all n>2 this means n and it's multiplier fit one of the ordered pairs (1,1),(1,5),(5,1),(5,5) mod 6 ( 1 in every 9 pairs, but most of that is taken care of).
  3. mod 7, n and it's multiplier have 6 pairs (of 49) they must avoid.

  4. etc.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.