3. Modul: Teilbarkeit ganzer Zahlen und modulare Arithmetik

Website:	WueCampus
Kurs:	vhb - Grundlagen der elementaren Zahlentheorie (DemoKurs)
Buch:	3. Modul: Teilbarkeit ganzer Zahlen und modulare Arithmetik

Gedruckt von:	Gast
Datum:	Sonntag, 28. April 2024, 11:19

Beschreibung

Grundlegende Konzepte wie Irrationalität und Primalität werden in diesem Modul behandelt und mit speziellen Methoden wie Kettenbruchentwicklung bzw. Kongruenzkalkül untersucht. Hierbei wird Wert auf eine algorithmische Herangehensweise gelegt, die einen rechnerischen Zugang zur Arithmetik ermöglicht.

______________________________________________________________________________

vhb - Kurs: Grundlagen der elementaren Zahlentheorie

III.1. Elementare Teilbarkeitslehre

______________________________________________________________________________

Im Folgenden bezeichnen kleine lateinische Buchstaben stets ganze Zahlen. Wir sagen d teilt n oder d ist ein Teiler von n, wenn ein b existiert, so dass n = bd; in Zeichen: d | n. Natürlich gilt in diesem Fall auch b | n; dabei heißt b der zu d komplementäre Teiler. Ansonsten ist d kein Teiler von n, was wir mit d ∤ n notieren. Dieses Prinzip der Teilbarkeit begegnet uns auch im Alltag.

Beispielsweise gelten

2 | 100, 11 | 165, − 13 | 169, 5 ∤ 21.

Es bestehen die folgenden Rechenregeln zur Teilbarkeit:

1 | n und n | n und d | 0;
0 | d ⇒ d = 0; d | 1 ⇒ d = ±1;
d | n, n | m ⇒ d | m;
d | a, d | b ⇒ d | (ax + by) für alle x,y ∈ ℤ;
bd | bn, b ≠ 0 ⇒ d | n (Kürzungsregel);
d | n, n ≠ 0 ⇒|d|≤|n|;
d | n, n | d ⇒ d = ±n.

Hierbei ist der Betrag |x| definiert als das Maximum von x und −x. Von diesen vielen Regeln verifizieren wir hier nur (4.): Nach Voraussetzung gelten a = md und b = nd mit gewissen m, n. Dann gilt für beliebige x,y ∈ ℤ zunächst ax + by = mdx + ndy = (mx + ny)d und damit d | (ax + by).

Aufgabe 1. Beweisen Sie die restlichen Rechenregeln zur Teilbarkeit.

Aus Rechenregel (4.) folgt u.a., dass eine ganze Zahl ≠ 0 nur endlich viele Teiler besitzt. Damit besitzen a,b ∈ ℤ, nicht beide gleich Null, einen größten gemeinsamen Teiler ggT(a,b) ∈ ℕ, für den also gilt

ggT(a,b) | a und ggT(a,b) | b;
wenn d | a und d | b, dann d | ggT(a,b).

Streng genommen ist die Existenz einer solchen Zahl ggT(a,b) hier zu zeigen. Hierzu kann man z.B. wieder mit Hilfe der Wohlordnung argumentieren; die Menge der Teiler d von a und b ist nicht-leer (da 1 | a und 1 | b). Ferner setzen wir ggT(0, 0) = 0. Gilt ggT(a,b) = 1, so nennen wir a und b teilerfremd.

Wie so oft starten wir mit einer simplen Tatsache, die sich jedoch als sehr wichtig erweisen wird und deshalb auch einen Namen trägt:

Satz (Division mit Rest).

Zu a,b ∈ ℤ mit b ≠ 0 existieren eindeutig bestimmte ganze Zahlen q,r, so dass

a = bq + r mit 0 ≤ r < |b|.

Beweis. Mit dem Prinzip der Wohlordnung besitzt

N = {a − bq : q ∈ ℤ } ∩ ℕ ∪ {0}

ein kleinstes Element r. Falls b ∤ a gilt 1 ≤ r < |b|; andernfalls ist r = 0 und in jedem Fall sind q,r ∈ ℤ offensichtlich eindeutig. qed.

Die Aussage des Satzes wird kurz mit ’Division mit Rest’ bezeichnet, weil in

a/b = q + r/b

für natürliche Zahlen b die Zahl q der eindeutig bestimmte Ganzteil von a/b ist, d.h. die größte ganze Zahl ≤ a/b; für den Rest gilt dabei 0 ≤ r/b < 1. Der Beweis des Satzes ist konstruktiv: Sind etwa a = 33 und b = 5 gegeben, so sind die ganzen Zahlen a − bq = 33 − 5q gegeben durch

..., − 2 = 33 − 5 ⋅ 7, 3 = 33 − 5 ⋅ 6, 8 = 33 − 5 ⋅ 5, 13 = 33 − 5 ⋅ 4, ...,

also N = {3, 8, 13,…} (denn die negativen a − bq gehören ja nicht zu N). Es ist hierbei offensichtlich

a − bq < 0 ⇐⇒ q > a/b falls b > 0

(bzw. q <a/b falls b < 0), so dass also letztlich nur wenige Werte für q mit eben 0 ≤ r = a − bq < |b| in Frage kommen. Oder noch einfacher: Mit Hilfe unserer vorangegangenen Bermerkung ist q als die eindeutig bestimmte größte ganze Zahl ≤ a/b zu nehmen; der Rest r ergibt sich dann unmittelbar.
Im Beispiel:

33/5= 6 + 3/5

Hier nun eine erste wichtige Konsequenz:

Korollar.

Für a,b ∈ ℤ mit b ≠ 0 bezeichne d = ggT(a,b). Dann gilt

d ℤ := {dk : k ∈ ℤ} = {ax + by : x,y ∈ ℤ}.

Der größte gemeinsame Teiler zweier ganzer Zahlen a,b lässt sich also als Linearkombination ax + by von a und b schreiben!

Beweis. Wir nehmen an, dass a ≠ 0 ist (ansonsten ist die zu beweisende Aussage trivial). Wir definieren

Z := {ax + by : x,y ∈ ℤ } ⊂ ℤ

und nennen m die kleinste natürliche Zahl in Z, also m := min{n ∈ ℕ ∩ Z} (existent auf Grund der Wohlordnung). Wir schreiben stets min{x : x ∈ M} für das kleinste Element einer Menge M (wenn es denn existiert). Nach Rechenregel (4.) gilt d | z für jedes z ∈ Z, also Z ⊂ dℤ und d | m. Nun ist mit a,qm ∈ Z auch a − qm ∈ Z (wie man sofort nachrechnet). Division mit Rest von a durch m (statt b im vorherigen Satz) liefert den Rest 0 da m ∈ ℕ minimal in Z ist. Also gilt m | a und analog m | b (mit demselben Argument für b statt a auf Grund der Symmetrie). Also m ≤ d = ggT(a,b). Zusammen mit d | m folgt d = m (nach (7.)) und dℤ⊂ Z. Also ergibt sich insgesamt Z = dℤ. qed.

Einige Rechenregeln für den größten gemeinsamen Teiler:

ggT(a,b) = ggT(b,a);
ggT(a, ggT(b,c)) = ggT(ggT(a,b),c);
ggT(ac,bc) = |c| ggT(a,b).

Das kleinste gemeinsame Vielfache zweier ganzer Zahlen a,b ist definiert als das Minimum aller m ∈ ℕ für die a | m und b | m gilt; in Zeichen kgV[a,b].

Aufgabe 2. Zeigen Sie für beliebige a,b ∈ ℤ die Formel

ab = ggT (a,b) ⋅ kgV [a,b].

Den größten gemeinsamen Teiler zweier ganzer Zahlen berechnet man am einfachsten mit dem so genannten euklidischen Algorithmus. Dieses Verfahren entspricht einer sukzessiven Division mit Rest (siehe obigen Satz).

Satz (Euklidischer Algorithmus).

Zu gegebenen natürlichen Zahlen a und b mit a > b seien r₋₁ := a,r₀ := b und

a = q₁b + r_1,

b = q₂ r₁ + r_2,

_...

r_j-2=q_jr_j-1 +r_j,

_...

r_n-2 = q_nr_m-1 + r_n,

r_n-1 = q_n+1r_n

mit jeweils q_j,r_j ∈ ℤ und 0 ≤ r_j< r_j−1. Dann gilt für den letzten nicht verschwindenden Rest r_n = ggT(a,b).

Beweis. Die Reste r_j sind nicht-negative ganze Zahlen, die in jedem Schritt kleiner werden: 0 ≤ r_j < r_j−1. Also terminiert der Algorithmus (nach höchstens b Schritten). Durchläuft man das Gleichungssystem von unten nach oben, so zeigt sich

r_n | r_n-1 ⇒ r_n|r_n-2 ⇒ ... ⇒ r_n| r₀ = b ⇒ r_n| r_-1 = a.

Damit ist r_n ein gemeinsamer Teiler von a und b. Für jeden gemeinsamen Teiler d von a und b ergibt sich beim Durchlauf des Gleichungssystems von oben nach unten sukzessive

d | a = r_-1, d | b = r₀ ⇒ d | r₁ ⇒ ... ⇒ d | r_n-1 ⇒ d | r_n.

Also ist r_n der größte gemeinsame Teiler von a und b. qed.

Beispiel des Euklidischen Algorithmus und Spiel zum Euklidischen Algorithmus.
Den größten gemeinsamen Teiler bzw. das kleinste gemeinsame Vielfache von mehr als zwei ganzen Zahlen erklärt man induktiv;

ggT (a,b,c) = ggT (a,ggT (b,c)).

Zahlen a₁,…,a_m heißen teilerfremd, wenn ggT(a₁,…,a_m) = 1 gilt; sie heißen paarweise teilerfremd, wenn ggT(a_i,a_j) = 1 für alle 1 ≤ i,j ≤ m mit i≠j besteht. Letzteres impliziert ihre Teilerfremdheit, die Umkehrung gilt jedoch nicht:

6 = 2 ⋅ 3, 10 = 2 ⋅ 5, 15 = 3 ⋅ 5.

______________________________________________________________________________

vhb - Kurs: Grundlagen der elementaren Zahlentheorie

III.2. Lineare diophantische Gleichungen

___________________________________________________________________________

Diophantische Gleichungen sind nach dem griechischen Mathematiker Diophantus (ca. 200 v.Chr. - 284 v. Chr.) benannt und spielen insbesondere in der algebraischen Zahlentheorie eine wichtige Rolle. Unter einer derartigen Gleichung versteht man eine polynomielle Gleichung mit ganzzahligen Koeffizienten bei der man sich insbesondere für die ganzzahligen Lösungen interessiert. Derartige Gleichungen haben häufig einen realen Bezug, so treten sie beispielsweise in der Chemie oder bei der Gewichteverteilung bei Balkenwaagen auf.

Wir starten bescheiden mit einer linearen Gleichung in zwei Unbekannten

aX + bY = 1

mit a,b ∈ ℤ. Dies beschreibt eine Gerade in der euklidischen Ebene und wir fragen: Gibt es Punkte mit ganzzahligen Koordinaten auf dieser Geraden?

Gibt es also ganzzahlige Lösungen der obigen Gleichung? Angenommen, a und b sind nicht teilerfremd, also ggT(a,b) > 1, dann ist nach dem Korollar aus III.1. ax + by für beliebige ganzzahlige x,y stets ein Vielfaches von ggT(a,b) und also nie gleich eins; in diesem Fall ist die Gleichung also unlösbar. Sind jedoch a und b teilerfremd, also ggT(a,b) = 1 (gleich der rechten Seite), dann ist die Gleichung wiederum nach dem Korollar aus III.1. lösbar.
Es ist gut zu wissen, wann diese Gleichung lösbar ist, aber im Falle ihrer Lösbarkeit ist es in der Praxis oft darüber hinaus sehr hilfreich, auch noch eine Lösung (oder gar alle) zu kennen. Unser bisheriges Argument reicht an dieser Stelle leider nicht aus, wohl aber hilft hier der euklidische Algorithmus aus dem vorhergehenden Kapitel weiter. Besonders gut lässt sich dies mit Hilfe eines Beispiels illustrieren.

Aufgabe 1.

Bestimmen Sie die Menge aller ganzzahligen Lösungen der linearen Gleichung

51X + 72Y = c für c ∈ {1,±3, 6}.

Eine wichtige Verallgemeinerung unserer bisherigen Überlegungen (insbesondere des Korollars aus III.1.) liefert der

Satz (Satz von Bézout).

Die lineare Gleichung

(1)

mit ganzen Zahlen a,b,c ist genau dann ganzzahlig lösbar, wenn ggT(a,b) ein Teiler von c ist; in diesem Fall ist die Menge der ganzzahligen Lösungen gegeben durch

wobei x₀,y₀ eine spezielle ganzzahlige Lösung der Gleichung darstellt.

Beweis. Nach Obigem sind die Gleichungen

(2) linea

bzw.

(3)

ganzzahlig lösbar. Falls ggT(a,b) ein Teiler von c ist, d.h. c = dggT(a,b) für ein d ∈ ℤ, so ist mit einer Lösung x,y von (3) dann dx,dy eine Lösung der Gleichung:

adx + bdy = d(ax + by ) = d ⋅ ggT (a,b) = c.

Für die Umkehrung erinnern wir uns wiederum an das Korollar aus der ’Division mit Rest’: Für beliebige x,y ∈ ℤ ist ax + by ein Vielfaches von ggT(a,b). Wenn also ggT(a,b) ∤ c, kann (2) nicht ganzzahlig gelöst werden.

Dank des euklidischen Algorithmus lässt sich die Lösungsgesamtheit wie folgt beschreiben: Gegeben eine spezielle ganzzahlige Lösung x₀,y₀ von (2), so ist insbesondere ggT(a,b) ein Teiler von c und jede Lösung von (1) ist – wie man sofort nachrechnet – von der Form

Der Satz ist somit vollständig bewiesen. qed.

Die ganzzahligen Lösungen einer linearen diophantischen Gleichung sind auch hinsichtlich der rationalen Approximation sehr interessant, siehe hierfür wiederum ein illustrierendes Beispiel.

______________________________________________________________________________

vhb - Kurs: Grundlagen der elementaren Zahlentheorie

III.3. Approximation mit Kettenbrüchen

_______________________________________________________________

In diesem Kapitel werden zunächst Kettenbrüche erklärt und anschließend die Approximation reeller Zahlen mit Kettenbrüchen beschrieben.

______________________________________________________________________________

vhb - Kurs: Grundlagen der elementaren Zahlentheorie

III.3.1 Approximationssatz von Dirichlet

_______________________________________________________________

Die Menge ℚ liegt dicht in der Menge ℝ, d.h. in jeder noch so kleinen Umgebung einer beliebigen reellen Zahl gibt es eine (tatsächlich sogar unendlich viele) rationale Zahl(en). Insofern macht es Sinn, reelle Zahlen durch rationale approximieren zu wollen, aber wie macht man das?

Eine wichtige Frage ist dabei, wann eine rationale Zahl überhaupt eine gute rationale Approximation genannt werden sollte?
Eine mögliche Antwort hierauf liefert der folgende

Satz (Approximationssatz von Dirichlet, 1842).

Zu einer Irrationalzahl α gibt es unendlich viele rationale Zahlen p/q mit

Beweis. Wir notieren den Ganzteil und den gebrochenen Anteil einer reellen Zahl x als

Sei nun Q eine natürliche Zahl, dann liegen die Q + 1 Punkte 0,{α},{2α},…,{Qα} im Einheitsintervall [0, 1) in den Q disjunkten Teilintervallen [(j−1)/Q, j/Q) verteilt, wobei j = 1,…Q. Das Schubfachprinzip besagt, dass wenn Q + 1 Objekte auf Q Fächer verteilt werden, mindestens eines der Fächer mindestens zwei Objekte enthalten muss. Also existiert mindestens ein Teilintervall, welches mindestens zwei unserer Punkte, sagen wir {kα} ≥ {ℓα}, enthält (wobei also 0 ≤ k, ℓ ≤ Q und k≠ℓ). Damit folgt

Weil nun {kα}−{ℓα} in dem Intervall [0,1/Q) liegt, addieren sich die Ganzteile in der vorangegangenen Formel zu null auf. Sei nun q = k − ℓ, dann gilt also {qα} = {kα}−{ℓα} <1/Q. Mit p := [qα] folgt ferner

welches wegen q < Q die gewünschte Abschätzung liefert.

Jetzt nehmen wir an, dass α irrational ist und nur endlich viele p₁/q₁,…,p_n/q_n der gewünschten Ungleichung genügen. Mit der Irrationalität von α gibt es dann ein Q mit |α −p_j/q_j| >1/Q für j = 1,…,n, was der oberen Abschätzung gegen 1/(q_jQ) widerspricht. Damit ist der Satz bewiesen. qed.

Der Beweis des Dirichletschen Approximationssatzes zeigt leider nicht, wie zu einer gegebenen Irrationalzahl wirklich gute rationale Approximationen tatsächlich gefunden werden können.

Tatsächlich charakterisiert die Approximationseigenschaft des Dirichletschen Approximationssatzes Irrationalzahlen:

Satz.

Für rationale Zahlen α gibt es nur endlich viele rationale Zahlen p/q mit

Die Frage, ob eine gegebene reelle Zahl α irrational ist, lässt sich also durch die Qualität rationaler Näherungen beantworten. Im Falle eines irrationalen α existieren unendlich viele p/q, die um weniger als 1/q² von α abweichen, während für rationale α nur endlich viele solche existieren.

Beweis. Ist α = m/n mit teilerfremden m,n und m/n ≠ p/q, so gilt

und also kann die Ungleichung des Satzes nur mit q < n erfüllt sein. Zu jedem 1 < q < n gibt es aber nur höchstens ein p mit dieser Eigenschaft, was die Endlichkeitsaussage beweist. qed.

______________________________________________________________________________

vhb - Kurs: Grundlagen der elementaren Zahlentheorie

III.3.2. Kettenbrüche

_______________________________________________________________________________

Kettenbrüche als Werkzeug zur Findung geeigneter rationaler Approximationen wurden in vielen Kulturen benutzt; eine erste systematische Theorie hingegen wurde aber erst durch den Astronomen Christaan Huygens im 17. Jahrhundert gegeben, als dieser ein mechanisches Modell unseres Sonnensystems bauen wollte.

Zunächst betrachten wir den euklidischen Algorithmus, welchen wir (gemäß der Notation aus III.1.) umschreiben als

(1)

für n ≤ m; dabei steht ⌊x⌋ für die größte ganze Zahl ≤ x (auch Gaußklammer bzw. Ganfteil genannt). Setzen wir a_n = ⌊r_n−1/r_n⌋, so ergibt sich

a/b

Die erste Gleichung liefert den Ganzteil von a/b; jede weitere gibt bessere und bessere Näherungen (mit den kleinst möglichen Nennern entsprechend der Approximationsqualität, wie wir unten zeigen werden). Ein Beispiel liefert das Sonnenjahr.
Der typographische Albtraum

heißt Kettenbruch (engl. continued fraction); die a_n nennt man Teilnenner. Wir notieren einen solchen Kettenbruch kurz mit

Zunächst betrachten wir [a₀,…,a_m] als eine formale Funktion in unabhängigen Variablen a₀,…,a_m. Offensichtlich gilt

und

[a ,a ,a ] = a2a1a0 +-a2-+-a0-. 0 1 2 a2a1 + 1

Per Induktion zeigt man

[ ] [a ,a ,...,a ] = a ,a ,...,a + -1- 0 1 n 0 1 n−1 an

und

[a0,a1,...,an] = a0 + ----1------= [a0,[a1,...,an]]. [a1,...,an ]

Ein besonders interessanter Kettenbruch ergibt übrigens sich für den Quotienten aufeinanderfolgender Fibonacci-Zahlen.
Für n ≤ m nennen wir [a₀,a₁,…,a_n] den n-ten Näherungsbruch an [a₀,a₁,…,a_m]. Wir definieren desweiteren

( { p−1 = 1, p0 = a0 und pn = anpn−1 + pn−2, (3) ( q−1 = 0, q0 = 1 und qn = anqn−1 + qn−2.

Die Berechnung der Näherungsbrüche erfolgt leicht mit Hilfe von

Satz.

Für 0 ≤ n ≤ m gilt

pn-= [a0,a1,...,an]. qn

Dabei ist

pnqn −1 − pn−1qn = (− 1)n−1

und insbesondere sind p_n und q_n teilerfremd für ganzzahlige Teilnenner a₀,a₁,…,a_m.

Beweis per Induktion nach n. Der Fall n = 0 ist trivial. Der Fall n = 1 folgt unmittelbar aus

a1a0 + 1 p1 [a0,a1] = ---------= --. a1 q1

Angenommen die Formel ist richtig für n. In Anbetracht von (2) gilt

[ ] --1-- [a0, a1,...,an,an+1] = a0,a1,...,an + an+1 .

Mit der Rekursionsformel (3) für die p_n,q_n schreibt sich dies als

( ) --1- (an-+-an+1)-pn−1-+-pn−2- (an+1an-+--1)pn−1 +-an+1pn−2 -1-- = (an+1an + 1)qn−1 + an+1qn−2 an + an+1 qn−1 + qn−2 an+1pn + pn−1 pn+1 = -------------- = -----, an+1qn + qn−1 qn+1

was die Induktion und den Beweis der ersten Aussage abschließt.

Mittels (3) ist

p q − p q = (a p + p )q − p (a q + q ) n n− 1 n− 1 n n n− 1 n−2 n−1 n−1 n n−1 n−2 = − (pn−1qn−2 − pn−2qn− 1).

Wiederholen wir dieses Argument für n − 1,n − 2,…, 2, 1, so ergibt sich induktiv

(− 1 )n (p0q− 1 − p− 1q0) = (− 1)n+1

und damit die zweite Behauptung; die Teilerfremdheitsaussage ist eine einfache Schlussfolgerung. qed.

Jetzt weisen wir den Teilnennern a_n und somit auch dem Kettenbruch [a₀,a₁,…,a_m] numerische Werte zu. Wir fordern a₀∈ℤ und a_n∈ℕ für 1 ≤ n < m, sowie a_m≥ 1. Sei jetzt α irgendeine rationale Zahl. Dann gibt es teilerfremde ganze Zahlen a und b > 0, so dass α = ab. Es folgt aus der Variation des euklidischen Algorithmus (1) angewandt auf r₋₁ = a und r₀ = b, dass α als endlicher Kettenbruch dargestellt werden kann:

[ ] a-= [a0,a1,a2,...,am ] , wobei an = rn−1-. b rn

Diese Darstellung ist nicht eindeutig, da

[a0,a1,a2,...,am ] = [a0,a1,a2, ...,am − 1,1];

wenn wir allerdings a_m≥ 2 für den letzten Teilnenner fordern, so besitzt jede rationale Zahl eine eindeutige Darstellung als endlicher Kettenbruch.
Jetzt wollen wir Kettenbrüche zu nicht notwendig rationalen Zahlen bilden. Wir können den Algorithmus (1) zur Berechnung der Kettenbruchentwicklung von rationalen Zahlen umschreiben als

-1--- α0 := α, αn = ⌊αn ⌋ + αn+1 f¨ur n = 0,1, ... .

Setzen wir a_n = ⌊α_n⌋, so erhalten wir α = [a₀,a₁,…,a_n,α_n+1]. Dieser Algorithmus ist der Kettenbruchalgorithmus. Ist α rational, dann bricht die Iteration nach endlich vielen Schritten ab und der Kettenbruchalgorithmus ist nichts anderes als der euklidische Algorithmus in Verkleidung. Beispiel.
Sei jetzt α irgendeine Irrationalzahl. Dann bricht die Iteration nicht ab, da ansonsten α ja eine Darstellung als endlicher Kettenbruch hätte und somit rational wäre. Also liefert die Iteration für Irrationalzahlen eine unendliche Folge endlicher Kettenbrüche:

[a ,a ,...] := lim [a ,a ,...,α ]. 0 1 m→ ∞ 0 1 m

Der Grenzwert [a₀,a₁,a₂,…] heißt unendlicher Kettenbruch und das Erste, was wir uns zu fragen haben, ist, ob dieser unendliche Prozess konvergent ist, und wenn ja, ob der Grenzwert etwas mit α zu tun hat?

Satz.

Sei α = [a₀,a₁,…,a_n,α_n+1] irrational mit Näherungsbrüchen p_n/q_n. Dann gilt

pn- -----(−-1)n------- α − q = q (α q + q ). n n n+1 n n−1

Insbesondere ist

| | || pn-|| --1---- |α − qn | < an+1q2. n

und

pn α = lim ---= [a0,a1,a2,...]. n→∞ qn

Beweis. Zunächst bemerken wir, dass alle unsere Beobachtungen über endliche Kettenbrüche sich auf unendliche Kettenbrüche übertragen - insbesondere (3) und der vorherige Satz. Eine kurze Berechnung zeigt

pn- αn+1pn-+--pn−1 pn- -pn−1qn-−-pnqn−1-- α − q = α q + q − q = q (α q + q ). n n+1 n n−1 n n n+1 n n−1

Der vorherige Satz impliziert damit die erste Behauptung.

Wegen a_n+1≤ α_n+1 folgt ferner

| | ||α − pn|| < --------1---------, | qn| qn(an+1qn + qn− 1)

was bereits (5) beweist. Im Falle eines irrationalen α sind die Folgen der p_n und der q_n jeweils streng monoton wachsend für n ≥ 2 (d.h. also p_n+1> p_n und q_n+1> q_n wie man sofort aus dem Bildungsgesetz (3) folgert). Damit ist die Folge der Näherungsbrüche p_n/q_n abwechselnd größer bzw. kleiner als α; die mit geradem Index n liegen links, die mit ungeradem Index rechts:

p0 p2 p3 p1 q--< q-< ...< α < ...< q--< q--. 0 2 3 1

Ferner gilt (wiederum) nach vorherigem Satz für die Distanz zweier aufeinanderfolgender Näherungsbrüche

||p p || |p q − p q | 1 ||--n− -n−1|| = --n-n−1----n−1-n- = ------, qn qn−1 qn−1qn qn−1qn

was mit q_n→∞ gegen null konvergiert. Die Folge der Näherungsbrüche bildet also eine Intervallschachtelung an α. Ist α irrational, dann terminiert der Kettenbruchalgorithmus nicht und die Folge der Nenner q_n der Näherungsbrüche ist unbeschränkt. Also folgt aus der ersten Behauptung, dass der Abstand aufeinanderfolgender Näherungsbrüche kleiner und kleiner wird und gegen Null konvergiert. Also konvergieren die p_n/q_n gegen den Grenzwert [a₀,a₁,…] und dieser Grenzwert ist gleich α. Der Satz ist damit vollständig bewiesen. qed.

Sehr interessant sind auch so genannte periodische Kettenbrüche.

______________________________________________________________________________

vhb - Kurs: Grundlagen der elementaren Zahlentheorie

III.3.3. Gesetz der besten Approximation

Man sieht leicht, dass die Kettenbruchentwicklung einer Irrationalzahl eindeutig ist. Dies liefert eine Möglichkeit, die Menge ℝ der reellen Zahlen aus der Menge ℚ der rationalen Zahlen zu konstruieren. Ferner, liefert die Kettenbruchentwicklung eine Ordnung auf der reellen Achse.

Gegeben zwei reelle Zahlen α = [a₀,…,a_n,α_n+1] und α' = [a₀,…,a_n,α_n+1'] mit denselben ersten Teilnennern, dann folgt, dass jedes α'', das zwischen α und α' liegt, eine Kettenbruchentwicklung besitzt, die mit denselben Teilnennern startet, wie die von α und α', nämlich:

α'' = [a ,...,a ,α '' ] 0 n n+1

für irgendein α_n+1'' zwischen α_n+1 und α_n+1'. Dies zeigt man leicht mit Induktion.
Der zweite Satz aus dem vorherigen Kapitel zeigt, wie wichtig Kettenbrüche in der Theorie der diophantischen Approximation sind. Es folgt nämlich unmittelbar: Ist α = [a₀,a₁,…] irrational mit Näherungsbrüchen p_n/q_n, dann gilt

| | || pn-|| --1---- |α − q | < a q2. n n+1 n

Dies verschärft den Dirichletschen Approximationssatz und die Folge der Näherungsbrüche approximiert α besser und besser (denn die Teilnenner wachsen streng monoton).
Diese Beobachtung ist kein Wunder wie Lagrange 1770 bewiesen hat:

Satz (Gesetz der besten Approximation).

Sei α irgendeine reelle Zahl mit Näherungsbrüchen p_n/q_n. Ist n ≥ 2 und sind p,q natürliche Zahlen mit 0 < q ≤ q_n und p/q ≠ p_n/q_n, so gilt

|qnα − pn| < |q α − p|.

Das Gesetz der besten Approximation besagt also, dass die besten rationalen Approximationen durch die Näherungsbrüche der Kettenbruchentwicklung gegeben sind. Dies lässt sich an Beispielen veranschaulichen - ein besonders Prominentes ist unser täglich verwendetes Papierformat Din-A.

Beweis. Wir dürfen annehmen, dass p und q teilerfremd sind. Wegen

|qnα − pn| < |qn−1α − pn−1|

genügt es, die Behauptung unter der Annahme q_n−1< q ≤ q_n zu zeigen; die volle Aussage ergibt sich dann per Induktion. Gilt q = q_n, so ist p ≠ p_n und

|| || |p-− pn|≥ 1-. |q qn| qn

Allerdings gilt

| | | pn | 1 1 ||α − ---|| ≤ -2-< ---- qn qn 2qn

denn q_n+1 ≥ 3 für n ≥ 2. Ferner gilt

| | | | | | | | || p|| ||p- pn|| || pn|| -1-- || pn|| |α − q| ≥ |q − q | − |α − q | > 2q > |α − q | , n n n n

was die zu beweisende Ungleichung nach Multiplikation mit q = q_n liefert.

Es verbleibt der Fall: q_n−1< q < q_n. Das lineare Gleichungssystem

pnX + pn−1Y = p und qnX + qn−1Y = q

besitzt die Lösung

x = -pqn−1-−-qpn−1--= ±(pqn− 1 − qpn −1) pnqn−1 − pn−1qn

und

y = ---pqn −-qpn----= ± (pqn − qpn); pnqn−1 − pn−1qn

Dies verifiziert man durch Nachrechnen. Tatsächlich ist diese Lösung eindeutig, d.h. es gibt neben dieser Lösung keine weitere, was man mit Hilfe der Cramerschen Regel zeigen kann (welche vielleicht aus der Schule bekannt ist, auf jeden Fall aber Thema der Lineraen Algebra sein wird). Insbesondere sind x und y von Null verschiedene ganze Zahlen. Offensichtlich haben x und y unterschiedliches Vorzeichen (denn q_n−1< q_nx + q_n−1y = q < q_n+1) und damit q_nα − p_n und q_n−1α − p_n−1 ebenso. Also besitzen x(q_nα − p_n) und y(q_n−1α − p_n−1) dasselbe Vorzeichen. Nach Konstruktion ist

qα − p = x(qnα − pn ) + y(qn− 1α − pn−1),

und also folgt

|qα − p | > |qn−1α − pn− 1| > |qnα − pn|,

was zu zeigen war. qed.

Eine Irrationalzahl α heißt quadratisch irrational, falls sie Wurzel eines quadratischen Polynoms mit ganzzahligen Koeffizienten ist; da α irrational ist, ist das Polynom irreduzibel (d.h. nicht als Produkt zweier linearer Polynome mit rationalen Koeffizienten darstellbar). Jede relle quadratische Irrationalität lässt sich also darstellen als

-- a + b√ d α = -------- , c

wobei a,b ∈ ℤ, c,d ∈ ℕ. Dies ergibt sich unmittelbar durch das Lösen der zu Grunde liegenden quadratischen Gleichung. Alle Beispiele dieser quadratischen Irrationalitäten haben folgendes gemein: Ihre Kettenbruchentwicklung ist periodisch! Hierbei heißt ein Kettenbruch [a₀,a₁,…] periodisch, falls es einen Index ℓ gibt, so dass a_n+ℓ = a_n für alle hinreichend großen n. Wir schreiben

-------------- [a0,a1, ...,ar,ar+1,...,ar+ℓ] = [a0,a1,...,ar,ar+1,...,ar+ ℓ,ar+1,...,ar+ ℓ,...];

hier gelte a_n+ℓ = a_n für alle n ≥ r + 1. Die Folge a_r+1,…,a_r+ℓ heißt Peridode und ℓ ist ihre Länge. Die minimale Periode nennt man auch die primitive Periode. Der folgende Satz beschreibt die Kettenbruchentwicklung von Quadratwurzeln in sehr expliziter Weise: Genau dann wenn d ∈ ℕ kein Quadrat ist, gilt

[[ ] ------------------[---]] √ -- √ -- √ -- d = d ,a1,a2,...,a2,a1,2 d ,

wobei a₁,a₂,…,a₂,a₁ ein Palindrom ist. Dies wurde von Galois bewiesen, der tragisch in einem Duell verstarb und trotz seines jungen Alters unsterblich für die Algebra und Zahlentheorie ist. Wir verzichten hier auf den Beweis.

______________________________________________________________________________

vhb - Kurs: Grundlagen der elementaren Zahlentheorie

III.4. Primzahlen

_______________________________________________________________________________

Primzahlen sind die multiplikativen Bausteine der ganzen Zahlen, da jede ganze Zahl in Primzahlen faktorisiert werden kann. Diese Faktorisierung ist bei großen Zahlen zumeist sehr aufwendig und es gibt noch kein effizientes Faktorisierungsverfahren. Diese Schwierigkeit wird bei modernen Verschlüsselungsverfahren oft ausgenutzt. Überhaupt haben Primzahlen eine sehr prominente Stellung im Alltag und in der Mathematik.

Eine natürliche Zahl n > 1 heißt Primzahl oder kurz prim, wenn sie nur durch sich selbst und 1 teilbar ist (innerhalb der Menge ℕ); ansonsten nennt man n zusammengesetzt. Die ’ersten’ Primzahlen findet man leicht:

2,3,5,7,11, 13,17,...,30449, ...

Wir starten mit dem Lemma des Euklid, welches wir schon in einem Exkurs zum ersten Kapitel benutzt hatten:

Lemma (Lemma von Euklid).

Teilt eine Primzahl p ein Produkt, so teilt sie mindestens einen der Faktoren:

p | ab ⇒ p | a oder p | b.

Beim Beweis dürfen wir natürlich kein Ergebnis verwenden, welches wir mit Hife des Euklidschen Lemmas bewiesen haben, ansonsten entstünde ein ’Zirkelschluss’ und nichts wäre wirklich bewiesen.

Beweis. Angenommen, p ∤ a, also insbesondere ggT(p,a) = 1 (da p eine Primzahl ist). Nach dem Korollar aus III.1. existieren ganze Zahlen x,y mit

px + ay = 1 bzw. bpx + aby = b.

Wegen p∣pbx und p∣aby folgt p∣b (nach Rechenregel (4) aus dem Kapitel zur Teilbarkeit). qed.

Die Aussage des euklidschen Lemmas ist falsch für zusammengesetzte Zahlen: Beispielsweise teilt 6 das Produkt 2 ⋅ 3, jedoch keinen der Faktoren. Insofern charakterisiert das Lemma von Euklid also Primzahlen! Man überlege sich, wo genau im Beweis davon Gebrauch gemacht wurde, dass p eine Primzahl ist und warum das so entscheidend ist?

Wir haben schon die multiplikative Zerlegbarkeit ganzer Zahlen in Primfaktoren angesprochen. Diese ist sogar eindeutig. So simpel dieser Sachverhalt auch sein mag, diese Beobachtung bildet einen der wichtigsten Sätze der Zahlentheorie überhaupt! Die entsprechende Aussage hätte eigentlich bereits in Euklids Elementen stehen können, jedoch findet man sie erst bei Gauß in seinen berühmten ’Disquisitiones Arithmeticae’ aus dem Jahre 1801.

Satz (Fundamentalsatz der Arithmetik).

Jede natürliche Zahl n besitzt eine eindeutige Primfaktorzerlegung, d.h. es gibt eindeutig bestimmte Exponenten ν_p(n) ∈ℕ₀, so dass

Hierbei läuft das Produkt über alle Primzahlen; tatsächlich sind stets jedoch nur endlich viele Exponenten ν_p(n) verschieden von Null. Für n = 1 verschwinden alle Exponenten und das Produkt ist leer.

Beweis. Wir nutzen die Wohlordnung von ℕ. Wir zeigen zunächst die Existenz: Ist n ∈ℕ die kleinste Zahl, für die eine solche Primfaktorzerlegung nicht bekannt ist, so ist n entweder prim oder ein Produkt kleinerer natürlicher Zahlen, für die die Aussage bereits bekannt ist. Also folgt die Existenz einer Primfaktorzerlegung von n.

Nun der Nachweis der Eindeutigkeit: Angenommen, n ist minimal mit zwei wesentlich verschiedenen Primfaktorzerlegungen,

wobei ’wesentlich verschieden’ p_i≠q_j für alle i,j bedeutet (ansonsten könnten wir ja kürzen). Jedes p_i teilt n = q₁q₂⋅…⋅ q_s, also nach dem Lemma von Euklid auch einen Faktor q_k. Da p_i und q_k jeweils prim sind, folgte p_i = q_k, ein Widerspruch zu unserer Annahme. qed.

Wie reichhaltig ist die Menge der multiplikativen Bausteine der ganzen Zahlen? Eine erste Antwort auf diese Frage gibt ein berühmtes Resultat von Euklid (was heutzutage bereits in der Schule gelehrt wird):

Satz (Euklid).

Es gibt unendlich viele Primzahlen.

Beweis. Wir zeigen: Zu jeder gegebenen endlichen Menge von Primzahlen existiert eine weitere; damit ist die Menge der Primzahlen also nicht endlich! Sei hierzu p₁ = 2,p₂,…,p_m eine Menge von Primzahlen. (Hierbei haben wir p₁ explizit mit dem Wert 2 belegt, damit wir nicht mit einer leeren Primzahlmenge argumentieren!) Dann ist die natürliche Zahl

sicherlich größer als 1 und besitzt also nach dem Fundamentalsatz (mindestens) einen Primfaktor p, d.h. p∣q. (Sie kann dabei auch selbst prim sein, aber das ist hier nicht weiter von Belang!) Käme nun die Primzahl p unter den Primzahlen p₁,…,p_m vor, so folgte

Mit q und q − 1 würde dann aber p auch jede Linearkombination dieser beiden Zahlen teilen (4. Rechenregel aus III.1.), also insbesondere

ein Widerspruch (mittels der 2. Rechenregel aus III.1., denn p ist eine Primzahl, also größer 1). Also war unsere Annahme falsch, d.h. p kommt nicht unter den Primzahlen p₁,…,p_m vor und der Satz ist bewiesen. qed.

Der Beweis liefert ein Beispiel dafür, zu einer gegebenen Liste von Primzahlen weitere zu finden.
Die Unendlichkeitsaussage von Euklid gibt nur eine unzulängliche Beschreibung für die Primzahlen. Auf den ersten Blick scheinen die Primzahlen wie zufällig aufzutreten, aber gehorcht ihre Verteilung vielleicht doch einer bestimmten erstaunlichen Gesetzmäßigkeit. Ein klassische Fragestellung der Zahlentheorie lautet deshalb:

Wie sind die Primzahlen innerhalb der natürlichen Zahlen verteilt? Veranschaulichen lässt sich diese Frage beispielsweise durch die sogenannte Ulam-Spirale.

______________________________________________________________________________

vhb - Kurs: Grundlagen der elementaren Zahlentheorie

III.5. Rechnen mit Restklassen

__________________________________________________________________________

Eine zahlentheoretische Besonderheit bildet das Rechnen mit sogenannten Restklassen. Eine besonders spannende Anwendung hierfür ist beispielsweise das Verschlüsselungsverfahren RSA.

Zunächst soll das Rechnen mit Restklassen eingeführt werden. Sei hierzu m eine natürliche Zahl, so definiert

a ∼ b : ⇔ m | (a − b)

eine Äquivalenzrelation auf ℤ. Wir prüfen dies nach: Zunächst gilt m∣0 = a−a für beliebiges a ∈ ℤ, womit die Reflexivität folgt: a ∼ a. Für den Nachweis der Symmetrie a ∼ b⇔b ∼ a bemerken wir, dass jeder Teiler von b − a auch ein Teiler von a − b ist. Ferner folgt im Falle m∣(b − a) und m∣(c − b) auch

m | (c − b + (b − a)) = c − a,

also die Transitivität. Damit ist der Nachweis der Äquivalenzrelationseigenschaft erbracht. Statt a ∼ b schreiben wir suggestiver

a ≡ b mod m : ⇔ m | (a − b)

und sagen a ist kongruent b modulo m; hierbei heißt m der Modul und a ≡ b mod m nennt man eine Kongruenz. Wir schreiben a≢b mod m und sagen a ist inkongruent b modulo m, wenn m ∤ (b − a).

Kongruenzen sind eine Verallgemeinerung von Gleichungen, denn mit a = b gilt sicherlich auch a ≡ b mod m für jedes beliebige m ∈ ℕ. Insbesondere bestehen folgende Rechenregeln: Für beliebige a,b,c,d ∈ ℤ und m ∈ ℕ gelten

a ≡ a mod m,
a ≡ b mod m⇔b ≡ a mod m,,
a ≡ b,b ≡ c mod m ⇒ a ≡ c mod m,
a ≡ b,c ≡ d mod m ⇒ ax + cy ≡ bx + dy mod m,
a ≡ b,c ≡ d mod m ⇒ ax ⋅ cy ≡ bx ⋅ dy mod m,
ac ≡ bc mod m ⇒ a ≡ b mod (m∕ggT(m,c)),
a ≡ b mod m ⇒ aⁿ≡ bⁿ mod m für jedes n ∈ ℕ.

Die ersten drei Rechenregeln reflektieren, dass es sich bei der Kongruenz um eine Äquivalenzrelation handelt (s.o.). Von den restlichen Rechenregeln beweisen wir hier nur die 6. Rechenregel: Nach Voraussetzung gilt m∣(a − b)c und weil ggT(m,c) sowohl m als auch c teilt, folgt

(m ∕ggT (m, c)) ⋅ ggT(m, c) | (a − b) ⋅ (c∕ggT (m, c)) ⋅ ggT (m, c)

und mit der Teilerfremdheit von m∕ggT(m,c) und c∕ggT(m,c) ergibt sich (6.).
Wir schreiben die Äquivalenzklassen bzgl. ∼ als

a mod m := {b ∈ ℤ : a ≡ b mod m } = {b = a + mk : k ∈ ℤ} =: a + m ℤ

und sprechen von der Restklasse a modulo m. Eine Restklasse besteht dann aus allen ganzen Zahlen, die denselben Rest bei Division durch m lassen. Statt a könnte natürlich auch jedes andere Element b ∈ a mod m als Repräsentant dieser Restklasse herhalten, also etwa

... = − 2 mod 3 = 1 mod 3 = 4 mod 3 = 7 mod 3 = ...

Als Nächstes wollen wir Restklassen addieren und multiplizieren. Es stellt sich dabei heraus, dass man mit Restklassen zu einem fest fixierten Modul wie mit Zahlen rechnen kann! (Dies rechtfertigt gewissermaßen auch, dass wir oft a statt a mod m schreiben.) Hierzu definieren wir die Addition vermöge

(a mod m) + (b mod m) := (a + b) mod m

sowie die Multiplikation durch

(a mod m ) ⋅ (b mod m ) := (a ⋅ b) mod m.

Diese Verknüpfungen sind wohldefiniert, hängen also nicht vom gewählten Repräsentanten ab, wie wir am Beispiel der Addition illustrieren:
Mit a ≡ A und b ≡ B mod m existieren per Definition ganze Zahlen k,ℓ mit a = A + km und b = B + ℓm, so dass

(a mod m) + (b mod m) = (a + b) mod m

= (A + B + (k + ℓ)m) mod m

= (A + B) mod m = (A mod m) + (B mod m).

Nun betrachten wir sämtliche Restklassen eines festen Moduls gemeinsam. Modulo m bilden die Restklassen

0 mod m, 1 mod m, ..., m − 1 mod m

ein vollständiges Restsystem modulo m. Dieser Name ist gerechtfertigt, denn mit a mod m = b mod m folgt unmittelbar m∣(b − a), was für a,b ∈ {0, 1,…,m − 1} nur mit a = b möglich ist; ferner lässt sich jede Restklasse b mod m mit einem b ∉ {0, 1,…,m − 1} mittels Divison mit Rest als eine der obigen Restklassen a mod m mit einem a ∈ {0, 1,…,m − 1} nachweisen. Es gibt also genau m verschiedene Restklasse modulo m. Wir notieren die Menge der Restklassen modulo m mit

ℤ∕m ℤ := {0 mod m, 1 mod m, ..., m − 1 mod m }.

Hierbei handelt es sich also um eine Menge, deren Elemente wiederum Mengen sind, genauer: um eine endliche Menge, deren Elemente jeweils unendliche Mengen sind. Anhand von ausgewählten Beispielen kann man erkennen, dass solche Mengen die aus Kapitel II bekannten Axiome von Gruppen, Ringen oder sogar Körpern erfüllen.
Diese Strukturen sind kein Zufall

Satz.

Sei m eine natürliche Zahl, dann ist die Menge ℤ∕mℤ mit der oben definierten Addition und Multiplikation ein kommutativer Ring, der sogenannte Restklassenring modulo m.

Beweis. Die Menge ℤ∕mℤ ist mit der oben eingeführten Addition eine abelsche Gruppe mit neutralem Element 0 mod m bzgl. der Addition (was sich aus unseren bisherigen Überlegungen unmittelbar ergibt). Mit der oben definierten Multiplikation ist ℤ∕mℤ eine Halbgruppe und 1 mod m ist das neutrale Element der Multiplikation, insbesondere gelten die Distributiv- und Assoziativgesetze. Damit ist ℤ∕mℤ ein Ring und der Satz bewiesen. qed.

Die Idee der Restklassenbildung ist oft hilfreich, um redundante Information los zu werden, mit dem Vorteil von der unendlichen Menge ℤ zur endlichen Menge von Restklassen modulo m übergehen zu können. Die Restklassenarithmetik hat ganz verschiedene Anwendungen, wie beispielsweise bei ISBN-Nummern.

Eine Restklasse a mod m heißt prim, wenn a und m teilerfremd sind. Wegen ggT(a + km,m) = ggT(a,m) ist entweder jedes Element einer Restklasse oder keines teilerfremd zum Modul m. Die primen Restklassen modulo m = 8 sind damit

1, 3, 5, 7 mod 8.

Die Menge der primen Restklassen modulo m ist offensichtlich multiplikativ abgeschlossen (denn mit a und b ist auch das Produkt ab teilerfremd zu m). Die Anzahl φ(m) der primen Restklassen modm zählt die Eulersche φ-Funktion. Es gelten (wie man sich leicht überlegt)

φ(8) = 4, φ(10) = 4 und φ(2^k) = 2^k+1

bzw.

φ(p) = p-1 und φ(p^k) = p^k(1 - 1/p) für p prim.

Ein Vertretersystem der φ(m) vielen primen Restklassen modm heißt primes Restsystem modulo m. Ist b₁,…,b_φ(m)ein primes Restsystem modm, so auch ab₁,…,ab_φ(m), sofern a teilerfremd zu m ist. Es ist klar, dass mit einem zum Modul teilerfremden a mit b_j auch ab_j eine prime Restklasse modulo m ist. Aus ab_j≡ ab_k mod m folgt mit der 6. Rechenregel auch b_j≡ b_k mod m. Also sind mit b_j und b_k auch ab_j und ab_k inkongruente Restklassen modulo m. Diese Rechenregeln bilden die Grundlage weiterer wichtiger Sätze zum Restklassenkalkül, wie beispielsweise der Satz von Euler.
Die Idee der primen Restklassen (bzw. multiplikativ Inversen) hilft auch beim Lösen von linearen Kongruenzen.
Diese Idee lässt sich verallgemeinern

Satz.

Seien a,b ∈ ℤ und m ∈ ℕ. Dann ist die Kongruenz

aX ≡ b mod m

genau dann lösbar, wenn ggT(a,m)∣b. In diesem Fall gibt es genau ggT(a,m) inkongruente Lösungen modulo m.

Beweis. Nach dem Satz von Bézout ist die lineare diophantische Gleichung

aX = b + mY bzw. aX − mY = b

genau dann lösbar, wenn b ein Vielfaches von ggT(a,m) ist. In diesem Fall existieren also ganze Zahlen x und y, so dass

ax = b + my bzw. ax ≡ b mod m.

Damit ist eine lösende Restklasse modulo m also gefunden. Ist ggT(a,m) > 1, so ergeben sich mehrere Lösungen modulo m über die 6. Kürzungsregel.qed.

Der Beweis ist konstruktiv (dank des euklidischen Algorithmus versteckt im Satz von Bézout).
In einem alten chinesischen Mathematikbuch vor ca. zweitausend Jahrhen stellte sein Verfasser Sun-Tsu folgende Aufgabe:

Aufgabe 1.

Finde eine Zahl, welche Zahl bei Division durch 3 den Rest 2, bei Division durch 5 den Rest 3 und bei Division durch 7 den Rest 2 lässt.

Hierher rührt auch der Name des folgenden Resultates:

Satz (Chinesischer Restsatz).

Es seien m₁,…,m_n∈ ℕ paarweise teilerfremd und a₁,…,a_n ∈ ℤ beliebig. Dann besitzt das lineare Konruenzsystem

kongruenzen

eine eindeutige Lösung x mod m, wobei m := m₁⋅…⋅ m_n.

Eine interessante Interpretation des chinesischen Restsatzes ist die folgende: In einem hinreichend kleinen Intervall ist eine ganze Zahl also eindeutig durch ihre Reste modulo kleiner Primzahlen bestimmt!

Beweis. Wir haben die Existenz und die Eindeutigkeit dieser Lösung zu zeigen. Hierzu setzen wir

chin

Hierbei ist m∕m_j eine ganze Zahl (klar) mit m∕m_j≡ 0 mod m_k für k≠j; ansonsten, wenn also j = k, sind m∕m_j und m_j = m_k teilerfremd. Mit dem Satz von Euler folgt

Also gilt x ≡ a_k mod m_k für 1 ≤ k ≤ n und x ist eine Lösung unseres linearen Kongruenzsystems. Dies beweist also die Existenz einer Lösung; nun der Nachweis der Eindeutigkeit: Eine Restklasse y ist genau dann eine Lösung, wenn m_j∣(x − y) für 1 ≤ j ≤ n gilt. Mit der paarweisen Teilerfremdheit der m_j ist dies äquivalent zu m = m₁⋅…⋅m_n∣(x−y) bzw. x ≡ y mod m, was zu zeigen war. qed.