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

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.

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

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.
• 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. Apr 23 '19 at 7:56
I actaully got the answer to my own question $$p_{1208198749} = 27788571557 \equiv 330 \mod(1208198749)$$