Primzahlen¶

Definition: Primzahl ¶

\(p\in\mathbb{N}\) heißt Primzahl, wenn p genau 2 Teiler besitzt. Jede natürliche Zahl n hat mindestens die trivialen Teiler 1 und n.

Hinweis: Die kleinste Zahl, die die Definition erfüllt, ist die 2.

Primzahlentest:¶

Naive Idee: Teste für alle Zahlen \(k=2,3,...,n-1\) ob sie Teiler sind.

Verbesserung: Der kleinst mögliche Teiler von n ist 2 (der n als Primzahl ausschließt), daher kann der größte Teiler maximal \(\frac{n}{2}\) sein.

Beobachtung: Wenn \(\frac{n}{2}\mid n\), dann gilt auch \(2\mid n\), denn \(n=2*\frac{n}{2}\).

Allgemein gilt: Für \(k\in \mathbb{N}\) gilt, wenn \(\frac{n}{k}\mid n\), dann gilt auch \(k\mid n\).

Sei \(k\ne 1\) der kleinste Teiler von n, dann findet der oben beschriebene Algorithmus k vor \(\frac{n}{k}\), da gilt \(k\le \frac{n}{k}\). Abschätzung für den kleinsten Teiler k : \(k \le \frac{n}{k} \Leftrightarrow k^2\le n \Leftrightarrow k \le \sqrt{n}\). D.h. existiert ein Teiler \(k \notin \{1, n\}\), dann ist mindestens ein Teiler von n kleiner als \(\sqrt{n}\). Um zu zeigen, dass n eine Primzahl ist, genügt es also zu zeigen, dass gilt: \(\forall k \le \sqrt{n}: k \nmid n\)

Beobachtung:

Wenn \(2 \nmid\), dann gilt \(\forall a < \sqrt{n}\) ebenfalls \((2a)\nmid n\)
Wenn \(3 \nmid\), dann gilt \(\forall a < \sqrt{n}\) ebenfalls \((3a)\nmid n\)
Allgemein: Für \(k<\sqrt{n}\) gilt, wenn \(k \nmid n\) dann gilt:

\(\forall a < \sqrt{n}\) ebenfalls \((k*a)\nmid n\)

Sieb des Eratosthenes ¶

Algorithmus um herauszufinden, ob eine Zahl n eine Primzahl ist. Ist die Zahl keine Primzahl wird ein Teiler zurückgegeben ansonsten 0. Der Algorithmus kann auch genommen werden um Primzahlen zu finden, wenn man anstatt eine Zahl zurückgibt, den prim Array nimmt und schaut wo nach Ende des Durchlaufs noch true drin steht.

Sieb_des_eratosthenes(n)
    If n = 2 then return 0
    If 2 | n then return 2
    prim[2] <- true
    // prim ist ein Array in dem steht, welche Zahlen Primzahlen sind
    for k <- 3 to floor(sqrt(n)) do prim[k] <- k ist ungerade?
    for k <- 3 to floor(sqrt(n)) step 2 do
        if prim[k] then
            if k | n then return k
            j <- k^2
            // Alle kleineren k werden zuvor schon gestrichen
            while j <= floor(sqrt(n))
                prim[j] <- false
                j <- j + 2k
                // ungerade + ungerade wäre gerade
                // und diese wurden schon alle gestrichen
    return 0

Lemma 2: Primfaktorzerlegung ¶

Jede natürliche Zahl \(n \ge 1\) kann als Produkt von Primzahlen geschrieben werden. Ein solches Produkt wird auch als Primfaktorzerlegung bezeichnet. Dabei ist die Primfaktorzerlegung von 1, das leere Produkt, welches auf den Wert 1 definiert ist.

Beweis:¶

Zu tun

Beweis

Beispiele:¶

\begin{align*} 10&=2*5\\ 24&=2*2*2*3=2^3*3\\ 29&= 29 \end{align*}

Theorem 3:¶

Für \(n\ge 1\) gilt: Die Darstellung von \(n=p_0*p_1*...*p_n\) mit Primzahlen \(p_i\) und \(p_0\le p_1 \le ... \le p_n\) ist eindeutig.

Beweis:¶

Zu tun

Beweis

Folgerung 5:¶

Es gibt unendlich viele Primzahlen.

Beweis:¶

Zu tun

Beweis

Theorem 4: Primzahlsatz der Zahlentheorie ¶

Sei \(\pi (n) := \{p \le n : n\, ist\, prim\}\), dann gilt: \(\pi (n)~\frac{n}{log(n)}\)

Folgerung 6:¶

Die Primfaktorzerlegung des ggT zweier Zahlen \(a,b\ne 0\) enthält genau die Faktoren der Primfaktorzerlegung von a und b, die in beiden enthalten sind.