A316566 -id:A316566 - cp's OEIS frontend

A000252 Number of invertible 2 X 2 matrices mod n.

1, 6, 48, 96, 480, 288, 2016, 1536, 3888, 2880, 13200, 4608, 26208, 12096, 23040, 24576, 78336, 23328, 123120, 46080, 96768, 79200, 267168, 73728, 300000, 157248, 314928, 193536, 682080, 138240, 892800, 393216, 633600, 470016, 967680, 373248, 1822176, 738720

Offset: 1

N. J. A. Sloane

For a prime p, a(p) = (p^2 - 1)*(p^2 - p) (this is the order of GL(2,p)). More generally a(n) is multiplicative: if the canonical factorization of n is the Product_{i=1..k} (p_i)^(e_i), then a(n) = Product_{i=1..k} (((p_i)^(2*e_i) - (p_i)^(2*e_i - 2)) * ((p_i)^(2*e_i) - (p_i)^(2*e_i - 1))). - Brian Wallace (wallacebrianedward(AT)yahoo.co.uk), Apr 05 2001, Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 18 2001
a(n) is the order of the automorphism group of the group C_n X C_n, where C_n is the cyclic group of order n. - Laszlo Toth, Dec 06 2011
Order of the group GL(2,Z_n). For n > 2, a(n) is divisible by 48. - Jianing Song, Jul 08 2018

T. D. Noe, Table of n, a(n) for n = 1..1000
Geoffrey Critzer, Combinatorics of Vector Spaces over Finite Fields, Master's thesis, Emporia State University, 2018.
C. J. Hillar and D. L. Rhea, Automorphisms of finite abelian groups, arXiv:math/0605185 [math.GR], 2006.
C. J. Hillar and D. L. Rhea, Automorphisms of finite abelian groups, Amer. Math. Monthly 114 (2007), no 10, 917-923.
J. Overbey, W. Traves and J. Wojdylo, On the Keyspace of the Hill Cipher, Cryptologia, Vol. 29 , Iss. 1, 2005.

The order of GL_2(K) for a finite field K is in sequence A059238.
Row n=2 of A316622.
Row sums of A316566.
Cf. A064767 (GL(3,Z_n)), A305186 (GL(4,Z_n)).
Cf. A000056 (SL(2,Z_n)), A011785 (SL(3,Z_n)), A011786 (SL(4,Z_n)).
Cf. A227499.

Table[n*EulerPhi[n]*Sum[d^2 MoebiusMu[n/d], {d, Divisors[n]}], {n, 21}] (* Jean-François Alcover, Apr 04 2011, after Vladeta Jovovic *)

a(n)=my(f=factor(n)[,1]); n^4*prod(i=1,#f, (1-1/f[i]^2)*(1-1/f[i])) \\ Charles R Greathouse IV, Feb 06 2017

from math import prod
from sympy import factorint
def A000252(n): return prod(p**((e<<2)-3)*(p*(p*(p-1)-1)+1) for p,e in factorint(n).items()) # Chai Wah Wu, Mar 04 2025

a(n) = n^4*Product_{primes p dividing n} (1 - 1/p^2)*(1 - 1/p) = n^4*Product_{primes p dividing n} p^(-3)*(p^2 - 1)*(p - 1). - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 18 2001
Multiplicative with a(p^e) = (p - 1)^2*(p + 1)*p^(4e-3). - David W. Wilson, Aug 01 2001
a(n) = A000056(n)*phi(n), where phi is Euler totient function (cf. A000010). - Vladeta Jovovic, Oct 30 2001
Dirichlet g.f.: zeta(s - 4)*Product_{p prime} (1 - p^(1 - s)*(p^2 + p - 1)). - Álvar Ibeas, Nov 28 2017
a(n) = A227499(n) for odd n; (3/4)*A227499(n) for even n. - Jianing Song, Jul 08 2018
Sum_{k=1..n} a(k) ~ c * n^5 / 5, where c = A330523 = Product_{primes p} (1 - 1/p^2 - 1/p^3 + 1/p^4) = 0.5358961538283379998085... - Vaclav Kotesovec, Aug 20 2021
Sum_{n>=1} 1/a(n) = (Pi^8/3240) * Product_{p prime} (1 - 2/p^2 + 1/p^4 + 1/p^5 + 2/p^6 - 1/p^8) = 1.2059016071... . - Amiram Eldar, Dec 03 2022

More terms from David W. Wilson, Jul 21 2001

A316564 Triangle read by rows: T(n,k) is the number of elements of the group SL(2, Z(n)) with order k, 1 <= k <= A316563(n).

Original entry on oeis.org

1, 1, 3, 2, 1, 1, 8, 6, 0, 8, 1, 7, 8, 24, 0, 8, 1, 1, 20, 30, 24, 20, 0, 0, 0, 24, 1, 7, 26, 24, 0, 74, 0, 0, 0, 0, 0, 12, 1, 1, 56, 42, 0, 56, 48, 84, 0, 0, 0, 0, 0, 48, 1, 15, 32, 144, 0, 96, 0, 96, 1, 1, 98, 54, 0, 98, 0, 0, 144, 0, 0, 108, 0, 0, 0, 0, 0, 144

Offset: 1

Andrew Howroyd, Jul 06 2018

For coprime p,q the group SL(p*q, Z(n)) is isomorphic to the direct product of the two groups SL(p, Z(n)) and SL(q, Z(n)).

			Triangle begins:
  1;
  1,  3,  2;
  1,  1,  8, 6, 0, 8;
  1,  7,  8, 24, 0, 8;
  1,  1, 20, 30, 24, 20, 0, 0, 0, 24;
  1,  7, 26, 24, 0, 74, 0, 0, 0, 0, 0, 12;
  1,  1, 56, 42, 0, 56, 48, 84, 0, 0, 0, 0, 0, 48;
  1, 15, 32, 144, 0, 96, 0, 96;
  1,  1, 98, 54, 0, 98, 0, 0, 144, 0, 0, 108, 0, 0, 0, 0, 0, 144;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..3478 (first 60 rows)

Column 2 is A316553.
Row sums are A000056.
Cf. A316537, A316566, A316586.

MatOrder(M)={my(id=matid(#M), k=1, N=M); while(N<>id, k++;N=N*M); k}
row(n)={my(L=List()); for(a=0, n-1, for(b=0, n-1, for(c=0, n-1, for(d=0, n-1, my(M=Mod([a, b; c, d], n)); if(matdet(M)==1, my(t=MatOrder(M)); while(#L

T(p*q,k) = Sum_{i>0, j>0, k=lcm(i, j)} T(p, i)*T(q, j) for gcd(p, q)=1.

T(n,k) = Sum_{d|k} mu(d/k) A316586(n,d).

A066947 Number of elements of order 2 in GL(2,Z_n).

Original entry on oeis.org

3, 13, 27, 31, 55, 57, 175, 109, 127, 133, 391, 183, 231, 447, 607, 307, 439, 381, 895, 811, 535, 553, 2463, 751, 735, 973, 1623, 871, 1791, 993, 2335, 1875, 1231, 1855, 3079, 1407, 1527, 2575, 5631, 1723, 3247, 1893, 3751, 3519, 2215, 2257, 8511, 2745

Offset: 2

Alec Mihailovs (alec(AT)mihailovs.com), Jan 24 2002 and Mar 24 2002

			a(3000) = (a(8)+1)*(a(3)+1)*(a(125)+1)-1 = (9*4^2 + 2)*(3^2 + 3 + 2)*(5^6 + 5^5 + 2) - 1 = 46204927 because 3000 = 2^3*3*5^3.

Charles R Greathouse IV, Table of n, a(n) for n = 2..10000
Alec Mihailovs, Problem 16 Solution
Alec Mihailovs, Abstract Algebra with Maple
Alec Mihailovs, Chapter 5. Cyclic Groups

Column 2 of A316566.

Cf. A066907, A227867.

Ord2inGL2 := proc(n::posint) local i,j,m,c; if n=1 then return 0 end if; m := ifactors(n)[2]; c := 1; j := 1; if (m[1,1]=2) then j := 2; if m[1,2]=1 then c := 4 elif m[1,2]=2 then c := 28 else c := 9*4^(m[1,2]-1)+32 end if end if; c := c*mul((m[i,1]+1)*m[i,1]^(2*m[i,2]-1)+2,i=j..nops(m))-1 end;

a[n_] := (c[0] = 1; c[1] = 4; c[2] = 28; c[k_] := 9*4^(k-1) + 32; fi = FactorInteger[n]; m = (s = Cases[fi, {2, _}]; If[s == {}, 0, s[[1, 2]]]); p = If[m == 0, fi, Rest[fi]]; p1 = p[[All, 1]]; p2 = p[[All, 2]]; c[m]*Times @@ (p1^(2p2) + p1^(2p2-1) + 2) - 1);
(* Jean-François Alcover, May 19 2011, after Maple prog. *)

a(n)=my(o=valuation(n,2),f=factor(n>>o)); prod(i=1,#f[,1],f[i,1]^(2*f[i,2])+f[i,1]^(2*f[i,2]-1)+2)*if(o, if(o>1, if(o>2, 9*4^(o-1)+32,28),4),1)-1 \\ Charles R Greathouse IV, May 29 2013

If n = 2^m*p^a...q^b where p, ..., q are the odd prime divisors of n, then a(n) = c(m)*(p^{2a} + p^{2a-1} + 2)...(q^{2b} + q^{2b-1} + 2) - 1 where c(0) = 1, c(1) = 4, c(2) = 28 and c(m) = 9*4^{m-1} + 32 for m > 2. The integer function f(n) = a(n)+1 is multiplicative, i.e., f(m*n)=f(m)*f(n) for coprime m and n. - Alec Mihailovs (alec(AT)mihailovs.com), Mar 24 2002
a(n) = A066907(n) - 1. - Andrew Howroyd, Jul 08 2018
a(n) = A227867(n) - 1 for odd n. - Jianing Song, Jul 08 2018

A316565 Maximum order of an element of the general linear group GL(2, Z(n)).

Original entry on oeis.org

1, 3, 8, 6, 24, 24, 48, 12, 24, 60, 120, 24, 168, 48, 60, 24, 288, 24, 360, 60, 168, 330, 528, 24, 120, 168, 72, 84, 840, 120, 960, 48, 440, 816, 420, 36, 1368, 360, 312, 60, 1680, 168, 1848, 330, 180, 1518, 2208, 48, 336, 300, 816, 168, 2808, 72, 1320, 168

Offset: 1

Andrew Howroyd, Jul 06 2018

nonn

Row lengths of A316566.

Cf. A000252, A316563.

Concatenation([1], List([2..10], n->Maximum(List(GL(2, Integers mod n), Order))));

MatOrder(M)={my(id=matid(#M), k=1, N=M); while(N<>id, k++;N=N*M); k}
a(n)={my(m=0); for(a=0, n-1, for(b=0, n-1, for(c=0, n-1, for(d=0, n-1, my(M=Mod([a, b; c, d], n)); if(gcd(lift(matdet(M)), n)==1, m=max(m, MatOrder(M))))))); m}

Conjecture: a(p) = (p-1)*(p+1) for prime p.
From Robert Israel, Dec 19 2019: (Start)
The conjecture is true.  In fact for T in GL(2,Z(p)), the order of T divides p*(p-1) if the characteristic polynomial of T splits over Z(p) and p^2-1 if it doesn't; moreover, if T is the companion matrix of the minimal polynomial of a primitive element of GF(p^2), the order is p^2-1.
a(p^k) <= (p^2-1) p^(k-1).
If m and n are coprime, a(m*n) <= a(m)*a(n). (End)

A316560 Number of cyclic subgroups of the group GL(2, Z(n)), counting conjugates as distinct.

Original entry on oeis.org

1, 5, 28, 62, 176, 148, 610, 696, 1252, 920, 2296, 1972, 4874, 3523, 6040, 6320, 8136, 7348, 14984, 13568, 22124, 11920, 17396, 23952, 29846, 28172, 38044, 47656, 47282, 32908, 75036, 53520, 71768, 42312, 145852, 99892, 123524, 88456, 187036, 179200, 152290

Offset: 1

Andrew Howroyd, Jul 06 2018

nonn

Cf. A053651, A066947, A316537, A316559, A316565, A316566.

Concatenation([1], List([2..7], n->Sum( Filtered( ConjugacyClassesSubgroups( GL(2, Integers mod n)), x->IsCyclic( Representative(x))), Size)));

MatOrder(M)={my(id=matid(#M), k=1, N=M); while(N<>id, k++;N=N*M); k}
a(n)={sum(a=0, n-1, sum(b=0, n-1, sum(c=0, n-1, sum(d=0, n-1, my(M=Mod([a, b; c, d], n)); if(gcd(lift(matdet(M)), n)==1, 1/eulerphi(MatOrder(M)))))))}

a(n) = Sum_{k=1..A316565(n)} 1/phi(A316566(n,k)).

A316584 Array read by antidiagonals: T(n,k) is the number of elements x in GL(2,Z_n) with x^k == I mod n where I is the identity matrix.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 3, 14, 1, 1, 4, 9, 28, 1, 1, 1, 20, 9, 32, 1, 1, 6, 1, 64, 21, 56, 1, 1, 1, 30, 1, 184, 27, 58, 1, 1, 4, 1, 60, 25, 80, 171, 176, 1, 1, 3, 32, 1, 72, 1, 100, 33, 110, 1, 1, 4, 9, 64, 1, 180, 1, 640, 297, 128, 1, 1, 1, 14, 9, 224, 1, 846, 1, 164, 63, 134, 1

Offset: 1

Andrew Howroyd, Jul 07 2018

All columns are multiplicative.

Some terms of this sequence may also be computed using a formula given by Kent Morrison (section 1.11 and 2.5 in the reference). See A053725 for a PARI implementation.

			Array begins:
======================================================
  n\k | 1   2   3    4    5    6   7    8   9   10
------+-----------------------------------------------
    1 | 1   1   1    1    1    1   1    1   1    1 ...
    2 | 1   4   3    4    1    6   1    4   3    4 ...
    3 | 1  14   9   20    1   30   1   32   9   14 ...
    4 | 1  28   9   64    1   60   1   64   9   28 ...
    5 | 1  32  21  184   25   72   1  224  21   80 ...
    6 | 1  56  27   80    1  180   1  128  27   56 ...
    7 | 1  58 171  100    1  846  49  184 171   58 ...
    8 | 1 176  33  640    1  432   1 1024  33  176 ...
    9 | 1 110 297  164    1 1566   1  272 729  110 ...
   10 | 1 128  63  736   25  432   1  896  63  320 ...
   11 | 1 134 111  244 1325  354   1  464 111 5950 ...
   12 | 1 392  81 1280    1 1800   1 2048  81  392 ...
   13 | 1 184 549 1096    1 2736 469 1408 549  184 ...
   14 | 1 232 513  400    1 5076  49  736 513  232 ...
   15 | 1 448 189 3680   25 2160   1 7168 189 1120 ...
   ...

Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.

Column 2 is A066907.

Cf. A053725, A316566, A316586.

T(n,k) = Sum_{d|k} A316566(n, d).

Conjecture: T(p,p) = p^2 for p prime.

A086147 Sum of the orders of the elements in the group GL(2,Z_n).

Original entry on oeis.org

1, 13, 219, 367, 4891, 1977, 36085, 9791, 46731, 39133, 479157, 37119, 1289911, 243703, 375219, 305599, 6991319, 299913, 11500123, 667219, 2610657, 3723423, 40035651, 781127, 14928331, 8544673, 11297307, 4540153, 129539703, 2739477, 209881105, 9748415

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Aug 25 2003

nonn

Eric M. Schmidt, Table of n, a(n) for n = 1..60

Cf. A000252, A036391, A316566.

A086147 := n -> Sum(ConjugacyClasses(GL(2,ZmodnZ(n))), cc->Size(cc) * Order(Representative(cc))); # Eric M. Schmidt, May 18 2013

a(n) = Sum_{k=1..n} k*A316566(n, k). - Andrew Howroyd, Jul 07 2018

Corrected and extended by Eric M. Schmidt, May 18 2013

A229292 Exponent of the group of 2 X 2 invertible matrices over Z/nZ.

Original entry on oeis.org

1, 6, 24, 30, 120, 24, 336, 126, 240, 120, 1320, 120, 2184, 336, 120, 510, 4896, 240, 6840, 120, 336, 1320, 12144, 504, 3120, 2184, 2184, 1680, 24360, 120, 29760, 2046, 1320, 4896, 1680, 240, 50616, 6840, 2184, 2520, 68880, 336, 79464, 1320, 240, 12144

Offset: 1

José María Grau Ribas, Nov 02 2013

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..1000

Cf. A000252, A227477, A316566.

ex[p_, s_] := LCM[p(p^(2 s) - 1), p - 1]; ex[1] := 1; ex[n_] := {aux = 1; Do[aux = LCM[aux, ex[fa[n][[i, 1]], fa[n][[i, 2]]]], {i, 1, Length[fa[n]]}]; aux}[[1]];Table[ex[n], {n, 1, 111}]

a(n)=if(n==1,return(1)); my(f=factor(n)); lcm(vector(#f~,i, f[i,1]*lcm((f[i,1]^(2*f[i,2])-1), f[i,1]-1))) \\ Charles R Greathouse IV, Nov 13 2013

a(p^s) = lcm(p*(p^(2*s) - 1), p - 1); if gcd(m,n)=1 then a(n*m) = lcm(a(n), a(m)).

cp's OEIS Frontend

A000252 Number of invertible 2 X 2 matrices mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A316564 Triangle read by rows: T(n,k) is the number of elements of the group SL(2, Z(n)) with order k, 1 <= k <= A316563(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A066947 Number of elements of order 2 in GL(2,Z_n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A316565 Maximum order of an element of the general linear group GL(2, Z(n)).

Views

Author

Keywords

Crossrefs

Programs

GAP

PARI

Formula

A316560 Number of cyclic subgroups of the group GL(2, Z(n)), counting conjugates as distinct.

Views

Author

Keywords

Crossrefs

Programs

GAP

PARI

Formula

A316584 Array read by antidiagonals: T(n,k) is the number of elements x in GL(2,Z_n) with x^k == I mod n where I is the identity matrix.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A086147 Sum of the orders of the elements in the group GL(2,Z_n).

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Formula

Extensions

A229292 Exponent of the group of 2 X 2 invertible matrices over Z/nZ.

Views

Author

Keywords

Links

Crossrefs