Inverse modulaire d’une matrice

L’inverse modulaire d’une matrice \(A\) modulo \(n\) est une matrice \(A^{-1}\) telle que le produit avec \(A\) soit congruent à la matrice identité \(I\) modulo \(n\) : $$ A A^{-1} \equiv I \pmod{n} $$

Autrement dit, chaque coefficient du produit est congruent modulo \(n\) au coefficient correspondant de la matrice identité.

Calcul de l’inverse d’une matrice modulo n

Considérons une matrice carrée 2x2 modulo \(n\) :

$$ A = \begin{pmatrix} a & b \\ c & d \end{pmatrix} $$

Pour déterminer l’inverse \(A^{-1}\), on commence par calculer le déterminant de \(A\) modulo \(n\) :

$$ \det(A) $$

Il est indispensable que le déterminant et \(n\) soient premiers entre eux, c’est-à-dire que leur plus grand commun diviseur soit égal à 1. Si ce n’est pas le cas, la matrice \(A\) n’est pas inversible modulo \(n\).

Lorsque \(\gcd(\det(A),n) = 1\), la matrice est inversible et le calcul peut se poursuivre.

$$ \gcd(\det(A),n) = 1 $$

On recherche alors l’inverse multiplicatif du déterminant modulo \(n\), noté \(\det(A)^{-1} \pmod{n}\).

Cela revient à trouver un entier \(\det(A)^{-1}\) vérifiant : $$ \det(A)\cdot \det(A)^{-1} \equiv 1 \pmod{n} $$

Une fois cet inverse déterminé, la formule de l’inverse modulaire de la matrice est la suivante :

$$ A^{-1} \equiv \det(A)^{-1} \cdot \begin{pmatrix} d & -b \\ -c & a \end{pmatrix} \pmod{n} $$

Enfin, on réduit chacun des coefficients de la matrice obtenue dans l’intervalle \([0,\,n-1]\).

Exemple concret

Calculons l’inverse de la matrice suivante modulo \(n=9\) :

$$ B = \begin{pmatrix} 2 & 3 \\ 1 & 4 \end{pmatrix} $$

Son déterminant est :

$$ \det(B) = 2 \cdot 4 - 3 \cdot 1 = 5 \ \pmod{9} $$

Vérifions que \(\det(B)=5\) et \(n=9\) sont premiers entre eux :

$$ \gcd(5,9) = 1 $$

La condition étant remplie, la matrice \(B\) est donc inversible modulo 9.

Remarque. Si \(\det(B)\) et \(n\) n’étaient pas premiers entre eux, la matrice \(B\) ne serait pas inversible et le calcul s’arrêterait immédiatement.

L’inverse multiplicatif de 5 modulo 9 est 2, car :

$$ 5 \cdot 2 \equiv 10 \equiv 1 \pmod{9} $$

Appliquons maintenant la formule de l’inverse d’une matrice 2x2 modulo 9 :

$$ B^{-1} \equiv 2 \cdot \begin{pmatrix} 4 & -3 \\ -1 & 2 \end{pmatrix} \pmod{9} $$

$$ B^{-1} \equiv \begin{pmatrix} 8 & -6 \\ -2 & 4 \end{pmatrix} \pmod{9} $$

On ramène ensuite les coefficients dans l’intervalle \([0,8]\) :

$$ -6 \equiv 3 \pmod{9}, \quad -2 \equiv 7 \pmod{9} $$

On obtient donc :

$$ B^{-1} \equiv \begin{pmatrix} 8 & 3 \\ 7 & 4 \end{pmatrix} \pmod{9} $$

Cet exemple illustre le calcul de l’inverse modulaire d’une matrice 2x2 lorsque le déterminant et \(n\) sont premiers entre eux.