Zum Inhalt springen

Pseudoprimzahlen: Formelsammlung

Aus Wikibooks


Anhänge
Geschichte
Mathematiker
Tabellen
Formelsammlung
Irrtümer zu den Pseudoprimzahlen
Glossar
Quellen


Formelsammlung

Um die Pseudoprimzahlen zu verstehen, muss man ein paar Dinge wissen.

Der kleine Fermatsche Satz

[Bearbeiten]

Für jede Primzahlund jede natürliche Zahl gilt

  • .

Für jede Primzahl und jede zu teilerfremde natürliche Zahl gilt

  • .

Kongruenz

[Bearbeiten]

Zwei Zahlen, die bei Division durch den gleichen Divisor den gleichen Modulo zurückliefern, sind zueinander kongruent. Bei Addition von ganzzahligen Vielfachen des Divisors bleibt die Kongruenz erhalten:

  • .

Eulersche φ-Funktion

[Bearbeiten]

Die Eulersche φ-Funktion gibt zu jeder natürlichen Zahl die Anzahl der zu teilerfremden Zahlen, die nicht größer als sind, an. Da die Eulersche φ-Funktion auch ein Vielfaches der Carmichael-Funktion ist, gilt für jedes zu teilerfremde .

Die Eulersche φ-Funktion wird wie folgt berechnet:

Satz von Euler

[Bearbeiten]

Carmichael-Funktion

[Bearbeiten]

Der Funktionswert der Carmichael-Funktion einer natürlichen Zahl ist die kleinste natürliche Zahl, mit der für jede zu teilerfremde Basis mit gilt: .

Die Carmichael-Funktion wird wie folgt berechnet:

Die allgemeinen Lucas-Folgen

[Bearbeiten]

Die beiden allgemeinen Lucas-Folgen und , deren jeweilige einzelne Glieder

und

sind, lassen sich aus der quadratischen Gleichung

ableiten, deren beide Lösungen

und sind.

Zwischen den Allgemeinen Lucas-Folgen und den Primzahlen gibt es einen Zusammenhang: Wenn die natürliche Zahl eine Primzahl ist, dann teilt sie für alle Folgen, deren und sind.

Wenn eine zusammengesetze Zahl ist, und trotzdem teilt, ist eine Pseudoprimzahl zu .

Beziehungen zwischen den Folgegliedern

[Bearbeiten]

Einige Beziehungen zwischen den Folgegliedern der allgemeinen Lucas-Folgen, der Fibonacci-Zahlen und der Lucas-Zahlen :[1]

Quellen

[Bearbeiten]
  1. en:w:Lucas_sequence#Other_relations