KAP 1
BAUSTEINE DER ZAHLENTHEORIE (1)

In diesem Kapitel geht es um die grundlegenden Begriffe der Zahlentheorie wie "Teilbarkeit" und "Primzahl". Es werden viele Dinge wiederholt, die Du aus den Klassen 6 bis 8 kennst.

DEFINITION 1.1
Es seien k und n aus N . k heißt "Teiler von n", wenn es eine Zahl rÎN gibt mit r·k=n. r heißt dann der "zu k komplementäre Teiler" von n.
Man schreibt kï n bzw. rïn.

Bemerkung: Auch 1 und n selbst sind Teiler von n. Alle Teiler von außer n selbst nennt man "echte Teiler" von n. Für die "Spezialzahl" 0 gilt "per definitionem": nï 0 für alle nÎN . 1 hat nur einen einzigen Teiler, nämlich 1 selbst.

SATZ 1.1 (Grundregeln der Teilbarkeit)

Für alle a, b ÎN gilt
(T1) aï b Ù bï a Þa=b
(T2) aï b Ù bï c Þ aïc
(T3) aï b Þ aï c×b
(T4) aï b Ù aï c Þ aï b±c
(T5) aï b ÙØ (aï c) ÞØ (aï b±c)
(T6) aï b Ù aï b± c Þ aïc

Beweise (teilweise):
ad (T1): (aïb Þ b=r₁·a; bï a Þ a=r₂·b) Þ b=r₁(r₂b)=(r₁·r₂)b Þ
r₁·r₂=1 Þr₁=r₂=1
ad (T2): (aïb Þb=r₁· a; bïc Þc=r₂· b) Þ c=r₂(r₁a)=(r₂·r₁)·a=r· a Þaïc

Versuche, die restlichen Beweise selbst zu führen.

Beispiele:
zu (T4) 17ï 3400 Ù 17ï 136 Þ 17ï 3536 (und ebenso 17ï 3264)
zu (T5) 17ï 3400 Ù Ø (17ï 137) Þ Ø (17ï 3537)

AUFGABE 1.1
Begründe ohne TR, aber mit den obigen Regeln, ob die folgenden Aussagen wahr sind:
(1) 13ï 13.407 (2) 13ï 13403 (3) 19ï 40.945 (4) 29ï 69.917

AUFGABE 1.2
a) Zeige, daß jede sechsstellige Zahl n der Form durch 7, 11 und 13 teilbar ist. Suche einen geeigneten Teiler von .)
b) Zeige entsprechend, daß n= durch 73 und 137 teilbar ist.

AUFGABE 1.3
Beweise oder gib ein Gegenbeispiel an:
a) aï b Ù aï c Þ aï5b+7c
b) aï b Ù aï c Þ a²ïbc
c) aï bc Þ aï b v aïc
d) nï a-1 Þ nï a²-1
e) nï a+3 Þ nï a²+2a-3
f) Zeige, daß n und n+1 teilerfremd sind.

AUFGABE 1.4
a) Zeige, daß nicht immer gilt: aï c Ù bï c Þ abï c. Welche Bedingung ist zu stellen, damit die Aussage immer gilt?
b) Beweise: Das Quadrat einer ungeraden Zahl läßt bei Division durch 8 den Rest 1.

AUFGABE 1.5
Zeige: Für alle nÎ N gilt (1) 2ï n²+n (2) 6ï n³- n (3) 12ï n⁴-n²

Im folgenden Beispiel führen wir ein wichtiges Beweisverfahren ein:
Sieht man sich die Zahlenbeispiele: 8-1=2³-1=1·7, 64-1=2⁶-1=9·7,512-1=2⁹-1=73·7 usw. an, so könnte man die Behauptung:
Für alle nÎ N gilt 7ï 2³ⁿ-1 (*) aufstellen.
Dabei ist Vorsicht geboten, denn man schließt ja von nur drei Beispielen auf unendlich viele Beispiele. Aber auch bei 999 Beispielen steht man nicht besser da, wie die falsche Aussage: "Alle natürlichen Zahlen sind kleiner als 1000." zeigt.
Wir zeigen deshalb die Aussage (*) in zwei Schritten. Vorher führen wir noch die Bezeichnung a_n:=2³ⁿ-1 ein.
(I) (*) gilt für n=1, also 7ï 2³-1, was ja offensichtlich gilt
(II) (*) gilt für a_n+1-a_n, denn:
a_n+1-a_n=(2³⁽ⁿ⁺¹⁾-1)- (2³ⁿ-1)=2³ⁿ⁺³ -2³ⁿ=
2³ⁿ ·2³-2³ⁿ=2³ⁿ(8- 1)=7·2³ⁿ, also teilt 7 a_n+1-a_n

Mit (I) und (II) folgt nun 7ï a_2-a₁ und daher mit (T6) 7ï a₂. Dann folgt aber aus 7ï a₃-a₂ wieder mit (T6) 7ï a₃ usw.usw. Wir rollen das Feld also von unten auf. Man nennt einen solchen Beweis einen
"Induktionsbeweis" (oder "Beweis durch Induktion").

AUFGABE 1.6
Beweise durch Induktion (berechne vorher für n=1,2,3):
a) 3ï n³+2n b) 8ï 3²ⁿ+7 c) 9ï 10ⁿ+3· 4ⁿ⁺²+5 d) 3ï 4n³-n
e) 6ï n³-n f) 6ï 7ⁿ-1 g) 3ï n³-6n²+14n
h) 133ï 11ⁿ⁺²+12²ⁿ⁺¹ i) 9ï n³+(n+1)³+(n+2)³

SATZ 1.2
(nützliche Formeln zur Teilbarkeit);
Für alle a,bÎ Â und alle nÎ N gilt:
(F1) (a^n-bⁿ):(a-b)=a^n-1+a^n-2·b+a^n-3·b² +...+a²·b^n-3+a· b^n-2+b^n-1
(F2) (a²ⁿ-b²ⁿ):(a+b)=a^2n-1-a^2n-2b+-+-...+ab^2n-2-b^2n-1
(F3) (a²ⁿ⁺¹+b²ⁿ⁺¹):(a+b)=a²ⁿ-a^2n-1b+-+-...-ab^2n-1+b²ⁿ

AUFGABE 1.7
a) Berechne a) (x^7- y⁷):(x-y)    b) (r^8-s⁸):(r+s)   g ) (u⁵+v⁵):(u+v)
b) Beweise mit Satz 1.2 die folgenden weiteren Teilbarkeitsregeln:
(T7) x-1ïxⁿ -1    (T8) x+1ïx²ⁿ⁺¹+1   (T9) x+1ïx²ⁿ-1
Zeige dann, daß gilt: 7ï 8ⁿ-1 und 17ï18ⁿ-1

AUFGABE 1.8
a) Zeige: (F4) 1+x+x²+x³+...+x^n-1= für x¹1.
b) Berechne damit die Summe der Reiskörner aus der berühmten "Schachbrettaufgabe"
c) Auch die aus unendlich vielen Summanden bestehende Summe: s= läßt sich mit F4 berechnen.
Berechne dazu erst mal einige "Teilsummen"
s₁= Schreibe dann die Teilsumme s_n auf (welches ist der letzte Summand?).
Überlege nun, was mit den auftretenden Zahlen passiert, wenn n immer größer wird.

AUFGABE 1.9
drei Aufgaben aus dem Jahr 1996 (beachte F1 - F4 und T7 - T9):
a) Es sei n=11..1122..22, wobei auf 1996 Einsen 1996 Zweien folgen. Zeige: 13.200ï n³-3n²-18n .(Benütze die Quersummenregeln, auch wenn sie erst später bewiesen werden!)
b) Es sei s=6+6²+6³+...+6¹⁹⁹⁶. Zeige: 1554ï s .
c) Zeige: 1996ï1+1995¹⁹⁹⁵

DEFINITION 1.2
Die Menge T_n:={xïx ist Teiler von n} heißt "Teilermenge" von n. Die Anzahl der Elemente von T_n wird mit t(n) bezeichnet. (Gelesen "tau von n")

AUFGABE 1.10
a) Bestimme t (n) für n=40, 41, 345.684.
b) Vergleiche t (n) von einigen Quadratzahlen mit t (n) für Nichtquadrate. Welche Vermutung drängt sich auf? Beweis?

DEFINITION 1.3
Eine Zahl pÎN heißt "Primzahl" genau dann, wenn t (p)=2 ist. Jede Zahl größer als 1, die nicht prim ist, heißt "zusammengesetzt".

SATZ 1.3
Es gibt unendlich viele Primzahlen.

Beweis: (Der im folgenden angedeutete Beweis geht auf Euklid (ca. 300 v.Chr. zurück.)Betrachte dazu:
(1)   2+1=3
(2)   2· 3+1=7
(3)   2·3·5+1=31
(4)   2·3·5·7+1=211
Setze die Folge um drei weitere Zeilen fort. Warum ist z.B. die 4.Zeile weder durch 2 noch 3 noch 5 noch7 teilbar?
Ist das Ergebnis immer eine Primzahl?
Nun nehmen wir einmal an, es gäbe eine größte Primzahl P. Wie verhält es sich mit dem Zahl z=2·3·5·7···P+1? Unterscheide zwei Fälle.

Da die Überprüfung einer beliebigen (ungeraden) Zahl auf Primalität nicht immer einfach ist, kannst Du mit dem folgenden Button ein kleines Übungsprogramm starten.

Der folgende Satz ist sehr hilfreich, wenn man von einer Zahl entscheiden will, ob sie Primzahl ist oder nicht.

SATZ 1.4
Jede zusammengesetzte Zahl n besitzt einen Primteiler p £ .

Beweis:Da n zusammengesetzt ist, besitzt n sicher einen Primteiler a mit a ¹ 1 und a¹ n. Zu a existiert ein komplementärer Teiler b. Ist b nicht prim, so hat b einen Primteiler c mit c¹1 und c ¹n.
Ist b selbst prim, so kann nicht gelten a > und b > , da sonst a ×b >n. Also ist entweder a oder b£ . Den zweiten Fall (a, c) behandelt man entsprechend.

Im Zusammenhang mit Primzahlen gibt es jede Menge ungelöster Probleme. Hier einige Stichpunkte:

• Gibt es unendlich viele Primzahlzwillinge bzw. -drillinge?
  Primzahlzwillinge sind zwei Primzahlen mit der Differenz 2.
  Primzahldrillinge sind nicht etwa drei Primzahlen p,p+2,p+4.
  Warum können nie drei aufeinanderfolgende ungerade Zahlen alle Primzahlen sein, wenn schon die erste größer als 3 ist?
• Liegt zwischen n und 2n mindestens eine Primzahl?
  Untersuche für n bis 500.
• Liegt zwischen n² und (n+1)² mindestens eine Primzahl?
  Untersuche bis n=50.
• Läßt sich jede gerade Zahl größer als 2 als Summe zweier Primzahlen schreiben (Goldbachsche Vermutung - nach Chr. Goldbach (1690-1764))?
  Warum äußerte Goldbach seine Vermutung nicht für ungerade Zahlen?

AUFGABE 1.11
a) Ermittle alle Primzahlzwillinge und -drillinge unter 200!
b) Schreibe (wenn möglich) alle Zahlen bis 50 als Summe zweier Primzahlen.
c) Suche alle MIRP-Zahlen unter 1000. Dies sind solche Primzahlen, bei denen auch die Spiegelzahl prim ist (z.B. 31 und 13 oder 11 und 11)
d) Wie viele Zahlen bleiben über, wenn man von den Zahlen von 1 bis 50.000 nacheinander alle Vielfachen der ungeraden Primzahlen streicht.
e) Welche der Zahlen, die sich als Produkt von genau zwei Primzahlen schreiben läßt, liegt am nächsten bei 100?

Der folgende Satz zeigt, wie man die Primalität (Primeigenschaft) einer Zahl geschickt ausnutzen kann:

Jede Primzahl p>2 läßt sich eindeutig als Differenz zweier Quadratzahlen darstellen.

Beweis: Wir versuchenīs einfach mal: p=x²-y²=(x-y)(x+y). Da p prim ist, muss einer der beiden Faktoren Eins sein (also x-y=1), während der andere p ist (also x+y=p). Das liefert ein LGS mit 2 Variablen: x-y=1 und x+y=p
Þ 2x=p+1 Ù 2y=p-1 Þ x= Ù y=. Wir haben damit die beiden gesuchten Quadratzahlen gefunden: p=
Diese Darstellung gilt übrigens für alle ungeraden Zahlen p, wie man leicht nachrechnet.

AUFGABE 1.12
a) Bestimme alle Primzahlen p, für die 4p+1 Quadratzahl ist.
(Hinweis: Angenommen 4p+1=x² Þ.....)
b) Zeige, das p=2 die einzige Primzahl p ist, für die gilt:
10ï (p+9)²-1

DEFINITION 1.4
Ist n>1, so heißt n= mit Primzahlen p₁<p₂<...<p_r und a _iÎN die "Primfaktorzerlegung" von n.
a _i heißt die "Vielfachheit" von p_i.

Ein ganz wichtiger, dennoch leicht einleuchtender Satz ist der folgende Fundamentalsatz. In der Mathematik wird der Zahlbegriff später etwas erweitert. Dann ist die Aussage dieses Satzes schon gar nicht mehr so selbstverständlich. Wir geben den Satz hier ohne Beweis an.

Satz 1.5 (Fundamentalsatz der Zahlentheorie)

Jede natürliche Zahl n>1 besitzt eine bis auf die Reihenfolge der Faktoren eindeutige Primfaktorzerlegung.

Beispiel:
980=10·98=(2·5)·(2·49)=2²·5·7²
980=20·49=(4·5)·(7·7)= 2²·5·7²
Wir haben die Zahl auf zwei verschiedenen Wegen zerlegt, die Ergebnisse sind dennoch gleich.

Mit dem Button kannst Du ein Programm zur Primfaktorzerlegung starten.

AUFGABE 1.13
Prüfe, welche der folgenden Produkte den selben Wert haben:
a=10·11·44·78·210·385·847
b=15·26·28·40·77·99·363
c=14·18·20·22·90·121·1001
d=8·22·35·36·143·225·847
e=21·26·40·49·75·242·1331

AUFGABE 1.14
Berechne x, y und z in:
a) 2³·3^x-1·10·11=2640
b) 24·3^x-15^y ·7^z+2=9000
c) 3·11^x-3 ·13^y+1=51.903

Ein einfaches Beispiel soll uns nun zeigen, daß der Satz 1.5 nicht immer trivial ist:
Es sei M:={xï x=4n+1 mit nÎ N₀} ={1,5,9,13......}. Nehme ich zwei Zahlen aus M, also z.B. 4k+1 und 4l+1, so liegt wegen (4k+1)·(4l+1)=16kl+4k+4l+1=
4(4kl+k+l)+1 auch ihr Produkt in M (M ist bezüglich der Multiplikation abgeschlossen.) Nun kann man sich fragen, welche der Zahlen von M sich wie 25=5× 5 oder 45=5·9 in M zerlegen lassen. Die nicht zerlegbaren Zahlen von M nennen wir "irreduzibel" (in M). Sie entsprechen den Primzahlen in N.
a) Bestimme alle irreduziblen Zahlen in M £ 301.
b) Zeige, dass 693 auf zwei verschiedenen Arten als Produkt irreduzibler
Elemente von M dargestellt werden kann.
c) Versuche weitere Elemente dieser Art zu finden.

AUFGABE 1.15
a) Beweise: Ist n ungerade und n>2, so gilt 24ï n³-n
b) Ist p>5 prim so gilt 1920ï p⁴-10p²+9
c) Für welche Primzahlen p ist 2p+1 eine Kubikzahl?
d) Das Produkt von drei Primzahlen ist gleich dem Siebenfachen ihrer Summe. Um welche Primzahlen handelt es sich?
e) Aus zwei verschiedenen natürlichen Zahlen a und b werden vier neue natürliche Zahlen gebildet: ihre Summe, ihr Produkt, die Differenz und der Quotient aus größerer und kleinerer Zahl. Die Summe der vier neuen Zahlen ist 243. Wie heißen die beiden Zahlen a und b?

Download Kap1_0 (40 KB)

Copyright © Michael Dorner, Okt. 2000.