Teilerfremde Zahlen zu n vollständig auflisten

Dieser Rechner liefert die vollständige, sortierte Liste und nicht nur den Wert der eulerschen Phi-Funktion. Geben Sie eine positive ganze Zahl ein, um den Ausgangswert, die Anzahl der passenden Zahlen und die Totative selbst zu erhalten. Damit können Sie Aufgaben zur modularen Arithmetik prüfen, reduzierte Restsysteme untersuchen und genau erkennen, welche Werte zur eulerschen Phi-Funktion beitragen.

Was die Totativliste darstellt

Die Totative von n sind genau die ganzen Zahlen von 1 bis n, deren größter gemeinsamer Teiler mit n gleich 1 ist. Haben zwei Zahlen den größten gemeinsamen Teiler 1, heißen sie teilerfremd oder relativ prim. Ein Kandidat wird beispielsweise ausgeschlossen, sobald er irgendeinen Primfaktor mit n teilt, auch wenn er n nicht teilt. Das zurückgegebene Array ist aufsteigend sortiert, da die Kandidaten ab 1 geprüft werden. Die Zahl 1 ist immer enthalten, weil sie zu jeder positiven ganzen Zahl teilerfremd ist. Der Endwert n selbst fehlt normalerweise, denn gcd(n, n) ist n; der Sonderfall n = 1 ergibt die Liste [1]. Die angegebene Anzahl entspricht der Listenlänge und damit der eulerschen Phi-Funktion phi(n). Diese Fähigkeit zeigt die tatsächlichen Elemente. Wenn Sie für eine sehr große ganze Zahl lediglich deren Anzahl benötigen, eignet sich ein reiner Phi-Rechner besser. Der Unterschied ist für die modulare Arithmetik wichtig, denn die Elemente bilden dort das reduzierte Restsystem modulo n.

So funktioniert die Berechnung

Der Rechner prüft n, bevor er eine arithmetische Operation ausführt. Er akzeptiert eine ganze Zahl oder eine als einfache Dezimalzeichenfolge geschriebene Ganzzahl, weist Brüche und nicht numerische Werte zurück und meldet einen Eingabefehler, wenn n kleiner als 1 ist. Außerdem setzt er die veröffentlichte Obergrenze durch, damit auch die Erzeugung eines möglicherweise großen JSON-Arrays im Browser und über die API vorhersehbar bleibt. Nach der Prüfung betrachtet der Algorithmus jede ganze Zahl von 1 bis n. Auf jeden Kandidaten wendet er den euklidischen Algorithmus an: Das Zahlenpaar wird wiederholt durch Divisor und Rest ersetzt, bis der Rest null ist. Der letzte von null verschiedene Divisor ist der größte gemeinsame Teiler. Nur wenn dieser Divisor 1 ist, gelangt der Kandidat ins Ergebnis. Das Verfahren verwendet exakte Ganzzahlarithmetik ohne Näherung, Faktordatenbank, Netzwerkanfrage, Zufall oder Uhrzeit. Daher erzeugt dieselbe Eingabe stets dieselbe sortierte Ausgabe. Die Anzahl wird aus dem fertigen Array abgeleitet und nicht separat berechnet, sodass Liste und angegebene Größe nicht voneinander abweichen können.

Das Ergebnis richtig verwenden

Verwenden Sie die Liste, wenn der nächste Schritt von den einzelnen Restklassen und nicht nur von deren Anzahl abhängt. In der elementaren Zahlentheorie lässt sich damit unmittelbar prüfen, welche Zahlen modulo n invertierbar sind: Jeder aufgeführte Wert besitzt ein multiplikatives Inverses modulo n, jeder ausgelassene Wert dagegen nicht. Im Kryptografieunterricht kann die Ausgabe veranschaulichen, warum ein Multiplikator zum Modul teilerfremd sein muss; sie ist jedoch ein arithmetisches Lernergebnis und kein System zur Schlüsselerzeugung. Sie können die zurückgegebene Anzahl außerdem mit einer manuellen Berechnung der eulerschen Phi-Formel vergleichen, um eine Faktorisierung zu kontrollieren. Beachten Sie, dass Teilerfremdheit eine Beziehung ist und nicht bedeutet, dass jede aufgeführte Zahl prim sein muss. Zusammengesetzte Werte können vorkommen, sofern sie keinen Primfaktor mit n teilen. So kann ein zusammengesetzter Kandidat ein Totativ eines Primzahlmoduls sein. Lesen Sie bei automatisierter Nutzung das Totativ-Array direkt und verwenden Sie die Anzahl als Zusammenfassung. Möchten Sie nur ein einzelnes Zahlenpaar prüfen, vermeidet ein Teilerfremdheitstest den Aufbau der vollständigen Liste.