|
Search: id:A060594
|
|
|
| A060594 |
|
Number of non-congruent solutions of x^2 == 1 mod n (square roots of unity mod n). |
|
+0
17
|
|
| 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, 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, 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
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
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
a(q) = number of real characters modulo q. - Benoit Cloitre (benoit7848c(AT)orange.fr), Feb 02 2003
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
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]
|
|
REFERENCES
|
G. Tenenbaum, "Introduction a la theorie analytique et probabiliste des nombres", Cours specialise, 1995, Collection SMF, p. 260
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].
Trygve Nagell, Introduction to Number Theory, AMS Chelsea, 1981, p. 100. [From T. D. Noe (noe(AT)sspectra.com), May 22 2009]
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=1..1000
S. R. Finch and Pascal Sebah, Squares and Cubes Modulo n (arXiv:math.NT/0604465).
K. Matthews, Solving the congruence x^2=a(mod m)
|
|
FORMULA
|
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
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
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
|
|
EXAMPLE
|
The four numbers 1^2, 3^2, 5^2 and 7^2 are congruent to 1 mod 8, so a(8)=4.
|
|
PROGRAM
|
(PARI) a(n)=sum(i=1, n, if((i^2-1)%n, 0, 1))
|
|
CROSSREFS
|
Cf. A005087.
Cf. A046073, A000010.
Sequence in context: A125918 A083533 A076500 this_sequence A104361 A086876 A066691
Adjacent sequences: A060591 A060592 A060593 this_sequence A060595 A060596 A060597
|
|
KEYWORD
|
nonn,mult
|
|
AUTHOR
|
Jud McCranie (j.mccranie(AT)comcast.net), Apr 11 2001
|
|
|
Search completed in 0.003 seconds
|
