91^5150 mod 437 < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:00 Di 30.10.2007 | | Autor: | klaus_84 |
| Aufgabe | Man berechne:
[mm] 91^{5150} [/mm] mod 437 |
Hallo.
ggT(91, 437) = 1 - Euklid'ischer Algorithmus.
91 = 7 * 13
437 = 19 * 23
Anzahl der primen Restklassen mod 437:
f(437) = [mm] 19^{0}*18*23^{0}*22 [/mm] = 396. - Euler'sche Funktion
Ich weiß also, dass es bei einer Division durch 437 396 prime Restklassen gibt, von denen [91] eine ist, da sie wie oben gezeigt, den ggT 1 haben.
Da für jede prime Restklasse k mod p mit ggT(k,m) = 1 gilt:
[mm] k^{f(m)} [/mm] = 1 folgt:
[mm] 91^{396} [/mm] = 1
Daraus folgt
[mm] 91^{5150}=91^{13*396+2}=(91^{396})^{13} [/mm] * [mm] 91^{2}
[/mm]
= 1 * [mm] 91^{2}.
[/mm]
= 8182
Und nun? Ich weiß nicht wirklich, was nun zu tun ist ...
Klaus.
|
|
| |
|
Jetzt gibst du (nicht 8182, da hattest du dich vertippt, sondern) 8281 mod 437 in ![[]](/images/popup.gif) google ein (kein Scherz). Alternativ kannst du ja auch einfach mal dividieren und den Rest bestimmen...
Lustig, dass du den komplizierten Teil richtig machst und dann an sowas scheiterst. Deine Aufgabe findet sich übrigens auch als Beispiel hier.
|
|
|
|
