A062803 Number of solutions to x^2 == y^2 (mod n).

1, 2, 5, 8, 9, 10, 13, 24, 21, 18, 21, 40, 25, 26, 45, 64, 33, 42, 37, 72, 65, 42, 45, 120, 65, 50, 81, 104, 57, 90, 61, 160, 105, 66, 117, 168, 73, 74, 125, 216, 81, 130, 85, 168, 189, 90, 93, 320, 133, 130, 165, 200, 105, 162, 189, 312, 185, 114, 117, 360, 121, 122, 273

Offset: 1

Author

Ahmed Fares (ahmedfares(AT)my-deja.com), Jul 19 2001

Keywords

• nonn
• mult
• easy

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000
• László Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014) # 14.11.6.

Crossrefs

Cf. A086933, A327767, A332794, A344372.

Programs

Mathematica

f[2, e_] := e*2^e; f[p_, e_] := ((p-1)*e+p)*p^(e-1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 10 2020 *)

Formula

a(n) is multiplicative and, for an odd prime p, a(p) = 2*p - 1.

Multiplicative with a(2^e)=e*2^e and a(p^e)=((p-1)*e+p)*p^(e-1) for an odd prime p. - Vladeta Jovovic, Sep 22 2003

From Ridouane Oudra, Jun 17 2025: (Start)

a(n) = (-1)^n*gcd(n,2)*Sum_{d|n} (-1)^d*d*phi(n/d).

a(n) = A327767(n)*A332794(n).

a(2*n) = 2*A344372(n).

a(2*n+1) = A332794(2*n+1). (End)

Extensions

More terms from Vladeta Jovovic, Sep 22 2003