Prime 11116667

[enzocreti]

The prime number 11116667 is congruent to 2*1667 (mod 1111) and congruent to 1111 (mod(2*1667)^2).
Are there other examples of this type of prime, primes p congruent to 2*s (mod 1111) and congruent to 1111 mod(4s^2)? where s is a prime.

[Dr Sardonicus]

Originally Posted by enzocreti

The prime number 11116667 is congruent to 2*1667 (mod 1111) and congruent to 1111 (mod(2*1667)^2).
Are there other examples of this type of prime, primes p congruent to 2*s (mod 1111) and congruent to 1111 mod(4s^2)? where s is a prime.

Aw, fer cyin' out loud! Never heard of the Chinese Remainder Theorem?

If s is not 11 or 101, the answer is "yes." For a given prime s, your conditions are

p == 2*s (mod 1111) and p == 1111 (mod 4*s^2)

or alternatively

p == 2*s (mod 11), p == 2*s (mod 101), and p == 1111 (mod 4*s^2)

If s is not 11 or 101, the moduli 11, 101 and 4*s^2 are pairwise relatively prime, so the simultaneous congruences are solvable. Also, the solutions are relatively prime to all three moduli, so the solutions form an arithmetic progression

k*4*11*101*s^2 + r, with

gcd(r, 4*11*101*s^2) = 1.

This AP contains infinitely many primes.

I had Pari-GP barf out just the cases for s < 2000 (s not 11 or 101), for which the first term of the AP (the positive term less than 4*11*101*s^2) is prime.

s p
5 101111
7 172219
31 1723223
53 3180899
71 19721503
89 29467231
97 2372179
109 20103763
163 45274687
197 48589979
199 93301067
331 84582203
349 224114951
359 75783139
463 5145967
647 142328171
659 1193405299
743 876654923
787 29730823
809 2248797827
839 408275291
853 1923799307
1093 1032177847
1123 3970035203
1231 2497316039
1381 3280318031
1489 8354113039
1511 5187252023
1667 11116667
1747 12720774623
1783 4972096307
1811 8422324639
1867 6567039187
1931 16257399071

[CRGreathouse]

By my calculations about a third of all primes should be of this type, though convergence up to this fraction will be slow. Up to ten million I find 144238/664579 = 21.7...%.

Inefficient code:

is(p)=forprime(s=2,7, if((p-1111)%(4*s^2)===0,return(s))); if(p<1787,return(0)); forprime(s=13,sqrtint((p-1111)\4), if((p-1111)%(4*s^2)===0, return(s))); 0