Inverse einer Matrix mit der Restklasse 29

Question

Wie berechnet man denn das Inverse z.B einer 2x2 Matrix mit der Restklasse 29?

Bsp:

0	1
24	25

Inverse Matrix mit der restklasse 29 soll laut Lösung:

5	23
1	0

 herauskommen aber ich verstehe hier nicht genau wie der Rechenweg dazu ist.

Ich habe mich an den Beitrag von Der_MatheCoach gehalten aber komme nicht auf das gleiche Ergebnis

https://www.mathelounge.de/12565/ist-die-matrix-invertierbar-in-z-3z…

Answer 1

Du schreibst die Matrix hin und daneben die Einheitsmatrix

$$\left. \begin{matrix} 0 & 1\\24 & 25 \end{matrix}~ \middle| ~ \begin{matrix}1&0\\0&1 \end{matrix} \right.$$

Jetzt bringst du links mit elementaren Zeilenumformungen auf die Einheitsmatrix.

1. Zeilen tauschen:

$$\left. \begin{matrix}24 & 25\\ 0 & 1 \end{matrix}~ \middle| ~ \begin{matrix}0&1 \\1&0\end{matrix} \right.$$

2.1. Zweite Zeile von der ersten 25 mal abziehen:

$$\left. \begin{matrix}24 & 0\\ 0 & 1 \end{matrix}~ \middle| ~ \begin{matrix}-25&1 \\1&0\end{matrix} \right.$$

2.2. Alle Zahlen modulo 29 rechnen, -25 mod 29 = -25 + 29 = 4:

$$\left. \begin{matrix}24 & 0\\ 0 & 1 \end{matrix}~ \middle| ~ \begin{matrix}4&1 \\1&0\end{matrix} \right.$$

3.1. Erste Zeile mit dem multiplikativ Inversen von 24 multiplizieren, das ist = 23

$$\left. \begin{matrix}552 & 0\\ 0 & 1 \end{matrix}~ \middle| ~ \begin{matrix}92 &23 \\1&0\end{matrix} \right.$$

3.2 Alle Zahlen modulo 29 rechnen, 552 mod 29 = 1, 92 mod 29 = 5

$$\left. \begin{matrix}1 & 0\\ 0 & 1 \end{matrix}~ \middle| ~ \begin{matrix}5 &23 \\1&0\end{matrix} \right.$$

Das Inverse steht jetzt auf der rechten Seite.

---

Falls du nicht weißt wie man multiplikativ Inverse modulo n bestimmt:

n eine natürliche Zahl, a ist genau dann modulo n invertierbar, wenn ggT(a,n) = 1.

Jetzt berechnet man mit dem erweiterten euklidischen Algorithmus eine Darstellung der Form

ggT(a,n) = u*a + v*n = 1

modulo n steht dann da u*a mod n = 1. Also ist das Inverse u (mod n)

In unserem Beispiel ist ggT(24,29) = 1 = -6*24 + 5*29 und -6 = 23 mod 29

Comments

Vielen Dank das hat mir sehr weitergeholfen

Answer 2

Du suchst eine Matrix $\begin{pmatrix} a & b \\ c & d \end{pmatrix}$ , für die  $\begin{pmatrix} 0 & 1 \\ 24& 25 \end{pmatrix}$· $\begin{pmatrix} a & b \\ c & d \end{pmatrix}$= $\begin{pmatrix} 29j+1 & 29k \\29n & 29m+1 \end{pmatrix}$ gilt.

Daraus folgt

c=29j+1

24a+25c=29n

d=29k

24b+25d =29m +1

Einsetzen der ersten in die zweite Gleichung liefert 24a+25(29j+1)=29n

Betrachtet man diese Gleichung mod 29, ergibt sich

24a+25≡0 mod 29

24a≡4 mod 29

6a≡1 mod 29

Das gilt z,B, für a=5, und bereits aus der ersten Gleichung folgt die Möglichkeit c=1.

Aus der dritten und vierten Gleichung kann man analog b und d bestimmen.