Pseudoprimzahlen: Formelsammlung


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 Primzahl und 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]

 
  1. en:w:Lucas_sequence#Other_relations