Satz von Euler
Was ist der Satz von Euler?
- Der satz hilft dir, modulo-probleme mit hohen potenzen zu lösen. Du musst also die niedrigste potenz finden, für die der modulo gleich eins ist, dann musst du die grosse potenz umschreiben, und zwar als vielfaches dieser niedrigen potenz.Der „rest“ ist das, wovon du den modulo nehmen kannst, weil das vielfache davor modulo eins ist.
Mathematisch Ausgedrückt
⇒Der Satz von Euler verallgemeinert den kleinen Fermatschen Satz und wird deshalb auch Satz von Euler-Fermat genannt. Zur Erinnerung – der kleine Fermat besagt: ap-1mod p = 1
Der Satz von Euler:
Sind a und n zwei natürliche teilerfremde Zahlen, dann gilt: aφ(n) mod n = 1
- φ(n) ist die Anzahl der zu n teilerfremden natürlichen Zahlen (die Anzahl aller Zahlen ≤ n, deren größter gemeinsamer Teiler mit n gleich 1 ist).
- Beispiele:φ(12) = 4, teilerfremde Zahlen sind {1, 5, 7, 11}φ(13) = 12, alle Zahlen von 1 bis 12 sind teilerfremd, da 13 eine Primzahl istφ(14) = 6, teilerfremde Zahlen sind {1, 3, 5, 9, 11, 13}
- Zu einer Primzahl p sind alle Zahlen von 1 bis (p – 1) teilerfremd – daraus folgt: φ(p) = p – 1.
- Für prime Moduln p geht der Satz von Euler daher in den kleinen Satz von Fermat über.
- Für das Produkt zweier Primzahlen p und q gilt weiters:φ(p q) = (p – 1) . (q – 1)
- Somit:aφ(n).φ(m) mod n.m = 1für n und m prima(n-1) (m-1) mod n.m = 1 (a teilerfremd zu m und n)
Ein Beispiel für den Satz von Euler – Fermat wäre:
a=3, n=4
3φ(4)≡1 mod 4
32≡1 mod 4
9≡1 mod 4 ⇒ wahre Aussage.
Der kleine Satz von Fermat (Spezialfall von Euler)
Sei p eine Primzahl. Dann gilt fur jede Zahl a ∈ Z:
ap = a (mod p)
Beispiele
p = 5, a = 2:
25 = 32 ≡ 2 (mod 5)
Restklassen
- Die Restklasse von 0 modulo 2 ist die Menge der geraden Zahlen.
- Die Restklasse von 1 modulo 2 ist die Menge der ungeraden Zahlen.
- Die Restklasse von 0 modulo m ist die Menge der Vielfachen von m.
- Die Restklasse von 1 modulo 3 ist die Menge: {1,4,7,10…., -2,-5,-8…. }
Merke:
- Eine natürliche Zahl größer als 1 heißt prim, wenn sie eine Primzahl ist, andernfalls heißt sie zusammengesetzt. Die Zahlen 0 und 1 sind weder prim noch zusammengesetzt.
- Eine Primzahl ist eine natürliche Zahl mit genau zwei natürlichen Teilern, nämlich 1 und sich selbst.
Interessante Fragen und Antworten zu Satz von Euler
Was kann man mit dem Satz von Euler anstellen? |
| Der Satz des Euler ist eine Erweiterung des Satzes von Femant und beschäftigt sich mit den Potenzen von ganzen rationalen Zahlen. Im Prinzip sagt er folgendes aus:Wenn a und n zwei natürliche ganze Zahlen sind, die zudem teilerfremd sind so gilt:
a hoch phi von n mod n = 1. Phi ist in diesem falle die Anzahl der in n enthaltenen Zahlen, durch die n nicht teilbar ist, außer n selber. Mit diesem Wissen lassen sich nun beispielsweise hoch komplexe Potenzen in ihre Bestandteile zerlegen im schneller zum Ergebnis zu gelangen. Beispiel: Wollen wir herausfinden, welches die letzte Ziffer im Dezimalsystem von 7 hoch 222 -also wie lautet die Dezimalziffer Modulo 10? Hierzu ermitteln wir zunächst dass der ggT von 7 und 10 1 ist und phi von 10 = 4. Laut dem Satz von Euler bedeutet dies nun: 7 hoch 4 = 1 mod 10 Daraus folgern wir nun: 7 hoch 222 ist gleich 7 hoch (4 x 55 + 2) was uns nach weiterer Umformung zu dem Ergebnis mod 10 = 9 führt. Der Satz des Euler findet in der Praxis im Bereich der Computer gestützten Kryptographie Anwendung. So bestehen zum Beispiel RSA Verschlüsselungssysteme aus Potenzen, die mittels Eulerschem Prinzip erstellt und auch zerlegt werden können. |