cp's OEIS Frontend

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

%I A060594 #137 Aug 28 2025 00:45:09
%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,
%T A060594 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,
%U A060594 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
%N A060594 Number of solutions to x^2 == 1 (mod n), that is, square roots of unity modulo n.
%C A060594 Sum_{k=1..n} a(k) appears to be asymptotic to C*n*log(n) with C = 0.6... - _Benoit Cloitre_, Aug 19 2002
%C A060594 a(q) is the number of real characters modulo q. - _Benoit Cloitre_, 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*log(n). - _Steven Finch_, 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). - _T. D. Noe_, May 22 2009
%C A060594 Shadow transform of A005563. - _Michel Marcus_, Jun 06 2013
%C A060594 For n > 2, a(n) = 2 iff n is in A033948. - _Max Alekseyev_, Jan 07 2015
%C A060594 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
%C A060594 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
%D A060594 Trygve Nagell, Introduction to Number Theory, AMS Chelsea, 1981, p. 100. [From _T. D. Noe_, May 22 2009]
%D A060594 Gérald Tenenbaum, Introduction à la théorie analytique et probabiliste des nombres, Cours spécialisé, 1995, Collection SMF, p. 260.
%D A060594 J. V. Uspensky and M. A. Heaslet, Elementary Number Theory, McGraw-Hill, NY, 1939, pp. 196-197.
%H A060594 T. D. Noe, <a href="/A060594/b060594.txt">Table of n, a(n) for n = 1..1000</a>
%H A060594 Steven R. Finch and Pascal Sebah, <a href="https://arxiv.org/abs/math/0604465">Squares and Cubes Modulo n</a>, arXiv:math/0604465 [math.NT], 2006-2016.
%H A060594 Keith Matthews, <a href="http://www.numbertheory.org/php/squareroot.html">Solving the congruence x^2=a(mod m)</a>.
%H A060594 Emilia Mezzetti and Rosa Maria Miró-Roig, <a href="http://arxiv.org/abs/1611.05620">Togliatti systems and Galois coverings</a>, arXiv preprint arXiv:1611.05620 [math.AG], 2016-2018. See Lemma 6.1.
%H A060594 John S. Rutherford, <a href="http://dx.doi.org/10.1107/S010876730804333X">Sublattice enumeration. IV. Equivalence classes of plane sublattices by parent Patterson symmetry and colour lattice group type</a>, Acta Cryst. (2009). A65, 156-163. [See Table 4].
%H A060594 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>.
%H A060594 Lực Ta, <a href="https://arxiv.org/abs/2508.16772">Good involutions of twisted conjugation subquandles and Alexander quandles</a>, arXiv:2508.16772 [math.GT], 2025.
%H A060594 László Tóth, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Toth/toth12.html">Counting Solutions of Quadratic Congruences in Several Variables Revisited</a>, J. Int. Seq. 17 (2014), Article 14.11.6.
%F A060594 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
%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_, Feb 02 2003
%F A060594 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
%F A060594 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
%F A060594 a(n) = 2^A046072(n) for n>2, in accordance with the above formulas by Ahmed Fares. - _Geoffrey Critzer_, Jan 05 2015
%F A060594 a(n) = Sum_{k=1..n} floor(sqrt(1+n*(k-1)))-floor(sqrt(n*(k-1))). - _Wesley Ivan Hurt_, May 19 2021
%F A060594 From _Amiram Eldar_, Dec 30 2022: (Start)
%F A060594 Dirichlet g.f.: (1-1/2^s+2/4^s)*zeta(s)^2/zeta(2*s).
%F A060594 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)
%e A060594 The four numbers 1^2, 3^2, 5^2 and 7^2 are congruent to 1 modulo 8, so a(8) = 4.
%p A060594 A060594 := proc(n)
%p A060594    option remember;
%p A060594    local a,b,c;
%p A060594    if type(n,even) then
%p A060594      a:= padic:-ordp(n,2);
%p A060594      b:= 2^a;
%p A060594      c:= n/b;
%p A060594      min(b/2, 4) * procname(c)
%p A060594    else
%p A060594      2^nops(numtheory:-factorset(n))
%p A060594    fi
%p A060594 end proc:
%p A060594 map(A060594, [$1 .. 100]); # _Robert Israel_, Jan 05 2015
%t A060594 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 *)
%t A060594 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 *)
%o A060594 (PARI) a(n)=sum(i=1,n,if((i^2-1)%n,0,1))
%o A060594 (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
%o A060594 (PARI) a(n)=if(n<=2, 1, 2^#znstar(n)[3] ); \\ _Joerg Arndt_, Jan 06 2015
%o A060594 (Sage) print([len(Integers(n).square_roots_of_one()) for n in range(1,100)]) # _Ralf Stephan_, Mar 30 2014
%o A060594 (Python)
%o A060594 from sympy import primefactors
%o A060594 def a007814(n): return 1 + bin(n - 1).count('1') - bin(n).count('1')
%o A060594 def a(n):
%o A060594     if n%2==0:
%o A060594         A=a007814(n)
%o A060594         b=2**A
%o A060594         c=n//b
%o A060594         return min(b//2, 4)*a(c)
%o A060594     else: return 2**len(primefactors(n))
%o A060594 print([a(n) for n in range(1, 101)]) # _Indranil Ghosh_, Jul 18 2017, after the Maple program
%o A060594 (Python)
%o A060594 from sympy import primefactors
%o A060594 def A060594(n): return (1<<len(primefactors(n>>(s:=(~n & n-1).bit_length()))))*(1 if n&1 else 1<<min(2,s-1)) # _Chai Wah Wu_, Oct 26 2022
%Y A060594 Cf. A000010, A005087, A033948, A046073, A073103 (x^4 == 1 (mod n)).
%Y A060594 Cf. A001620, A306016.
%Y A060594 Cf. A387317.
%K A060594 nonn,mult,changed
%O A060594 1,3
%A A060594 _Jud McCranie_, Apr 11 2001