Satz von Fermat.Rest bestimmen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:45 Di 04.12.2007 | | Autor: | muy |
| Aufgabe | | Bestimmen Sie den Rest von 3^99 bei Division durch 17. (Hinweis: Satz von Fermat, geschickte Zerlegung von 99) |
So ich hab dann mal angefangen.
3^99 geschickt zerlegen, wäre dann ja [mm] 3^{6(17-1)} *3^3
[/mm]
der satz von Fermat bedeutet ja [mm] n^{p-1} \equiv [/mm] 1 (mod p)
dann wäre von [mm] 3^{(17-1)} [/mm] der Rest 1, da p=17.
dann bleibt übrig [mm] 3^6 [/mm] * [mm] 3^3 [/mm] = 19683 : 17 = 1157 R 14
Ist das so richtig?
Oder hab ich dabei den Rest von [mm] 3^{(17-1)} [/mm] vergessen, also R 15?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Guten Tach. Also 14 kommt nicht raus.
Du hast 3^99 zerlegt in [mm] 3^{(17-1)*6}*3^3. [/mm] Das ist ja das selbe wie [mm] (3^{(17-1)})^6*3^3. [/mm] Nun sagt dir der Satz von Fermat das [mm] 3^{(17-1)} \equiv [/mm] 1 [mm] \mod [/mm] 17. Also ist [mm] (3^{(17-1)})^6 [/mm] auch [mm] \equiv [/mm] 1 [mm] \mod [/mm] 17. Jetzt kannst du verwenden dass man reste multiplizieren kann und das das Produkt dann der Rest des Produktes ist(verstanden???) Also [mm] (3^{(17-1)})^6*3^3 [/mm] = [mm] (k*17+1)*3^3 [/mm] = ............
[mm] 3^3 [/mm] lässt bei Teilung den rest 10 also ist der Rest ingesamt 10= 1*10. Ich hoffe ich konnte das verständlich ausdrücken
Einen schönen Tag noch
|
|
|
|
