Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenMittwoch, 11. Dezember 2019 

Kleiner Fermat-Satz


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Der kleine Fermat-Satz von Pierre de Fermat entdeckt macht eine Aussage über die von Primzahlen:
Wenn eine natürliche Zahl n eine Primzahl ist dann gilt
<math>2^{n} \equiv 2 \mod n</math> .
Hätte man diese Aussage umdrehen können sagen können das wenn für eine natürliche n gilt:
<math>2^{n} \equiv 2 \mod n</math> .
diese eine Primzahl ist hätte man prima Primzahlengenerator bekommen können. Dem ist aber so.

In Wirklichkeit gibt es auch Nichtprimzahlen die diese Eigenschaft zutrifft: Die Pseudoprimzahlen .

Man kann aber den Satz auf Basen 1 < b < n erweitern. man also sagen kann das bei einem n für alle Basen b mit 1 b < n gilt:

<math>b^{n} \equiv b \mod n</math>
dann muß diese Zahl n eine Primzahl sein.

Dazu muß man nicht alle Basen < b < n durchtesten sondern es das man alle Primzahlen p 1 < < n benutzt.

Der Nachteil an diesem verfahren ist es sehr langsam und aufwendig ist (das auf Primzahlen über die Teilbarkeit ist schneller).

Wie funktioniert der Fermatsche Satz? Wenn eine Zahl immer wieder mit sich multipliziert bekommt man gewisse Zyklen bezüglich der Modulo-Operation:

Beispiel: 7

2 2 mod 7 3 3 mod 7 5 5 mod 7
0 1 1 1 1 1 1
1 2 2 3 3 5 5
2 4 4 9 2 25 4
3 8 1 6 6 20 6
4 2 2 18 4 30 2
5 4 4 12 5 10 3
6 8 1 15 1 15 1
7 2 2 3 3 5 5

und so weiter. In Bezug auf 7 ergibt sich bei der 2 folgender .. 1 2 4 1 2 4 . Bei der 3: .. 1 3 6 4 5 1 3 .. .

Für alle drei Basen 2 3 5 gilt zur Zahl 7 folgende Regel:

<math>a^{(7-1)*c} \equiv 1 \mod 7</math> für alle \ge 1</math>

oder allgemein:

<math>a^{(n-1)*c} \equiv 1 \mod n</math> für alle \ge 1</math> und alle natürlichen a für gilt 1 < a < n

Im Beispiel des 2er-Zyklus .. 1 4 1 2 4 .. zeigt sich man den Algorithmus verkürzen kann wenn sich läßt daß der Zyklus kürzer .. 1 4 .. ist als benötigt.

Ausserdem hat es sich als sinnvoll daß man folgende Formel benutzt:

<math>a^{n-1}-1 \equiv 0 \mod n</math>



Bücher zum Thema Kleiner Fermat-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_Fermat-Satz.html">Kleiner Fermat-Satz </a>