Satz von Fermat-Euler

Der Satz von FERMAT-EULER ist einer der wichtigsten Sätze der elementaren Zahlentheorie. Sind a und m teilerfremde natürliche Zahlen, dann gilt:

Beispiel

Es sind die letzten drei Ziffern der Dezimalbruchdarstellung von 9^{9 9} zu ermitteln. Gesucht ist x mit mit Es gilt und nach dem Satz von FERMAT ist Weiter gilt
Daraus folgt Die Dezimaldarstellung von 9⁹⁹ endet mit den Ziffern 289.

Hinweis: Der obige Satz geht für m=p, d.h. auf FERMAT zurück; die allgemeine Form stammt von EULER. Der Satz bildet die Grundlage eines Codierungsverfahrens. Er beinhaltet ein notwendiges Kriterium für die Primzahleigenschaft einer natürlichen Zahl: Ist p eine Primzahl, dann gilt für jede ganze Zahl a mit