Division mit Rest < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:29 Mi 15.12.2010 | | Autor: | Bodo0686 |
| Aufgabe | | Bestimmen Sie den Rest von 7^549 bei Division durch 13 |
Hallo,
also man kann diese Sache ja nach dem Fermatschen Satz lösen.
n^(p-1) [mm] \equiv [/mm] 1 (mod p)
7^(13-1) [mm] \equiv [/mm] 1 (mod 13). Aber muss ich hier nicht die 549 noch irgendwie zerlegen? Könnt ihr mir weiterhelfen!? Danke!
|
|
| |
|
> Bestimmen Sie den Rest von 7^549 bei Division durch 13
> Hallo,
>
> also man kann diese Sache ja nach dem Fermatschen Satz
> lösen.
>
> n^(p-1) [mm]\equiv[/mm] 1 (mod p)
>
> 7^(13-1) [mm]\equiv[/mm] 1 (mod 13). Aber muss ich hier nicht die
> 549 noch irgendwie zerlegen? Könnt ihr mir weiterhelfen!?
> Danke!
Hallo,
zerleg sie in 549=k*12+r.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:41 Mi 15.12.2010 | | Autor: | Bodo0686 |
Hallo,
also habe ich: 549=k*12+r -> 549=45*12+9
Dann gilt doch: [mm] 7^{45(13-1)}\equiv 7^9 \gdw (7^{13-1})^{45}\equiv 7^9
[/mm]
Was muss man als nächstes machen?
|
|
|
| |
|
> Hallo,
>
> also habe ich: 549=k*12+r -> 549=45*12+9
>
> Dann gilt doch: [mm]7^{45(13-1)}\equiv 7^9 \gdw (7^{13-1})^{45}\equiv 7^9[/mm]
>
> Was muss man als nächstes machen?
Na! Ausrechnen, welchen Rest [mm] 7^9 [/mm] bei Division durch 13 läßt...
Du könntest hierfür z.B. den Rest von [mm] 7^2 [/mm] oder [mm] 7^3 [/mm] ausrechnen.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:50 Mi 15.12.2010 | | Autor: | Bodo0686 |
Also [mm] 7^9=40353607 [/mm] : 13 = 3104123 * 13 = 8
Aber warum, ist es sinnvoll die Reste von [mm] 7^2 [/mm] bzw. [mm] 7^3 [/mm] auszurechnen?
[mm] 7^2 [/mm] = 49 : 13 = 3 * 13 = 39 -> R 10
[mm] 7^3 [/mm] = 343 : 13 = 26 * 13 = 338 -> R 5
[mm] 7^9 [/mm] = [mm] (7^3)^3 [/mm] = -> [mm] 5^3=125 [/mm] : 13 = 9*13=117 -> R 8
Grüße
|
|
|
| |
|
> Also [mm]7^9=40353607[/mm] : 13 = 3104123 * 13 = 8
>
> Aber warum, ist es sinnvoll die Reste von [mm]7^2[/mm] bzw. [mm]7^3[/mm]
> auszurechnen?
>
> [mm]7^2[/mm] = 49 : 13 = 3 * 13 = 39 -> R 10
> [mm]7^3[/mm] = 343 : 13 = 26 * 13 = 338 -> R 5
>
> [mm]7^9[/mm] = [mm](7^3)^3[/mm] = -> [mm]5^3=125[/mm] : 13 = 9*13=117 -> R 8
Wenn auch der Aufschrieb eine wirkliche Katastrophe ist, beantwortest Du Dir in dieser Zeile die Frage doch selbst.
Gruß v. Angela
> Grüße
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:01 Mi 15.12.2010 | | Autor: | Bodo0686 |
Ja... Also ist 8 die Lösung der Aufgabe.. richtig? Aber warum betrachte ich denn nur [mm] 7^9 [/mm] und nicht [mm] 7^{45(13-1)}
[/mm]
|
|
|
| |
|
> Ja... Also ist 8 die Lösung der Aufgabe.. richtig? Aber
> warum betrachte ich denn nur [mm]7^9[/mm] und nicht [mm]7^{45(13-1)}[/mm]
Hallo,
Du betrachtest doch beides:
es ist [mm] 7^{549}=7^{45*12 + 9}= (7^12)^45*7^9,
[/mm]
und mit dem kl. Fermat weißt Du, daß [mm] 7^{12}\equiv [/mm] 1 (mod 13).
Also ist [mm] 7^{549}\equiv 7^9 [/mm] (mod 13),
und Deine weiteren Überlegungen haben ergeben, daß [mm] 7^9=(7^3)^3 \equiv [/mm] 8 (mod 13).
Gruß v. Angela
|
|
|
|
