Elementare Zahlentheorie WS 2003/04
[Zurück
zur Protokollübersicht.]
Konventionen: x0 bezeichnet den „Topf“ bezüglich x.
/Z bezeichnet die Menge der „Ganzen Zahlen“.
xk bezeichnet den Repräsentanten r mit 0 < r < k der Restklasse x + k /Z, also r = x mod k.
Ausgangsthematik waren Zahlenproben, etwa die Proben mod 2, mod 3, mod 4, etc.
Kann man etwa bei gegebener Zahl a und bekannten a2 und a3 auf a6 schließen?
Ist das a6 festgelegt? Gibt es eine Formel aus a2 und a3?
Beispiele:
|
a2 |
a3 |
a6 |
|
0 |
0 |
0 |
|
0 |
1 |
4 |
|
1 |
0 |
3 |
|
1 |
2 |
5 |
|
0 |
2 |
2 |
|
1 |
1 |
1 |
Es sei
a = q × 2 + a2 , b = q´ × 2 + b2
a = r × 3 + a3 , b = r´ × 3 + b3
Folgt a6 =
b6 , wenn
a2 = b2 und a3 = b3
ist?
(a = s × 6 + a6 , b = s × 6 + b6
a – b = (q – q´) × 2
a – b = (r – r´) × 3
________________
a – b = t × 6 (Hier wird stillschweigend die Eindeutigkeit der Primfaktorzerlegung genutzt.)
Also ist (a – b)6 = 0,
a6 – b6 = 0,
a6 = b6.
Also ist a6
festgelegt.
Gibt es eine Formel für a6? Zu geg. a2 , a3 finde b ∈ /Z mit b2 = a2 und b3 = a3.
Ansatz:
Es sei b = 2 a3 x + 3 a2 y.
(Lagrange)
Gesucht sind x, y ∈ /Z, so dass für b:= 2 x a3 + 3 y a2 gilt:
b2 = a2 und b3 = a3.
Wegen des Ansatzes ist b2 = 0 + (3 y a2)2 = (3y)2 a2 . Wir suchen also ein y mit (3y)2 = 1. Entsprechend suchen wir ein x mit (2x)3 = 1.
Allgemeines Problem: Gegeben der Restering n = {0, 1, 2, 3, …, m, ..., (n-1)}. Welche Elemente m sind invertierbar: d. h. für welche m ∈ /Z existiert ein x ∈ /Z mit xn mn = 1?
Antwort. Bei teilerfremden m, n ∈ /Z existiert ein x mit (x m)n = 1, also (xn mn) = 1.
Denn die Berechnung des ggT g von m und n (in /Z) erfolgt über den Euklidischen Algorithmus und den Erweiterten Euklidischen Algorithmus XEA: Es existiert eine Darstellung von g mit:
g = u m + v n.
Bei uns ist g = 1 = u m + v n (u, v ∈ /Z).
Also 1 = un mn + 0.
à (2 x)3 = 1 = (3
y)2.
Diese Lösung des allgemeinen Problems liefert speziell die Existenz von x und y mit (2 x)3 = 1 = (3 y)2, wie im Ansatz für die obige Formel gewünscht. Das Ergebnis ist der folgende Satz.
Chinesischer
Restesatz:
Sind m und n teilerfremd in IN und sind r und s ∈ /Z, so existiert ein b ∈ /Z mit bm = rm und bn = sn.
Zusatz:
Man erhält ein solches b in der Form b = n u rm + m v sn, wenn 1 = v m + u n (XEA) gilt.
Anwendung auf Rechenproben:
Wenn m1,
..., mr paarweise teilerfremd sind und die Proben mod m1, ..., mod mr
„stimmen“, dann stimmt das Ergebnis mod m1
... mr.
B) Allgemeine Strukturfragen an die Ringe-m-1 der Form n.
Für a ∈ n
schreiben wir {x | x ∈
/Z, xn = a} =: a0.
Offenbar gilt
/Z = ∪a ∈ /Z a0
Hilfssatz. a0 + b0 := (a + b)0 ist wohldefiniert.
Zum Beweis sei
a0 = (a´)0. [Z.z.: (a´+ b)0 = (a + b)0.] Also n | a´ - b. [Z.z.: n | (a + b) – (a´ + b).]
Deshalb n | (a´ + b) – (a + b), also (a´ + b)0 = (a + b)0.
Hilfssatz. a0 × b0 = (a b)0 ist wohldefiniert. (Beweis selbst.)
Wir schreiben ab jetzt +, × statt +, × .
n /Z < /Z (Gruppe bezüglich (+, 0, -)).
/Z / n ×/Z :=
{m + n /Z | m ∈ /Z}
+, 0, - m0
×, 1 -m0 =
(-m)0
Ring-m-1
E(/Z / n /Z) = {x0 | x ∈ /Z, es existiert ein y0 mit x0 × y0 = 1} ist Gruppe bzgl. ×
(„Einheitengruppe“)
= {m0 | ggT (m, n) = 1}
= (?)
Beispiel: n = 6:
/Z / 6 /Z = {00, 10, 20, 30,
40, 50}
0 = 30 × 20 × x0 = 30 × 10 = 30, ein Widerspruch.
Zurück
zur vorangehenden Stunde (23.10.03),
zur nächsten
Stunde (28.10.03),
zur Protokollübersicht.