cp's OEIS Frontend

Number of involutory matrices mod n. - Charles R Greathouse IV, May 29 2013

Old name was: Minimal residue (in absolute value) of A001783(n) (mod n).

If the positive representation for integers modulo n is used this is A160377. Here the symmetric (or minimal) representation for the integers modulo n is used.

From Gauss's generalization of Wilson's theorem (see Weisstein link) it follows that, for n>1, a(n) = -1 if and only if there exists a primitive root modulo n (cf. the Hardy and Wright reference, Theorem 129. p. 102). (Adapted from a comment by Vladimir Shevelev in A001783). - Peter Luschny, Oct 20 2012

T_k(0) = 1 if k == 0 mod 4, but x=0 is not counted as a solution. - Robert Israel, Apr 06 2015

Number of matrices M = [a,b;c,d] with 0 <= a,b,c,d < n such that M*transpose(M) == [1,0;0,1] (mod n).

From Jianing Song, Nov 05 2019: (Start)

Elements in O(2,Z_n) are of the form [x,y;-ty,tx], where x^2+y^2 == 1 (mod n), t^2 == 1 (mod n). Proof: If n = Product_{i=1..k} (p_i)^(e_i), then it can be shown by the Chinese Remainder Theorem that O(2,Z_n) is isomorphic to Product_{i=1..k} O(2,Z_(p_i)^(e_i)), so we can just study the elements in O(2,Z_p^e).

Let M = [x,y;z,w] be such a matrix; according to the conditions we have x^2+y^2 == z^2+w^2 == 1 (mod p^e), x*z+y*w == 0 (mod p^e). Here at least one of x,y is coprime to p^e, otherwise x^2+y^2 cannot be congruent to 1 mod p^e. If gcd(x,p^e) = 1, let t = x^(-1)*w; if gcd(y,p^e) = 1, let t = -y^(-1)*z (if gcd(x,p^e) = gcd(y,p^e) = 1 then these two t's are the same), then M = [x,y;-ty,tx] with determinant t, so t^2 == 1 (mod p^e). Specially, the elements in SO(2,Z_n) are of the form [x,y;-y,x], as the determinant is restricted to 1 mod n. See also A060968.

Note that O(2,Z_n) is non-abelian when n > 2: [0,1;-1,0] * [-1,0;0,1] = [0,1;1,0], but [-1,0;0,1] * [0,1;-1,0] = [0,-1;-1,0].

In general, let R be any commutative ring with unity, O(m,R) be the group of m X m matrices M over R such that M*M^T = I and SO(m,R) be the group of m X m matrices M over R such that M*M^T = I and det(M) = 1, then O(m,R)/SO(m,R) is isomorphic to {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. Here, O(2,Z_n) is the internal semiproduct of SO(2,Z_n) and {[a,0;0,1]: a^2 = 1}. As a result:

If p is an odd prime or p^e = 4, then O(2,Z_p^e) is the internal semiproduct of SO(2,Z_p^e) and {I, P}, where I = [1,0;0,1] and P = [-1,0;0,1]. For any M in SO(2,Z_p^e), we have P*M*P = M^(-1). For odd primes p, O(2,Z_p^e) is, in fact, isomorphic to the dihedral group D_(2*(p+1)*p^(e-1)) if p == 3 (mod 4) and D_(2*(p-1)*p^(e-1)) if p == 1 (mod 4), since SO(2,Z_p^e) is cyclic as discussed in A060968. O(2,Z_4) is isomorphic to D_8 X C_2.

If e >= 3, then O(2,Z_2^e) is the internal semiproduct of SO(2,Z_2^e) and {I, P, Q, P*Q}, where I = [1,0;0,1], P = [-1,0;0,1] and Q = [2^(e-1)+1,0;0,1]. For any M in SO(2,Z_2^e), we have P*M*P = M^(-1); Q*M*Q = M if the upper-right entry of M is even, (2^(e-1)+1)*M otherwise.

The exponent of O(2,Z_n) (i.e., least e > 0 such that M^e = I for every M in O(2,Z_n)) is given by A235863(n).

The rank of O(2,Z_n) (i.e., the minimum number of generators) is 2*omega(n) if n is odd, 2*omega(n)-1 if n is even but not divisible by 4, 2*omega(n)+1 if n is divisible by 4 but not by 8 and 2*omega(n)+3 if n is divisible by 8, omega = A001221.

(End) [Comment partly rewritten by Jianing Song, Oct 09 2020]

Rows with indices n in A033948 (or with A046144(n)=0) are empty. Indices of nonempty rows are given by A033949.

This is A228179 without the trivial square roots {1, n-1}.

The number of terms in each nonempty row n is even: A060594(n)-2.

Row n and Row n' are the same if and only if (Z/nZ)* = (Z/n'Z)*, where (Z/nZ)* is the multiplicative group of integers modulo n.

Given n, T(n,k) only depends on gcd(k,psi(n)). For the truncated version see A354060.

Each column is multiplicative.

This sequence is related to A060594: in fact, for every square root of unity modulo n, there are either one or two such groups of order 2n.

For n >= 3, a(n) is also the number of equivalence classes of automorphisms of order 2 (involutions) of the dihedral group D_n (see the reference below). - Tom Edgar, Jul 03 2013

Is a(n)<> 1 iff n in A033948, n>2? [R. J. Mathar, May 21 2009]

Same as A103131, except there -1 appears instead of n-1. By Gauss's generalization of Wilson's theorem, a(n)=-1 means n has a primitive root (n in A033948) and a(n)=1 means n has no primitive root (n in A033949). [T. D. Noe, May 21 2009]

The trivial solutions of the congruence x^2 == 1 (mod 3*prime(n+2)), n>=1, with the primes prime(n+2) = A000040(n+2) have positive representatives 1 and 3*prime(n+2)-1. There are all-together four incongruent solutions due to a general theorem (see, e.g., the Hardy-Wright reference, Theorem 122, p. 96, and also A060594) and the fact that the number of incongruent solutions of this congruence with odd prime modulus p is two, namely with positive representative p and p-1 (see, e.g., Hardy-Wright, Theorem 109, p. 85). a(n) is the smallest positive odd representative >1 which solves this congruence. The other nontrivial even representative solving this congruence is 3*prime(n+2) - a(n), i.e. 4, 8, 10, 14, 16, 20, ... See 2*A207336.

a(n) solves also the congruence x^2 == 1 (Modd A001748(n+2)), n>=1. For Modd n (not to be confused with mod n) see a comment on A203571. This follows from floor(a(n)^2/3*prime(n+2)) being even, in fact it is 8*A024699(n) (see a comment there), hence a(n)^2 (Modd 3*prime(n+2)) = a(n)^2 (mod 3*prime(n+2)) = 1. For those multiplicative groups Modd 3*p with p an odd prime which are cyclic (this is not possible in the mod case, see A033949), a(n) is the representative of the only other nontrivial solution of this congruence. The representative of the trivial solution is 1 (-1 belongs to the same Modd class). (The conjecture stated here earlier is wrong, that is, the multiplicative group Modd (91=7*13) is non-cyclic. It may still be true for 3*p. - Wolfdieter Lang, Mar 15 2012)