The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS"). Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A060594 Number of solutions to x^2 == 1 (mod n), that is, square roots of unity modulo n. 49
 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; refs; listen; history; text; internal format)
 OFFSET 1,3 COMMENTS Sum_{k=1..n} a(k) appears to be asymptotic to C*n*log(n) with C = 0.6... - Benoit Cloitre, Aug 19 2002 a(q) is the number of real characters modulo q. - Benoit Cloitre, 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*log(n). - Steven Finch, 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). - T. D. Noe, May 22 2009 Shadow transform of A005563. - Michel Marcus, Jun 06 2013 For n > 2, a(n) = 2 iff n is in A033948. - Max Alekseyev, Jan 07 2015 REFERENCES Trygve Nagell, Introduction to Number Theory, AMS Chelsea, 1981, p. 100. [From T. D. Noe, May 22 2009] G. Tenenbaum, Introduction à la théorie analytique et probabiliste des nombres, Cours spécialisé, 1995, Collection SMF, p. 260. J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, pp. 196-197. 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/0604465 [math.NT], 2006-2016. K. Matthews, Solving the congruence x^2=a(mod m) Emilia Mezzetti, RM Miró-Roig, Togliatti systems and Galois coverings, arXiv preprint arXiv:1611.05620 [math.AG], 2016-2018. See Lemma 6.1. John S. Rutherford, Sublattice enumeration. IV. Equivalence classes of plane sublattices by parent Patterson symmetry and colour lattice group type, Acta Cryst. (2009). A65, 156-163. [See Table 4]. N. J. A. Sloane, Transforms L. Toth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014) # 14.11.6. FORMULA If n == 0 (mod 8), a(n) = 2^(A005087(n) + 2); if n == 4 (mod 8), a(n) = 2^(A005087(n) + 1); otherwise a(n) = 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, Feb 02 2003 For n >= 2 A046073(n) * a(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 Multiplicative with a(2) = 1; a(2^2) = 2; a(2^e) = 4 for e > 2; a(q^e) = 2 for q an odd prime. - Eric M. Schmidt, Jul 09 2013 a(n) = 2^A046072(n) for n>2, in accordance with the above formulas by Ahmed Fares. - Geoffrey Critzer, Jan 05 2015 EXAMPLE The four numbers 1^2, 3^2, 5^2 and 7^2 are congruent to 1 modulo 8, so a(8) = 4. MAPLE A060594 := proc(n)    option remember;    local a, b, c;    if type(n, even) then      a:= padic:-ordp(n, 2);      b:= 2^a;      c:= n/b;      min(b/2, 4) * procname(c)    else      2^nops(numtheory:-factorset(n))    fi end proc: map(A060594, [\$1 .. 100]); # Robert Israel, Jan 05 2015 MATHEMATICA a[n_] := Sum[ Boole[ Mod[k^2 , n] == 1], {k, 1, n}]; a[1] = 1; Table[a[n], {n, 1, 103}] (* Jean-François Alcover, Oct 21 2011 *) a[n_] := Switch[Mod[n, 8], 2|6, 2^(PrimeNu[n]-1), 1|3|4|5|7, 2^PrimeNu[n], 0, 2^(PrimeNu[n]+1)]; Array[a, 103] (* Jean-François Alcover, Apr 09 2016 *) PROG (PARI) a(n)=sum(i=1, n, if((i^2-1)%n, 0, 1)) (PARI) a(n)=my(o=valuation(n, 2)); 2^(omega(n>>o)+max(min(o-1, 2), 0)) \\ Charles R Greathouse IV, Jun 06 2013 (PARI) a(n)=if(n<=2, 1, 2^#znstar(n)[3] ); \\ Joerg Arndt, Jan 06 2015 (Sage) print([len(Integers(n).square_roots_of_one()) for n in range(1, 100)]) # Ralf Stephan, Mar 30 2014 (Python) from sympy import primefactors def a007814(n): return 1 + bin(n - 1).count('1') - bin(n).count('1') def a(n):     if n%2==0:         A=a007814(n)         b=2**A         c=n//b         return min(b//2, 4)*a(c)     else: return 2**len(primefactors(n)) print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Jul 18 2017, after the Maple program CROSSREFS Cf. A000010, A005087, A046073, A073103 (x^4 == 1 (mod n)). Sequence in context: A239202 A083533 A076500 * A327813 A104361 A211449 Adjacent sequences:  A060591 A060592 A060593 * A060595 A060596 A060597 KEYWORD nonn,mult AUTHOR Jud McCranie, Apr 11 2001 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 3 18:30 EST 2020. Contains 338912 sequences. (Running on oeis4.)