The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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) = (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{ 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)my-deja.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^(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}] PROG (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 (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)my-deja.com), May 09 2001 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 14 20:21 EDT 2021. Contains 345038 sequences. (Running on oeis4.)