close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

1 Was ist Zahlentheorie? Ursprünglich ist die Zahlentheorie (auch

EinbettenHerunterladen
Proseminar mathematisches Problemlösen
Thema: elementare Zahlentheorie
Was ist Zahlentheorie?
Ursprünglich ist die Zahlentheorie (auch: Arithmetik) ein Teilgebiet der Mathematik, welches sich
allgemein mit den Eigenschaften der ganzen Zahlen und insbesondere mit den Lösungen von
Gleichungen in den ganzen Zahlen beschäftigt. Aus moderner Sicht umfasst sie alle
mathematischen Theorien, die sich historisch aus diesen Fragestellungen entwickelt haben.
Elementare Zahlentheorie
Bereich der Zahlentheorie, der ohne andere mathematische Teilgebiete auskommt. Ihre einzigen
Hilfsmittel waren die Eigenschaften der ganzen Zahlen, insbesondere Primfaktorzerlegung und
Teilbarkeit.
Wichtige Resultate, die sich mit Hilfe elementarer Methoden erzielen lassen, sind der Euklidische
Algorithmus, der kleine Satz von Fermat, dessen Verallgemeinerung, und der Chinesische
Restsatz.
Frühe Geschichte:
2000 v. Chr. Erste schriftliche Nachweise der Zahlentheorie. Babylonier kannten Zahlen kleiner
einer Million, Quadratzahlen und einige pythagoräische Tripel.
300 v. Chr.
Systematische Entwicklung durch Euklid. „Euklids Elemente“ war lange Zeit
Standardlehrbuch für Zahlentheorie.
• Euklidischer Algorithmus und ggT
• Existenz unendlich vieler Primzahlen (Satz von Euklid)
250 v. Chr.
Diophantische Gleichungen: Lösung von Gleichungen mit linearen Substitutionen
Hauptwerk „Arithmetika“
Danach arithmetische Fragestellungen wie vollkommene Zahlen und Dreieckszahlen der Griechen.
Weitere wichtige Zahlentheoretiker:
• Pierre de Fermat
• Leonhard Euler
• Carl Friedrich Gauß
Wir werden uns mit den ersten Kapiteln der elementaren Zahlentheorie beschäftigen.
Teilbarkeit
Primzahlen
ggT (größter gemeinsamer Teiler)
Euklidischer Algorithmus
1
Proseminar mathematisches Problemlösen
Definition:
Thema: elementare Zahlentheorie
Seien n ∈ und m ∈ ≥1 zwei Zahlen. Dann gibt es genau eine eindeutige
Darstellung von n in der Form
n = qm + r (*)
n
mit einem q ∈ und einem r ∈ {0,1,2,..., m − 1}. Dabei gilt: q =   .
m
Die Zahlen q und r heißen der Quotient bzw. der Rest der Zahl n bei Division durch
m. Ist r = 0, so sagt man, m ist ein Teiler von n (Bezeichnung: m n ), und n ist durch
m (restlos) teilbar (Bezeichnung nΜm )
Existenz der Darstellung (*): Betrachten wir die Menge M = {n − km : k ∈ Z}. Diese Menge ist nach
unten und nach oben unbeschränkt, sie enthält sowohl negative, als
auch positive ganze Zahlen. Sei r = n − qm ∈ M die kleinste
nichtnegative Zahl dieser Menge.
Dann ist r ≥ 0 nach Definition.
Andererseits ist n − (q + 1)m = r − m < 0 sonst wäre die Zahl
r − m ∈ M ebenfalls nichtnegativ, aber kleiner als r.
Also ist r < m , d.h. r ∈ {0,1,2,..., m − 1}.
Eindeutigkeit von (*):
Sei qm + r = q ' m + r ' mit r ≤ r ' .
Dann ist r − r ' = (q '−q )m , also ein Vielfaches von m.
Da aber 0 ≤ r − r ' ≤ r < m ist, erhalten wir r − r ' = 0 , also r = r ' .
Daraus folgt auch q = q ' .
Bemerkung: Wir betrachten hier nur positive Teiler, d.h. die Zahl m muss eine positive ganze
Zahl sein.
Aufgabe 1.1:
Die Gesamtzahl aller Teiler einer Zahl n ≥ 2 ist ungerade, wenn n eine Quadratzahl ist, d.h.
wenn n ∈ ist, und sonst gerade.
Lösung:
Sei n keine Quadratzahl. Betrachten wir die Menge T± aller Teiler von n, die
größer (bzw. kleiner) sind als n . Die Menge T aller Teiler von n ist die
Vereinigung T = T− ∪ T+ . Nun sind die beiden Mengen T− und T+
n
von T− nach T+ ist bijektiv. Also
gleichmächtig, denn die Abbildung a α
a
ist T = T− + T+ = 2 T− gerade.
Sei jetzt n ∈ also n eine Quadratzahl. Dann ist T = T− ∪
somit T = T− + 1 + T+ = 2 T− + 1 ungerade.
2
{ n }∪ T
+
, und
Proseminar mathematisches Problemlösen
Thema: elementare Zahlentheorie
Aufgabe 1.2:
Ein Schrank hat 100 Schließfächer, die am Abend geschlossen sind. In der Nacht kommen 100
Geister und treiben ihr Unwesen:
•
Der erste Geist macht alle Schließfächer auf;
•
Der zweite Geist ändert den Zustand jedes Schließfaches mit gerader Nummer,
d.h. macht die Schließfächer 2,4,6, ... , 100 wieder zu.
•
Der dritte Geist ändert den Zustand jedes Schließfaches, dessen Nummer durch 3
teilbar ist, usw.;
•
... Der k-te Geist ändert den Zustand jedes Schließfaches, dessen Nummer durch
k teilbar ist;
•
... Der letzte Greift nur die Nummer 100 an.
Wie viele (und welche) Schließfächer sind am nächsten Morgen auf?
Lösung:
Betrachten wir das Schließfach Nummer N. An diesem Schließfach werden
sich genau diejenigen Geisterbetätigen, deren Nummern Teiler von N sind
(inklusive der 1). Insgesamt wird der Zustand des Schließfaches also so oft
geändert, wie die Zahl N Teiler hat.
Ist N keine Quadratzahl, so ist die Gesamtzahl ihrer Teiler gerade. In diesem
Fall bleibt das Schließfach im Endeffekt geschlossen.
Ist N hingegen eine Quadratzahl, so ist die Gesamtzahl ihrer Teiler ungerade.
In diesem Fall bleibt das Schließfach also offen.
Die Antwort lautet also: ausgerechnet die Schließfächer mit den Nummern 1,
4, 16, 25, ..., 100 (also insgesamt 10 Stück) sind am nächsten morgen offen.
3
Proseminar mathematisches Problemlösen
Thema: elementare Zahlentheorie
Aufgabe 1.3:
Beweisen Sie: Für jede natürliche Zahl n ≥ 2 ist der kleinste von l verschiedene Teiler q von n eine
Primzahl.
Lösung: Sei q der kleinste von l verschiedene Teiler von n. Angenommen, q ist eine
zusammengesetzte Zahl, d. h. sei q = pr, wobei
2 ≤ p < q und 2 ≤ r < q
ist. Dann ist p (sowie r) auch ein Teiler von n, da
n q n
n
= q • p =q • r
p
eine natürliche Zahl ist. Das ergibt einen Widerspruch zu der Annahme, dass q der kleinste Teiler
von n ist, da p < q ist.
Aufgabe 1.4:
Jede natürliche Zahl n ≥ 2 kann als Produkt n = p1 • p2 • ... • pm von Primzahlen dargestellt
werden.
Lösung: Wir beweisen diese Behauptung durch vollständige Induktion.
Induktionsanfang: n = 2. Da gilt die Darstellung mit m = l, p1= 2 = n.
Induktionsschritt: Sei eine solche Darstellung für alle natürliche Zahlen n ≤ N möglich.
Betrachten wir nun die Zahl n = N + 1. Ist n eine Primzahl, so setzen wir m = l, p1 = n.
Ist n zusammengesetzt, so bezeichnen wir mit p1 den kleinsten Teiler von n. Wir wissen schon,
dass p1 eine Primzahl ist. Nun stellen wir die Zahl n1 = n/p1 in der Form n1 = p2 • … • pm dar
(dies ist möglich, weil n1 < n = N + l und damit n1 ≤ N ist). Für n gilt dann
n = p1 • n 1 = p1 • p 2 • … • pm.
4
Proseminar mathematisches Problemlösen
Thema: elementare Zahlentheorie
Aufgabe 1.5:
Beweisen Sie, dass die Darstellung n = p1 • p2 • … • pm (die so genannte Primfaktorzerlegung
(PFZ) der Zahl n) mit Primzahlen p1, p2, …, pm, die p1 ≤ p2 ≤ ... ≤ pm erfüllen, eindeutig ist.
Lösung: (Der Beweis von Zermelo) Wir verfahren nach dem Extremalprinzip:
Wenn es Zahlen n gibt, für die die Darstellung n = p1 • p2 • … • pm nicht eindeutig ist, dann gibt es
auch eine kleinste solche Zahl n. Seien
p1 • p 2 • … • pm = n = q1 • q 2 • … • ql = n
zwei verschiedene Darstellungen dieser Zahl n, wobei p1, p2, …, pn, q1, q2, …, qn
Primzahlen sind und p1≤ p2 ≤ … ≤ pn und q1 ≤ q2 ≤ ... ≤ qn gilt.
Die Gleichung p1 = q1 ist unmöglich, da es sonst für die Zahl n/ p1 < n zwei verschiedene
Primfaktorzerlegungen p2 • … • pm = q2 • … • ql = n/ p1 gäbe, was zu der Minimalität von n im
Widerspruch stehen würde. Also ist p1 ≠ q1. O.B.d.A. nehmen wir an, dass p1< q1 ist. Dann ist
q1 = a p1 + r, wobei a und r natürliche Zahlen sind mit l ≤ r ≤ p1- l < p1. Aus dieser Darstellung
folgt
p1 • p2 • … • pm = (a p1 + r) • q 2 • … • ql = p1• a • q 2 • … • ql + r • q2 • … • ql ,
also
p1• ( p2 • … • pm – a • q2 • … • ql ) = rq 2 • … • ql
R
Da die Zahl R kleiner ist als n, hat sie nur eine einzige Primfaktorzerlegung
R = ql+1• … • ql +k • q 2 • … • ql
=r
Die Primzahl p1 muss also mit einer der Primzahlen qj übereinstimmen. Dies ist aber unmöglich,
weil p1< qj ist für j = 2, …, l und p1 > qj ist für j = l + 1, …, l + k (denn p1 > r). Dieser
Widerspruch zeigt, dass es keine Zahl mit mehreren verschiedenen Primfaktorzerlegungen gibt. Das
heißt, jede natürliche Zahl hat eine einzige Primfaktorzerlegung.
5
Proseminar mathematisches Problemlösen
Thema: elementare Zahlentheorie
Definition
Die Darstellung
n = p1α1 • p2 α2 • … • pm αm
mit Primzahlen pj, j = 1...m, wobei p1 < p2 < ... < pm, und αj natürliche Zahlen ≥ l sind, heißt
kanonische Primfaktorzerlegung der natürlichen Zahl n.
Aufgabe 1.6:
Sei n = p1α1 • p2 α2 • … • pm αm die kanonische Primfaktorzerlegung einer natürlichen Zahl n.
Dann hat n genau (l +α1) (l + α2) • … • (1+αm) verschiedene natürliche Teiler.
Lösung: Jeder Teiler x von n hat die Primfaktorzerlegung x = p1β1 • p2 β 2 • … • pm β m, wobei
β j ∈ {0, l, 2, ..., αj} ist. Daher gibt es für jedes β j genau l + αj Wahlmöglichkeiten. Insgesamt
ergibt das (l +α1) (l + α2) • … • (1+αm) Möglichkeiten für den Teiler.
Aufgabe 1.7:
Für zwei teilerfremde Zahlen a und b und für eine weitere natürliche Zahl n gelte a n und b n .
Dann ist ab n .
Lösung:
Es ist a = p1β1 ⋅ p 2β 2 ⋅ Κ ⋅ p mβ m und b = p1γ 1 ⋅ p 2γ 2 ⋅ Κ ⋅ p mγ m mit 0 ≤ β j ≤ α j und
0 ≤ γ j ≤α j .
Da a und b teilerfremd sind, gilt bei γ j ≠ 0 zwangsweise β j = 0 und
umgekehrt folgt aus β j ≠ 0 unbedingt γ j = 0 .
In diesem Fall ist: β j + γ j = max{β j , γ j } erfüllt.
Daraus folgt: a ⋅ b = p1β1 +γ 1 ⋅ p 2β 2 +γ 2 ⋅ Κ ⋅ p mβ m +γ m .
Da β j + γ j = max{β j , γ j } ≤ α j ist, ist ab n .
6
Proseminar mathematisches Problemlösen
Thema: elementare Zahlentheorie
Aufgabe 1.8:
Wie viele Nullen stehen am Ende der zahl 100! ?
Lösung:
Dies ist zu der folgenden Frage äquivalent:
Durch welche maximale Potenz von 10 ist 100! teilbar?
Sei 100! = 2 a 5 b n wobei n mit 10 teilerfremd ist. Dann ist 100! Durch 10c
teilbar mit c = min{a, b} , aber nicht durch 10c+1. Es ist a ≥ 50 , da mindestens
50 Faktoren in 100! gerade Zahlen sind. Ferner gibt es unter den Zahlen 1 bis
100 genau 20, die durch 5 teilbar sind, 4 davon sind auch noch durch 5²
teilbar (durch 5³ teilbare Faktoren gibt es in diesem Bereich nicht). Insgesamt
ergibt das b = 20 + 4 = 24. Daher ist c = b = 24.
Die Antwort lautet also: 24 Nullen.
Aufgabe 1.9:
Auf jeder der sechs Seitenflächen eines Würfels steht eine positive ganze Zahl angeschrieben.
Für jede Ecke des Würfels berechnen wir das Produkt der Zahlen auf den drei angrenzenden
Flächen. Die Summe dieser Produkte beträgt 1001. Welchen Wert hat die Summe der Zahlen
auf den sechs Würfelflächen?
Lösung:
Wir bezeichnen die Würfelflächen mit den Zahlen a1, a2, b1, b2, c1, c2 wobei
sich die Zahlen mit gleichen Buchstaben (z.B.: a1, a2) gegenüberliegen.
Die Summe aller acht Produkte beträgt dann genau
(a1 + a 2 )(b1 + b2 )(c1 + c 2 ) = 1001 = 7 ⋅ 11 ⋅ 13 (Primfaktorzerlegung!)
Da die Zahlen a1 + a2, b1 + b2 und c1 + c2 natürliche Zahlen ≥ 2 sind, müssen
sie also gleich 7, 11 und 13 sein (evtl. in einer anderen Reihenfolge). Somit
ist die gesuchte Summe gleich 7 + 11 + 13 = 31.
7
Proseminar mathematisches Problemlösen
Thema: elementare Zahlentheorie
Aufgabe 1.10:
 p
Sei p eine Primzahl. Beweisen Sie, dass alle Binomialkoeffizienten   mit n ∈ {1,2,..., p − 1}
n
durch p teilbar sind.
Lösung:
 p  p ⋅ ( p − 1) ⋅ ... ⋅ ( p − n + 1) pa
Es ist   =
=
eine ganze Zahl (nach Definition
n!
n!
n
des Binomialkoeffizienten). Also ist pa durch n! teilbar. Wir wollen zeigen,
a
dass ∈ ist. Für n ≤ p − 1 sind p und n! teilerfremd; daher gibt es
n!
natürliche x und y mit px − n! y = 1 , also mit px = n! y + 1 .
 p  xpa ( yn!+1)a
a
Das ergibt x  =
=
= ya + .
n!
n!
n!
n
 p
a
und folglich ist   durch p teilbar.
Daher ist n! a , also ∈
n!
n
8
Proseminar mathematisches Problemlösen
Thema: elementare Zahlentheorie
2. Der Euklidische Algorithmus
Aufgabe 2.1:
Seien p und q natürliche Zahlen. Beweisen Sie die folgenden Aussagen:
a) Wir bezeichnen mit MgT(p, q) die Menge aller (positiven) gemeinsamen Teiler
von p und q. Es ist dann MgT(p, q) = MgT(q, r), wobei der Rest r durch p = sq + r
gegeben wird.
b) Wir bezeichnen mit ggT (p, q) den größten gemeinsamen Teiler von p und q.
Dann kann ggT (p, q) durch den folgenden Algorithmus, genannt Euklidischer
Algorithmus, bestimmt werden:
•
1. Schritt: Wir bezeichnen p0 = p und p1= q, wobei p ≥ q ist.
•
Schritt des Euklidischen Algorithmus: Seien pk und pk+1 zwei natürliche
Zahlen mit pk ≥ pk+1. Man teile pk durch pk+1mit einem Rest, den man
mit pk+2 bezeichnet:
pk = sk pk+1 + pk+2
Es ist dann pk+2 < pk+1
•
Man führe diesen Algorithmus solange durch, bis pK = r = 0 auftritt (also höchstens q
mal).
•
Es ist pK-1 = ggT (p, q).
Lösung:
a) Jeder gemeinsame Teiler t von p und q ist auch ein gemeinsamer Teiler von r und
q, denn
p = s1t und q = s2t
impliziert
r = p - sq = s1t — ss2t = (s1 - ss2) t.
Umgekehrt: Ist r = s3t und q = s2t, so ist
p = sq + r = ss 2 t + s 3 t = (s3 + ss2) t.
9
Proseminar mathematisches Problemlösen
Thema: elementare Zahlentheorie
b) Nach (a) ist
MgT( p0 ; p1) = MgT( p1 ; p2) = ... = MgT( pK-1 ; 0)
Daraus folgt
ggT( p0 ; p1) = ggT( pK-1 ; 0) = pK-1
Aufgabe 2.2:
Seien a und b zwei natürliche Zahlen ≥ 1. Dann gibt es zwei natürliche nichtnegative Zahlen x und
y mit
ax – by = ggT(a,b).
Lösung: Wir beweisen es durch vollständige Induktion nach a + b.
Induktionsanfang: Für a + b = 2, also für a = b = l setzen wir x = l, y = 0.
Das ergibt l • l - l • 0 = 1.
Induktionsschritt: Angenommen, die Darstellung ax – by = ggT(a,b)
existiert für alle a, b mit a + b ≤ N. Betrachten wir nun a und b mit a + b = N + l.
Betrachten wir zuerst den Fall a ≥ b. Dann ist a = qb + r, wobei der Rest r kleiner ist als b.
Wegen r + b < a + b gibt es natürliche Zahlen x' und y' mit
rx' - by' = ggT (b, r) = ggT (a, b).
Einsetzen von r = a - qb ergibt
ggT (a, b) = (a - qb) x' - by' = ax' - b (qx' + y'),
also die nötige Kombination ax – by = ggT(a,b) mit x = x ' und y = qx' + y'.
Kommen wir nun zum Fall a < b. Dann ist b = qa + r mit einem r < a.
Dann gibt es eine Darstellung
ax' - ry' = ggT (a, r) = ggT (a, b).
Das ergibt
ax' -(b- qa) y' = a (x' + qy') - by' = ggT (a, b),
also genau die Darstellung ax – by = ggT(a,b) mit x = x' + qy' und y = y'.
Quellen:
• Peter Bundschuh: „Einführung in die Zahlentheorie“, Springer Verlag, 2. Auflage
• Vorlagen von Frau Dr. Natalia Grinberg
• www.wikipedia.de
© Christian Hoffmann, Roxana Herma
10
Document
Kategorie
Gesundheitswesen
Seitenansichten
10
Dateigröße
83 KB
Tags
1/--Seiten
melden