________________________________________________________________________________
Inhalt....: Konstruktion von Primzahlen
Kategorie.: Unterrichtsmaterial
Mathematik: Zahlentheorie
MuPAD.....: 3.1.0
Datum.....: 2006-10-24
Autoren...: August Barkhausen <abarkhausen@gmx.de>
Funktionen: for, if, print, Typeset, min, numlib::primedivisors, testeq, matrix
Funktionen: map, testeq
________________________________________________________________________________
Konstruktion von Primzahlen nach einem
Beweis des Satzes von Euklid über die
Anzahl von Primzahlen
Im folgenden wird ein Algorithmus zur Berechnung von Primzahlen durchgeführt, der
auf die in dem Buch "Elementare Zahlentheorie" von Remmert und Ulrich, 2. Auflage
Birkhäuser1995 dargestellte Version des Satzes von Euklid zurückgeht. Der Algorith-
mus wird zunächst heuristisch und dann mit einer Programmierlösung durchgeführt.
In diesem Zusammenhang wird darüber hinaus nachgewiesen, dass die gefundenen
Zahlen tatsächlich Primzahlen sind.
Im Rahmen der heuristischen Vorarbeit wird darüber hinaus mit gezeigt, dass die
gefundenen Primzahlen paarweise voneinander verschieden sind.
Am Ende des Notebooks finden sich Anregungen für Folgeaufgaben.
Als mathematischer Hintergrund werden ausreichende Kenntnisse über Primzahlen
und Primfaktorzerlegungen sowie Grundkenntnisse der Logik vorausgesetzt. Aus
dem Bereich der EDV werden Programmierkenntnisse benötigt. Schließlich werden
zur Simulation von Tabellen Matrizen benutzt. Wenn keine mathematischen Kennt-
nisse über Matrizen bzw. Vektoren vorhanden sind, sollte zumindest erklärt werden,
wie man Matrizen in MuPAD erstellen und zur Datenein- und ausgabe nutzen kann.
Aus der Zahlentheorie (siehe zum Beispiel Remmert, Ulrich: "Elementare Zahlentheorie",
2. Auflage Birkhäuser 1995 S. 25 ff) ist bekannt, dass es unendlich viele Primzahlen gibt.
Genauer gilt: Sind die Primzahlen q1, q2, ... ,qn bekannt, so ist der kleinste
Teiler t > 1 der natürlichen Zahl a = (q1*q2*...*qn + 1) eine Primzahl, die von den
bisherigen Primzahlen q1, q2, ....., qn verschieden ist.
Es soll (sollen) in diesem Notebook
1) schrittweise beginnend mit 2 einzelne Primzahlen mit dem angegebenen Algorithmus
konstruiert werden.
2) nachgewiesen werden, dass die so konstruierten Zahlen tatsächlich Primzahlen sind.
3) die Aussage, dass die so konstruierte Primzahl von den Primzahlen q1, q2, ..... qn
paarweise verschieden ist, außerhalb der Programmierlösung nachgewiesen werden.
4) in einer Programmierlösung Primzahlen nach dem angegebenen Algorithmus konstruiert
werden.
5) nachgewiesen werden, dass die in der Programmierlösung ermittelten Zahlen tatsächlich
Primzahlen sind.
6) überprüft werden, ob mit dem Algorithmus alle Primzahlen ermittelt werden.
Heuristische Lösung
Zunächst werden iterativ ausgehend von der Primzahl 2 zwei Primzahlen in Einzelschritten
bestimmt, um den Algorithmus zu überprüfen. An dieser Stelle erscheint eine Prüfung durch
MuPAD, ob die gefundenen Zahlen Primzahlen sind, noch überflüssig, da diese Eigenschaft
bei den gefundenen Zahlen offensichtlich ist. Andererseits ist die Eigenschaft "Primzahl"
bei großen Zahlen nicht mehr offensichtlich. Insofern wird hier die Prüfung zur Erklärung
und Kontrolle des Algorithmus doch durchgeführt.
Um zu erkennen, ob eine Zahl Primzahl ist, lässt man zweckmäßigerweise durch MuPAD
die Primfaktorzerlegung durchführen. Eine Probe, ob eine natürliche Zahl a Primzahl ist, ist
mit MuPAD ist wie folgt möglich:
Zunächst wird die Primfaktorzerlegung der Zahl a mit dem Befehl primedivisors durchgeführt.
Dann prüft man, ob das erste Element der Primfaktorzerlegung von a identisch mit der der
Zahl a ist.
Sind beide Zahlen identisch, kann es keine weiteren Elemente der Primfaktorzerlegung geben
und die gefundenen Zahl ist tatsächlich eine Primzahl. Anderenfalls ist a keine Primzahl.
Der Algorithmus zur Bestimmung von Primzahlen weicht in einem Punkt von der oben
angegebenen Theorie ab. Entsprechend der Theorie ist der kleinste von 1 verschiedene
Teiler der Zahl a die neue Primzahl. In MuPAD entspricht dies dem Befehl
"numlib::divisors[2]", da MuPAD die Teiler von links nach rechts in wachsender Größe
anordnet.
In diesem Notebook wird abweichend davon der kleinste Primteiler benutzt. Da der kleinste
Primteiler allerdings mit dem kleinsten von 1 verschiedenem Teiler entspricht, ist es möglich,
auch mit diesem Wert zu rechnen. In MuPAD spricht man den kleinsten Primteiler mit
dem Befehl "numlib::primdivisors[1]" an.
Wir beginnen mit der ersten Primzahl 2. (Die Zahl 1 ist keine Primzahl)
primzahl1:=2
Die zweite potenzielle Primzahl wird konstruiert.
primzahl2:=min(numlib::primedivisors(primzahl1+1))
Es wird überprüft, ob die gefundene Zahl tatsächlich Primzahl ist. Bei der Antwort
True handelt es sich um eine Primzahl, bei der Antwort false liegt keine Primzahl vor.
testeq(numlib::primedivisors(primzahl1+1)[1]=primzahl2)
Es wird nun überprüft, ob die gefundene neue Primzahl von den bisher bekannten
Primzahlen verschieden ist. Bei der Antwort false sind die Zahlen des überprüften
Zahlenpaares voneinander verschieden.
testeq(primzahl1=primzahl2)
Die ersten beiden Primzahlen sind somit voneinander verschieden.
Die dritte potenzielle Primzahl wird konstruiert.
primzahl3:=
min(numlib::primedivisors(primzahl1*primzahl2+1))
Es wird nachgewiesen, dass die gefundene Zahl eine Primzahl ist.
testeq
(numlib::primedivisors(primzahl1*primzahl2+1)[1]=primzahl3)
Es wird nachgewiesen, dass die gefundene Primzahl von den beiden bisher bekannten
Primzahlen verschieden ist.
testeq(primzahl1=primzahl3)
testeq(primzahl2=primzahl3)
Bereits mit diesem Iterationsschritt wird klar, dass der benutzte Algorithmus nicht alle
Primzahlen liefert, da die Primzahl 5 fehlt.
Im folgenden soll eine Programmierlösung für eine größere Anzahl von Primzahlen
erfolgen. Zunächst soll nur der konstruktive Aspekt berücksichtigt werden.
Erster Schritt: Die Anzahl der Iterationsschritte und der Startwert für die Laufvariable
werden festgelegt.
Ende:=10:
n:=1:
Zweiter Schritt: Die Daten sollen in einen Vektor der Dimension Ende geschrieben
werden.
Die erste Komponente wird mit 2 als erster Primzahl vorinitialisiert.
Möchte man den Algorithmus mit einer anderen Zahl beginnen, ist die zwei
entsprechend zu ersetzen.
Die anderen Elemente der Matrix werden automatisch mit 0 initialisiert und später
überschrieben.
Durch den Doppelpunkt wird die Ausgabe unterdrückt.
Primzahlmatrix:=matrix(Ende,1,[2]):
Die Variable Primzahlprodukt ist eine Hilfsvariable, da die Produkte im Algorithmus
benötigt werden. Diese Variable wird mit dem Startprimzahl für den Algorithmus
vorinitialisiert.
Primzahlprodukt:=Primzahlmatrix[1]:
Nun werden die Primzahlen berechnet und in die Primzahlmatrix geschrieben.
while n < Ende do
Primzahlmatrix[n+1]
:=min(numlib::primedivisors(Primzahlprodukt+1));
Primzahlprodukt
:=Primzahlprodukt*Primzahlmatrix[n+1];
n:=n+1;
end_while:
Die Primzahlmatrix wird ausgegeben.
Primzahlmatrix
Offensichtlich stimmen die ersten drei ausgegebenen Elemente der Matrix mit den oben
bestimmten Primzahlen überein. Die weiteren Elemente lassen sich sowohl durch
manuelle Berechnungen, als auch wie oben beschrieben mit MuPAD berechnen.
Man stellt durch Ablesen fest:
1) Die Zahlen sind paarweise voneinander verschieden.
2) Es werden nicht alle Primzahlen erfasst. Hier fehlt beispielsweise die Primzahl 11.
3) Wider Erwarten ist die Folge der Primzahlen nicht monoton steigend.
Die ersten sieben Ergebnisse der Iteration sind offensichtlich Primzahlen. Bei größeren
Zahlen ist jedoch nicht ohne weiteres erkennbar, dass es sich eine um eine Primzahl
ergeben hat.
Für den Nachweis, dass die berechneten Zahlen tatsächlich Primzahlen sind, werden
die Elemente der Primzahlmatrix ausgelesen und einzeln entsprechend dem weiter oben
angegebenem Algorithmus mit dem ersten Element der Primzahlzerlegung verglichen.
Die Ergebnisse der jeweiligen Proben werden in eine als Testmatrix bezeichnete Matrix
eingelesen. Die Elemente der Matrix sind mit 0 vorinitialisiert und werden dann bei
jedem Iterationsschritt überschrieben.
Die hier durchgeführte Entkopplung der Iterationen hat den Vorteil, dass die Algorithmen
unabhängig voneinander entwickelt und getestet werden können. Gemeinsame Daten
aller Iterationen sind die Variable Ende, die die Anzahl der Iterationen bestimmt,
die Primzahlmatrix und die Testmatrix.
Testmatrix:=matrix(Ende,1):
delete(m):
An dieser Stelle sollte zunächst die Iteration bei 1 begonnen werden. Fehlermeldungen
von MuPAD erzwangen die Besetzung der ersten Komponente der Testmatrix außerhalb
der Schleife und die Benutzung der Variablen Zwischenspeicher.
Zwischenspeicher:=
testeq(numlib::primedivisors(Primzahlmatrix[1])[1]
=Primzahlmatrix[1]):
Testmatrix[1]:=Zwischenspeicher:
for m from 2 to Ende do
Testmatrix[m]:=testeq(numlib::primedivisors
(Primzahlmatrix[m])[1]=Primzahlmatrix[m]);
end_for:
Testmatrix
An dieser Stelle sind bis auf die angegebene Lücke bei der Überprüfung auf Ungleichheit
der Primzahlen die mathematischen Inhalte im Rahmen des Algorithmus abgearbeitet.
Allerdings ist die Ausgabe der Testmatrix ohne gemeinsame Darstellung mit der zuge-
hörigen Primzahl nicht optimal. Angebrachter erscheint es, die Primzahlen mit den
Ergebnissen der Überprüfung, ob es sich um Primzahlen handelt, gemeinsam darzustellen.
Um Doppelausgaben der Ergebnisse zu vermeiden, kann es sinnvoll sein, die uner-
wünschten Ausgaben durch einen Doppelpunkt hinter dem jeweiligen Befehl zu
unterdrücken.
Die gemeinsame Darstellung in einer einheitlichen Matrix mit geeigneter Dokumentation wird
im folgenden durchgeführt. Dabei wird in einem ersten Schritt das Ergebnis der Testmatrix
in eine besser lesbare Aussage "ist Primzahl" beim Ergebnis TRUE bzw. "ist keine Primzahl"
beim Ergebnis FALSE übersetzt.
Der folgende Teil der Notebooks benutzt anspruchsvollere Funktionen von MuPAD als in
den vorherigen Teilen, dient aber andererseits zur Verbesserung der Dokumentation und kann
bei einer ersten Durchsicht übersprungen werden.
Zunächst wird der Startwert der Laufvariablen zurückgesetzt. Dann wird die Ausgabematrix
definiert. Alle Elemente dieser Matrix sind mit 0 vorinitialisiert und werden dann in der
Durchführung der Iteration mit den Werten aus den oben angegebenen Matrizen über
schrieben.Es werden zwei Ausgabevarianten dargestellt: Erst wird die Funktion print benutzt
und anschließend wird die Ausgabematrix ausgegeben. Auch hier lassen sich unerwünschte
Ausgaben durch Doppelpunkte hinter den Befehlen unterdrücken.
delete k:
Ausgabe:= matrix(Ende, 2):
for k from 1 to Ende do
if Testmatrix[k] = TRUE
then
print(Typeset,
"Primzahl Nr. ".expr2text(k).": ".Primzahlmatrix[k]);
Ausgabe[k,1]:= "Primzahl Nr. ".expr2text(k);
Ausgabe[k,2]:= Primzahlmatrix[k];
else
print(Typeset,
"keine Primzahl: ".expr2text(Primzahlmatrix[k]));
Ausgabe[k,1]:= "keine Primzahl: ";
Ausgabe[k,2]:= Primzahlmatrix[k];
end_if;
end_for:
Ausgabe
Eine Auswahl möglicher Anschlussaufgaben:
1) Ein noch offener Punkt in der Programmierlösung ist der Nachweis, dass die gefundenen
Primzahlen paarweise voneinander verschieden sind. Die Programmierlösung kann um
diesen Nachweis ergänzt werden.
2) Es ist unter Umständen lästig, dass der Nachweis, dass die gefundenen Zahlen Primzahlen
sind, für jede Zahl einzeln ausgegeben wird. Es ist möglich, die Ergebnisse der Nachweise
zu einer einzigen Aussage zusammenzufassen.
3) Bei der Benutzung des Algorithmus wurden die beginnend mit 2 die gefundenen Primzahlen
im jeweils nächsten Iterationsschritt benutzt. Es ist möglich, mit anderen Startwerten als 2
zu beginnen und den Algorithmus in der beschriebenen Form durchführen.
Es ist aber auch möglich, sich von der beschriebenen Iteration zu lösen und
mit willkürlich gewählten Produkten von Primzahlen zu experimentieren.
4) Eine interessante Aufgabe ist es, große Primzahlen bzw. Primzahlen mit bestimmten
Eigenschaften zu finden.
Man kann daher die Programmierlösung so ergänzen, dass der Algorithmus Primzahlen
findet, deren Ziffernzahl eine vorgegebene Anzahl von Ziffern überschreitet bzw. mit
dieser Ziffernzahl übereinstimmt. Alternativ ist es auch möglich, sich nur die Anzahl der
Ziffern mit der gewünschten Eigenschaft ausgeben zu lassen.
5) Es kann überprüft werden, welche Auswirkungen auftreten, wenn man im Algorithmus
Zahlen benutzt, die keine Primzahlen sind. Diese Überprüfung ist problemlos außerhalb
der Programmierlösung möglich. Andererseits kann man auch den Startwert der
Programmierlösung so wählen, dass er keine Primzahl ist. In diesem Fall sollte erklärt,
werden, warum alle weiteren Zahlen doch Primzahlen sind.
6) Es kann einen Check eingebaut werden, der bewirkt, dass der Algorithmus nur mit
Primzahlen als Startwert durchlaufen wird.
7) Man kann die Programmierlösung in Form einer Prozedur realisieren.
8) In der vorliegenden Lösung wird die Primzahlnummer fehlerhaft ausgegeben, wenn man
den Algorithmus mit einer Zahl beginnt, die keine Primzahl ist. Der Fehler tritt nicht auf,
wenn der Startwert eine Primzahl ist. Dies teilkorrekte Verhalten sollte verifiziert,
begründet und korrigiert werden.
9) Es ist möglich, die vorliegende Lösung zu verkürzen und optimieren, indem man die aus
didaktischen Gründen getrennt dargestellten Programmierlösungen zu einer
kompakten Lösung zusammenfasst.
10) Schließlich kann man den Algorithmus auf den Befehl "numlib::divisors[2] umstellen.
______________________________________________________________________________
Anmerkung:
1. Darstellungen des gewählten Algorithmus finden sich in vielen Büchern zur Zahlentheorie. Das vorliegende
Notebook bezieht sich auf die Darstellung in Remmert, Ulrich: "Elementare Zahlentheorie", 2. Auflage
Birkhäuser 1995.
2. Lösungen von Programmierproblemen im Rahmen der linearen Algebra und Analysis finden sich in weiteren
Notebooks des gleichen Autors.
3. Weitere Aspekte der Anwendung von MuPAD auf die Zahlentheorie finden sich in zwei Notebooks des
gleichen Autors, die sich mit vollkommenen Zahlen beschäftigen.
4. Weitere Anregungen finden Sie in der Unterrichsmaterialsammlung unter schule.mupad.de. In diesen
Notebooks werden eine Vielzahl unterschiedlichster mathematischer Probleme mit MuPAD Pro gelöst.
______________________________________________________________________________