Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenSamstag, 7. Dezember 2019 

Kleiner Fermatscher Satz


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Der Kleine Fermatsche Satz kurz der Kleine Fermat ist ein Lehrsatz in der Zahlentheorie aufgestellt im 17. Jahrhundert von Pierre de Fermat . Dieser Satz beschreibt eine allgemein gültige Kongruenz :

<math>a^p \equiv a \pmod{p}</math>

wobei a eine ganze Zahl und p eine Primzahl sind. Falls a kein Vielfaches von p ist kann man das Resultat in häufig benutzte Form

<math>a^{p-1} \equiv 1 \pmod{p}</math>

bringen.

Beweis

Der Beweis beruht auf der Tatsache wenn zwei Zahlen a und b zueinander inkongruent (modulo einer festen Zahl n ) sind auch die beiden Produkte x · a und x · b inkongruent modulo n sind für x >0 und ggT( x n )=1. Im folgenden betrachtet man zum einen Menge A aller Reste (mod p ) - also alle natürlichen Zahlen kleiner als p und zum anderen die Menge B die diese Reste multipliziert mit a enthält. Zwei beliege Zahlen aus A sind zueinander inkongruent modulo p . Aus dem oberen Satz folgt dass auch zwei beliebige Zahlen aus B zueinander inkongruent sind. Dadurch ergibt sich das Produkt über allen Zahlen aus A kongruent zum Produkt aller Zahlen aus B ist:

<math>1 \cdot 2 \cdot 3 \cdot \dots (p-1) \equiv (1 \cdot a)\cdot(2 \cdot a)\cdot\dots\cdot \cdot a) \pmod{ p} </math>
 also  
<math>W \equiv W\cdot a^{p-1} \pmod{p} </math>

wobei W das Produkt 1·2·3·...·( p -1) ist. Da es in Restklassenkörpern stets ein multiplikatives Inverses gibt kann man diese Kongruenzgleichung durch W dividieren und man erhält:

<math>a^{p-1} \equiv 1 \pmod{p}</math>

Verallgemeinerung

Man kann den kleinen Fermatschen Satz Satz von Euler verallgemeinern: Für zwei teilerfremde Zahlen n und a gilt:

<math>a^{\varphi (n)} \equiv 1 \pmod{n}</math>
wobei φ( n ) die Eulersche Phi-Funktion bezeichnet. Diese hat als Ergebnis die der Zahlen zwischen 1 und n -1 welche teilerfremd zu n sind. Ist n eine Primzahl so ist φ( n ) = n -1 so dass man Fermats kleinen Satz Spezialfall erhält.

Mit Hilfe des Kleinen Fermatschen Satzes Fermat den Fermatschen Primzahltest .



Bücher zum Thema Kleiner Fermatscher Satz

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Kleiner_Satz_von_Fermat.html">Kleiner Fermatscher Satz </a>