Dokumentation

Zahlen - Teiler, Vielfache, Primeigenschaften

Promathika stellt einige Routinen zur Untersuchung von Zahleneigenschaften bereit.


Teiler und Vielfache

Größter gemeinsamer Teiler:
Der ggT der Zahlen Z_1 und Z_2 lässt sich mit mithilfe des Befehls ggt(Z_1; Z_2) berechnen. Es ist darauf zu achten, dass die beiden Zahlen durch ein Semikolon voneinander getrennt werden.

Eingabe: ggt(2145; 330)
Ausgabe: 165

Kleinstes gemeinsames Vielfaches:
Das kgV zweier Zahlen lässt sich analog wie der ggt berechnen:

Eingabe: kgv(2145; 330)
Ausgabe: 4290

Primfaktorzerlegung:
Beliebige ganze Zahlen lassen sich mithilfe des Befehls Primfaktorzerlegung(Zahl) in ihre Primfaktoren zerlegen:

Eingabe: primfaktorzerlegung(186340)
Ausgabe: 2^2*5*7*11^3

Promathika wird laufend um weitere Routinen zur Untersuchung der Teiler- und Vielfacheneigenschaften von Zahlen erweitert. Konkret für die nächsten Versionen geplant sind folgende Funktionen:

  • Eine Funktion zur Erstellung von Teilertabellen

Primeigenschaften

Promathika kann beliebig große Zahlen auf deren Primeigenschaften untersuchen und beim Auffinden weiterer Primzahlen helfen. Der hierzu zur Verfügung stehende Befehlssatz wird nun vorgestellt.

Testen, ob eine Zahl prim ist:
Mithilfe der Funktion IstPrim(Zahl) können Sie prüfen, ob die angegebene Zahl prim ist. IstPrim gibt dabei wahr zurück, wenn es sich bei der Zahl um eine Primzahl handelt und falsch, wenn es keine Primzahl ist.

Eingabe: IstPrim(1213)
Ausgabe: wahr

Eingabe: IstPrim(1211)
Ausgabe: falsch

Hinweis: Der von IstPrim verwendete Primzahltest ist deterministisch. Für große Zahlen ist der weiter unten vorgestellte Befehl MillerRabinItera schneller, bei dem es sich um einen probabilistischen Primzahltest handelt.

Primzahlen finden:
Gerade bei großen Zahlen kann das Auffinden von Primzahlen durch Promathika erleichtert werden: Der Befehl PrimDanach(Zahl) gibt die nach Zahl nächst größere Primzahl zurück. Analog dazu erhält man mit dem Befehl PrimDavor(Zahl) die vor Zahl nächst kleinere Primzahl.

Eingabe: PrimDanach(50)
Ausgabe: 53

Eingabe: PrimDavor(1000000000000000000000000000000000000000000000000000)
Ausgabe: 999999999999999999999999999999999999999999999999677

Primzahl-Listen:
Mithilfe des Befehls PrimzahlListe(Von; Bis) kann Promathika Primzahl-Listen zwischen den angegebenen Grenzen erstellen. Beispiel:

Eingabe: PrimzahlListe(1; 30)
Ausgabe: [ 2 3 5 7 11 13 17 19 23 29 ]

Der Miller-Rabin-Primzahltest:
Der Miller-Rabin-Primzahltest ist ein probabilistischer Primzahltest. Er kann von der Konsole aus manuell bedient werden:
Der Befehl MillerRabinPrim(Primkandidat; Zeuge) enthält die Parameter Primkandidat, bei dem es sich um eine ungerade zu testende Zahl handelt, und Zeuge bei dem es sich um eine zufällige Zahl zwischen 1 und Primkandidat-1 handelt. Wenn die Zahl Zeuge nun bezeugt, dass Primkandidat zerlegbar und somit keine Primzahl ist, gibt MillerRabinPrim falsch zurück. Wenn MillerRabinPrim den Wert wahr zurück gibt, hat der Primkandidat den Test bestanden und die Wahrscheinlichkeit, dass es sich dennoch um eine in Faktoren zerlegbare Zahl handelt, schrumpft um den Faktor 0,25.
Der Befehl MillerRabinItera(Primkandidat; Anzahl) führt den Miller-Rabin-Primzahltest automatisiert mit der angegebenen Anzahl an zufällig gewählten Zeugen durch. Besteht der Primkandidat den Test, wird die Zahl 1 zurückgegeben. In diesem Fall ist die Wahrscheinlichkeit, dass es sich dennoch um eine zerlegbare Zahl handelt, nur noch (0,25)^Anzahl. Besteht der Primkandidat den Test nicht, ist er unter Garantie zerlegbar.

Eingabe: MillerRabinPrim(103; 11)
Ausgabe: wahr

Eingabe: MillerRabinItera(999999999999999999999999999999999999999999999999677; 40)
Ausgabe: wahr