A273543 Numbers for which 9 is a nontrivial quadratic residue.

16, 18, 20, 24, 27, 28, 32, 35, 36, 40, 44, 45, 48, 52, 54, 55, 56, 60, 63, 64, 65, 68, 70, 72, 76, 77, 80, 81, 84, 85, 88, 90, 91, 92, 95, 96, 99, 100, 104, 105, 108, 110, 112, 115, 116, 117, 119, 120, 124, 126, 128, 130, 132, 133, 135, 136, 140, 143, 144, 145, 148, 152

Offset: 1

Author

Dale Taylor, May 25 2016

Keywords

• nonn

Comments

Composite numbers greater than 9 may have additional solutions to x^2=9 (mod n) beyond the trivial 3^2 and (n-3)^2 solutions. Numbers may be squarefree, such as 35, 55, 65, 70.

Examples

			For 54, x^2 = 9 (mod 54) has nontrivial solutions 15, 21, 33, 39, and trivial solutions 3, 51. For 57 which is not in the list, x^2 = 9 (mod 57) has only the trivial solutions 3, 54.
		

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Programs

Mathematica

Select[Range[10, 230], Length@PowerModList[9, 1/2, #] > 2 &]

PARI

is(n)=for(k=4,n\2, if(k^2%n==9, return(1))); 0 \\ Charles R Greathouse IV, Jun 08 2016

PARI

is(n)=if(n<16, return(0)); my(v2=valuation(n,2), v3=valuation(n,3), k=n/2^v2/3^v3); if(v2<3 && v3<2, if(v2>1,k>1,!isprimepower(k)), 1) \\ Charles R Greathouse IV, Jun 08 2016

Formula

a(n) ~ n. More specifically, a(n) = n + 2n/log n + O(n/log^2 n). - Charles R Greathouse IV, Jun 08 2016

For n > 12, these are numbers not of the form k*p^e where k is in {1, 2, 3, 6}, p > 3 is prime, and e > 0. - Charles R Greathouse IV, Jun 08 2016