A060968 Number of solutions to x^2 + y^2 == 1 (mod n).

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

Offset: 1

Author

Ahmed Fares (ahmedfares(AT)my-deja.com), May 09 2001

Keywords

• nonn
• easy
• mult

Comments

From Jianing Song, Nov 05 2019: (Start)

a(n) is also the order of the group SO(2,Z_n), i.e., the group of 2 X 2 matrices A over Z_n such that A*A^T = E = [1,0;0,1] and det(A) = 1. Elements in SO(2,Z_n) are of the form [x,y;-y,x] where x^2+y^2 == 1 (mod n). For example, SO(2,Z_4) = {[1,0;0,1], [0,1;3,0], [1,2;2,1], [2,1;3,2], [3,0;0,3], [0,3;1,0], [3,2;2,3], [2,3;1,2]}. Note that SO(2,Z_n) is abelian, and it is isomorphic to the multiplicative group G_n := {x+yi: x^2 + y^2 = 1, x,y in Z_n} where i = sqrt(-1), by the mapping [x,y;-y,x] <-> x+yi. See my link below for the group structure of SO(2,Z_n).

The exponent of SO(2,Z_n) (i.e., least e > 0 such that x^e = E for every x in SO(2,Z_n)) is given by A235863(n).

The rank of SO(2,Z_n) (i.e., the minimum number of generators) is omega(n) if n is not divisible by 4, omega(n)+1 if n is divisible by 4 but not by 8 and omega(n)+2 if n is divisible by 8, omega = A001221. (End)

In general, let R be any commutative ring with unity, O(m,R) be the group of m X m matrices A over R such that A*A^T = E and SO(m,R) be the group of m X m matrices A over R such that A*A^T = E and det(A) = 1, then O(m,R)/SO(m,R) = {square roots of unity in R*}, where R* is the multiplicative group of R. This is because if we define f(M) = det(M) for M in O(m,R), then f is a surjective homomorphism from O(m,R) to {square roots of unity in R*}, and SO(m,R) is its kernel. See also A182039. - Jianing Song, Nov 08 2019

Examples

			a(3) = 4 because the 4 solutions are (0,1), (0,2), (1,0), (2,0).
		

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
• Jianing Song, Structure of the group SO(2,Z_n).
• László Tóth, Counting solutions of quadratic congruences in several variables revisited, arXiv preprint arXiv:1404.4214 [math.NT], 2014.
• László Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014), Article 14.11.6.

Crossrefs

Cf. A006752, A060594, A087784.

Cf. A027748, A124010.

Cf. A235863, A182039.

Programs

Haskell

a060968 1 = 1
a060968 n = (if p == 2 then (if e == 1 then 2 else 2^(e+1)) else 1) *
   (product $ zipWith (*) (map (\q -> q - 2 + mod q 4) ps'')
                          (zipWith (^) ps'' (map (subtract 1) es'')))
   where (ps'', es'') = if p == 2 then (ps, es) else (ps', es')
         ps'@(p:ps) = a027748_row n; es'@(e:es) = a124010_row n
-- Reinhard Zumkeller, Aug 05 2014

Mathematica

fa=FactorInteger; phi[p_,s_] := Which[Mod[p,4] == 1, p^(s-1)*(p-1), Mod[p,4]==3, p^(s-1)*(p+1), s==1, 2, True, 2^(s+1)]; phi[1]=1; phi[n_] := Product[phi[fa[n][[i,1]], fa[n][[i,2]]], {i, Length[fa[n]]}]; Table[phi[n], {n,1,100}]

PARI

a(n)=my(f=factor(n)[,1]);n*prod(i=if(n%2,1,2),#f,if(f[i]%4==1, 1-1/f[i], 1+1/f[i]))*if(n%4,1,2) \\ Charles R Greathouse IV, Apr 16 2012

Formula

Multiplicative, with a(2^e) = 2 if e = 1 or 2^(e+1) 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). - David W. Wilson, Jun 19 2001

a(n) = n * (Product_{prime p|n, p == 1 (mod 4)} (1 - 1/p)) * (Product_{prime p|n, p == 3 (mod 4)} (1 + 1/p)) * (1 + [4|n]) where "[ ]" is the Iverson bracket. - Ola Veshta (olaveshta(AT)my-deja.com), May 18 2001

a(n) = A182039(n)/A060594(n). - Jianing Song, Nov 08 2019

Sum_{k=1..n} a(k) ~ c * n^2 + O(n*log(n)), where c = 5/(8*G) = 0.682340..., where G is Catalan's constant (A006752) (Tóth, 2014). - Amiram Eldar, Oct 18 2022