%I A060594
%S A060594 1,1,2,2,2,2,2,4,2,2,2,4,2,2,4,4,2,2,2,4,4,2,2,8,2,2,2,4,2,4,2,4,4,2,4,
%T A060594 4,2,2,4,8,2,4,2,4,4,2,2,8,2,2,4,4,2,2,4,8,4,2,2,8,2,2,4,4,4,4,2,4,4,4,
%U A060594 2,8,2,2,4,4,4,4,2,8,2,2,2,8,4,2,4,8,2,4,4,4,4,2,4,8,2,2,4,4,2,4,2
%N A060594 Number of non-congruent solutions of x^2 == 1 mod n (square roots of 
               unity mod n).
%C A060594 Sum(k=1,n,a(k)) appears to be asymptotic to C*n*Log(n) with C=0.6... 
               - Benoit Cloitre (benoit7848c(AT)orange.fr), Aug 19 2002
%C A060594 a(q) = number of real characters modulo q. - Benoit Cloitre (benoit7848c(AT)orange.fr), 
               Feb 02 2003
%C A060594 Also number of real Dirichlet characters modulo n and sum(k=1,n,a(k)) 
               is asymptotic to (6/pi^2)*n*ln(n). - S. R. Finch (Steven.Finch(AT)inria.fr), 
               Feb 16 2006
%C A060594 Let P(n) be the product of the numbers less than and coprime to n. By 
               theorem 59 in Nagell (which is Gauss's generalization of Wilson's 
               theorem): for n>2, P = (-1)^(a(n)/2) (mod n). [From T. D. Noe (noe(AT)sspectra.com), 
               May 22 2009]
%D A060594 G. Tenenbaum, "Introduction a la theorie analytique et probabiliste des 
               nombres", Cours specialise, 1995, Collection SMF, p. 260
%D A060594 John S. Rutherford, Sublattice enumeration. IV. Equivalence classes of 
               plane sublattices by parent Patterson symmetry and colour lattice 
               group type, Acta Cryst. (2009). A65, 156163. [See Table 4].
%D A060594 Trygve Nagell, Introduction to Number Theory, AMS Chelsea, 1981, p. 100. 
               [From T. D. Noe (noe(AT)sspectra.com), May 22 2009]
%H A060594 T. D. Noe, <a href="b060594.txt">Table of n, a(n) for n=1..1000</a>
%H A060594 S. R. Finch and Pascal Sebah, <a href="http://arXiv.org/abs/math.NT/0604465">
               Squares and Cubes Modulo n</a> (arXiv:math.NT/0604465).
%H A060594 K. Matthews, <a href="http://www.numbertheory.org/php/squareroot.html">
               Solving the congruence x^2=a(mod m)</a>
%F A060594 If q is the number of distinct odd primes dividing n (sequence A005087) 
               then: if 8 divides n a(n) = 2^(q+2) = 2^(A005087(n) + 2); if n == 
               4 (mod 8) a(n) = 2^(q+1) = 2^(A005087(n) + 1); otherwise a(n) = 2^q 
               = 2^(A005087(n)) - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 29 
               2001
%F A060594 a(n)=2^omega(n)/2 if n==+/-2 (mod 8), a(n)=2^omega(n) if n==+/-1, +/-3, 
               4 (mod 8), a(n)=2*2^omega(n) if n==0 (mod 8), where omega(n)=A001221(n). 
               - Benoit Cloitre (benoit7848c(AT)orange.fr), Feb 02 2003
%F A060594 For n>=2 A046073(n) * A060594(n) = A000010(n) = phi(n) (This gives a 
               formula for A046073(n) using the one in A060594(n) ). - Sharon Sela 
               (sharonsela(AT)hotmail.com), Mar 09 2002
%e A060594 The four numbers 1^2, 3^2, 5^2 and 7^2 are congruent to 1 mod 8, so a(8)=4.
%o A060594 (PARI) a(n)=sum(i=1,n,if((i^2-1)%n,0,1))
%Y A060594 Cf. A005087.
%Y A060594 Cf. A046073, A000010.
%Y A060594 Sequence in context: A125918 A083533 A076500 this_sequence A104361 A086876 
               A066691
%Y A060594 Adjacent sequences: A060591 A060592 A060593 this_sequence A060595 A060596 
               A060597
%K A060594 nonn,mult
%O A060594 1,3
%A A060594 Jud McCranie (j.mccranie(AT)comcast.net), Apr 11 2001