|
Search: id:A060594
|
|
|
| A060594 |
|
Number of non-congruent solutions of x^2 == 1 mod n (square roots of unity mod n). |
|
+0
13
|
|
| 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
|
|
REFERENCES
|
G. Tenenbaum, "Introduction a la theorie analytique et probabiliste des nombres", Cours specialise, 1995, Collection SMF, p. 260
|
|
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.
Adjacent sequences: A060591 A060592 A060593 this_sequence A060595 A060596 A060597
Sequence in context: A125918 A083533 A076500 this_sequence A104361 A086876 A066691
|
|
KEYWORD
|
nonn,mult
|
|
AUTHOR
|
Jud McCranie (j.mccranie(AT)comcast.net), Apr 11 2001
|
|
|
Search completed in 0.003 seconds
|
