Zum Inhalt springen
Topos Uranos
Deutsch

Kongruenzen und modulare Arithmetik

Zusammenfassung

Diese Lektion verwandelt die Einteilung der ganzen Zahlen nach ihrem Rest in einen Kalkül. Sie definiert die Kongruenz modulo nn, beweist, dass sie gleichbedeutend damit ist, denselben Rest zu lassen, dass sie eine Äquivalenzrelation ist und dass sie Addition, Multiplikation und Potenzen respektiert, und konstruiert mit ihren Klassen die Menge Zn\mathbb{Z}_n der Reste mit ihren Additions- und Multiplikationstafeln. Mit dem Lemma von Bézout entscheidet sie, welche Reste ein Inverses besitzen, und löst die linearen Kongruenzen vollständig; sie beweist den chinesischen Restsatz und den kleinen fermatschen Satz, liest die Teilbarkeitsregeln als Kongruenzen neu und wendet all dies auf Prüfziffern, auf den Kalender und auf das Kryptosystem RSA an, dessen Korrektheit bewiesen wird.

Lernziele

  1. Beweisen, dass die Kongruenz modulo nn eine Äquivalenzrelation ist, die mit Addition, Multiplikation und Potenzen verträglich ist, und sie verwenden, um Reste großer Zahlen zu berechnen.
  2. Die Additions- und Multiplikationstafeln von Zn\mathbb{Z}_n aufstellen und mithilfe des größten gemeinsamen Teilers entscheiden, welche Reste ein Inverses besitzen.
  3. Entscheiden, ob eine lineare Kongruenz lösbar ist, berechnen, wie viele Lösungen sie modulo nn hat, und sie alle finden.
  4. Systeme von Kongruenzen mit teilerfremden Moduln mithilfe des chinesischen Restsatzes lösen, dabei die Lösung konstruieren und ihre Eindeutigkeit beweisen.
  5. Den kleinen fermatschen Satz beweisen und ihn auf Reste von Potenzen, auf Teilbarkeiten, die für jede ganze Zahl gelten, und auf die Korrektheit des Kryptosystems RSA anwenden.
  6. Analysieren, welche Fehler eine Prüfziffer erkennt, und Wochentage mithilfe von Kongruenzen berechnen.

Die Kongruenzrelation

Ist heute Montag, so ist in 1515 Tagen Dienstag und in 10001000 Tagen Sonntag: Um das zu wissen, muss man die Tage nicht einzeln abzählen, denn es genügt der Rest der Division der Anzahl der Tage durch 77. Ebenso ist es 55 Stunden nach 99 Uhr genau 22 Uhr, wenn die Uhr 1212 Stunden zählt, und die letzte Ziffer eines Produkts hängt nur von den letzten Ziffern der Faktoren ab. In allen drei Fällen rechnet man mit Resten und vergisst den Quotienten. Die Lektion über Teilbarkeit und Division mit Rest hat die ganzen Zahlen nach dem Rest, den sie bei der Division durch eine natürliche Zahl lassen, in Klassen eingeteilt und bewiesen, dass der Rest einer Summe, eines Produkts und einer Potenz nur von den Resten der gegebenen Zahlen abhängt. Diese Lektion gibt diesen Beobachtungen eine eigene Sprache, die der Kongruenzen, die Gauß 1801 in seinen Disquisitiones Arithmeticae einführte, und macht sie zu einem Rechenwerkzeug. Wie in jener Lektion werden die ganzen Zahlen vorgreifend verwendet, mit den Regeln ihrer Arithmetik und ihrer Ordnung, die in der Lektion über die ganzen Zahlen begründet werden.

Definition (Kongruenz). Sei nn eine natürliche Zahl. Zwei ganze Zahlen aa und bb heißen kongruent modulo nn, wenn nn ihre Differenz a−ba - b teilt. Man schreibt a≡b(modn)a \equiv b \pmod{n} und liest „aa ist kongruent zu bb modulo nn“; die natürliche Zahl nn heißt der Modul der Kongruenz.
a≡b(modn)↔n∣a−ba \equiv b \pmod{n} \leftrightarrow n \mid a - b

So ist 17≡2(mod5)17 \equiv 2 \pmod{5}, weil 17−2=1517 - 2 = 15; ferner −3≡9(mod4)-3 \equiv 9 \pmod{4}, weil −3−9=−12-3 - 9 = -12; und eine ganze Zahl ist genau dann gerade, wenn sie kongruent zu 00 modulo 22 ist. Dass aa ein Vielfaches von nn ist, schreibt man nun a≡0(modn)a \equiv 0 \pmod{n}. Beim Modul 11 sind alle ganzen Zahlen zueinander kongruent, weil 11 jede ganze Zahl teilt; dieser Fall ist ohne Interesse, und in den Beispielen ist der Modul mindestens 22. Das Zeichen ≡\equiv mit drei Strichen erinnert an das Gleichheitszeichen, weil sich die Kongruenz, wie man sehen wird, fast in allem wie die Gleichheit verhält; die Ausnahme, die Division, beschäftigt den Abschnitt über die Inversen.

Die Definition über die Differenz ist für Beweise die bequemste, aber die Anschauung der einleitenden Beispiele ist die des Restes. Die folgende Proposition sichert, dass beide dasselbe besagen; ihr Inhalt wurde in anderer Form schon in der Lektion über die Teilbarkeit beobachtet, bei der Begründung der Teilbarkeitsregeln, und wird hier vollständig bewiesen.

PropositionDie Kongruenz und der Rest

Zwei ganze Zahlen sind genau dann kongruent modulo nn, wenn sie bei der Division durch nn denselben Rest lassen. Seien a=nq+ra = nq + r und b=ns+tb = ns + t die Divisionen mit Rest von aa und von bb durch nn, mit 0≤r<n0 \leq r < n und 0≤t<n0 \leq t < n. Die Abbildung ordnet die ganzen Zahlen von −10-10 bis 2424 in Zeilen zu 55 an, sodass jede Spalte diejenigen vereinigt, die denselben Rest lassen.

Beweis

  1. a−b=(nq+r)−(ns+r)=n(q−s)a - b = (nq + r) - (ns + r) = \resaltar{n(q - s)}

    Stimmen die Reste überein, r=tr = t, so hebt sich beim Subtrahieren der beiden Divisionen der Rest weg, und die Differenz ist ein Vielfaches von nn.

  2. a=b+nk=ns+t+nk=n(s+k)+ta = \resaltar{b} + nk = \resaltar{ns + t} + nk = \dato{d}{n(s + k) + t}

    Umgekehrt nehmen wir an, dass nn die Zahl a−ba - b teilt, das heißt, dass a=b+nka = b + nk für eine ganze Zahl kk gilt. Wir setzen die Division von bb ein.

  3. 0≤t<n→r=t0 \leq t < n \rightarrow \resaltar{r = t}

    Da 0≤t<n0 \leq t < n gilt, ist diese Gleichung eine Division von aa durch nn mit Rest tt. Wegen der Eindeutigkeit von Quotient und Rest ist tt der Rest von aa, das heißt t=rt = r.

  4. 23≡8≡−2≡−7≡3(mod5)23 \equiv 8 \equiv -2 \equiv -7 \equiv 3 \pmod{5}

    In der Abbildung stehen −7-7, −2-2, 33, 88, 1313, 1818 und 2323 in derselben Spalte: Alle lassen den Rest 33, und ihre Differenzen sind Vielfache von 55.

Insbesondere ist jede ganze Zahl modulo nn kongruent zu ihrem Rest, der eine der nn ganzen Zahlen 0,1,…,n−10, 1, \ldots, n - 1 ist, und nur zu einer von ihnen, denn zwei dieser Zahlen sind ihre eigenen Reste und lassen, wenn sie verschieden sind, verschiedene Reste. Modulo nn rechnen heißt, jede Zahl durch einen bequemen Repräsentanten ihrer Spalte zu ersetzen: den Rest oder manchmal eine kleine negative Zahl, etwa −1-1 statt n−1n - 1.