A330406 a(n) is the smallest prime q such that q^((p-1)/2) == -1 (mod p), where p = A002144(n) is the n-th prime congruent to 1 mod 4.

2, 2, 3, 2, 2, 3, 2, 2, 5, 3, 5, 2, 2, 3, 3, 2, 2, 2, 2, 5, 2, 2, 3, 7, 3, 2, 2, 3, 2, 5, 2, 5, 2, 3, 2, 2, 2, 3, 7, 2, 5, 3, 5, 2, 2, 3, 2, 2, 3, 5, 3, 7, 2, 3, 3, 2, 2, 5, 2, 2, 2, 2, 2, 3, 7, 2, 2, 3, 2, 2, 2, 3, 2, 3, 3, 5, 2, 3, 3, 2, 11, 2, 2, 5, 3, 2, 2, 2, 3, 2, 2, 11, 5, 2, 3, 11, 2, 3, 2, 2, 7, 2, 3, 5, 2, 7, 3, 2, 2

Offset: 1

Author

Nicholas C. Singer, Dec 13 2019

Keywords

• nonn

Comments

Subset of A053760 corresponding to p == 1 (mod 4).

A002144(n) = p is a sum of two integer squares (Fermat): p = a^2 + b^2. To find a and b, calculate gcd(p, A330406(n)^((p-1)/4)+i) = a + bi in the Gaussian integers.

Examples

			Let p = A002144(30)= 313. Then (p-1)/2 = 156. Now 2^156 == 3^156 == 1 (mod p) but 5^156 == -1 (mod p).  Thus A330406(30)=5.
		

Crossrefs

Cf. A002144, A053760.

Programs

Mathematica

Map[Block[{q = 2}, While[PowerMod[q, (# - 1)/2, #] != # - 1, q = NextPrime@ q]; q] &, Select[4 Range[350] + 1, PrimeQ]] (* Michael De Vlieger, Dec 29 2019 *)

PARI

A002144 = select(p->p%4==1, primes(2200));
A330406 = vector(1000); for(i=1, 1000, my(p=A002144[i]); forprime(j=1, 20, my(x=Mod(j, p)^((p-1)/2)); if(x+1, , A330406[i]=j; break)))
A330406