OFFSET

1,1

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.

LINKS

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

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

EXAMPLE

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.

MATHEMATICA

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

PROG

(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

CROSSREFS

KEYWORD

nonn

AUTHOR

Dale Taylor, May 25 2016

STATUS

approved