MathePrisma Logo

RSA

RSA

Modulo

Reste

Bei der Modulo-Rechnung geht es um Reste der Division.

Kongruenz

Zwei ganze Zahlen \(a\) und \(b\), die bei Division durch eine natürliche Zahl \(m\) denselben Rest lassen, d.h.

\[ a = k\cdot m + r \text{ und } b = l\cdot m + r \text{ mit } k,l,r \in \mathbb{Z} \text{ und } 0 \le r < m \text{ , } \]

heißen kongruent modulo \(m\). Man schreibt

\[ a \equiv b \bmod m \text{ . } \]

Beispiel

Es gilt \(9 \equiv 7 \bmod 2\), denn 9 und 7 lassen bei Division durch 2 beide den Rest 1.

Was bedeutet \(a \equiv 0 \bmod m\)? (Es sind mehrere Antworten möglich!)

Überzeuge dich von der Aussage:
Die Konguenz modulo m ist eine Äquivalenzrelation in \(\mathbb{Z}\), d.h. es gilt
  • \(a \equiv a \bmod m \) für alle \(a \in \mathbb{Z}\)
  • aus \(a \equiv b \bmod m\) folgt \(b \equiv a \bmod m\)
  • \(a \equiv b \bmod m\) und \(b \equiv c \bmod m\) folgt \( a \equiv c \bmod m\)

Restklassen

Die Menge aller ganzen Zahlen, die bei Division durch \(m\) den gleichen Rest wie \(a\) lassen, heißt Restklasse "\(a\) modulo \(m\)" oder "\(a\; mod \;m\)". Ganz kurz kann man auch \([a]_m\) schreiben.

\[ [a]_m = { x \in \mathbb{Z} \; | \; x \equiv a \bmod m} \]

ausgezeichnet!

Jede Restklasse hat ein ausgezeichnetes Element, nämlich das kleinste nicht negative.

Der Rest

Ist \(a = k\cdot m + r\) mit \(0 \le r < m\), so ist \(r\) die kleinste ganze Zahl, die zu \(a\) kongruent modulo \(m\) ist:

\[ a \equiv r \bmod m \]

und für alle \(x \in \mathbb{N}\) mit \( x \equiv a \bmod m\) gilt \( x > r\).

Tachenrechner- Notation

Dieses kleinste Element einer Restklasse ist der Rest, den alle Elemente der Restklasse beim Teilen durch \(m\) lassen. Es ist auch das Ergebnis, dass der Taschenrechner liefert, wenn du eintippst: "a mod m =". Wenn wir (nicht ganz korrekt) schreiben:

\[ 10 \bmod 4 = 8 \bmod 6 = 2 \]

meinen wir also

\[ 10 \equiv 2 \bmod 4 \text{ und } 8 \equiv 2 \bmod 6 \]

oder anders

\[ 10 = k\cdot 4 + 2 \text{ und } 8 = l\cdot 6 + 2. \]