Der Satz von Euler-Fermat: Unterschied zwischen den Versionen
(Erstellen der Seite als ausgelagerte Hilfsseite für Primzahlen) |
|||
| Zeile 3: | Zeile 3: | ||
\[ k^{\varphi(n)} \equiv 1 \ (\text{mod} \ n) \] | \[ k^{\varphi(n)} \equiv 1 \ (\text{mod} \ n) \] | ||
| − | <math> k^{\varphi(n)}</math> | + | Für <math> k^{\varphi(n)}</math> gilt also <math> [k^{\varphi(n)}] = [1] </math>. |
== ggT == | == ggT == | ||
ggT steht für '''g'''rößter '''g'''emeinsamer '''T'''eiler und liefert die größte ganze Zahl, die alle angegebenen Zahlen ohne Rest teilt. <br> | ggT steht für '''g'''rößter '''g'''emeinsamer '''T'''eiler und liefert die größte ganze Zahl, die alle angegebenen Zahlen ohne Rest teilt. <br> | ||
| − | Also ist eine Zahl <math>g=</math> ggT(<math>z_1, \dots , z_n)</math>, falls gilt: | + | Also ist eine Zahl <math>g=</math> ggT(<math>z_1, \dots , z_n)</math>, falls gilt: <br> |
| − | + | <br> | |
| − | + | <math> (i) \ z_i\text{ mod } g = 0 \ \forall 1 \leq i \leq n </math> <br> | |
| + | <br> | ||
| + | <math> (ii)\ \text{Für alle } h \in \mathbb{Z} \text{ mit } z_i \text{ mod } h = 0 \ \forall 1 \leq i \leq n \text{ gilt: } h \leq g </math> | ||
| + | |||
| + | === Beispiel === | ||
| + | Betrachten wir ggT(8,12). <br> | ||
| + | |||
| + | * Die Zahl 9 wird ganzzahlig von den Zahlen <math> \{1, 2, 4, 8\}</math> geteilt. | ||
| + | * Die Zahl 12 wird ganzzahlig von den Zahlen <math> \{1, 2, 3, 4, 6, 12\} </math> geteilt. | ||
| + | * Die gemeinsamen Teiler sind also <math> \{1, 2, 4\} </math>. | ||
| + | * Somit ist der größte gemeinsame Teiler 4. | ||
| + | |||
| + | Also: <math>\text{ggT}(8,12) = 4</math>. | ||
| + | |||
| + | === Sonderfall === | ||
| + | Gilt <math> \varphi(p) = p-1 </math> für eine Zahl <math> p </math>, so ist <math>p</math> eine Primzahl. Dies folgt daraus, dass in diesem Fall jede Zahl, die kleiner als <math>p</math> ist, nur 1 als größten gemeinsamen Teiler hat. | ||
| + | |||
| + | |||
== Die Eulersche <math> \varphi </math>-Funktion == | == Die Eulersche <math> \varphi </math>-Funktion == | ||
Die Eulersche <math> \varphi </math>-Funktion ordnet einer positiven ganzen Zahl <math>m</math> die Anzahl der ganzen positiven Zahlen zu, für die gilt: | Die Eulersche <math> \varphi </math>-Funktion ordnet einer positiven ganzen Zahl <math>m</math> die Anzahl der ganzen positiven Zahlen zu, für die gilt: | ||
| − | * | + | * Die Zahl ist kleiner oder gleich <math>m</math>. |
| − | * | + | * Der größte gemeinsame Teiler von <math>m</math> und der Zahl ist 1. |
Also: | Also: | ||
\[ \varphi: \ \mathbb{Z}_{>0} \longrightarrow \mathbb{C}\] | \[ \varphi: \ \mathbb{Z}_{>0} \longrightarrow \mathbb{C}\] | ||
| − | \[ m \mapsto |\{d \in \mathbb{Z} | 1 \leq d \leq m \text{ und | + | \[ m \mapsto |\{d \in \mathbb{Z} | 1 \leq d \leq m \text{ und ggT}(d,m) = 1\}|\] |
| + | |||
| + | === Beispiel === | ||
| + | Wir betrachten <math> \varphi(6)</math>.<br> | ||
| + | |||
| + | * Es werden alle Zahlen betrachtet, die kleiner oder gleich 6 sind. | ||
| + | * Zuerst wird der <math>\text{ggT}(h,6) \ \forall 1\leq h \leq 6</math> betrachtet. | ||
| + | {| class="wikitable" | ||
| + | |- | ||
| + | |'''<math>h</math>''' | ||
| + | |1 | ||
| + | |2 | ||
| + | |3 | ||
| + | |4 | ||
| + | |5 | ||
| + | |6 | ||
| + | |- | ||
| + | |'''<math>\text{ggT}(h,6)</math>''' | ||
| + | |1 | ||
| + | |2 | ||
| + | |3 | ||
| + | |2 | ||
| + | |1 | ||
| + | |2 | ||
| + | |} | ||
| + | * Für die <math>\varphi</math>-Funktion werden nur die Zahlen betrachtet, für die der größte gemeinsame Teiler von 6 und der Zahl 1 ist. Also bleiben <math>\{1,5\}</math>. | ||
| + | * Da gilt <math>|\{1,5\}| = 2</math> ist <math> \varphi(6) = 2 </math> | ||
| + | |||
== Beweis des Satzes von Euler-Fermat == | == Beweis des Satzes von Euler-Fermat == | ||
| + | Es gibt verschiedene Beweise für den Satz von Euler-Fermat. In diesem Beweis wird der Satz von Euler-Fermat als Anwendung des Satzes von Lagrange betrachtet. <br> | ||
| + | <br> | ||
| + | Da <math> \text{ggT}(k,n) = 1</math> gilt, | ||
== Spezialfall == | == Spezialfall == | ||
Version vom 23. März 2021, 17:19 Uhr
Aussage
Für alle [math] k, n \in \mathbb{Z}_{\gt 0}[/math] mit ggt[math](k,n) = 1 [/math] gilt \[ k^{\varphi(n)} \equiv 1 \ (\text{mod} \ n) \]
Für [math] k^{\varphi(n)}[/math] gilt also [math] [k^{\varphi(n)}] = [1] [/math].
ggT
ggT steht für größter gemeinsamer Teiler und liefert die größte ganze Zahl, die alle angegebenen Zahlen ohne Rest teilt.
Also ist eine Zahl [math]g=[/math] ggT([math]z_1, \dots , z_n)[/math], falls gilt:
[math] (i) \ z_i\text{ mod } g = 0 \ \forall 1 \leq i \leq n [/math]
[math] (ii)\ \text{Für alle } h \in \mathbb{Z} \text{ mit } z_i \text{ mod } h = 0 \ \forall 1 \leq i \leq n \text{ gilt: } h \leq g [/math]
Beispiel
Betrachten wir ggT(8,12).
- Die Zahl 9 wird ganzzahlig von den Zahlen [math] \{1, 2, 4, 8\}[/math] geteilt.
- Die Zahl 12 wird ganzzahlig von den Zahlen [math] \{1, 2, 3, 4, 6, 12\} [/math] geteilt.
- Die gemeinsamen Teiler sind also [math] \{1, 2, 4\} [/math].
- Somit ist der größte gemeinsame Teiler 4.
Also: [math]\text{ggT}(8,12) = 4[/math].
Sonderfall
Gilt [math] \varphi(p) = p-1 [/math] für eine Zahl [math] p [/math], so ist [math]p[/math] eine Primzahl. Dies folgt daraus, dass in diesem Fall jede Zahl, die kleiner als [math]p[/math] ist, nur 1 als größten gemeinsamen Teiler hat.
Die Eulersche [math] \varphi [/math]-Funktion
Die Eulersche [math] \varphi [/math]-Funktion ordnet einer positiven ganzen Zahl [math]m[/math] die Anzahl der ganzen positiven Zahlen zu, für die gilt:
- Die Zahl ist kleiner oder gleich [math]m[/math].
- Der größte gemeinsame Teiler von [math]m[/math] und der Zahl ist 1.
Also: \[ \varphi: \ \mathbb{Z}_{>0} \longrightarrow \mathbb{C}\] \[ m \mapsto |\{d \in \mathbb{Z} | 1 \leq d \leq m \text{ und ggT}(d,m) = 1\}|\]
Beispiel
Wir betrachten [math] \varphi(6)[/math].
- Es werden alle Zahlen betrachtet, die kleiner oder gleich 6 sind.
- Zuerst wird der [math]\text{ggT}(h,6) \ \forall 1\leq h \leq 6[/math] betrachtet.
| [math]h[/math] | 1 | 2 | 3 | 4 | 5 | 6 |
| [math]\text{ggT}(h,6)[/math] | 1 | 2 | 3 | 2 | 1 | 2 |
- Für die [math]\varphi[/math]-Funktion werden nur die Zahlen betrachtet, für die der größte gemeinsame Teiler von 6 und der Zahl 1 ist. Also bleiben [math]\{1,5\}[/math].
- Da gilt [math]|\{1,5\}| = 2[/math] ist [math] \varphi(6) = 2 [/math]
Beweis des Satzes von Euler-Fermat
Es gibt verschiedene Beweise für den Satz von Euler-Fermat. In diesem Beweis wird der Satz von Euler-Fermat als Anwendung des Satzes von Lagrange betrachtet.
Da [math] \text{ggT}(k,n) = 1[/math] gilt,
Spezialfall
Ein Spezialfall des Satzes ist der kleine Fermatsche Satz.
Anwendungen
Der Satz von Euler-Fermat findet unter anderem in der Kryptographie anwendung. Beispielsweise beim RSA-Verfahren.
Quellen
Lassueur, Dr. Caroline(2017): Elementare Zahlentheorie – Kurzskript zur Vorlesung