Modulare Arithmetik

Modulo

Zwei ganze Zahlen heißen “kongruent modulo $m$ ”, wenn sie bei Division durch $m$ den gleichen Rest haben.

Beispiel
$a=b\mathrm{mod}m$
$24=4\mathrm{mod}10$

$\{19;23;27;31;35;...\}$ sind alle $\mathrm{mod}4=5$
Sie sind Teil einer Restklasse
Es gibt immer $m$ Restklassen bei Modulo $m$

Satz-Mod-Regeln

Wenn $a=b\mathrm{mod}m$ und $c=d\mathrm{mod}m$ dann gilt:

• $a+c=b+d\mathrm{mod}m$
• $a\ast c=b\ast d\mathrm{mod}m$
  Dabei ist nicht erforderlich, dass $a$ und $c$ der gleichen Restklasse angehören.

Anwendungen

1. Hash-Funktionen
2. Prüfziffern (ISBN, EAN, IBAN, $\dots$ )

Addition und Multiplikation in ${\mathbb{Z}}_n$

Definition

${\mathbb{Z}}_n=\{0;1;2;3;4;\dots ;(n-1)\}$
Ist die Menge aller möglichen Reste
${\mathbb{Z}}_2=\{0;1\}$

Addition und Multiplikation in ${\mathbb{Z}}_5$

Damit die Ergebnisse auch innerhalb des erlaubten Zahlenbereichs sind, werden sie $\mathrm{mod}5$ genommen. Für ${\mathbb{Z}}_5$ entsteht so folgende Verteilung

+	0	1	2	3	4
0	0	1	2	3	4
1	1	2	3	4	0
2	2	3	4	0	1
3	3	4	0	1	2
4	4	0	1	2	3

*	0	1	2	3	4
0	0	0	0	0	0
1	0	1	2	3	4
2	0	2	4	1	3
3	0	3	1	4	2
4	0	4	3	2	1

Addition

Man erkennt $4+1=0\mathrm{mod}5$
Daher betrachtet man $1$ als das Negative Element zu $4$.

Definition

Für eine Zahl $e\in \mathbb{Z}$ ist die Zahl $d$ das additive Invers zu $e$, wenn $e+d=0\mathrm{mod}m$ und $d\in {\mathbb{Z}}_n$
Es gilt $d=n-e$
Es kann Zahlen geben die ihr eigenes Invers sind.

Multiplikation

Rechenregeln ^Rules

Im Taschenrechner lassen sich zu große Exponenten schlecht oder nicht berechnen. Die Werte können zerlegt werden

$$20^{69}=20^{6\ast 10+9}={\left(20^{10}\right)}^6\ast 20^9$$

Es ist möglich, die Modulo Operation auch in diesen einzelnen Faktoren durchzuführen

$${\left(20^{10}\right)}^6\ast 20^9=(31{)}^6\ast 5\mathrm{mod}69$$

Durch

• $20^{10}=31\mathrm{mod}69$
• $20^9=5\mathrm{mod}69$

gilt also

$$20^{69}=31^6\ast 5=65\mathrm{mod}69$$

Definition

Wenn es zu $e\in {\mathbb{Z}}_n$ eine Zahl $d$ gibt mit $d\in {\mathbb{Z}}_n$ und $d\ast e=1$ so heißt $d$ Kehrwert von $e$ oder auch multiplikatives Invers.
Man schreibt auch $d=e^{-1}=\frac{1}{e}$

In ${\mathbb{Z}}_5$ ist also mit $\frac{1}{2}$ die Zahl $3$ gemeint.

Nicht jede Zahl hat ein Multiplikatives Invers:
$0\ast d=0\ne 1$

Satz-Existenz

Für $e\ne 0\in {\mathbb{Z}}_n$ hat $e$ genau dann einen Kehrwert, wenn $e$ und $n$ koprim, also teilerfremd sind.

Beispiel-Invers-Suche

$4^{-1}\in {\mathbb{Z}}_9$ “Erweitern” in gleicher Restklasse

$$\frac{1}{4}\to \frac{1+9}{4}\to \frac{1+2\ast 9}{4}\to \frac{1+3\ast 9}{4}=7$$

Gleichungen

Addition

$$\begin{array}{lc}4+x=3& \mathrm{mod}6\\ x=-1& \mathrm{mod}6\\ x=5& \mathrm{mod}6\end{array}$$

Multiplikation

$$\begin{array}{lcc}5\ast x=2& \mathrm{mod}12& \\ x=\frac{1}{5}\ast 2& \mathrm{mod}12& \frac{1}{5}\to \frac{1+12}{5}\to \frac{1+2\ast 12}{5}=\frac{25}{5}=5\\ x=5\ast 2& \mathrm{mod}12& \\ x=10& \mathrm{mod}12& \end{array}$$

---

$2\ast x=3\mathrm{mod}6\to$ 2 und 6 sind nicht teilerfremd, probieren statt rechnen

$2\ast 0=0$
$2\ast 1=2$
$2\ast 2=4$
$2\ast 3=0$
$2\ast 4=2$
$2\ast 5=4$
$\to$ Keine Lösung

---

$2\ast x=0\mathrm{mod}6$
vgl. oben, $\to 2$ Lösungen $(0|3)$

Lösungsmengen

Addition

$$a+x=b$$

Besitzt immer eine eindeutige Lösung.
Addition des additiven Invers $-a$ von $a$

Multiplikation

Wenn $a$ und $m$ teilerfremd sind, besitzt $a\ast x=b\mathrm{mod}m$ genau eine Lösung in ${\mathbb{Z}}_m$.
Sonst existieren $0$ oder mehrere Lösungen.
Die Anzahl lässt sich mit Hilfe des größten gemeinsamen Teilers $t$ von $a$ und $m$ feststellen. Wenn $t$ auch Teiler von $b$ ist, so existieren genau $t$ Lösungen.
Sonst gibt es $0$ Lösungen.

${\mathbb{Z}}_m^{\ast }=\{a\in {\mathbb{Z}}_m\mid ggT(a;m)=1\}$
Diese Menge ist also die Menge aller Zahlen aus ${\mathbb{Z}}_m$, für die ein multiplikatives Invers existiert. Alle diese Zahlen sind zu $m$ teilerfremd.