A182039 -id:A182039 - cp's OEIS frontend

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

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

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

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

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.

Cf. A006752, A060594, A087784.
Cf. A027748, A124010.
Cf. A235863, A182039.

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

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}]

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

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

A235863 Exponent of the multiplicative group G_n:={x+iy: x^2+y^2==1 (mod n); 0 <= x,y < n} where i=sqrt(-1).

Original entry on oeis.org

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

Offset: 1

José María Grau Ribas, Jan 16 2014

nonn

From Jianing Song, Nov 05 2019: (Start)
Exponent of the group G is the least e > 0 such that x^e = 1 for every x in G, where 1 is the identity element.
Also the exponent of O(2,Z_n) or SO(2,Z_n). O(2,Z_n) is the group of 2 X 2 matrices A over Z_n such that A*A^T = E = [1,0;0,1]; SO(2,Z_n) is 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. Note that G_n is isomorphic to SO(2,Z_n) by the mapping x+yi <-> [x,y;-y,x]. See A060698 for the group structure of SO(2,Z_n) and A182039 for the group structure of O(2,Z_n). (End)

Andrew Howroyd, Table of n, a(n) for n = 1..10000
José María Grau, A. M. Oller-Marcén, Manuel Rodriguez and Daniel Sadornil, Fermat test with Gaussian base and Gaussian pseudoprimes, arXiv:1401.4708 [math.NT], 2014.
José María Grau, A. M. Oller-Marcén, Manuel Rodriguez and Daniel Sadornil, Fermat test with Gaussian base and Gaussian pseudoprimes, Czechoslovak Mathematical Journal 65(140), (2015) pp. 969-982.

                                   (Z/nZ)*    ------    G_n
Order:                             A000010    ------  A060968.
Exponent:                          A002322    ------  this sequence.
                                     n-1      ------  A201629.
Carmichael/G-Carmichael numbers:   A002997    ------  A235865.
Lehmer /G-Lehmer numbers:          unknown    ------  A235864.
Cyclic/G-cyclic numbers:           A003277    ------  A235866.
n such that the group is cyclic:   A033948    ------  A235868.
Cf. A060698, A182039.

fa=FactorInteger; lam[1]=1;lam[p_, s_] := Which[Mod[p, 4] == 3, p ^ (s - 1 ) (p + 1) , Mod[p, 4] == 1, p ^ (s - 1 ) (p - 1)  , s ≥ 5, 2 ^ (s - 2 ), s > 1, 4, s == 1, 2];lam[n_] := {aux = 1; Do[aux = LCM[aux, lam[fa[n][[i, 1]], fa[n][[i, 2]]]], {i, 1, Length[fa[n]]}]; aux}[[1]] ; Array[lam, 100]

a(n)={my(f=factor(n)); lcm(vector(#f~, i, my([p,e]=f[i,]); if(p==2, 2^max(e-2, min(e,2)), p^(e-1)*if(p%4==1, p-1, p+1))))} \\ Andrew Howroyd, Aug 06 2018

a(2) = 2, a(4) = a(8) = a(16) = 4, a(2^e) = 2^(e-2) for e >= 5; a(p^e) = (p-1)*p^(e-1) if p == 1 (mod 4) and (p+1)*p^(e-1) if p == 1 (mod 4). - Jianing Song, Nov 05 2019

If gcd(n,m)=1 then a(nm) = lcm(a(n), a(m)).

A068197 Number of squares (of another matrix) in M_2(n) - the ring of 2 X 2 matrices over Z_n.

Original entry on oeis.org

1, 10, 29, 48, 223, 290, 865, 344, 1587, 2230, 5341, 1392, 10459, 8650, 6467, 3182, 30745, 15870, 48061, 10704, 25085, 53410, 103489, 9976, 108035, 104590, 118179, 41520, 262291, 64670, 342721, 41736, 154889, 307450, 192895, 76176, 696655, 480610, 303311, 76712, 1051261, 250850, 1272349, 256368, 353901

Offset: 1

Sharon Sela (sharonsela(AT)hotmail.com), Mar 23 2002

a(n) is multiplicative. This is the 2-dimensional analog of A000224.

Giovanni Resta, Table of n, a(n) for n = 1..210

Cf. A000224, A068516, A182039, A209411.

a(n)={my(M=Map()); for(a=0, n-1, for(b=0, n-1, for(c=0, n-1, for(d=0, n-1, mapput(M, lift(Mod([a, b; c, d], n)^2), 1))))); #M} \\ Andrew Howroyd, Aug 06 2018

def A68197(n):
    S = set()
    L = list(range(n))
    for a, b, c, d in cartesian_product([L, L, L, L]):
        M = Matrix([[a, b], [c, d]])
        N = tuple(x % n for x in (M * M).list())
        if N not in S:
           S.add(N)
    print(n, len(S)) # Manfred Scheucher, Jun 12 2015

More terms from Manfred Scheucher, Jun 12 2015
a(45) corrected by Giovanni Resta, Jun 12 2015
a(1) added by Andrew Howroyd, Aug 06 2018

A209411 Number of 2 x 2 matrices M such that M*transpose(M) == 0 mod n.

Original entry on oeis.org

1, 4, 1, 16, 49, 4, 1, 64, 81, 196, 1, 16, 337, 4, 49, 256, 577, 324, 1, 784, 1, 4, 1, 64, 1825, 1348, 81, 16, 1681, 196, 1, 1024, 1, 2308, 49, 1296, 2737, 4, 337, 3136, 3361, 4, 1, 16, 3969, 4, 1, 256, 2401, 7300, 577, 5392, 5617, 324, 49, 64, 1

Offset: 1

José María Grau Ribas, Mar 08 2012

Joerg Arndt, Table of n, a(n) for n = 1..500

Cf. A182039.

gg[n_] := gg[n] = Flatten[Table[{{x, y}, {z, t}}, {x, n}, {y, n}, {t, n}, {z, n}], 3]; nil[n_] := nil[n] = Length@gg[n][[Select[Range[Length[gg[n]]], Mod[gg[n][[#]].Transpose[gg[n][[#]]], n] == {{0, 0}, {0, 0}} &]]]; Table[Print[nil[n]]; nil[n], {n, 1, 22}]

Keyword:mult added by Andrew Howroyd, Aug 02 2018

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A235863 Exponent of the multiplicative group G_n:={x+iy: x^2+y^2==1 (mod n); 0 <= x,y < n} where i=sqrt(-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A068197 Number of squares (of another matrix) in M_2(n) - the ring of 2 X 2 matrices over Z_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Sage

Extensions

A209411 Number of 2 x 2 matrices M such that M*transpose(M) == 0 mod n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Extensions