0
$\begingroup$

‎‎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})‎‎‎‎$

$\endgroup$
  • 1
    $\begingroup$ How is this related to cryptography? $\;$ $\endgroup$ – user991 Apr 23 '15 at 11:00
  • 1
    $\begingroup$ You are talking about the General Linear Group of matrices of degree m over $\mathbb Z_p$. $\endgroup$ – cygnusv Apr 24 '15 at 7:11
  • $\begingroup$ @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$. $\endgroup$ – fgrieu Apr 24 '15 at 8:32
  • $\begingroup$ 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. $\endgroup$ – fgrieu Apr 24 '15 at 8:35
0
$\begingroup$

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.

|improve this answer|||||
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.