Erklärung und Herleitung der Gleichungen des Siebs von Atkin

Die hier vorgestellte Erklärung betrachtet die Eigenschaften der gelösten Werte P und ihre möglichen Teiler.

Das Sieb von Atkin kurz erklärt

Das Sieb von Atkin verwendet die drei Gleichungen

4x² + y² = P wobei P = 1 oder 5 mod 12

3x² + y² = P wobei P = 7 mod 12

3x² – y² = P wobei P = 11 mod 12 und x > y

zur Bestimmung von Primzahlen.

Besitzt eine Zahl P für eine dieser Gleichungen den erlaubten Rest modulo 12 und eine ungerade Anzahl Lösungen, dann ist P entweder eine Primzahl oder besitzt quadratische Teiler.

Man erstellt eine Liste mit einem Eintrag für jede positive ganze Zahl bis zum gewünschten Limit mit einem Schalter für „prim“/“nicht prim“. Dieser steht standardmäßig auf „nicht prim“ (gerade).

Für jede gefundene Lösung schaltet man den Schalter um.

Nur Primzahlen und Zahlen, die quadratische Teiler besitzen sind jetzt auf „prim“ gesetzt. Man geht die Liste der auf „prim“ gesetzten Zahlen durch, quadriert sie und setzt alle Vielfachen des Quadrates auf „nicht prim“.

Die Primzahlen 2 und 3 haben hier keine Lösung und werden in der Liste ergänzt.

Der Algorithmus ist schnell erklärt. Viel spannender ist die Mathematik dahinter.

Wichtiger Hinweis

Die folgenden Aussagen stellen Beobachtungen und Vermutungen von mir dar. Sie wurden anhand vollständiger numerischer Berechnungen bis zu einem hohen Grenzwert überprüft und haben sich in allen getesteten Fällen bestätigt. Ein allgemeiner mathematischer Beweis ist mir jedoch nicht bekannt.

Die Inhalte sind also als experimentelle Ergebnisse und nicht als bewiesene Sätze zu verstehen.

Aussagen wie „sicher“, „immer“ oder „das ist so“ bedeuten daher: „getestet, keine Gegenbeispiele gefunden“. Sie bedeuten nicht, dass die Aussage bewiesen ist.

Für Hinweise auf bekannte Beweise, Literatur oder Gegenbeispiele bin ich jederzeit dankbar.

Je mehr Tabellen miteinander verglichen wurden, desto mehr gemeinsame Strukturen traten hervor. Diese Beobachtungen führten Schrittweise zu den hier beschriebenen Vermutungen und Herleitungen.

Wenn man die hier vorgestellten Tabellen vergleicht, dann klären sich viele Aussagen daher von selbst. Es lohnt sich also, zwischendurch immer wieder einen Blick darauf zu werfen.

Die Mathematik hinter dem Sieb von Atkin

Um zu verstehen, warum das Sieb von Atkin genau diese Gleichungen verwendet, betrachtet man zunächst alle Gleichungen, die nach dem selben Prinzip funktionieren.

Insgesamt existieren 13 geeignete Gleichungen. Jede dieser Gleichungen erzeugt bestimmte Reste modulo 24..

Ist der Rest einer ganzen Zahl P modulo 24 in der folgenden Tabelle farbig markiert, dann kann die zugehörige Gleichung zur Primzahlbestimmung verwendet werden.

Ist der Rest modulo 24 in keiner Tabelle markiert, dann ist P immer durch 2 oder 3 teilbar und daher keine Primzahl.

Anm.: Bei „Modulo n“ wird nur der Rest einer Division durch n betrachtet.

Warum ist 4x² + y² hier nicht angeführt?

Wie man sieht, ist bei allen Gleichungen a bzw. b = 1, 2, 3 oder 6. Das sind die Grundformen, die auf die gleiche Weise zur Primzahlensuche verwendet werden können.

4x² + y² entspricht einer Variante der Form x² + y². Beide lösen die selben vier P modulo 24. Diese Gleichung kommt erst später dazu, weil ihre Herleitung etwas anders ist.

Folgende Primzahl-Kriterien gelten für alle Gleichungen

Eine ganze Zahl P > 3 ist prim, wenn…

1. P nicht durch 2 oder 3 teilbar ist (das trifft auf 1, 5, 7, 11, 13, 17, 19 und 23 mod 24 zu).
2. Die geeignete Gleichung (P mod 24 ist farbig markiert) exakt eine positive ganzzahlige Lösung im erlaubten Verhältnis hat.
3. x und y in dieser Lösung keinen gemeinsamen Teiler größer als 1 besitzen (andernfalls teilt dessen Quadrat P).

Anm.: Hier werden Quadrate addiert oder subtrahiert, daher ist ein gemeinsamer Teiler von x und y in P quadratisch.

Atkin nutzt diese Kriterien etwas allgemeiner indem er fragt: „Ist die Anzahl der Lösungen für P ungerade und ist P quadratfrei?“ Warum auch das funktioniert, wird weiter unten genau erklärt.

Die Eleganz liegt darin, dass Primzahlen nicht durch Ausschluss aller zusammengesetzten Zahlen ermittelt, sondern direkt auf Grund bestimmter Eigenschaften erkannt werden.

Primzahltest für eine einzelne Zahl P

(Ist hier zwar noch nicht Thema, passt aber perfekt zu den Primzahl-Kriterien)

1. Berechne für eine beliebige Zahl P den Rest mod 24 und wähle eine geeignete Gleichung.
2. Berechne das größte erlaubte x. Bsp.: P = 2x² – 3y²: x =ABRUNDEN((3P/2)^0,5).
3. Setze P und x in die Gleichung ein und suche mit absteigendem x nach y. Bsp.: y =((2x²-P)/3)^0,5
4. Ist eine ganzzahlige Lösung gefunden, prüfe x und y auf ggT > 1.

Beende den Test, wenn mehr als eine Lösung gefunden oder x bzw. y >= null ist.

Wurde nur eine einzige Lösung gefunden und ist der ggT (x, y) = 1 in dieser Lösung, dann ist P eine Primzahl. Andernfalls ist P zusammengesetzt.

Das Gleiche geht auch für einen größeren Zahlenbereich oder für einzelne Segmente. Dazu mehr bei „Optimierungen“ Anm.: n^0,5 = Wurzel(n)

x und y lassen sich gut in Tabellenform darstellen

x aus der Gleichung entspricht den Zeilenüberschriften und y den Spaltenüberschriften. x und y sind Reste modulo 12.Manchmal kann man schon mit einem kleineren Modulus alle Werte P berechnen. Bsp..: modulo 2, modulo 4 oder modulo 6.

Alle berechneten Werte P sind Reste modulo 24.

Atkin verwendet die Gleichungen 1, 3 und 13. Letztere in etwas abgewandelter Form.

Die Tabellen zeigen, dass man mindestens drei Gleichungen, braucht, um alle 8 Werte P modulo 24 zu lösen. Die Gleichungen 5/9, 6/8 sowie 11/12 lösen jeweils die gleichen Werte P.

Wann gibt es Lösungen für die Gleichungen?

Zu jeder Tabelle gehört eine Restklasse von vier Teilern modulo 24. Diese sind jeweils daneben farbig markiert.

Sind alle Teiler von P Elemente einer Teiler-Restklasse, dann gibt es in der Regel eine gerade Anzahl Lösungen innerhalb der erlaubten Verhältnisse. Es gibt aber Ausnahmen:

Primzahlen haben exakt eine Lösung.

Die Anzahl der Lösungen für einen Wert P stimmt in der Regel mit der Anzahl der möglichen Darstellungen als m * n überein. Daher haben Primzahlen exakt eine Lösung .

Bsp.: 91 (7 * 13 und 1 * 91) hat nur in Gleichung 1 zwei Lösungen: Eine Lösung zeigt nur die Teilbarkeit von P, Sie zeigt aber nicht die konkreten Teiler.

Gibt es fremde Teiler (Teiler modulo 24, die nicht farbig markiert sind), dann gibt es keine Lösung. Bsp.: 455 (5 * 7 * 13) kann mit keiner der 13 Gleichungen gelöst werden. Vergl. die Teiler-Restklassen.

Im Quadrat können alle Teiler (auch fremde) zu einer Lösung führen. Dann haben in mindestens einer Lösung x und y einen ggT größer als 1. Dessen Quadrat teilt auch P.

Fremde Teiler mit ungeradem Exponenten (n¹, n³, n⁵…) sind keine Quadrate und führen dazu, dass es keine Lösung gibt.

Hat P quadratische Teiler, dann kann die Anzahl der Lösungen auch ungerade sein.

Genau deshalb funktioniert das Sieb von Atkin.

Bsp.: 637 (7 * 7 * 13) hat drei Lösungen für m * n und Gl. 1.

• m * n = P:

1 * 637 = 637

7 * 91 = 637

13 * 49 = 637

• Gl. 1: x² + 3y² = P:

7² + 3 * 14² = 637

23² + 3 * 6² = 637

25² + 3 * 2² = 637

Vergl.: Bei der ersten Gleichung ist der ggT (x, y) = 7, weil 7 ein quadratischer Teiler von 637 ist.

Welche Zahlen werden mit den Gleichungen gelöst?

Zum besseren Verständnis des folgenden Abschnittes:

Jede positive Zahl, deren Primfaktorzerlegung ausschließlich die Primzahlen 2 und/oder 3 enthält, ist entweder ein Quadrat oder das 2-, 3- oder 6-fache eines Quadrates.

Die grün markierten Felder beziehen sich auf die Teiler-Restklassen oberhalb. Je nach Markierung wird

P = 1, 2, 3 oder 6 mal n² mal oberhalb markierter Teiler

gelöst. Vorausgesetzt, es gibt keine fremden Teiler, diese können als Produkt „getarnt“ als Element der Teiler-Restklasse auftauchen.

Bsp.: 7 * 13 = 19 mod 24 und 5 * 23 = 19 mod 24 werden nicht mit der selben Gleichung gelöst.

Bei n² sind fremde Teiler von n aber erlaubt. Fremde quadratische Teiler stören die Teiler-Struktur nicht, denn sie „erzwingen“ keine Lösung und verhindern auch keine. Sie ändern nur die Größe einer Bestehenden Lösung.

Bsp Gl 1: 1² + 3 * 2² = 13 (x, y) = (1, 2)

Multiplizieren wir nun: 13 * 5² = 325

5² + 3 * 10² = 325 (x, y) = (5, 10)

Der quadratische Teiler 5² hat keine neue Struktur geschaffen. Es wurde lediglich sowohl x als auch y mit 5 multipliziert.

Vergl. mit den Beispiel für 637 oben:

7 * 7 * 13 = 637 hat in Gl. 1 drei Lösungen. Alle Teiler gehören zur Restklasse.

5 * 5 * 13 = 325 hat jedoch genau eine Lösung (genauso wie 13), weil 5 hier ein fremder Teiler ist.

Teiler-Restklassen und grüne Markierungen

Anm.: Ein Wert P entspricht einem Element einer Teiler-Restklasse, wenn für ihn 1 grün markiert ist. Ob auch das 2-, 3- oder 6-fache eines Elements gelöst werden kann, erkennt man nicht eindeutig an modulo 24.

Bsp.: 2 * 7 = 14 mod 24

und 2 * 19 = 14 mod 24.

Die grünen Markierungen dienen dazu, solche Fälle zu unterscheiden.

Die Teiler-Restklassen sind nach modulo 6 in zwei Spalten aufgeteilt. 1, 2, 3 oder 6 ist jeweils nur für eine Spalte grün markiert.

Für die meisten Repräsentanten aller Restklassen ist 1, 2, 3, und 6 bei einer Gleichung oder aufgeteilt auf zwei Gleichungen grün markiert.

Ausnahme: Bei Gleichung 1, 11, 12 und 13 fehlen einige grüne Markierungen. Diese findet man indem man Gleichung 1 mit 2 und Gleichung 11, 12, und 13 mit 3 multipliziert.

Bsp.: Gl. 1: x² + 3y² löst das 1- und 3-fache aller Teiler der Teiler-Restklasse.

2 *(x² + 3y²)= 2x² + 6y² löst die fehlenden 2- und 6-fachen der Teiler.

Weil diese Gleichungen dann keine Primzahlen lösen, sind sie hier nicht angeführt. Alle 17 Gleichungen zusammen lösen also alle vielfachen von jedem Element aller Teiler-Restklassen, solange kein fremder Teiler mit ungeradem Exponenten involviert ist.

Durch 2 oder 3 teilbare Werte P müssen ausgeschlossen werden

Weil die Vorgabe – jeder Teiler muss der Teiler-Restklasse zugeordnet werden können – nur für nicht durch 2 oder 3 teilbare Zahlen definiert ist, verhalten sich diese etwas anders.

Es gibt für durch 2 oder 3 teilbare Werte P entweder gleich viele oder mehr (niemals weniger) Lösungen als für P. Die Zählung stimmt hier nicht mit der Anzahl der Lösungen für m * n = P überein.

Bsp.: Gl. 4 (2x² + 3y²) hat genau eine Lösung für 14 (2 * 1² + 3 * 2²) und ist deshalb nicht von einer Primzahl zu unterscheiden.

Durch 2 oder 3 teilbare Werte P müssen daher immer ausgeschlossen werden. Das passiert entweder durch die Modulo-Prüfung der berechneten Werte P, wie Atkin es macht, oder durch die gezielte Verwendung von gültigen x/y-Kombinationen.

Kleinste erlaubte Verhältnisse

Die jeweils angegebenen Verhältnisse in negativen Gleichungen ax² – by² = P dürfen nicht unterschritten werden, weil sie dann nicht mehr ganzzahlig wären und weil in kleineren Verhältnissen weitere Lösungen auftreten, die die Anzahl verfälschen würden. Wenn es im erlaubten Bereich Lösungen gibt, dann gibt es immer auch außerhalb welche.

Bei positiven Gleichungen ax² + by² = P ist das Verhältnis ohnehin dadurch beschränkt, dass sowohl ax² als auch by² kleiner oder gleich dem Wert P bleiben müssen.

Es gibt sieben Teiler-Restklassen      

Multipliziert man die Repräsentanten einer Teiler-Restklasse miteinander, egal wie oft, dann ist das Produkt immer ein Repräsentant der Teiler-Restklasse. Vergl. folgende Multiplikationen:

Jede Zeile in der oberen Tabelle repräsentiert eine Teiler-Restklasse. 1 mod 24 ist Repräsentant jeder Teiler-Restklasse.

Schreibt man die 8 Repräsentanten modulo 24 auf die Ecken eines Würfels, dann entsteht dieses Bild. Das zeigt, dass alle Kombinationen von zwei Teilern berücksichtigt sind.

Aufteilung der Abstände nach P

In den folgenden Tabellen sind die Faktoren danach sortiert, welchen Wert P sie jeweils ergeben.

Daneben steht jeweils der mögliche Abstand modulo 24 der Faktoren zueinander und als zweiter Wert der Abstand der Faktoren, wenn man sie vertauscht. (Jeder Faktor kann der größere oder der kleinere sein.)

Bsp.: 7 * 11 = 5 modulo 24:

Abstand (7, 11) ist 4 modulo 24.

Abstand (11, 7) ist 20 modulo 24.

Die Abstände der Teiler modulo 24 sind für einen einzelnen Repräsentanten in allen Teiler-Restklassen auf zwei Abstände beschränkt. Ausnahme: bei 11 und 23 kann man die Abstände mit modulo 12 auf zwei reduzieren.

Innerhalb einer Teiler-Restklasse ist eine Sortierung nicht sinnvoll. Die Abstände sind für jede Kombination unterschiedlich.

Besonderheit bei 23:

Die Summe der Faktoren ergibt immer null modulo 24.

Ein Wert P = 23 modulo 24 kann als einziger nicht mit einer positiven Gleichung getroffen werden. (Alle anderen 7 Werte P modulo 24 können sowohl mit einer positiven als auch mit einer negativen Gleichung getroffen werden.)

Wie sich gerade und ungerade Exponenten auswirken

Gerade Exponenten

n^k mit geradem Exponenten k ist immer = 1 modulo 24, wenn n nicht durch 2 oder 3 teilbar und m gerade ist.

Bsp.: 5², 5⁴, 5⁶… = 1 mod 24

1 modulo 24 kann bei 9 der 13 Gleichungen gleich P sein, ist aber Repräsentant aller sieben Teiler-Restklassen, und kann daher in allen 13 Gleichungen als Teiler vorkommen. Deshalb eignen sich alle Gleichungen für ein Primzahlsieb. (Teiler: P * 1)

1 modulo 24 ist ein neutraler Faktor innerhalb aller Teiler-Restklassen. 1 wird aber nicht in allen Teiler-Restklassen gleich erzeugt.

Bsp.: Nur in Gl 1.: kann (7 * 13) * 19 = 1 mod 24 gelöst werden.

Hinweis: Alle Gleichungen die 1 modulo 24 lösen, lösen auch die Zahl 1. Diese ist keine Primzahl, hat aber genau eine Lösung.

n^k mit geradem Exponenten k kann immer als m² dargestellt werden. Ist n kein Repräsentant der Teiler-Restklasse, dann werden x und y in allen Lösungen um den Faktor m erhöht. Vergl. (x, y) in folgenden Lösungen:

Bsp. Gl 1.:

• x² + 3 * y² = 13

1² + 3 * 2² = 13 (x, y) = (1, 2)

• 13 * 5² = 325

5² + 3 * 10² = 325 (x, y) = (5, 10)

• 13 * 5⁴ = 8125

25² + 3 * 50² = 8125 (x, y) = (25, 50)

Es gibt, wie für 13, jeweils genau eine Lösung, da 5 hier ein fremder Teiler ist.

Sind sowohl 13 als auch 5 Repräsentanten der Teiler-Restklasse (das ist bei Gl. 13.: x² + y² = P der Fall), dann gibt es jeweils so viele Lösungen, wie es Möglichkeiten der Darstellung als m * n gibt. Also eine Lösung für 13, drei Lösungen für 325 und fünf Lösungen für 8125.

Ungerade Exponenten

Der Rest modulo 24 von n^m mit ungeraden Exponenten m bleibt immer gleich, wenn n nicht durch 2 oder 3 teilbar ist.

Bsp.: 5¹, 5³, 5⁵… = 5 mod 24.

Wenn 5 kein Element der Teiler-Restklasse ist, dann gibt es keine Lösung.

Zusammenfassung

Was ist bewiesen?

Eine Restklassen-Filterung lässt sich durch vollständige Modulo-Berechnung beweisen. Dass eine sich daraus ergebende Lösungsmenge vollständig ist, lässt sich dadurch aber nicht beweisen.

Die Anzahl der Lösungen für einen Wert P kann nur in zwei Fällen ungerade sein:

• P ist prim

• P hat quadratische Teiler

Das ist meines Wissens nur für die drei Atkin-Gleichungen bewiesen.

Der Zusammenhang von gerade/ungerade Anzahl mit der Darstellbarkeit als Produkt von zwei Faktoren ist aber bewiesen: Die Anzahl kann nur dann ungerade sein, wenn ein Faktor mehr als einmal vorkommt oder P eine Primzahl ist.

Alle weiteren Aussagen sind Vermutungen, die sich durch beobachtete Symmetrien ergeben haben.

Die beschriebenen Zusammenhänge wurden für sämtliche Werte P mit x und y kleiner 10 000 vollständig überprüft. (Für negative Gleichungen wurde x entsprechend erhöht) Dabei wurden für alle Gleichungen sämtliche auftretenden Lösungen ausgewertet und miteinander verglichen. Die nach Restklassen geordnete Darstellung aller Lösungen machte die wiederkehrenden Symmetrien und Teiler-Strukturen sichtbar.

Alle 13 hier vorgestellten Gleichungen funktionieren auf die gleiche Weise:

Jeder der Gleichungen kann eindeutig eine Teiler-Restklasse von 4 Repräsentanten modulo 24 zugeordnet werden. Diese ist jeweils durch Multiplikation geschlossen.

Alle gelösten Werte P sind entweder das 1-, 2-, 3- oder 6-fache eines Teilers der Teiler-Restklasse oder das Vielfache eines Quadrates.

Umgekehrt kann jedes Vielfache aller Elemente der Teiler-Restklassen mit mindestens einer Gleichung gelöst werden, solange keine fremden Teiler involviert sind.

Vier weitere Gleichungen sind nötig, um alle diese Vielfachen einzuschließen. Diese Gleichungen lösen keine Primzahlen sondern nur durch 2 oder 3 Teilbare Werte P und sind deshalb hier nicht angeführt.

Gibt es Lösungen, dann kann immer mindestens ein fremder quadratischer Teiler involviert sein. Fremde Teiler können nur im Quadrat Teil einer Lösung sein.

Gibt es keine Lösung, obwohl P modulo 24 gelöst werden kann, dann ist mindestens ein fremder Teiler mit ungeradem Exponenten involviert.

In der Regel stimmt die Anzahl der Lösungen mit der Anzahl der möglichen Darstellungen von P als m * n überein. Aber es gibt Ausnahmen:

• Die Primfaktoren 2 oder 3 von P (immer ausschließen)
• Fremde Teiler mit geradem Exponenten (diese erzeugen keine Lösung sondern skalieren nur die bestehenden Lösungen)
• Fremde Teiler mit ungeradem Exponenten (keine Lösung)

Nur in diesen drei Fällen gibt es für einen Wert P unterschiedlich viele Lösungen für die geeignete Gleichung und für m * n.

Herleitung der Gleichungen

Hinweis

Die folgende Herleitung ist keine allgemein anerkannte mathematische Herleitung. Sie beschreibt meine eigene Sichtweise, die aus umfangreichen numerischen Untersuchungen und dem Vergleich der 13 Gleichungen entstanden ist.

Von x² – y² zu ax² – by²

Durch 2 oder 3 Teilbare Werte P sind auch hier von der Regel ausgenommen,

Mit x² – y² = (x + y) * (x – y) berechnet man Durchschnitt (x) und Abstand zum Durchschnitt (y) zweier Teiler, die einen geraden Abstand zueinander haben.

Mit a und b aus ax² – by² = P verschiebt man x² und y² so, dass nur bestimmte Kombinationen von zwei Teilern zu einer ganzzahligen Lösung führen (vergl. die Restklassen).

a^0,5x und b^0,5y, also Durchschnitt und Abstand zum Durchschnitt sind dann meistens keine ganzen Zahlen mehr, sondern bestimmte Dezimalzahlen (a bzw. b ist 1, 2, 3 oder 6).

Eine Lösung gibt also keinen Hinweis auf den ganzzahligen Teiler. Ausnahme: ggT (x, y) größer als 1 in einigen Lösungen.

Erhalten bleibt nach der Umformung nur die Anzahl der Lösungen.

a und b ändern die algebraische Darstellung der Lösungen, aber nicht die zugrunde liegende Teiler-Struktur.

Kleinstes erlaubtes Verhältnis

Bei x² – y² = P ist für P * 1 = P:   

x = 0,5P + 0,5

und y = 0,5P – 0,5.

Also ist x – 1 = y.

Bsp.: (x + y) * (x – y) = 7;

x = 3,5 + 0,5 = 4; y = 3,5 – 0,5 = 3

(4 + 3) * (4 – 3) = 7

Auch das Verhältnis bei ax² – by² = P muss begrenzt werden, damit es zu den ganzzahligen Teilern passt, bei 3 : 1 : 2 oder  3 : 2 : 1 oder 2 : 1 : 1. Das entspricht jeweils der kleinsten Lösung für eine der negativen Gleichungen mit x und y = 1. Bei den anderen Gleichungen wird das Verhältnis erst mit etwas größeren x und y erreicht. Der Suchraum ist hier viel kleiner als bei x² – y².

ax² + by² als Nebeneffekt

ax² + by² = P funktioniert quasi als Nebeneffekt von ax² – by² = P. Man sucht so gesehen ein Verhältnis von drei ganzen Zahlen unter bestimmten Bedingungen (Vorgegeben sind a und b). In diesem Verhältnis kann P auch die größte Zahl sein. Z.B.:

P – 3x² = y² (das entspricht 3x² + y² = P)

oder 3x² – y² = P

oder x² – 3y² = P.

Vergl. die drei nebeneinander liegenden Gleichungen und Tabellen (am besten im nächsten Abschnitt)

Gemeinsamkeiten von x² – y² und den 13 Gleichungen

Die in den 13 Gleichungen verwendeten Werte für die Koeffizienten a und b = 1, 2, 3 oder 6 verändern die Teiler-Struktur nicht. Sie stellen sie nur anders dar. Das zeigen umfangreichte Untersuchungen.

Folgende Gemeinsamkeiten und Unterschiede stützen diese Vermutung:

Die Primfaktorzerlegung entscheidet bei den 13 Gleichungen, ob überhaupt Lösungen existieren. Die Anzahl der Lösungen wird dann durch die Struktur der Faktorenpaare (Teiler-Restklassen) bestimmt.

Das ist bei x² – y² nicht anders, nur dass hier mit (x + y) * (x -y) jede Lösung eindeutig einem Faktorenpaar zugeordnet werden kann.

Enthält bei x² – y² die Primfaktorzerlegung 2¹, dann gibt es keine Lösung.

Bei den 13 Gleichungen gibt es keine Lösung wenn die Primfaktorzerlegung einen fremden Teiler mit ungeradem Exponenten enthält.

Für jede der 14 Gleichungen gibt es einen natürlichen Suchraum, in dem jedes zulässige Teiler-Paar höchstens einer ganzzahligen Lösung entspricht.

Die kleinste ganzzahlige Lösung legt den Rand des Suchraums fest. Innerhalb dieses Bereichs können die Verhältnisse x : y beliebig variieren, solange sie weiterhin zu ganzzahligen Lösungen der Gleichung führen.

Da die Koeffizienten a und b das kleinste zulässige Verhältnis von x und y verändern, wächst ax² – by² entlang des Suchbereichs mit einer anderen Geschwindigkeit als bei x² – y². Dadurch verschiebt sich die Verteilung der Lösungen.

Bei x² – y² sind die Lösungen nach Größe von x und y geordnet. Je größer x und y werden, desto langsamer nähern diese sich an.

Bei ax² – by² sind die Lösungen im gesamtem Suchraum unregelmäßig verteilt, Der Suchraum ist im Verhältnis zu P viel kleiner.

Bei x² – y² ist die Faktorisierung (x + y) * (x -y) so einfach, dass die Abstände im Vordergrund stehen.

Bei den 13 Gleichungen gibt es keine entsprechende Faktorisierung. Stattdessen wird die selbe Struktur nur über die Teiler-Restklassen sichtbar. Die 13 Gleichungen benutzen die Größen Abstand und Durchschnitt vermutlich gar nicht. Sie arbeiten nur mit der Mitgliedschaft in einer Klasse.

Weil x und y nicht mehr nach Abstand und Durchschnitt getrennt sind, muss ax² nicht mehr zwangsweise gleich oder größer sein als P. Auch y größer x ist möglich. Darum funktionieren auch positive Gleichungen.

Werte P mit den Primfaktoren 2 und 3 sind Sonderfälle. Die Anzahl der Lösungen ist für gerade und durch 3 teilbare Zahlen oftmals gleich manchmal größer und niemals kleiner, als für P. Wenn z.B. die Anzahl für 4 P größer ist, entspricht die Anzahl bei 16P, 64P… jeweils der Anzahl bei 4P. Warum es manchmal mehr Lösungen gibt, habe ich noch nicht genauer untersucht. 2n und 3n bilden vermutlich nur die Skalierungsfaktoren.

Fazit

Die Art, wie eine Lösung entsteht, ändert sich nicht. Was sich ändert ist nur, wie viele Quadrate addiert oder subtrahiert werden müssen, um denselben Wert P zu erhalten.

Die Mechanik – ganze Zahlen x und y zu finden, die eine Quadratische Gleichung erfüllen – bleibt dieselbe. a und b verändern nur die Gewichtung der Quadrate.

Ob zwischen einem einzelnen Faktorenpaar und einer konkreten Lösung eine direkte Verbindung besteht oder ob lediglich die Anzahl der Faktorenpaare relevant ist, lässt sich vermutlich erst durch einen Beweis über die Summen und Differenzen von Quadraten klären.

Die nächsten Abschnitte sind wieder Fakten.

Mit modulo 120 durch fünf teilbare Werte P anzeigen

Um alle durch 5 teilbaren Werte P auszuschließen, wird mit P modulo 120 gerechnet. Jede Kombination von x in einer Zeile und y in einer Spalte ergibt den gleichen Wert P modulo 120. x gilt jeweils für alle Tabellen nebeneinander. modulo n für x und y steht jeweils darüber.

Für jedes der 8 P modulo 24 gibt es 5 P modulo 120, diese sind jeweils gemeinsam in einem 3*3-Kästchen farbig markiert. Die Positionen der durch 5 teilbaren Werte P (grau markiert) zeigen deutlich, ob 5 zur Teiler-Restklasse gehört. Vergl. die dazugehörenden x und y in den Tabellen (gemeinsame Teiler).

In einigen Gleichungen sind x und y vertauscht um Platz zu sparen und um folgendes zu zeigen: Nimm einen Wert P aus der Tabelle x² – 3y² und addiere ihn zum P aus 3y² – x² an der gleichen Position. Die Summe ist 120. Die beiden negativen Gleichungen erzeugen jeweils entgegengesetzte Restklassen für P.

Vergl. auch die zugehörigen Teiler-Restklassen und grünen Markierungen bei den Tabellen mod 24.

Varianten der 13 Gleichungen

Grundsätzlich ist bei allen Gleichungen a bzw. b = 1, 2, 3 oder 6. Mit anderen a oder b (z.B. 5) ließe sich P nicht mehr auf mod 24 eingrenzen. Die Gleichung wäre für die Primzahlsuche unbrauchbar.

Die Umformung einer Gleichung ist nur dann zulässig, wenn sich x bzw. y auf bestimmte Moduli eingrenzen lassen. Bsp.: Statt

x² + 2y² = 1 mod 24

kann man

x² + 72y² = 1 mod 24

schreiben, weil y nur ein Vielfaches von 6 sein darf.

2 * 6² = 72 * 1²

y kann dann nicht mehr nur Vielfache von 6 sondern jeden ganze Zahl annehmen.

Alle erlaubten Umformungen

Die Zahl im Kästchen zeigt, welche Gleichung jeweils umgeformt wurde.

Atkin verwendet x² + 4y². Das ist nur dann ein Vorteil, wenn x und y nicht beschränkt sind, wie bei der Anleitung auf Wikipedia.

Anm.: Weil hier für x² + y² = P nur ungerade x verwendet werden, gilt: x <=> y (nicht: x >= y wie bei der Tabelle mod 24, wo ungerade x mit geraden y und gerade x mit ungeraden y kombiniert sind).

Effizienz der Gleichungen

Grundsätzlich können alle 14 Gleichungen des erweiterten Siebs von Atkin verwendet werden.

Die Tabellen modulo 24 zeigen, dass jede Gleichung zunächst ungefähr gleich viele Werte P erzeugt, da jede Gleichung vier der acht Teiler-Restklassen modulo 24 löst.

Bei positiven Gleichungen der Form

ax² + by² = P

sinkt die Anzahl der berechneten Werte mit wachsendem b. Je größer b ist, desto weniger x/y-Kombinationen müssen laut Tabelle überprüft werden. Die Anzahl der zu prüfenden Werte P ist also bei allen positiven Gleichungen nahezu gleich.

Vergl. in den Tabellen Mod 24 die Anzahl der markierten Lösungen:

1x² + 1y² : 8 von 144 Kombinationen, wobei x größer y

1x² + 2y² : 8 von 144 Kombinationen

1x² + 3y² : 12 von 144 Kombinationen

1x² + 6y² : 24 von 144 Kombinationen

Wobei y jeweils bis (P/b)^0,5 groß wird.

Bei negativen Gleichungen der Form

ax² – by² = P

Ist die Anzahl der zu prüfenden Werte P stark abhängig vom Verhältnis zwischen den berechneten Termen und dem Zielwert P. Je kleiner das Verhältnis um so kleiner ist der Suchraum.

Warum Atkin genau diese drei Gleichungen verwendet

Die Gleichungen

x² + 4y²,

3x² + y²

3x² – y²

scheinen besonders effizient zu sein.

Für diese drei Gleichungen funktioniert auch mod 12, weil 1/13, 5/17, 7/19 und 11/23 mod 24 jeweils mit derselben Gleichung berechnet werden. Sie ergeben mod 12 jeweils den gleichen Rest.

Bei Wikipedia wird modulo 60 verwendet. (5 * 12 = 60). Alle Werte größer 60 sind dann um 60 kleiner als bei mod 120. Vergl. die Tabellen. Dadurch lassen sich die x/y-Kombinationen auf weniger Kombinationen modulo n eingrenzen als bei modulo 120. Insgesamt müssen aber gleich viele Kombinationen gelöst werden.

Mindestens eine negative Gleichung ist notwendig, um alle 8 Restklassen modulo 24 abzudecken. Die Gleichung

3x² – y² = P

besitzt das kleinste Verhältnis zwischen den berechneten Termen und dem Zielwert P.

3x² – y² = P = 1,5 : 0,5 : 1.

Dadurch entstehen insgesamt weniger berechnete Werte P als bei den anderen negativen Gleichungen. Diese Gleichung ist also die effizienteste negative Gleichung.

Die Gleichung

x² + 4y²

erzeugt die Klassen 1, 5, 13 und 17 modulo 24. Da y jede ganze Zahl annehmen kann, entstehen vergleichsweise wenige ungültige Werte P, auch wenn x und y nicht auf bestimmte Werte begrenzt sind.

Die Gleichung

3x² + y²

liefert schlielich die verbleibenden Klassen 7 und 19 mod 24 und ergänzt damit die vollständige Abdeckung aller zulässigen Restklassen modulo 24.

Größere Restklassen für die Werte P

Die folgenden Abschnitte stellen die Werte P in Tabellen mit größeren Restklassen dar. Es zeigt sich jedoch dass diese Darstellungen keine weiterführenden Erkenntnisse über die Teiler liefern.

Leserinnen und Leser die diesen Aspekt überspringen möchten, gelangen hier direkt zu den Optimierungen des Algorithmus.

Aufteilung von x und y für P modulo 288

Will man eine einzelne Zahl P testen, ob sie eine Primzahl ist oder nur Primzahlen erzeugen, die bestimmten Modulo-Resten entsprechen, dann hilft die Aufteilung nach mod 288.

Zählt man alle x bzw. y, die für ein P benötigt werden und vergleicht sie mit dem dazugehörenden Modulo, dann kommt man auf 1 von 2 bis 1 von 18 x bzw. y, die zu testen sind. Die Gleichungen sind also unterschiedlich effizient.

Die Tabellen sind hier aber nicht angeführt um einen Primzahltest daraus zu erstellen, sondern sie dienen der Veranschaulichung, wie sich eine größere Restkasse für P auf die Restklassen von x und y auswirkt.

Modulo 288 ist ein Kompromiss für die bessere Vergleichbarkeit der Tabellen, der die größten Restklassen für alle P erzeugt, bevor sich x und y nur noch wiederholen. Für einige x, y oder P funktionieren kleinere Restklassen genauso gut.

Für jedes der 8 P modulo 24 gibt es 12 P modulo 288. Anders als bei modulo 120 kommen hier alle 12 P jeweils gleich oft vor. Das jeweils kleinste der 12 P ist farblich hervorgehoben. Alle P modulo 288 können theoretisch eine Primzahl sein. Ausnahme: In den beiden grauen Bereichen.

Auch hier entspricht x den Zeilenüberschriften und y den Spaltenüberschriften. In einigen Gleichungen sind x und y vertauscht, damit alle Tabellen auf eine Seite passen. Alles ist weitestgehend komprimiert. Es ist auch kein Platz mehr für das „+“ in positiven Gleichungen.

Drei Tabellen sind mit einer zweiten Tabelle verbunden und sind als eine Tabelle zu werten. Für ein P müssen also alle x bzw. y in beiden Tabellen gesucht werden (Es sind ungerade x mit geraden y und gerade x mit ungeraden y angegeben, wenn a und b ungerade sind).

Auch x² + 2y² ist auf zwei Tabellen aufgeteilt, diese können aber getrennt berechnet werden, weil es keine Überschneidung der Werte P gibt.

Was sagen die Tabellen aus?

Meine Vermutung war, dass größere Tabellen eine genauere Auskunft über das gelöste Teiler-Paar geben. Diese Vermutung hat sich nicht bestätigt.

Gibt es mehrere Lösungen für den selben Wert P dann kann jede Lösung aus verschiedenen Restklassen für x und y kommen, die den selben Wert P erzeugen.

Die Aufteilung nach x und y sagt daher nur aus, mit welchen Restklassen für x/y-Kombinationen ein Wert P modulo 288 überhaupt erzeugt werden kann.

Es gibt bei den 13 Gleichungen viele Werte P, die keine Lösung haben, aber in der selben Restklasse liegen.

Alle Tabellen sind daher weniger eine Liste von Lösungen sondern eher eine Karte der möglichen und unmöglichen Kombinationen.

Anwendungsbeispiel

Mersenne-Zahlen (2^k – 1) mit ungeradem k haben mit der Gleichung 2x² – y² immer eine Lösung für Primzahlen mit y = 1. Man muss also nur eine weitere Lösung finden, um auszuschließen, dass es sich um eine Mersenne-Primzahl handelt. Ist die Zahl tatsächlich eine Primzahl dann rechnet man aber je nach Größe der Zahl sehr lange.

x² – y² modulo 1728

Mit x² – y² = (x + y) * (x – y) berechnet man Durchschnitt (x) und Abstand zum Durchschnitt (y) zweier ganzzahliger Teiler (vgl. Herleitung der Gleichungen). Das ist aber nur für Teiler sinnvoll, die größer als die halbe Wurzel von P sind.

 Bsp.: (x² – P)^0,5 = y: 

(125² – 10 000)^0,5 = 75.   

(x + y) * (x – y) = P:   

200 * 50 = 10 000.

x ist also genau 1,25P^0,5, wenn der kleinere Teiler genau der halben Wurzel von P entspricht. Je kleiner die Teiler werden, je größer also x und y werden, desto langsamer nähern sich x und y einander an. Die Kurve wird also immer flacher. x geht bis 0,5P.

Anm.: Im Vergleich dazu wird x bei den 13 Gleichungen zwischen P^0,5 und (3P^0,5) groß, je nach Gleichung. Der Suchraum ist also viel kleiner. Es gibt keine Kurve, sondern die Lösungen sind unregelmäßig im gesamten Suchraum verteilt.

Hier wird nach mod 1728 sortiert. Für jedes der 8 P mod 24 gibt es 72 P mod 1728. Jedes der 72 P kommt viermal vor.

Auch hier sind in den unteren Gleichungen x und y vertauscht. Was oben der Durchschnitt ist, das ist unten der Abstand und umgekehrt.

Man muss nur 1 von 12 bis 1 von 54 x bzw. y testen. Die Gleichung ist also durchaus effizient für Teiler nahe der Wurzel von P, wenn man x bzw. y beschränkt.

Dass die Restklassen hier so viel feiner aufgeteilt sind, liegt daran, dass die Regelmäßigkeit nicht innerhalb einer Teiler-Restklasse besteht, sondern im Abstand der beiden Faktoren, die das selbe P ergeben, wie die Tabelle bei „Aufteilung der Abstände nach P“ weiter oben zeigt.

Für diese Tabellen lassen sich x und y sehr einfach sortieren

Schreibe alle Zahlen = 1 und 5 mod 6 bis 863 in einer Spalte untereinander. Berechne jeweils daneben das Quadrat.

Berechne jeweils daneben für das Quadrat mod 16, mod 9, mod 64 und mod 27 und sortiere nach diesen Spalten in dieser Reihenfolge. Die erste Spalte ergibt die sortierten Reste modulo 864.

Verfahre ebenso mit den Zahlen:

0 mod 6 bis 138 (Reste mod 144)   

3 mod 6 bis 285 (Reste mod 288)   

4, 8 mod 12 bis 212 (Reste mod 216)    

2, 10 mod 12 bis 430 (Reste mod 432)

Die Tabellen sind nach vielen Teilern von 1728 sortiert. Man kann anstatt modulo 1728 jeden Teiler von 1728 einsetzen, die Tabellen bleiben weitestgehend sortiert.(1728 = 2⁶ * 3³),

Für Tabellen mit durch 2 oder 3 teilbaren Zahlen werden die selben fünf sortierten Restklassen anders kombiniert. Welche Restkassen kombiniert werden müssen, das zeigt die Tabelle modulo 24.

Bei den 13 Tabellen funktioniert das mit modulo 24 auch. Mit größeren Restklassen für P müssen die Größen der Restklassen von x und y vermutlich angepasst werden. Das habe ich nicht getestet.

Anm.: Wenn man sich die Gleichung bei der Tabelle anschaut, dann sieht man, wie man mit nur einer Tabelle alle Gleichungen lösen kann: Man berechnet in der Tabelle ax² + by² mit absoluten Bezügen zu a und b. Dann setzt man für b positive oder negative Werte ein.

Für die schon mehrmals erwähnte Vertauschung von x und y vertauscht man nur die Vorzeichen von a und b.

Bsp.: 1x² + (-3)y² wird vertauscht zu -1x² + 3y².

Restklassen

Die Restklassen entstehen dadurch, dass man zwar Quadrate addiert oder subtrahiert aber nach Wurzeln sortiert.

Alle x in einer Zeile und y in einer Spalte (also die feinste Aufteilung für ein einzelnes P) sind von oben und von unten gleich. Sie können zum zugehörigen Modulus addiert oder von diesem subtrahiert werden.

Bsp.: Eine Restklasse modulo 12 hat die Repräsentanten 1, 5, 7, 11. Die Summe der äußeren Werte und der inneren Werte ist immer 12. (1 + 11 oder 5 + 7).

Der Modulus minus x/y ergibt ein anderes x/y.

Bsp.: Von modulo 12 subtrahiert ergeben sich die selben vier Werte:

12 – 1 = 11

12 – 5= 7

12 – 7 = 5

12 – 11 = 1

Ausnahmen nur bei null mod 6. Hier gibt es oft nur einen Rest, oder wie bei den Tabellen modulo 1728 die Reste null und 72 modulo 144.

Der größte Modulus für x und y ist jeweils höchstens halb so groß, wie der Modulus für P.

Zwei Bilder zum Abschluss

Ich habe zwei Bilder in meinem Archiv gefunden und finde sie passen hier zum Abschluss ganz gut.

Bild 1

Man sieht im ersten Bild die 14 Gleichungen als Detailbilder mit x und y aufsteigend von 0 bis 287, also unsortiert und P modulo 288.

Die Graustufen zeigen die Größe der berechneten Werte P von weiß = null bis schwarz = 287. In Bunt sieht man jeweils die bekannten 8 kleinsten P.

Wenn man vergleicht wie oft sich das Muster Wiederholt, dann erkennt man, welche a und b benutzt wurden. Bsp.: Erste Reihe: 1x² und 3y², zweite Reihe 2x² und 3y² usw.

Die positive Gleichung steht jeweils ganz links.

In der Reihe rechts sind x und y in der Gleichung vertauscht, daher sind die mittleren und rechten Bilder annähernd gleich. Ein Feld an der jeweils gleichen Position zeigt den gegenteiligen Rest modulo 288 und daher die entgegengesetzte Graustufe.

Es entsteht also ein optisches Negativ. Das erkennt man gut entlang der Linie, an der die beiden Detailbilder sich treffen.

Das letzte Bild zeigt x² – y². Man könnte auch hier mit y² – x² ein optisches Negativ erzeugen.

Die Tabellen erzeugen zwar auch negative Reste, diese werden aber durch den Modulus angepasst. Die erlaubten Verhältnisse müssen daher nicht beachtet werden.

Vergrößert man die Bilder, dann erkennt man Interferenzmuster.

Bild 2

Mit modulo 1728 werden noch mehr Details sichtbar. Hier ein Ausschnitt von 2x² + 3y².

Das Muster wiederholt sich waagerecht sechs mal, und senkrecht vier mal, wenn man x und y von null bis 1727 laufen lässt.