login
A273543
Numbers for which 9 is a nontrivial quadratic residue.
2
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,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
Sequence in context: A178980 A031315 A077914 * A274127 A328736 A348143
KEYWORD
nonn
AUTHOR
Dale Taylor, May 25 2016
STATUS
approved