A086932 Number of non-congruent solutions of x^2 + y^2 == -1 (mod n).

1, 2, 4, 0, 4, 8, 8, 0, 12, 8, 12, 0, 12, 16, 16, 0, 16, 24, 20, 0, 32, 24, 24, 0, 20, 24, 36, 0, 28, 32, 32, 0, 48, 32, 32, 0, 36, 40, 48, 0, 40, 64, 44, 0, 48, 48, 48, 0, 56, 40, 64, 0, 52, 72, 48, 0, 80, 56, 60, 0, 60, 64, 96, 0, 48, 96, 68, 0, 96, 64, 72, 0, 72, 72, 80, 0, 96, 96

Offset: 1

Author

Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 21 2003

Keywords

• mult
• nonn

Links

• Andrew Howroyd, 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), Article 14.11.6.

Crossrefs

Cf. A060968, A006752.

Programs

Mathematica

a[n_] := If[n == 1, 1, Module[{p, e}, Product[{p, e} = pe; Which[p == 2 && e == 1, 2, p == 2 && e > 1, 0, Mod[p, 4] == 1, (p - 1) p^(e - 1), Mod[p, 4] == 3, (p + 1) p^(e - 1)], {pe, FactorInteger[n]}]]];
a /@ Range[1, 100] (* Jean-François Alcover, Sep 14 2019 *)

PARI

a(n)={my(v=vector(n)); for(i=0, n-1, v[i^2%n + 1]++); sum(i=0, n-1, v[i+1]*v[(-1-i)%n + 1])} \\ Andrew Howroyd, Jul 15 2018

PARI

a(n)={my(f=factor(n)); prod(i=1, #f~, my(p=f[i,1], e=f[i,2]); if(p==2, if(e>1, 0, 2), p^(e-1)*if(p%4==1, p-1, p+1)))} \\ Andrew Howroyd, Jul 15 2018

Formula

Multiplicative, with a(2^e) = 2 if e = 1 or 0 if e > 1, a(p^e) = (p-1)p^(e-1) if p == 1 (mod 4), a(p^e) = (p+1)p^(e-1) if p == 3 (mod 4). - Vladeta Jovovic, Sep 24 2003

Sum_{k=1..n} a(k) ~ c * n^2, where c = 3/(8*G) = 0.409404..., where G is Catalan's constant (A006752). - Amiram Eldar, Oct 18 2022

Extensions

More terms from John W. Layman, Sep 25 2003