Elementare Zahlentheorie WS 2003/04
Stundenprotokoll vom 23.10.2003 AW
[Zurück zur Protokollübersicht.]
§2 Rechnen: Teilbarkeit und Reste in Z
§ 2 Teil A) Rechenproben:
Proben sind zwar kein Beweis für die Richtigkeit einer Rechnung, jedoch können sie eventuelle Fehler aufdecken.
Bsp: Addition zweier Zahlen
a + b = c
163 057 + 16 513 = 179 570
Ist das Ergebnis richtig?
Wie kann man Proben durchführen?
Betrachte jetzt einen Ring mit zwei Elementen:
2 := {0, 1}
In diesem Ring rechnen wir „modulo 2“
Allgemein gilt: n := {0, 1, ..., n-1}
Rechenregeln:
x # y = x + y mod n є Z
x * y = x . y mod n є
Z
Warum liefert das Rechnen modulo n eine Probe?
a + b = c є Z
Übergang zu den Resten:
a’ = a mod n є
n
b’ = b mod n є n
c’ = c mod n є n
Was wird überprüft? Worin besteht die Probe?
Frage: Ist a’ # b’ = c’ ?
Ja! Wenn a + b = c gilt, dann gilt auch a’ # b’ = c’ .
’: (x → x mod n): Z → n ist Ring-m-1-Epimorphismus.
Warum ist das so?
Um diese Frage zu beantworten, benötigen wir die Beziehung zwischen x und x’. Es gilt:
Es existieren q, n є Z, sodass gilt: x = qn + x’. Denn x’ ist der Rest, der bei Division durch n entsteht.
Beweis:
1. Addition: qcn + c’ = c = a +b = (qan + a’) + (qbn + b’)
= (qa + qb)n + (a’ + b’)
= (qa + qb)n + qn (a’ # b’)
2. Multiplikation: qcn + c’ = c = a . b = (qan + a’) . (qbn + b’)
Ist die Darstellung einer Zahl in der Form z = qn +
z’, z’ є n eindeutig?
Ja, bei Division mit Rest sind sowohl q als auch der Rest eindeutig bestimmt.
Es gilt also in der Tat
c’ = a’ # b’
Was nützt uns diese Erkenntnis jetzt für Proben?
Betrachte die sogenannten 2-er-Probe, 3-er-Probe, 7-er- Probe,
9-er-Probe, 11-er-Probe, 13-er-Probe und 17-er-Probe:
Betrachte hierfür die folgende Dezimalschreibweise einer Zahl a є Z:
a = [an ... a3a2a1a0] = an10n + ...
+ a2102
+ a1101+
a0100
9-er-Probe:
Bildung der iterierten Quersumme:
Bsp: 2817651119 = 5
Bilde ich also die Quersumme von 281765111 und rechne modulo 9, erhalte ich 5.
Wenn bei dieser Vorgehensweise der Rest 0 herauskommt, ist die gegebene Zahl durch 9 teilbar. Außerdem gilt: Wenn die 9-er Probe stimmt, dann stimmt die 3-er Probe erst recht, denn jede Zahl, die durch 9 teilbar ist, ist insbesondere durch 3 teilbar.
Beweis der Formel für den 9-er-Rest:
a = [an ... a3a2a1a0]
= (an10n
+ ... + a2102
+ a110+
a01)9
= (an)9 + ... + (a1)9 + (a0)9
11-er-Probe:
Bildung der alternierenden (iterierten) Quersumme:
Beweis der Formel für den 11-er-Rest:
a11 = [an ... a3a2a1a0]11
= (an10n
+ ... + a2102
+ a110+
a01)11
= (an)11 10n11 + ... + (a1)1110111 + (a0)11 10011
= (±1)n an +....+ a2 – a1 + a0
Bsp: 28176511111 = 11 1 denn: 1 + 1 – 1 + 5 – 6 + 7 – 1 + 8 - 2 = 11 1
13-er-Probe:
a13 = [an ... a3a2a1a0]13
= (an10n
+ ... + a2102
+ a110+
a01)13
= (an)13 10n13 + ... + (a1)1310113 + (a0)13 10013
Folge der Reste (d.h. Koeffizienten der jeweiligen ai): (1, -3, -4, -1, 3, 4, 1, -3, -4, ...)
Fragen:
Frage: Wenn die 2-er-Probe und die 3-er-Probe stimmt, stimmt dann auch die 6-er-Probe?
Betrachte:
a = q.2 + a2
a = q’.3+ a3
a = q’’.6+ a6
Die letzte Zeile ergibt sich, da 2 und 3 teilerfremd sind, das heißt, dass der ggT(2, 3) = 1 ist.
Andererseits:
a = q.2 + a2
a = q’.4+ a4
a = q’’.4+ a4
Die letzte Zeile ergibt sich, da 2 und 4 nicht teilerfremd sind. Man würde vielleicht in der dritten Zeile die 8 erwarten, betrachte jedoch hierzu folgendes Gegenbeispiel:
2 teilt 4 und 4 teilt 4, jedoch teilt 8 nicht 4.
(Für den Beweis, dass aus der Richtigkeit der 2-er- und der 3-er-Probe die Richtigkeit der 6-er-Probe folgt, siehe Protokoll vom 24.10.2003)
Zurück
zur vorangehenden Stunde (21.10.03),
zur nächsten Stunde
(24.10.03),
zur Protokollübersicht.