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?

• Stellenzahl abschätzen.
• Wenn a und b gerade sind, so ist auch die Summe gerade.
• Wenn a und b ungerade sind, so ist die Summe gerade.
• Wenn a gerade ist und b ungerade, so ist die Summe ungerade.
• Wenn a und b gerade sind, so ist auch das Produkt gerade.
• Wenn a und b ungerade sind, so ist auch das Produkt ungerade.
• Wenn a gerade ist und b ungerade, so ist das Produkt gerade.

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: q_cn + c’ = c = a +b = (q_an + a’) + (q_bn + b’)

= (q_a + q_b)n + (a’ + b’)

= (q_a + q_b)n + qn (a’ # b’)

2. Multiplikation: q_cn + c’ = c = a ^. b = (q_an + a’) ^. (q_bn + 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 = [a_n ... a₃a₂a₁a₀] = a_n10ⁿ + ... + a₂10² + a₁10¹+ a₀10⁰.

9-er-Probe:

Bildung der iterierten Quersumme:

Bsp: 281765111₉ = 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 = [a_n ... a₃a₂a₁a₀]

= (a_n10ⁿ + ... + a₂10² + a₁10+ a₀1)₉

= (a_n)₉ + ... + (a₁)₉ + (a₀)₉

11-er-Probe:

Bildung der alternierenden (iterierten) Quersumme:

Beweis der Formel für den 11-er-Rest:

a₁₁ = [a_n ... a₃a₂a₁a₀]₁₁

= (a_n10ⁿ + ... + a₂10² + a₁10+ a₀1)₁₁

= (a_n)₁₁ 10ⁿ₁₁ + ... + (a₁)₁₁10¹₁₁ + (a₀)₁₁ 10⁰₁₁

= (±1)ⁿ a_n +....+ a₂ – a₁ + a₀

Bsp: 281765111₁₁ = ₁₁ 1 denn: 1 + 1 – 1 + 5 – 6 + 7 – 1 + 8 - 2 = ₁₁ 1

13-er-Probe:

a₁₃ = [a_n ... a₃a₂a₁a₀]₁₃

= (a_n10ⁿ + ... + a₂10² + a₁10+ a₀1)₁₃

= (a_n)₁₃ 10ⁿ₁₃ + ... + (a₁)₁₃10¹₁₃ + (a₀)₁₃ 10⁰₁₃

Folge der Reste (d.h. Koeffizienten der jeweiligen a_i): (1, -3, -4, -1, 3, 4, 1, -3, -4, ...)

Fragen:

• Wie viele Proben sind sinnvoll? (Wie richtig ist mein Ergebnis?)
• Welche Proben sind sinnvoll oder besser?

Frage: Wenn die 2-er-Probe und die 3-er-Probe stimmt, stimmt dann auch die 6-er-Probe?

Betrachte:

a = q^.2 + a₂

a = q’^.3+ a₃

a = q’’^.6+ a₆

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 + a₂

a = q’^.4+ a₄

a = q’’^.4+ a₄

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.