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

1, 2, 1, 4, 1, 2, 13, 8, 9, 2, 1, 4, 1, 26, 1, 16, 33, 18, 1, 4, 13, 2, 45, 8, 25, 2, 9, 52, 1, 2, 61, 32, 1, 66, 13, 36, 1, 2, 1, 8, 81, 26, 1, 4, 9, 90, 93, 16, 133, 50, 33, 4, 1, 18, 1, 104, 1, 2, 1, 4, 1, 122, 117, 64, 1, 2, 1, 132, 45, 26

Offset: 1

Author

Yuval Dekel (dekelyuval(AT)hotmail.com), Oct 28 2003

Keywords

• mult
• nonn
• easy

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. A087561, A062803, A196525, A328895.

Programs

Maple

A088964 := proc(n) local a,x,y ; a := 0 ; for x from 0 to n-1 do for y from 0 to n-1 do if (x^2-2*y^2) mod n = 0 then a := a+1 ; end if; end do; end do ; a ; end proc:
seq(A088964(n),n=1..70) ; # R. J. Mathar, Jan 07 2011

Mathematica

a[n_] := Product[{p, e} = pe; Which[p == 2, 2^e, Abs[Mod[p, 8] - 4] == 1, (p^2)^Quotient[e, 2], True, (p+e(p-1))p^(e-1)], {pe, FactorInteger[n]}];
Array[a, 100] (* Jean-François Alcover, Apr 08 2020, after Andrew Howroyd *)
f[2, e_] := 2^e; f[p_, e_] := If[MemberQ[{1, 7}, Mod[p, 8]], ((p-1)*e + p)*p^(e-1), p^(2*Floor[e/2])]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 20 2020 *)

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[2*i%n + 1])} \\ Andrew Howroyd, Jul 09 2018

PARI

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

Formula

Multiplicative with a(2^e) = 2^e, a(p^e) = p^(2*floor(e/2)) for p mod 8 = +-3, a(p^e) = ((p-1)*e+p)*p^(e-1) for p mod 8 = +-1. - Andrew Howroyd, Jul 13 2018

Sum_{k=1..n} a(k) ~ c * n^2, where c = (64/Pi^4) * A328895 * A196525 = 0.35720726027165235652... . - Amiram Eldar, Nov 21 2023