Modulo

Modulare Arithmetik - Rechnen mit Resten - ist ein nützliches Werkzeug der Zahlentheorie.

Example 1

Wir wissen, dass die Menge $\mathbb{Z}$ in zwei Klassen aufgespalten werden kann:

die geraden Zahlen:

\{\dots,-6,-4,-2,0,2,4,6,\dots\} =: [0]

die ungeraden Zahlen:

\{\dots,-5,-3,-1,1,3,5,\dots\} =: [1]

Nun können wir gewisse Verallgemeinerungen formulieren: Beispielsweise ist die Summe zweier gerader Zahlen wieder gerade; die Summe einer geraden und einer ungeraden Zahl ist ungerade; die Summe zweier ungerader Zahlen ist gerade; das Produkt zweier gerader Zahlen ist gerade, usw.

Note 1: Modul

Im obigen Beispiel ist der sogenannte Modul gleich $2$ . Der Modulus kann als Anzahl der Klassen betrachtet werden, in die unsere Zahlenmenge $\mathbb{Z}$ aufgeteilt wird.

Note 2

Jetzt legen wir für jede der beiden Klassen ein Symbol fest: Wir schreiben $[0]$ für die Klasse der geraden Zahlen - die Bezeichnung erfolgt nach dem kleinsten nicht-negativen Element. Wir schreiben oft kurz $0$ für die Klasse aller geraden Zahlen und $1$ für die Klasse aller ungeraden Zahlen, wählen also einen Repräsentanten. Wir hätten auch $2$ und $3$ , oder $-32$ und $177$ wählen können; $0$ und $1$ sind aber die üblichen Bezeichnungen.

Example 2

Die Aussage

Die Summe zweier gerader Zahlen ist eine gerade Zahl.

wird schlanker wie folgt geschrieben:

0+0\equiv0\pmod 2

Das Symbol $\equiv$ beziechnet nicht Gleichheit, sondern Kongruenz. $\pmod 2$ bedeutet, dass unser Modulus $2$ ist; obige Aussage liest man: "Null plus Null ist kongruent Null Modulo Zwei". Die Aussage, dass die Summe einer geraden und einer ungeraden Zahl ungerade ist, schreibt sich

0+1\equiv1\pmod 2.

Example 3

Diese Beispiele sind trivial. Wie aber schreiben wir, dass die Summe zweier ungerader Zahlen gerade ist?

1+1\equiv0\pmod 2.

Analoge Aussagen erhält man für die Multiplikation:

\begin{align*} 0\cdot0&\equiv0\pmod 2\\ 0\cdot1&\equiv0\pmod 2\\ 1\cdot1&\equiv1\pmod 2 \end{align*}

Definition

Selbstverständlich kann man allgemein Modulo $m$ , $m\in\mathbb{N}$ , rechnen. Wir definieren

Definition 1: Kongruent Modulo

Sei $n\in\mathbb{N}$ . Zwei Zahlen $a,b\in\mathbb{Z}$ heissen kongruent Modulo $n$ , falls ein $k\in\mathbb{Z}$ existiert, so dass $a-b=k\cdot n$ . Man schreibt

a\equiv b\pmod n.

Example 4

$5$ und $8$ sind kongruent Modulo $3$ , denn es gilt $5-8=-1\cdot 3$ .

Example 5

Wir betrachten ganze Zahlen Modulo $3$ . Klar ist, dass alle Vielfachen von $3$ , $3k$ , kongruent Modulo $3$ sind, da jede Differenz zweier solcher Zahlen durch $3$ teilbar ist. Analog sind alle Zahlen der Form $3k+1$ und alle Zahlen der Form $3k+2$ kongruent Modulo $3$ , $k\in\mathbb{Z}$ .

\begin{align*} \dots\equiv-6\equiv-3\equiv0\equiv3\equiv6\equiv9\dots\pmod 3\\ \dots\equiv-7\equiv-4\equiv-1\equiv2\equiv5\equiv8\dots\pmod 3\\ \dots\equiv-8\equiv-5\equiv-2\equiv1\equiv4\equiv7\dots\pmod 3 \end{align*}

Die Uhr

Ein alltäglicher Fall ist der Modulus $12$ . Man nennt den Fall $m=12$ auch die Uhr-Arithmetik.

Example 6

Wenn es 07:00 Uhr ist, welche Zeit haben wir in $25\,\text{Stunden}$ . Da $25\equiv1\pmod{12}$ können wir einfach $1$ zu $7$ addieren:

7+25\equiv7+1\equiv8\pmod{12}.

Also 08:00 Uhr.

Die Sekunden und Minuten auf der Uhr sind auch modular, nämlich Modulo $60$ .

Rechenregeln

Die Grundlage für folgende Rechenregeln ( $a,b\in\mathbb{Z}$ und $m,n\in\mathbb{N}$ ) mit Moduln bildet

Theorem 1

a\equiv b\pmod n \;\Leftrightarrow\; a-b\equiv 0\pmod n \;\Leftrightarrow\; n\mid(a-b)

Proof

Per Definition von Kongruenz: $a\equiv b\pmod n$ genau dann, wenn $n\mid(a-b)$ . Die Umformung $a-b\equiv 0\pmod n$ ist nur eine andere Schreibweise derselben Aussage.

Theorem 2

a\equiv b\pmod n \quad\Leftrightarrow\quad a+c\equiv b+c\pmod n

Proof

Gelte $a\equiv b\pmod n$ . Dann ist $n\mid(a-b)$ . Also $n\mid((a+c)-(b+c))$ . Damit $a+c\equiv b+c\pmod n$ - umgekehrt subtrahiert man.

Theorem 3

a\equiv b\pmod n \quad\Rightarrow\quad ac\equiv bc\pmod n

Proof

Aus $a\equiv b\pmod n$ folgt $n\mid(a-b)$ . Damit $n\mid c(a-b)=(ac-bc)$ . Also $ac\equiv bc\pmod n$ .

Theorem 4

a\equiv b\pmod n \quad\Rightarrow\quad a^m\equiv b^m\pmod n

Proof

Induktion über $n$ :
$n=1$ trivial.
Angenommen $a^m\equiv b^m\pmod n$ . Dann $a^{m+1}=a^m\cdot a\equiv b^m\cdot a\pmod n$ . Da $a\equiv b\pmod n$ , folgt $b^m\cdot a\equiv b^m\cdot b=b^{m+1}\pmod n$ ; damit $a^{m+1}\equiv b^{m+1}\pmod n$ .

Theorem 5

a\equiv b\pmod n \text{ und } c\equiv d\pmod n\quad\Rightarrow\quad a+c\equiv b+d\pmod n

Proof

Aus $a\equiv b\pmod n$ folgt $n\mid(a-b)$ . Aus $c\equiv d\pmod n$ folgt $n\mid(c-d)$ . Addieren liefert $n\mid((a+c)-(b+d))$ ; also $a+c\equiv b+d\pmod n$ .

Theorem 6

a\equiv b\pmod n \text{ und } c\equiv d\pmod n\quad\Rightarrow\quad ac\equiv bd\pmod n

Proof

Aus $a\equiv b\pmod n$ folgt $n\mid(a-b)$ . Aus $c\equiv d\pmod n$ folgt $n\mid(c-d)$ . Schreibe $ac-bd=(a-b)c+b(c-d)$ . Beide Summanden sind durch $n$ teilbar; also $n\mid(ac-bd)$ und $ac\equiv bd\pmod n$ .

Theorem 7

\gcd(a,n)=1 \textup{ und } ab\equiv ac\pmod n\quad\Rightarrow\quad b\equiv c\pmod n

Proof

Aus $ab\equiv ac\pmod n$ folgt $n\mid a(b-c)$ . Da $\gcd(a,n)=1$ , teilt $n$ $(b-c)$ ; also $b\equiv c\pmod n$ .

Exercise 1: Sätze beweisen

Gib konkrete Beispiele zu den Sätzen und beweise sie.

Solution

Zum Beispiel zur Addition:

4\equiv10\pmod 3\;\Rightarrow\; 4+2\equiv10+2\pmod 3.

Beweis über die Definition: Gelte $a\equiv b\pmod n$ und sei $c\in\mathbb{Z}$ beliebig. Das heisst $\exists k\in\mathbb{Z}$ mit $b-a=kn$ und daraus

kn=b-a=(b+c)-(a+c).

Das heisst $a+c\equiv b+c\pmod n$ .

Exercise 2: Einfache Restberechnungen

a) $37 \bmod 6$

b) $125 \bmod 12$

c) $1001 \bmod 9$

d) $234 \bmod 11$

e) $5678 \bmod 10$

f) $999 \bmod 7$

g) $81 \bmod 13$

h) $31415 \bmod 8$

Solution

a) $37=6\cdot 6+1\;\Rightarrow\;37\equiv 1\pmod 6$ .

b) $125=12\cdot 10+5\;\Rightarrow\;125\equiv 5\pmod{12}$ .

c) Quersumme $1+0+0+1=2\;\Rightarrow\;1001\equiv 2\pmod 9$ .

d) $234=11\cdot 21+3\;\Rightarrow\;234\equiv 3\pmod{11}$ .

e) Rest bei Division durch $10$ ist einfach die letzte Ziffer: $5678\equiv 8\pmod{10}$ .

f) $999=7\cdot 142+5\;\Rightarrow\;999\equiv 5\pmod 7$ .

g) $81=13\cdot 6+3\;\Rightarrow\;81\equiv 3\pmod{13}$ .

h) $31415=8\cdot 3926+7\;\Rightarrow\;31415\equiv 7\pmod 8$ .

Äquivalenzrelation

Definition 2: Äquivalenzrelation

Eine Relation auf einer Menge $\mathbb{M} \neq \emptyset$ , die für beliebige $a,b,c$ und $m\neq0$ folgende drei Bedingungen erfüllt:

$a\equiv a\pmod m$ (Reflexivität)
Falls $a\equiv b\pmod m$ , dann gilt $b\equiv a\pmod m$ (Symmetrie)
Falls $a\equiv b\pmod m$ und $b\equiv c\pmod m$ , dann $a\equiv c\pmod m$ (Transitivität)

nennt man Äquivalenzrelation auf $\mathbb{M}$ .

Note 3: Restklassen

Die Äquivalenzrelation $\pmod m$ teilt $\mathbb{Z}$ in $m$ Äquivalenzklassen.

Definition 3: Äquivalenzklasse

Sei $M$ eine Menge und $\sim$ eine Äquivalenzrelation auf $M$ . Für ein Element $a\in M$ heisst die Menge

\overline{a} := \{\,x\in M \mid x \sim a\,\}

die Äquivalenzklasse von $a$ bezüglich $\sim$ ; sie besteht also aus allen Elementen von $M$ , die zu $a$ in Relation stehen.

Man schreibt manchmal für die Äquivalenzklasse einer Zahl $a$ etwa $[a]$ oder auch $\overline{a}$ , um zwischen Zahl und Klasse zu unterscheiden. (Äquivalenz kommentiert)

Note 4: Induzierte Partition

Jede Äquivalenzrelation $\sim$ auf einer Menge $\mathbb{M}$ induziert in natürlicher Weise eine Partition von den in $\mathbb{M}$ enthaltenen Äquivalenzklassen.

Solution

In der Tat:

Sei $a\in\mathbb{M}$ beliebig; betrachte $[a] = \{x\in\mathbb{M} \mid x\sim a\}$ : Da $\sim$ reflexiv, gilt $a\sim a$ ; also gehört $a$ sicher zu seiner eigenen Äquivalenzklasse $[a]$ . Wir haben also mit $\bigcup_{a\in\mathbb{M}}[a] = \mathbb{M}$ eine Überdeckung von $\mathbb{M}$ .

Um die Partition einzusehen betrachten wir zwei Äquivalenzklassen $[a]$ und $[b]$ mit nichtleerem Schnitt: $[a]\cap[b] \neq \emptyset$ . Also gibt es $c\in[a]\cap[b]$ , d.h. $c\in[a]$ und $c\in[b]$ . Es folgt $c\sim a$ und $c\sim b$ , also $a\sim c$ und $c\sim b$ und schliesslich $a\sim b$ - dieses Resultat brauchen wir für die Fortsetzung.

Sei $x\in[a]$ , d.h. $x\sim a$ und mit dem Resultat von eben $x\sim b$ , also $[a]\subset[b]$ . Ist $x\in[b]$ folgt analog $[b]\subset[a]$ ; also $[a] = [b]$ . Das heisst Äquivalenzklassen, welche einen nichtleeren Schnitt haben, sind identisch. Also teilt $\sim$ die Menge $\mathbb{M}$ in disjunkte Äquivalenzklassen - Partitionen.

Exercise 3: 🧩

Zeige, dass das Gleichungssystem

\begin{align} 11x-5y=7\\ 9x+10y=-3 \end{align}

keine ganzzahlige Lösung besitzt.

Solution

Modulo $2$ gilt:

\begin{align} x+y\equiv1\\ x\equiv1 \end{align}

Also ist $x$ ungerade und $y$ gerade. Modulo $5$ gilt:

\begin{align} x\equiv2\\ 4x\equiv2 \end{align}

Es folgt $5x\equiv4$ , Widerspruch, da $5x\equiv0\mod5$ !

Exercise 4: 🧩

Zeige, dass für $x,y,z\in\mathbb{Z}$ mit

x^2+y^2=z^2

mindestens eine der Zahlen durch $2$ , mindestens eine durch $3$ und mindestens eine durch $5$ teilbar ist.

Solution

Modulo $2$ betrachten wir die Fälle $z^2\equiv0$ und $z^2\equiv1$ . Im ersten Fall gälte dann $x^2\equiv0$ und $y^2\equiv0$ oder $x^2\equiv1$ und $y^2\equiv1$ . Für den zweiten Fall gilt oEdA $x^2\equiv1$ woraus $y^2\equiv0$ und damit $y\equiv0$ folgt. Also ist immer sicher mindestens eine Zahl durch $2$ teilbar.

Modulo $3$ gelte $z^2\equiv1$ . Dann muss oEdA $x^2\equiv1$ und $y^2\equiv0$ gelten, also $y\equiv0\mod{3}$ . Oder es wäre $x^2\equiv2$ und $y^2\equiv2$ . Aber das kann wegen $x\equiv\sqrt{2}$ nicht passieren. Aus dem gleichen Grund muss $z^2\equiv2$ nicht betrachtet werden und für $z^2\equiv0$ ist die Behauptung trivial. Somit ist mindestens eine Zahl durch $3$ teilbar.

Modulo $5$ äquivalent zu $0$ ist wiederum trivial. Gelte noch Modulo $5$ $z^2\equiv1$ oder $z^2\equiv4$ . Im ersten Fall sind nur möglich $x\equiv1$ und $y\equiv0$ oder viceversa. Im zweiten Fall klappt nur $x\equiv4$ woraus $y\equiv0$ folgt. Also ist sicher mindestens eine Zahl durch $5$ teilbar.

Exercise 5: 🧩

a) Finde das kleinste $x\in\mathbb{N}$ mit $x\equiv 7\pmod 9$ und $x\equiv 2\pmod 4$ .

b) Löse $5x\equiv 1\pmod{12}$ .

c) Löse $6x\equiv 9\pmod{15}$ (alle Kongruenzklassen).

d) Berechne $2^{100}\bmod 7$ .

e) Bestimme die letzte Ziffer von $3^{2025}$ .

Solution

a) Schreibe $x=7+9k$ . Bedingung $7+9k\equiv 2\pmod 4\;\Leftrightarrow\;9k\equiv -5\equiv 3\pmod 4$ .
Da $9\equiv 1\pmod 4$ , gilt $k\equiv 3\pmod 4$ . Kleinste Wahl $k=3$ , also $x=7+27=34$ .

b) Wir suchen $x$ mit $5x\equiv 1\pmod{12}$ . Test: $5\cdot 5=25\equiv 1\pmod{12}$ .
Also $x\equiv 5\pmod{12}$ .

c) $\gcd(6,15)=3$ teilt $9$ , also lösbar. Durch $3$ kürzen:

6x\equiv 9\;(\bmod 15)\;\Leftrightarrow\;2x\equiv 3\;(\bmod 5).

Inverse von $2$ mod $5$ ist $3$ (denn $2\cdot 3=6\equiv 1$ ). Somit

x\equiv 3\cdot 3\equiv 9\equiv 4\;(\bmod 5).

Alle Lösungen: $x\equiv 4\pmod 5$ (also $x=4,9,14,\dots$ ).

d) Mod $7$ hat $2^k$ Periode $3$ (denn $2^3=8\equiv 1$ ). $100\equiv 1\pmod 3$ , also

2^{100}\equiv 2^{1}\equiv 2\;(\bmod 7).

e) Mod $10$ hat $3^k$ Periode $4$ und $2025\equiv 1\pmod 4$ , also

3^{2025}\equiv 3^{1}\equiv 3\;(\bmod 10).

Letzte Ziffer: $3$ .

Osterformel

Die Osterformel von Gauss

Die Gauss'sche Osterformel erlaubt die Berechnung des Osterdatums für ein gegebenes Jahr. Das Verfahren gilt allgemein für den Gregorianischen Kalender.

Note 5

In seltenen Fällen kann der Algorithmus im Gregorianischen Kalender den 26. April als spätesten Ostersonntag liefern. Die bei der Kalenderreform aufgestellte Zusatzbestimmung, dass der letzte mögliche Ostersonntag der 25. April ist, muss zusätzlich beachtet werden.

Nun zum Verfahren ( $\div$ steht für eine ganzzahlige Division ohne Nachkommastellen):

\begin{align*} a &= \text{Jahr}\mod19\\ b &= \text{Jahr}\mod4\\ c &= \text{Jahr}\mod7\\ k &= \text{Jahr}\div100\\ p &= (8k+13)\div25\\ q &= k\div4\\ M &= (15+k-p-q)\mod30\\ N &= (4+k-q)\mod7\\ d &= (19a+M)\mod30\\ e &= (2b+4c+6d+N)\mod7 \end{align*}

Mit den so bestimmten Variablen kann man nun das Osterdatum berechnen:

\text{Ostern}=(22+d+e)\text{ter März},

wobei der 32. März der 1. April ist etc.

Exercise 6: Osterformel von Gauss

Berechne das Datum der nächsten Ostern.

Solution

Selbstkontrolle ;)