A330423 Least nonsquare k that is a quadratic residue modulo n and is coprime to n.

2, 3, 7, 5, 6, 7, 2, 17, 7, 11, 3, 13, 3, 11, 19, 17, 2, 7, 5, 21, 22, 3, 2, 73, 6, 3, 7, 29, 5, 19, 2, 17, 31, 13, 11, 13, 3, 5, 10, 41, 2, 37, 6, 5, 19, 3, 2, 73, 2, 11, 13, 17, 6, 7, 14, 57, 7, 5, 3, 61, 3, 5, 22, 17, 14, 31, 6, 13, 13, 11, 2, 73, 2, 3, 19, 5, 15

Offset: 1

Author

Jianing Song, Dec 14 2019

Keywords

• nonn

Comments

a(n) > n if and only if n is in A303704.

It seems that lim_{n->oo} a(n)/n = 0. Conjectured last term m such that a(m)/m > 1/k, k = 1, 2, 3, ...: 840, 1680, 2640, 9240, 10920, 10920, 18480, 18480, 21840, 29640, ...

Examples

			k is a coprime quadratic residue modulo 16 if and only if k == 1 (mod 8). Since 1 and 9 are squares, a(16) = 17.
k is a coprime quadratic residue modulo 24 if and only if k == 1 (mod 24). Since 1, 25 and 49 are squares, a(24) = 73.
k is a coprime quadratic residue modulo 840 if and only if k == 1, 121, 169, 289, 361, 529 (mod 840). Since 1, 121, 169, 289, 361, 529, 841, 961 are squares, a(840) = 840+169 = 1009.
		

Links

• Jianing Song, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A303704, A330404.

Programs

PARI

a(n) = my(k=1); while(!issquare(Mod(k,n)) || issquare(k) || gcd(k,n)>1, k++); k