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,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

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

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ászló Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014), Article 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

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)

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
(Python)
from sympy import primefactors
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

Crossrefs

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

Cf. A001620, A306016.

Sequence in context: A083533 A076500 A344887 * A327813 A104361 A211449

Adjacent sequences: A060591 A060592 A060593 * A060595 A060596 A060597

Keyword

nonn,mult

Author

Jud McCranie, Apr 11 2001

Status

approved