Primzahlen

Note 1

Die Menge der natürlichen Zahlen wird mit

\mathbb{N} := \{1,2,3,\dots\}

abgekürzt.

Unter den natürlichen Zahlen gibt es solche, die jedem Divisionsversuch mit einem natürlichen Divisor, der zwischen $1$ und der Zahl selbst liegt, widerstehen. Solche – in diesem Sinne teilerlose – Zahlen werden Primzahlen genannt.

Definition 1: Teiler

Seien $a, b \in \mathbb{Z}$ mit $b \neq 0$ .
$b$ ist ein Teiler von $a$ , wenn es ein $c \in \mathbb{Z}$ gibt, so dass

a = b \cdot c

gilt.
Man schreibt $b\mid a$ .

Definition 2: Primzahl

Eine Zahl $p\in\mathbb{N}$ heisst Primzahl, wenn $p$ genau zwei verschiedene, natürliche Teiler hat.

\mathbb{P} := \{2,3,5,7,11,13,17,19,23,\dots\}

Note 2

Beachte, dass $1$ per Definition keine Primzahl ist!

Primfaktorzerlegung

Exercise 1: Primfaktorzerlegung

Zerlege die Zahlen $210$ , $541$ , $1'771$ , $7'571$ , $198'000$ und $234'600$ in ihre Primfaktoren.

Solution

$210 = 2\cdot3\cdot5\cdot7$

$541$ ist prim.

$1771 = 7\cdot11\cdot23$

$7571=67\cdot113$

$198000 = 2^4\cdot3^2\cdot5^3\cdot11$

$234600=2^3\cdot3\cdot5^2\cdot17\cdot23$

Primzahlen sind die Bausteine der natürlichen Zahlen. Dies besagt der folgende Satz, den ich gerne als Satz der "DNA der natürlichen Zahlen" bezeichne.

Theorem 1: Fundamentalsatz der Arithmetik

Jede natürliche Zahl grösser $1$ lässt sich eindeutig, bis auf die Reihenfolge der Faktoren, als Produkt von Primzahlen darstellen.

Proof

BWoC: Falls die Primfaktorzerlegung in $\mathbb{N}\setminus\{1\}$ nicht eindeutig wäre, dann gäbe es eine kleinste Zahl $n\in\mathbb{N}\setminus\{1\}$ , die auf mindestens zwei Arten darstellbar wäre:

n=p_1\cdot\ldots\cdot p_r=q_1\cdot\ldots\cdot q_s.

Da $n$ das kleinste Beispiel ist, sind alle $p_i\neq q_j$ für alle $i,j$ in ihren Indexmengen. Ausserdem können wir OEdA annehmen, dass die Faktoren der Grösse nach sortiert seien (Wohlordnung von $\mathbb{N}$ ) und $p_1\neq q_1$ mit $p_1+1\leq q_1\leq\sqrt{n}$ .

Betrachte nun $m:=n-p_1q_1$ mit $\sqrt{n}<m<n$ . Beachte, dass $m<n$ eine eindeutige Primfaktorzerlegung hat. Aus

m=p_1\cdot(p_2\cdot\ldots\cdot p_r-q_1)=q_1\cdot(q_2\cdot\ldots\cdot q_s-p_1)

folgt $p_1|(q_2\cdot\ldots\cdot q_s-p_1)$ , also $p_1|(q_2\cdot\ldots\cdot q_s)$ . Weil aber für Zahlen kleiner $n$ die Primfaktorzerlegung eindeutig ist, muss $p_1=q_j$ für ein $j\neq1$ ; im Widerspruch zu $p_1\neq q_j$ $\forall j$ .

Sieb von Eratosthenes

Der alexandrinische Bibliothekar, Mathematiker und Geograph Eratosthenes (276-194 BC), der als erster einen ausgezeichneten Wert für den Umfang der Erde ermittelt hat, kannte bereits ein einfaches Verfahren, um die Primzahlen schrittweise aus der Reihe der natürlichen Zahlen heraus zu filtern: das Sieb des Eratosthenes.

Betrachten wir die Primzahlen kleiner $100$ :

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Auffallend ist, dass die Primzahlen scheinbar zufällig über $\mathbb{N}$ verteilt sind. Zudem gibt es Primzahlen, die sich als Paar um eine einzige Zahl schmiegen, wie zum Beispiel $11$ und $13$ , $17$ und $19$ , $29$ und $31$ oder $59$ und $61$ . Die von einem solchen Primzahlzwilling eingeschlossene Zahl besitzt immer viele Teiler, auf jeden Fall den Teiler $6$ .

Exercise 2: 🧩

Seien $p$ und $p+2$ prim. Beweise, dass die Zahl zwischen einem Primzahlzwilling $(p\mid p+2)$ durch $6$ teilbar ist.

Solution

Für $(3\mid 5)$ stimmt die Aussage nicht. Lassen wir also diesen Fall ausser betracht.

Da $2$ die einzige gerade Primzahl ist, muss die Zahl zwischen einem Primzahlzwillinge gerade sein. Betrachte für $k\in\mathbb{N}$ die Kette

6k-2\quad 6k-1\quad 6k\quad 6k+1\quad 6k+2\quad 6k+3.

Damit werden für $k\in\mathbb{N}$ alle natürlichen Zahlen grösser $3$ durchlaufen. $6k-2$ und $6k$ , sowie $6k$ und $6k+2$ und $6k+1$ , $6k+3$ können keine Primzahlzwillinge sein. Also kommt als Primzahlzwilling in dieser Kette nur $(6k-1\mid 6k+1)$ in Frage. Offensichtlich ist $6k$ durch $6$ teilbar.

Es ist übrigens nicht bekannt, ob es endlich oder unendlich viele Primzahlzwillinge gibt.

Exercise 3: Primzahldrillinge

Gibt es Primzahldrillinge, also Zahlentrippel mit $p$ , $p+2$ und $p+4$ alle prim?

Solution

Es gibt nur das Tripel $(3\mid 5\mid 7)$ . Denn jedes weitere Tripel würde ungerade Zahlen enthalten, wobei sicher eine davon durch $3$ teilbar wäre, da jede dritte ungerade Zahl durch $3$ teilbar ist.

Man kann dies auch formal einsehen: Wäre $(p\mid p+2\mid p+4)$ mit $p>3$ ein weiteres Tripel, so dürfte $p$ nicht durch $3$ teilbar sein. Es gälte also $p\mod{3}\equiv1$ oder $p\mod{3}\equiv2$ . Sei $p\mod{3}\equiv1$ , dann ist aber $p+2\mod{3}\equiv0$ durch $3$ teilbar, also keine Primzahl. Gälte $p\mod{3}\equiv2$ , so wäre $p+4\mod{3}\equiv0$ durch $3$ teilbar. Somit ist $(3\mid 5\mid 7)$ der einzige Primzahldrilling.

Note 3

Die Abstände zwischen aufeinanderfolgenden Primzahlen – also die Anzahl der nichtprimen Zahlen zwischen zwei Primzahlen – fallen sehr unterschiedlich aus. Mit zunehmender Grösse der Zahlen treten neben kleinen auch immer grössere Lücken auf.

Daraus ergibt sich die Frage:

Ist die Menge der Primzahlen endlich? Gibt es eine grösste Primzahl?

Die Antwort auf diese Frage lieferte bereits um $350\,\text{BC}$ Euklid mit einem indirekten Beweis.

Exercise 4: 🧩

Zeige, dass es unendlich viele Primzahlen gibt.

Solution

Gegenannahme: Es gebe endlich viele Primzahlen und daher gebe es eine grösste, die wir $p$ nennen. Wir betrachten die Menge dieser endlich vielen Primzahlen

\{2,3,5,7,11,\dots,p\}.

Wir basteln daraus die Zahl

2\cdot3\cdot5\cdot7\cdot11\cdot\dots\cdot p+1=:z.

Diese Zahl $z\in\mathbb{N}$ ist sicher grösser als $p$ und sie ist auch prim. Denn beispielsweise hat man $z\div 7=2\cdot3\cdot5\cdot11\cdot\dots\cdot p+1$ , d.h. $z=7\cdot2\cdot3\cdot5\cdot11\cdot\dots\cdot p+1$ hat bei Division mit $7$ Rest $1$ . Und dies gilt analog für alle Primzahlen in unserer Menge

\{2,3,5,7,11,\dots,p\}.

Dies widerspricht der Annahme, dass $p$ die grösste Primzahl sei, denn $z>p$ ist prim. Also muss das Gegenteil unserer Annahme gelten: Es gibt unendlich viele Primzahlen.

Dichte von Primzahlen

Deutlich ist, dass die Primzahlen im allgemeinen mit wachsenden Zahlenwerten weniger häufig auftreten. Aber auch diese Gesetzmässigkeit wird durchbrochen. So finden wir in den ersten Hunderter-Blöcken die folgenden Anzahlen Primzahlen:

Primzahlen	und ihre	Verteilung
$1$ bis $100$	$101$ bis $200$	$201$ bis $300$
$25$	$21$	$16$
$301$ bis $400$	$401$ bis $500$	$501$ bis $600$
$16$	$17$	$14$
$601$ bis $700$	$701$ bis $800$	$801$ bis $900$
$16$	$14$	$15$
$901$ bis $1000$
$14$

Das erste Tausend weist also $168$ Primzahlen auf, was etwa $\tfrac{1}{6}$ aller natürlichen Zahlen dieses Intervalls entspricht. In den ersten $3000$ finden sich etwa $\tfrac{1}{7}$ , und unter den ersten $10\,000$ treffen wir auf rund $\tfrac{1}{8}$ . Die Dichte nimmt also scheinbar ab. (Primzahldichte kommentiert)

Primzahlen im Internet

Die Suche nach schnellen Verfahren zum Auffinden von Primzahlen dauert bis zum heutigen Tag an; und das nicht nur aufgrund des Reizes, den sie seit jeher auf die Menschen ausgeübt haben. Über zweitausend Jahre lang wusste man keinen praktischen Nutzen aus dem Wissen über die Primzahlen zu ziehen. Dies änderte sich allerdings schlagartig mit dem Aufkommen des elektronischen Datenverkehrs, als Primzahlen zum Verschlüsseln von Informationen eine zentrale Rolle zu spielen begannen.

Die Güte einer Geheimsprache besteht einerseits darin, Botschaften ohne grossen Aufwand in Geheimschrift umschreiben (chiffrieren) zu können, andererseits darin, die Schwierigkeit für Uneingeweihte eine geheime Botschaft zu knacken (dechiffrieren), ins Unermessliche zu steigern. Solch asymmetrische Eigenschaften trifft man beim Rechnen mit Primzahlen an:

Note 4

Es ist relativ einfach, das Produkt von zwei grossen Primzahlen zu berechnen, aber nahezu unmöglich, dieses Produkt wieder in seine Faktoren zu zerlegen.

Das Verschlüsseln einer Botschaft läuft heute tatsächlich auf die Multiplikation zweier sehr grosser Primzahlen hinaus, während das Entschlüsseln im Wesentlichen aus dem Faktorisieren dieses Produkts besteht (ausprobieren). Bis dato hat man noch keinen schnellen Algorithmus zur Faktorisierung eines Produkts zweier grosser Zahlen gefunden. Ja, man weiss sogar nicht einmal, ob ein solcher überhaupt existiert.

Übungen zu $\mathbb{N}$ und Primzahlen

Exercise 5: Primzahlformel

Was taugen die folgenden Formeln als Primzahlerzeuger? Dabei steht stets $p$ für eine Primzahl und $n$ für eine natürliche Zahl.

a) $z_a=2^p-1$

b) $z_b=2^p+1$

c) $z_c=n^2-n+41$

Solution

a) $p=6$ liefert $63=3^2\cdot7$ .

b) $p=3$ liefert $9=3^2$ .

c) $n=41$ liefert sicher keine Primzahl, weil $z_c(41)=41^2$ .

Exercise 6: 🧩

Wähle $5$ gerade Zahlen zwischen $3$ und $1000$ . Versuche jeder dieser Zahlen als Summe von zwei Primzahlen darzustellen (Stichwort Goldbach'sche Vermutung). Wie lautet deine Vermutung? Beweise sie!

Solution

Beispiele sind $4=2+2$ , $6=3+3$ , $8=3+5$ , $10=3+7$ . Beachte, dass die Zerlegung nicht eindeutig sein muss. Beispielsweise ist $10=3+7=5+5$ oder $20=3+17=7+13$ .

Bis dato konnte die Goldbach-Vermutung nicht bewiesen werden.

Sidenote: Dem Russen Winogradow gelang mittels statistischer Methoden über die Primzahlen um 1937 der Beweis, dass sich jede "genügend" grosse, ungerade Zahl als Summe von drei Primzahlen schreiben lässt.

Exercise 7: Primzahllücken

Es gibt "Primzahllücken" beliebiger Grösse. Man definiert für $n\in\mathbb{N}$ den Ausdruck $n!:=1\cdot2\cdot3\cdot\dots\cdot n$ und sagt " $n$ Fakultät".

a) Sind unter den Zahlen $5!+1$ , $5!+2$ , $5!+3$ , $5!+4$ und $5!+5$ Primzahlen?

b) Welche der Zahlen $47!+1, 47!+2, 47!+3,\dots,47!+47$ sind sicher nicht prim?

Solution

a) $5!+1=121=11^2$ , $5!+2=122$ ist gerade, $5!+3=123=3\cdot41$ , $5!+4$ ist gerade, $5!+5=125=5^3$ sind alle nicht prim.

b) Für $47!+1$ ist ohne Hilfsmittel aufwändig zu beurteilen, ob sie prim ist oder nicht. Hingegen $47!+2=1\cdot2\cdot3\cdot\dots\cdot47+2=2\cdot(1\cdot3\cdot\dots\cdot47+1)$ . Analog $47!+3=1\cdot2\cdot3\cdot\dots\cdot47+3=3\cdot(1\cdot2\cdot4\cdot\dots\cdot47+1)$ . Das heisst, alle Zahlen $47!+2$ , $47!+3$ , $\dots$ , $47!+47$ sind sicher nicht prim.

Exercise 8: Double Triple

Nimm eine dreistellige Zahl und notiere sie zweimal hintereinander, so dass eine sechstellige Zahl entsteht. Teile diese Zahl nacheinander durch $7$ , $11$ und $13$ .

a) Was fällt auf?

b) Erkläre das "Phänomen".

Solution

a) Man kriegt wieder diejenige dreistellige Zahl, die man sich ausgedacht hat.

b) Multiplikation mit $7\cdot11\cdot13=1001$ schreibt eine dreistellige Zahl zweimal hintereinander.

Exercise 9: Nicht durch 4 teilbar

Zeige, dass die Summe von vier aufeinander folgenden natürlichen Zahlen niemals ein Vielfaches von $4$ sein kann.

Solution

In der Tat ist für beliebig gewähltes $n\in\mathbb{N}$ die Summe von vier aufeinander folgenden natürlichen Zahlen $n+(n+1)+(n+2)+(n+3)=4n+6=4\cdot(n+1)+2$ immer $(n+(n+1)+(n+2)+(n+3))\mod{4}\equiv2$ , hat also Rest $2$ bei Division mit $4$ .

Exercise 10: 🧩

Vier aufeinanderfolgende natürliche Zahlen werden miteinander multipliziert und zum Produkt $1$ addiert.

a) Stelle einige konkrete Berechnungen an.

b) Formuliere eine Vermutung und beweise diese.

Solution

a) Beispielsweise hat man $1\cdot2\cdot3\cdot4+1=25=5^2$ , $2\cdot3\cdot4\cdot5+1=121=11^2$ oder $10\cdot11\cdot12\cdot13+1=17\,161=131^2$ .

b) Man kriegt eine Quadratzahl. In der Tat: Sei $x\in\mathbb{N}$ . $x(x+1)(x+2)(x+3)+1=(x^2+x)(x^2+5x+6)+1=x^4+6x^3+11x^2+6x+1=(x^2+3x+1)^2$ .

Exercise 11: Teilbarkeit von Quadratzahlen

Suche Quadratzahlen, welche bei der Division durch $3$ den Rest $2$ lassen. Solltest du keine derartige Zahl finden, so versuche zu beweisen, dass es keine Quadratzahl gibt, die bei der Division durch $3$ den Rest $2$ lässt.

Solution

Man kriegt bei der Division durch $3$ nie den Rest $2$ . Einige Beispiele: $1^2\mod{3}\equiv1$ , $2^2\mod{3}\equiv1$ , $3^2\mod{3}\equiv0$ oder $4^2\mod{3}\equiv1$ .

In der Tat: Betrachte für $n\in\mathbb{N}$ die Kette

3n-2,3n-1,3n,

welche für $n\in\mathbb{N}$ alle natürlichen Zahlen durchläuft. Die Quadrate $(3n-2)^2=9n^2-12n+4=3\cdot (3n^2-4n+1)+1$ und $(3n-1)^2=9n^2-6n+1=3\cdot(3n^2-2n)+1$ haben offensichtlich Rest $1$ bei Division mit $3$ . Das Quadrat $9n^2=3\cdot3n^2$ hat Rest $0$ bei Division durch $3$ . Daher kann keine Quadratzahl bei Division durch $3$ Rest $2$ haben.

Primzahlen

Primfaktorzerlegung

Sieb von Eratosthenes

Dichte von Primzahlen

Primzahlen im Internet

Übungen zu N\mathbb{N} und Primzahlen

Übungen zu $\mathbb{N}$ und Primzahlen