|
%I #59 Apr 21 2024 19:20:38
%S 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,
%T 24,36,64,28,32,32,64,48,32,32,96,36,40,48,64,40,64,44,96,48,48,48,
%U 128,56,40,64,96,52,72,48,128,80,56,60,128,60,64,96,128,48,96,68,128,96,64,72
%N Number of solutions to x^2 + y^2 == 1 (mod n).
%C From _Jianing Song_, Nov 05 2019: (Start)
%C 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).
%C 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).
%C 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)
%C 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
%H Charles R Greathouse IV, <a href="/A060968/b060968.txt">Table of n, a(n) for n = 1..10000</a>
%H Jianing Song, <a href="/A060968/a060968.txt">Structure of the group SO(2,Z_n)</a>.
%H László Tóth, <a href="http://arxiv.org/abs/1404.4214">Counting solutions of quadratic congruences in several variables revisited</a>, arXiv preprint arXiv:1404.4214 [math.NT], 2014.
%H László Tóth, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Toth/toth12.html">Counting Solutions of Quadratic Congruences in Several Variables Revisited</a>, J. Int. Seq. 17 (2014), Article 14.11.6.
%F 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
%F 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
%F a(n) = A182039(n)/A060594(n). - _Jianing Song_, Nov 08 2019
%F 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
%e a(3) = 4 because the 4 solutions are (0,1), (0,2), (1,0), (2,0).
%t 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}]
%o (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
%o (Haskell)
%o a060968 1 = 1
%o a060968 n = (if p == 2 then (if e == 1 then 2 else 2^(e+1)) else 1) *
%o (product $ zipWith (*) (map (\q -> q - 2 + mod q 4) ps'')
%o (zipWith (^) ps'' (map (subtract 1) es'')))
%o where (ps'', es'') = if p == 2 then (ps, es) else (ps', es')
%o ps'@(p:ps) = a027748_row n; es'@(e:es) = a124010_row n
%o -- _Reinhard Zumkeller_, Aug 05 2014
%Y Cf. A006752, A060594, A087784.
%Y Cf. A027748, A124010.
%Y Cf. A235863, A182039.
%K nonn,easy,mult,changed
%O 1,2
%A Ahmed Fares (ahmedfares(AT)my-deja.com), May 09 2001
|
