A060594 Number of solutions to x^2 == 1 (mod n), that is, square roots of unity modulo n.

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

Offset: 1

Author

Jud McCranie, Apr 11 2001

Keywords

• nonn
• mult
• changed

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

For n > 1, number of square numbers on the main diagonal of an (n-1) X (n-1) square array whose elements are the numbers from 1..n^2, listed in increasing order by rows. - Wesley Ivan Hurt, May 19 2021

a(n) is the number of linear Alexander quandles (Z/nZ, k) that are kei (equivalently, that have good involutions); see Ta, Prop. 5.6 and cf. A387317. - Luc Ta, Aug 26 2025

Examples

			The four numbers 1^2, 3^2, 5^2 and 7^2 are congruent to 1 modulo 8, so a(8) = 4.
		

References

• Trygve Nagell, Introduction to Number Theory, AMS Chelsea, 1981, p. 100. [From T. D. Noe, May 22 2009]
• Gérald 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
• Steven R. Finch and Pascal Sebah, Squares and Cubes Modulo n, arXiv:math/0604465 [math.NT], 2006-2016.
• Keith Matthews, Solving the congruence x^2=a(mod m).
• Emilia Mezzetti and Rosa Maria 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ực Ta, Good involutions of twisted conjugation subquandles and Alexander quandles, arXiv:2508.16772 [math.GT], 2025.
• László Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014), Article 14.11.6.

Crossrefs

Cf. A000010, A005087, A033948, A046073, A073103 (x^4 == 1 (mod n)).

Cf. A001620, A306016.

Cf. A387317.

Programs

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 *)

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

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

Python

from sympy import primefactors
def A060594(n): return (1<>(s:=(~n & n-1).bit_length()))))*(1 if n&1 else 1<Chai Wah Wu, Oct 26 2022

Sage

print([len(Integers(n).square_roots_of_one()) for n in range(1,100)]) # Ralf Stephan, Mar 30 2014

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

a(n) = Sum_{k=1..n} floor(sqrt(1+n*(k-1)))-floor(sqrt(n*(k-1))). - Wesley Ivan Hurt, May 19 2021

From Amiram Eldar, Dec 30 2022: (Start)

Dirichlet g.f.: (1-1/2^s+2/4^s)*zeta(s)^2/zeta(2*s).

Sum_{k=1..n} a(k) ~ (6/Pi^2)*n*(log(n) + 2*gamma - 1 - log(2)/2 - 2*zeta'(2)/zeta(2)), where gamma is Euler's constant (A001620). (End)