Mathematische Grundlagen 3

In der 6. Klasse hast du dich schon einmal mit Kehrwerten beschäftigt. Bei der Zahl 2 ist der Kehrwert bezüglich der Multiplikation 0,5. $2\cdot 0,5 =1$, den Kehrwert kann man auch als Inverse bezeichnen. Im Folgenden gilt es zu untersuchen, ob auch modulo Inverse existieren und wenn ja unter welchen Bedingungen, wenn wir nur ganzzahlige Inverse betrachten möchten. Aus den Angaben von Alice folgt: $a = 13, n = 24, x \in \Z$ Wie für den Kehrwert, so gilt auch für die modulare Inverse, dass das Resultat 1 ergeben muss.

Allgemein gilt also:	Alternative Schreibweise für die modulare Inverse:
$a\cdot x\ mod\ n =1$	$a^{-1}\equiv x\ mod\ n$

man schreibt für das inverse Element auch:

für die Aufgabe von Alice gilt somit:

$13\cdot x\ mod\ 24 =1$

Diese Gleichung ist äquivalent zu :
$a\cdot x = r\cdot n +1\in\Z$ diese Schreibweise erinnert an Lemma 1.2, wonach man vermuten kann, dass die Gleichung nur für ggT(a,n)=1 gilt.

Falls eine Lösung existiert, soll nun eine ganze Zahl x gefunden werden, so dass die Gleichung erfüllt ist. Wie du anhand Alice Beispiel selbst überprüfen kannst, ist dies bereits bei so kleinen Zahlen ziemlich schwierig.
Deshalb betrachten wir nun den Satz von der modularen Inverse und werden darauf einen Algorithmus kennen lernen, mithilfe dessen sich die Modulo Inverse relativ einfach berechnen lässt.

Satz 2.3 (Satz von der modularen Inversen) Es sei $a,x \in \Z$ und $n \in \N$ mit ggT(a,n)=1, so ist x die modulare Inverse zu a, wenn gilt:

$a\cdot x\ mod\ n =1$

Beweis: Da gilt ggT(a,n)=1, gibt es ganze Zahlen x und y mit folgenden Eigenschaften:
$1 =a\cdot x + n\cdot y$
da ny durch n teilbar ist, ergibt ax bei Division durch n den Rest 1, also ist
$a\cdot x\ mod\ n =1$

Folglich gibt es immer eine eindeutige modulare Inverse, wenn gilt ggT(a,n)=1 □

Wie du bereits aus Abschnitt 1 weißt, lässt sich der ggT zweier Zahlen mithilfe des Euklidischen Algorithmus bestimmen.

Algorithmus 2.4 (Berechnung der modularen Inverse) Es seien $a,n \in \Z$ mit ggT(a,n) = 1. Man berechne zunächst die Vielfachsummendarstellung $1=a\cdot x+y\cdot n$. Dann ist x die modulare Inverse von a modulo n.