# what is number of invertible matrix m*m on$z_n$? [closed]

‎‎please help me what is number of invertible matrix $‎m*m$‎‎‎ on Group $\mathbb{z}_n$ ?‎‎‎, assuming we know‎ this number in $\mathbb{Z}_p \quad$ (‎p is prime‎‎) is $‎(p^{n}-1)(p^{n}-p) \cdots (p^n-p^{n-1})‎‎‎‎$

• How is this related to cryptography? $\;$ – user991 Apr 23 '15 at 11:00
• You are talking about the General Linear Group of matrices of degree m over $\mathbb Z_p$. – cygnusv Apr 24 '15 at 7:11
• @Ricky Demer: the OP gives a hint with the tag hill-cipher, which indeed uses as key an invertible $m\times m$ matrix with elements in $\mathbb Z_n$. – fgrieu Apr 24 '15 at 8:32
• The question is in fact a duplicate of this one, which has a satisfactory solution (if not answer in the sense of the CSE website logic) in comment, and as an edit of the question. – fgrieu Apr 24 '15 at 8:35

Assume you know the number of invertible $m \times m$ matrices over $\mathbb{Z}_{p^k}$ for $p$ prime. Call this number $N(p^k)$.

By the Chinese Remainder Theorem, $N(\prod_{i=1}^l p_i^{k_i}) = \prod_{i=1}^l N(p_i^{k_i})$ because a matrix is invertible iff every component in its CRT decomposition is invertible. For $m = 1$, $N$ is just the $\phi$ function.

Finding $N(p^k)$ is another matter.