Transcript
26
Chr.Nelius : Zahlentheorie (SoSe 2016)
§ 5. Primzahlen Jede ganze Zahl a besitzt die sog. unechten Teiler ±1 und ±a . Davon verschiedene Teiler von a heißen echte Teiler von a . urliche Zahl p ∈ (5.1) DEF: a) Eine nat¨
N heißt Primzahl oder prim, wenn gilt:
P1 ) p ≥ 2
P2 ) 1 und p sind die einzigen positiven Teiler von p . b) IP bezeichne die Menge aller Primzahlen . c) Eine nat¨ urliche Zahl, die einen echten Teiler besitzt, heißt eine zusammengesetzte Zahl. Beispiele: {2, 3, 5, 7, 11, 13} ⊆ IP 1 6∈ IP ,
4 6∈ IP ,
6 6∈ IP ,
− 2 6∈ IP ,
− 3 6∈ IP ,
− 13 6∈ IP
!
(5.2) BEM: a) 1 ist keine Primzahl !!! b) Eine nat¨ urliche Zahl p ≥ 2 ist genau dann eine Primzahl, wenn gilt f¨ ur alle t ∈
N
mit t | p folgt t = 1 oder t = p .
c) Eine nat¨ urliche Zahl n ≥ 2 ist genau dann keine Primzahl, wenn n einen echten positiven Teiler besitzt, d.h. wenn es ein t∈
N
mit 1 < t < n und t | n
gibt. In dem Falle ist dann auch der zu t komplement¨are Teiler s von n ein echter Teiler von n . Also n∈
N, n ≥ 2 :
n 6∈ IP
⇐⇒
es gibt s, t ∈
N
mit 1 < s, t < n und n = s · t .
d) Bezeichnet M die Menge der zusammengesetzten nat¨ urlichen Zahlen, so gilt
N
= {1} ∪ IP ∪ M .
e) 2 ist die einzige gerade Primzahl, alle anderen Primzahlen sind ungerade. f) F¨ ur n ∈
N gilt :
n prim
(5.3) SATZ: F¨ ur a ∈
Z und p ∈ IP gilt:
a) ggT(a, p) ∈ {1, p} b) ggT(a, p) = p c) ggT(a, p) = 1
⇐⇒
⇐⇒
⇐⇒
p|a
p 6 | a.
τ (n) = | T + (n) | = 2 .
27
Chr.Nelius : Zahlentheorie (SoSe 2016)
(5.4) SATZ: Eine Kennzeichnung von Primzahlen (Euklid) F¨ ur eine nat¨ urliche Zahl p ≥ 2 sind folgende Aussagen ¨aquivalent:
a) p ist eine Primzahl b) F¨ ur alle a, b ∈
Z gilt:
p | (a · b)
=⇒
(p | a oder p | b) .
Dieses Ergebnis l¨asst sich mit Hilfe vollst¨andiger Induktion auf Produkte mit mehr als zwei Faktoren verallgemeinern:
(5.5) SATZ: a) Sind a1 , a2 , . . . , an (n ∈ gilt:
N)
ganze Zahlen und ist p eine Primzahl, so
Teilt p das Produkt a1 · a2 · . . . · an , so teilt p mindestens einen der Faktoren.
b) F¨ ur Zahlen p ∈ IP , a ∈
Z, n∈N
gilt:
p | an
=⇒
p|a.
BEM: Formelm¨aßig bedeutet (5.5a): p | a1 · a2 · . . . · an
=⇒
es gibt ein k ∈ {1, 2, 3, . . . , n} mit p | ak .
urliche Zahl n ≥ 2 besitzt einen Primteiler , d.h. es gibt eine (5.6) SATZ: Jede nat¨ Primzahl p mit p | n . (5.7) FOLGERUNG: Zwei ganze Zahlen a und b sind genau dann teilerfremd, wenn sie keinen gemeinsamen Primteiler besitzen.
¨ Uber die Verteilung der Primzahlen (5.8) SATZ: (Euklid)
Es gibt unendlich viele Primzahlen.
(5.9) DEF: Ein Zahlenpaar (p, p + 2) , bei dem sowohl p als auch p + 2 Primzahlen sind, heißt ein Primzahlzwilling .
ur Primzahlzwillinge: (3, 5) , (5, 7) , (11, 13) , (17, 19) , (29, 31) , Beispiele: f¨ (q, q + 2) mit q = 242 206 083 · 238 880 − 1 (q hat 11 713 Dezimalziffern) . ¨ UNGELOSTES PROBLEM: Bis heute ist nicht bekannt, ob es unendlich viele Primzahlzwillinge gibt oder nur endlich viele.
28
Chr.Nelius : Zahlentheorie (SoSe 2016)
urliche Zahl, so sind die n aufeinanderfolgenden Zahlen (5.10) SATZ: Ist n eine beliebige nat¨ (n + 1)! + 2, (n + 1)! + 3, (n + 1)! + 4, . . . , (n + 1)! + n, (n + 1)! + (n + 1) alle zusammengesetzt. Dabei bezeichnet n! (lies: n–Fakult¨at) das Produkt der nat¨ urlichen Zahlen von 1 bis n , d.h. n! = 1 · 2 · 3 · . . . · n . BEM: (5.10) bedeutet, dass der Abstand zwischen zwei aufeinanderfolgenden Primzahlen beliebig groß werden kann.
(5.11) SATZ: Zu jeder Primzahl p ≥ 5 gibt es eine Zahl k ∈
N mit
p = 6 · k − 1 oder p = 6 · k + 1 .
urlichen (5.12) BEM: a) Eine Primzahl p ≥ 5 liegt also auf dem Zahlenstrahl der nat¨ Zahlen entweder unmittelbar vor oder hinter einem Vielfachen von 6 . b) Umgekehrt muss aber eine Zahl der Form 6 · k − 1 oder 6 · k + 1 keine Primzahl sein. So ist z.B. f¨ ur k = 6 die Zahl 6 · 6 − 1 = 35 keine Primzahl, und f¨ ur k = 4 ist 6 · 4 + 1 = 25 keine Primzahl.
(5.13) BEM: Die folgende Tabelle enth¨alt Angaben u ¨ ber die Anzahl der Primzahlen bis zu einer bestimmten Grenze: m
Anzahl der Primzahlen ≤ m
10 100 1000 104 105
4 25 168 1 229 9 592
106
78 498
Chr.Nelius : Zahlentheorie (SoSe 2016)
29
Wie kann man testen, ob eine Zahl prim ist? (5.15) SATZ: F¨ ur eine nat¨ urliche Zahl n ≥ 4 sind folgende Aussagen a¨quivalent: a) n ist eine Primzahl
√ b) n besitzt keinen Teiler t mit 2 ≤ t ≤ ⌊ n⌋ √ c) n besitzt keinen Primteiler p mit p ≤ ⌊ n⌋ .
Aus diesem Satz ergibt sich ein Primzahltest f¨ ur eine nat¨ urliche Zahl n ≥ 4 :
(5.16) Primzahltest √ Teste der Reihe nach, ob eine der Primzahlen ≤ ⌊ n⌋ die Zahl n ≥ 4 teilt. Wenn nein, ist n eine Primzahl, wenn ja, ist ein echter Teiler von n gefunden, und n ist nicht prim.
√ Um den Primzahltest (5.16) ausf¨ uhren zu k¨onnen, m¨ ussen alle Primzahlen ≤ ⌊ n⌋ bekannt sein. Ein Verfahren, Primzahllisten aufzustellen, ist
(5.17) Das Sieb des Eratosthenes Sei n ≥ 3 eine nat¨ urliche Zahl. Gehe folgendermaßen vor: Streiche in der Folge der ungeraden nat¨ urlichen Zahlen von 3 bis n alle echten Vielfachen von 3 , dann alle echten Vielfachen der n¨achsten ungestrichenen Zahl usw. √ Brich das Verfahren ab, wenn die n¨achste ungestrichene Zahl > ⌊ n⌋ ist.
Es bleiben alle ungeraden Primzahlen ≤ n u ¨ brig. F¨ ugt man noch die einzige gerade Primzahl 2 hinzu, so erh¨alt man alle Primzahlen ≤ n .
