Wie berechne ich (multiplikative) Inverse bei der modularen Arithmetik?

...komplette Frage anzeigen

3 Antworten

Für eine lineare Kongruenz aX = b mod m gilt:

1) Es gibt genau dann eine Lösung , wenn der ggT(a,m)  b teilt.
2) Wenn x0 eine Lösung ist, so sind 

   x0,
   x0 +    m/ggT(a,m),
   x0 + 2* m/ggT(a,m),
   x0 + 3* m/ggT(a,m),
  ...
   x0 + (ggT(a,m)-1)* m/ggT(a,m)

    ebenfalls Lösungen. Das sind (modulo m) alle Lösungen.

Beispiel 1: 4X = 2 mod 17
Da ggT(4,17) = 1, gibt es genau eine Lösung (mod 17). Es gilt

 1 = 17 + 4*(-4)
   = 4*(-4)        mod 17
   = 4*13          mod 17

Also (Multiplikation mit 2, denn wir wollen 2 darstellen und nicht 1)

 2 = 4*26          mod 17
   = 4*9           mod 17

Beispiel 2: 4X = 2 mod 8
ggT(4,8) = 4 und teilt 2 nicht, also gibt es keine Lösung.

Beispiel 3: 4X = 2 mod 6
ggT(4,6) = 2. Dieser teilt 2. Also gibt es ggT(4,6) = 2 Lösungen. Es gilt

 2 = 6 + 4*(-1)
   = 4*(-1)        mod 6
   = 4*5           mod 6

Also ist 5 eine Lösung. Die andere erhält man durch Addition von

m/ggT(a,m) = 6/2 = 3.

Also

 5 + 3 = 8
       = 2 mod 6.

Ein großes Dankeschön für die ausführliche Antwort!!!

0

Zu 1.: 13 ist das Inverse von 4. Das heißt aber noch nicht, dass x = 13 auch die Lösung der Gleichung ist. Du berechnest das Inverse ja nur, damit du die Gleichung damit multiplizieren kannst:

4x = 2 (mod 17)

13 * 4x = 13 * 2 (mod 17)

x = 26 (mod 17)

x = 9.

Zu 2.: ggT(4,8) = 4 und nicht 0. Und nein, das impliziert noch nicht, dass die Gleichung keine Lösung hat. Z.B. die Gleichung 4x = 4 (mod 8) hätte unter anderem die Lösung x = 1. Der Grund, aus dem 4x = 2 (mod 8) keine Lösung hat, ist dass ggT(4,8) kein Teiler von der 2 ist. 

Zu 3.: Dass der ggT 2 ist, heißt nur, dass es 2 Lösungen geben könnte oder auch gar keine. Z.B. die Gleichung 4x = 3 (mod 6) wäre unlösbar [wie oben: ggT(4,6) ist kein Teiler von 3].

Zum Berechnen der anderen Lösungen: Setze z = 6 / ggT(4,6). Sei x eine Lösung der Gleichung. Dann sind auch x + z, x + 2z, x + 3z usw Lösungen der Gleichung.

Vielen Dank für die ausführliche Beantwortung!!! Ich habe da wirklich manches falsch bzw. nicht verstanden, du hast mir sehr geholfen!

Liebe Grüße

1

Dürfte ich vielleicht noch fragen, wie man von 13*4x = 13*2 (mod 17) kommt?

0
@kattsiermiau

Bei der Gleichung 4x = 2 (mod 17) würde ich ja gerne "durch 4 teilen", um sie nach x aufzulösen. D.h. ich will mit "1/4" multiplizieren, dann würde da nämlich sowas stehen wie 

x = 1/4 * 2 (mod 17).

Jetzt muss ich halt nur noch wissen, was dieses "1/4" modulo 17 überhaupt ist. Dafür haben wir das Inverse von 4 berechnet: 1/4 ist 13 modulo 17. Also folgt:

x = 13 * 2 (mod 17).

Die obige Gleichung 13 * 4x = 13 * 2 (mod 17) ist übrigens nichts anderes wegen 13 * 4 = 1.

0

sorry- kann da nicht helfen aber

warum ggT(4;8) = 0 und nicht 4   ?

Ups - da habe ich einen Fehler gemacht - danke, das ist mir gar nicht aufgefallen!

0

Was möchtest Du wissen?