Primzahlen

(prime numbers)

Definition	Eine Zahl p³2 und pÎ IN heißt Primzahl genau dann, wenn sie genau 2 Teiler aus IN hat, und zwar 1 und p selbst.
Beispiele	Die ersten Primzahlen sind: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, . . . .
Satz 1	Jede Zahl nÎ IN mit n³2 ist in Primfaktoren zerlegbar, das heißt das Produkt von Primzahlen. (Man spricht auch von Primzahlzerlegung) Beweis: Vollständige Induktion über n Induktionsanfang n=2=1*2 Induktionsschluss: Voraussetzung: Jede Zahl kleiner gleich n ist in Primfaktoren zerlegbar. Schluss: Wenn n+1 eine Primzahl ist, so ist nichts zu beweisen. Sei n+1 keine Primzahl, dann existieren 2 Zahlen n1 und n2 beide kleiner als n mit n1*n2=n. Diese sind beide per Voraussetzung in Primzahlen zerlegbar. Also ist auch n ein Produkt von Primzahlen.
Beispiel 1	630=2*3*3*5*7
Satz 2	Es gibt unendlich viele Primzahlen. Beweis: Indirekter Beweis: Voraussetzung: Es gäbe endlich viele Primzahlen p1 bis pn. Nun bilden wir die Zahl p mit der Eigenschaft p=p1*p2*...pn+1. Wenn man nun p durch p1 teilt, so bleibt der Rest 1. Wenn man nun p durch p2 teilt, so bleibt der Rest 1. ..... Wenn man nun p durch pn teilt, so bleibt der Rest 1. Also hat p in seiner Primzahlzerlegung keine der Primzahlen p1 bis pn. Deshalb kann p nur selbst eine Primzahl sein oder eine zusammengesetzte Zahl sein, deren Primfaktorenzerlegung Primzahlen enthält, die sich von p1 bis pn unterscheiden. Widerspruch zur Voraussetzung.
Satz 3	Um festzustellen, ob eine Zahl n eine Primzahl ist, ist es ausreichend n durch alle Primzahlen von 1 bis zu teilen. Ist bis keine Primzahl als Teiler von n aufgetreten, dann ist n eine Primzahl. Beweis: Wenn n eine zusammengesetzte Zahl wäre, dann gilt für die kleinste Primzahl der Primfaktorzerlegung, also q, die n teilt q£ , denn anderenfalls wäre q*q>*=n und erst recht jede andere Primzahl der Zerlegung multipliziert mit q.
Beispiel 2	n=1001, , n=7*11*13, n=93, , n=3*31
Satz 4	Es gibt unendlich viele Primzahlen der Art 4k+3 mit kÎ IN. (aber nicht für alle kÎ IN ist 4k+3 eine Primzahl) Beweis: Indirekter Beweis: Voraussetzung Es gibt endlich viele Primzahlen p1 bis pn, die sich als 4*k+3 mit kÎ IN darstellen lassen. Sei nun N=4*p1*p2*...*pn-1. Da N ungerade ist muss jeder Primfaktor von N ungerade sein und ist somit von der Gestalt 4k+1 oder 4k+3, denn zwischen 4k und 4(k+1)=4k+4 gibt es genau diese 2 ungeraden Zahlen. Das Produkt von Zahlen der Art 4k+1 und 4l+1 ist von der Art 4m+1, denn (4k+1)(4l+1)=16kl+4k+4l+1=4(4kl+k+l)+1. Da N nicht von der Art 4m+1 ist, enthält N mindestens einen Primfaktor q der Art q=4k+3. Da q|N aber alle p1 bis pn N nicht teilen folgt ein Widerspruch zur Voraussetzung.
Beispiel 3	4*1+1=5 ist Primzahl 4*2+1=9 ist keine Primzahl 4*3+1=13 ist Primzahl 4*4+1=17 ist Primzahl 4*5+1=21 ist keine Primzahl
Satz 5	Satz von Dirichlet Seien a,bÎ IN mit ggt(a,b)=1, dann gibt es unendlich viele Primzahlen der Art ak+b.
Satz 6	Für jede Zahl kÎ IN gibt es zwei hintereinander folgende Primzahlen p und q, so dass zwischen p und q mindestens k zusammengesetzte Zahlen liegen. Also können die Lücken zwischen 2 aufeinanderfolgenden Primzahlen beliebig groß werden. Beweis: Sei kÎ IN gegeben. Man betrachte die Zahlen (k+1)!+2, (k+1)!+3,...(k+1)!+(k+1). Die erste Zahl ist durch 2 teilbar. Die zweite Zahl ist durch 3 teilbar. Die dritte Zahl ist durch 4 teilbar ... Die k. Zahl ist durch k+1 teilbar Also haben wir k zusammengesetzte hintereinander laufende Zahlen gefunden, die von 2 Primzahlen p und q umgeben werden, mit p<(k+1)!+2 und q>(k+1)!+(k+1).
Satz 7	Hauptsatz der Arithmetik: Die Primfaktorzerlegung einer Zahl nÎ IN ist eindeutig. Also ist , wobei pi<pj für i<j. Beweis Angenommen n habe 2 unterschiedliche Primfaktorzerlegungen, dann gilt mit pi und qi Primzahlen und ai,biÎ IN Für alle pi gilt, dass pi|n, also teilt pi genau ein der qi. Da beide Zahlen Primzahlen sind entspricht jedem pi genau ein qi und somit sind r=s, ai=bi und pi=qi.
Definition 2	Die natürlichen Zahlen ai der Primzahlzerlegung der Zahl n mit heißen Vielfachheit der Zahl pi.
Satz 8	Die Folge der Summe der Reziprokwerte der Primzahlen divergiert. Also: .