login
Number of invertible 2 X 2 matrices mod n.
33

%I #71 Dec 03 2022 05:44:14

%S 1,6,48,96,480,288,2016,1536,3888,2880,13200,4608,26208,12096,23040,

%T 24576,78336,23328,123120,46080,96768,79200,267168,73728,300000,

%U 157248,314928,193536,682080,138240,892800,393216,633600,470016,967680,373248

%N Number of invertible 2 X 2 matrices mod n.

%C 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

%C 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

%C Order of the group GL(2,Z_n). For n > 2, a(n) is divisible by 48. - _Jianing Song_, Jul 08 2018

%H T. D. Noe, <a href="/A000252/b000252.txt">Table of n, a(n) for n = 1..1000</a>

%H Geoffrey Critzer, <a href="https://esirc.emporia.edu/handle/123456789/3595">Combinatorics of Vector Spaces over Finite Fields</a>, Master's thesis, Emporia State University, 2018.

%H C. J. Hillar and D. L. Rhea, <a href="http://arxiv.org/abs/math/0605185">Automorphisms of finite abelian groups</a>, arXiv:math/0605185 [math.GR], 2006.

%H C. J. Hillar and D. L. Rhea, <a href="http://www.jstor.org/stable/27642365">Automorphisms of finite abelian groups</a>, Amer. Math. Monthly 114 (2007), no 10, 917-923.

%H J. Overbey, W. Traves and J. Wojdylo, <a href="http://jeff.over.bz/papers/undergrad/on-the-keyspace-of-the-hill-cipher.pdf">On the Keyspace of the Hill Cipher</a>, Cryptologia, Vol. 29 , Iss. 1, 2005.

%F 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

%F Multiplicative with a(p^e) = (p - 1)^2*(p + 1)*p^(4e-3). - _David W. Wilson_, Aug 01 2001

%F a(n) = A000056(n)*phi(n), where phi is Euler totient function (cf. A000010). - _Vladeta Jovovic_, Oct 30 2001

%F Dirichlet g.f.: zeta(s - 4)*Product_{p prime} (1 - p^(1 - s)*(p^2 + p - 1)). - _Álvar Ibeas_, Nov 28 2017

%F a(n) = A227499(n) for odd n; (3/4)*A227499(n) for even n. - _Jianing Song_, Jul 08 2018

%F 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

%F 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

%t 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_ *)

%o (PARI) 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

%Y The order of GL_2(K) for a finite field K is in sequence A059238.

%Y Row n=2 of A316622.

%Y Row sums of A316566.

%Y Cf. A064767 (GL(3,Z_n)), A305186 (GL(4,Z_n)).

%Y Cf. A000056 (SL(2,Z_n)), A011785 (SL(3,Z_n)), A011786 (SL(4,Z_n)).

%Y Cf. A227499.

%K nonn,easy,nice,mult

%O 1,2

%A _N. J. A. Sloane_

%E More terms from _David W. Wilson_, Jul 21 2001