

A060968


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


24



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


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


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. Tóth, Counting solutions of quadratic congruences in several variables revisited, arXiv preprint arXiv:1404.4214 [math.NT], 2014.
L. Toth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014) # 14.11.6.


FORMULA

Multiplicative, with a(2^e) = 2 if e = 1 or 2^(e+1) if e > 1, a(p^e) = (p1)p^(e1) if p == 1 (mod 4), a(p^e) = (p+1)p^(e1) if p == 3 (mod 4).  David W. Wilson, Jun 19 2001
a(n) = n * product{ 1  1/p, p is prime, p  n and p = 1 mod 4 } * product{ 1 + 1/p, p is prime, p  n and p = 3 mod 4 } * {2, if 4  n }.  Ola Veshta (olaveshta(AT)mydeja.com), May 18 2001
a(n) = A182039(n)/A060594(n).  Jianing Song, Nov 08 2019


EXAMPLE

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


MATHEMATICA

fa=FactorInteger; phi[p_, s_] := Which[Mod[p, 4] == 1, p^(s1)*(p1), Mod[p, 4]==3, p^(s1)*(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}]


PROG

(PARI) a(n)=my(f=factor(n)[, 1]); n*prod(i=if(n%2, 1, 2), #f, if(f[i]%4==1, 11/f[i], 1+1/f[i]))*if(n%4, 1, 2) \\ Charles R Greathouse IV, Apr 16 2012
(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


CROSSREFS

Cf. A060594, A087784.
Cf. A027748, A124010.
Cf. A235863, A182039.
Sequence in context: A031401 A191333 A078479 * A323651 A151569 A016635
Adjacent sequences: A060965 A060966 A060967 * A060969 A060970 A060971


KEYWORD

nonn,easy,mult


AUTHOR

Ahmed Fares (ahmedfares(AT)mydeja.com), May 09 2001


STATUS

approved



