Inverse Modulo < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:09 Do 28.11.2013 | | Autor: | capri |
Hallo,
Ich habe mal eine kurze Frage, wenn ich eine 2x2 oder 3x3 Matrix modulo 26 invertieren möchte. Muss ich ja die Inverse zu einer Matrix A bestimmen.
2x2:
wenn ich laut formel 1/det(A) * [mm] \begin{pmatrix}
d & -b \\
-c & a
\end{pmatrix} [/mm] und ich sagen wir mal als det(A)=9 habe.
Habe ich ja [mm] \bruch{1}{9} [/mm] * die Matrix. und wie würde ich das in modulo 26 machen da ich keine Brüche haben darf? (mir ist leider kein bsp eingefallen.)
und 3x3:
genau das selbe Problem eigentlich wenn ich eine Inverse berechne und am ende durch eine Zahl dividieren möchte kann ich ja auch kein Bruch schreiben. wie mache ich das bei modulo berechnungen?
LG
|
|
| |
|
Hallo,
> ..
> Hallo,
>
> Ich habe mal eine kurze Frage, wenn ich eine 2x2 oder 3x3
> Matrix modulo 26 invertieren möchte. Muss ich ja die
> Inverse zu einer Matrix A bestimmen.
>
> 2x2:
>
> wenn ich laut formel 1/det(A) * [mm] \begin{pmatrix}
d & -b \\
-c & a
\end{pmatrix}[/mm] und ich sagen wir mal als
> det(A)=9 habe.
>
> Habe ich ja [mm]\bruch{1}{9}[/mm] * die Matrix. und wie würde ich
> das in modulo 26 machen da ich keine Brüche haben darf?
Nun, du musst dir klar machen, dass mit [mm]\frac{1}{9} \ \mod(26)[/mm] kein Bruch im eigentlichen Sinne gemeint ist, sondern das multiplikativ Inverse zu 9.
Um [mm]\frac{1}{9} \ \mod(26)[/mm] zu bestimmen, löse [mm]9\cdot{}x \ \equiv \ 1 \ \mod(26)[/mm]
Das geht hier per Hand recht schnell, man sieht auf den ersten oder zweiten Blick, dass [mm]x=3[/mm] es tut, denn [mm]9\cdot{}3=27 \ \equiv \ 1 \ \mos(26)[/mm]
Also [mm]\frac{1}{9} \ \hat = \ 3 \ \mod(26)[/mm]
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:35 Do 28.11.2013 | | Autor: | capri |
ok danke.
Was passiert denn wenn man es nicht so leicht hat wie jetzt bei 9? einfach immer ausprobieren oder?
LG
|
|
|
| |
|
Hallo nochmal,
> ok danke.
> Was passiert denn wenn man es nicht so leicht hat wie
> jetzt bei 9? einfach immer ausprobieren oder?
Das wäre aber umständlich und zeitraubend 
Das geht mit dem Euklidischen Algorithmus und Rückwärtseinsetzen (Lemma von Bézout):
Ich zeig's mal für dieses Bsp.:
Ges. [mm]9\cdot{}x\equiv 1 \ \mod(26)[/mm]
Bestimme den [mm]\ggT(9,26)[/mm]
[mm]26=2\cdot{}9+8[/mm]
[mm]9=1\cdot{}8+\red{1}[/mm]
Damit haben wir [mm]\ggT(26,9)=1[/mm]
Lösen wir die Gleichungen aus dem Euklid. Algo. danach auf:
[mm]1=9-1\cdot{}8[/mm] nun die erste nach 8 umstellen und ersetzen:
[mm]\red{1}=9-1\cdot{}8=9-1\cdot{}(26-2\cdot{}9)=\red{3\cdot{}9-26}[/mm]
Also haben wir [mm]9\cdot{}x\equiv \red{1}\equiv \red{3\cdot{}9-26}\equiv 3\cdot{}9 \ \mod(26)[/mm] (letzteres, weil [mm]-26\equiv 0 \ \mod(26)[/mm])
Damit [mm]9\cdot{}x\equiv 9\cdot{}3 \ \mod(26)[/mm]
Nun kannst du 9 kürzen, was [mm]x\equiv 3 \ \mod(26)[/mm] ergibt. (beachte [mm]\ggT(9,26)=1[/mm])
Gruß
schachuzipus
|
|
|
|
