|
| |
|
|
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
|
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
|
|
|
LINKS
|
|
|
|
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
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
|
|
|
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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,mult,changed
|
|
|
AUTHOR
|
Ahmed Fares (ahmedfares(AT)my-deja.com), May 09 2001
|
|
|
STATUS
|
approved
|
| |
|
|
