Primzahlen: naive Ansätze

Einleitung

Wenn man testen möchte, ob eine natürliche Zahl $n$ eine Primzahl ist, kommt einem vielleicht als erstes das Konsequente Durchtesten auf Teilbarkeit in den Sinn. Dabei testet man, ob es eine natürliche Zahl zwischen $2$ und $n-1$ gibt, die $n$ teilt. Existiert keine natürliche Zahl zwischen $2$ und $n-1$ gibt, die $n$ teilt, so ist $n$ eine Primzahl. Findet sich wenigstens eine Zahl zwischen $2$ und $n-1$ die $n$ teilt, so ist $n$ keine Primzahl.

Beispiele

• 7

$7mod2=1$

$7mod3=1$

$7mod4=3$

$7mod5=2$

$7mod6=1$

Keine Zahl zwischen 2 und 6 teilt 7 (ohne Rest), also ist 7 eine Primzahl.

• 9

$9mod2=1$

$9mod3=0$ Teiler!

$9mod4=1$

$9mod5=4$

$9mod6=3$

$9mod7=2$

$9mod8=1$

Die 3 teilt 9 (ohne Rest), also kann 9 keine Primzahl sein.

Balast und Verbesserungen

Wenn man sich den naiven Ansatz des konsequenten Durchtestens durch Teilung so ansieht, fallen einem einige Überflüssigkeiten und Verbesserungsmöglichkeiten auf.

• $n$ kann nie durch $n-1$ geteilt werden.

Es ist einfach nicht möglich, und daher fällt $n-1$ als Teilerkriterium weg. Korrekt wäre also: Existiert keine natürliche Zahl zwischen $2$ und $n-2$ gibt, die $n$ teilt, so ist $n$ eine Primzahl!

• Wenn aus einem beliebigen Produkt $a\cdot b=n$ mit $a<b$ der Faktor $a$ schon als Teiler getestet wurde, so ist es nicht mehr nötig, Faktor $b$ auch noch zu testen.

Angenommen ich teste die Zahl $35=5\cdot 7$ auf ihre primalität. Wenn ich die 5 getestet und festgestellt habe, das sie ein Teiler von 35 ist, kann ich aufhören, weitere Zahlen darauf zu testen, ob sie Faktoren der 35 sind oder nicht. Um mal den Extremfall zu zeigen: Angenommen ich will 49 auf ihre primalität testen. Dann muß ich das nur bis zur 7 machen, weil 7 die Quadratwurzel von 49 ist: $7\cdot 7=49$.

Wie sieht das nun bei einer Primzahl aus? Wie weit muß ich da testen? Bis $n-2$? Nein, es reicht, bis $\lfloor \sqrt{n}\rfloor$ zu testen. Warum?

Angenommen, es gibt keinen Teiler kleiner $\lfloor \sqrt{n}\rfloor$, der $n$ teilt. Dann kann es auch keinen Teiler größer $\lfloor \sqrt{n}\rfloor$ geben, der $n$ teilt. Warum?

Nehmen wir mal an, wir haben zwei natürliche Zahlen $\lfloor \sqrt{n}\rfloor <a\le b$ für die gilt $a$ teilt $n$ und $b$ teilt $n$. Daraus würde folgen, das $(\lfloor \sqrt{n}\rfloor {)}^2=n<a\cdot b$ ist. Das ist ein Widerspruch, und deshalb muß man auch nur bis maximal $\lfloor \sqrt{n}\rfloor$ testen.

• Primzahlen größer 3 haben die Form $6k+1$ oder $6k-1$

Aus diesem Grund braucht man Primzahlen, die nicht dieser Form entsprechen nicht kosequent auf alle mögliche Teiler zu testen. Es reicht, einen Vortest auf die Formen $6k+1$ und $6k-1$ zu machen. Zahlen die nicht diesen Formen entsprechen, fallen als Kandidaten für Primzahlen gleich raus. Das sind $\frac{2}{3}$ aller natürlichen Zahlen.

• Primzahlen größer 5 haben die Form $30n+k$ mit einem $k$ aus der Menge $\{1,7,11,13,17,19,23,29\}$. Da für alle $k$ aus $\{1,7,11,13,17,19,23,29\}$ gilt, daß sie teilerfremd zu 30 sind, für alle $\overline{k}$ aus $\{2,3,4,5,6,8,...\}$ aber nicht, muß für einen Vortest nur getestet werden, ob für die zu testende Zahl $n$ gilt: $\mathrm{ggT}(n,30)=1$. Ist der $\mathrm{ggT}(n,30)>1$, so ist n mit Sicherheit zusammengesetzt. Ist der $\mathrm{ggT}(n,30)$ aber 1, und ist $7\le n\le 47$, dann ist $n$ in jedem Falle eine Primzahl, und für den Fall $n>47$ doch mit größerer Wahrscheinlichkeit.

Fehltreffer:

49, 77, 91, 119, 121, 133, ...

Eine Variation des naiven Ansatzes

Statt auf die Teilbarkeit läßt sich auf die Teilerfremdheit testen. Wie in Kapitel Ib. schon beschrieben gilt für alle natürlichen Zahlen $a$ und $b$, in die sich eine Primzahl additiv zerlegen läßt, das $a$ und $b$ zueinander Teilerfremd sind. das also gilt: $\mathrm{ggT}(a,b)=1$. Dabei können wir den Fall $\mathrm{ggT}(1,n-1)=1$ aussen vor lassen, da er wie $n-1$ ist kein Teiler von $n$ immer war ist, egal ob die zu testende Zahl $n$ eine Primzahl ist, oder nicht. Existieren zu einer Zahl $n=a+b$ zwei Zahlen $a$ und $b$, die nicht zueinander teilerfremd sind, dann handelt es sich bei $n$ um keine Primzahl. Sind dagegen alle $a$ und $b$ von einer Zahl $n=a+b$ zueinander teilerfremd, so ist $n$ eine Primzahl.

Identisch

Diese Form des Primzahltests ist nicht unabhängig von dem Primzahltest durch konsequentes Testen auf Teilbarkeit. Die eine Form läßt sich in die andere Form überführen. Das läßt sich wie folgt zeigen:

Der Primzahltest durch konsequentes Testen auf Teilbarkeit läßt sich als $\mathrm{ggT}(a,n)$ auffassen. Es gilt $n=a+b$. Also gilt auch $\mathrm{ggT}(a,n)=\mathrm{ggT}(a,a+b)$. Weiterhin gilt $\mathrm{ggT}(a,a+b)=\mathrm{ggT}(a,a)+\mathrm{ggT}(a,b)=0+\mathrm{ggT}(a,b)=\mathrm{ggT}(a,b)$.

Und genau das ($\mathrm{ggT}(a,b)$) ist ja der Primzahltest auf Teilerfremdheit.

Genauso läßt sich zeigen, das $\mathrm{ggT}(n-1,1)=\mathrm{ggT}(n-1,n)$ ist.