Kleiner Satz von Fermat < Sonstiges < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:35 Mo 25.10.2010 | | Autor: | anno |
| Aufgabe | Berechnen Sie möglichst effizient:
[mm] 2^{167} [/mm] mod 83 |
Hallo,
hat jemand eine Idee wie ich genau den Satz von Fernat mit der Hand am effizientesten ausrechne?
Also folgendes weß ich:
[mm] a^{p-1} \equiv [/mm] 1 mod p
p = 83
a = 2
[mm] a^{p-1} [/mm] = [mm] 2^{82}
[/mm]
Hat da jemand eine Idee wie ich das machen kann?
|
|
| |
|
> Berechnen Sie möglichst effizient:
>
> [mm]2^{167}[/mm] mod 83
>
> Hallo,
>
> hat jemand eine Idee wie ich genau den Satz von Fermat mit
> der Hand am effizientesten ausrechne?
>
> Also folgendes weiß ich:
>
> [mm]a^{p-1} \equiv[/mm] 1 mod p
>
>
> p = 83
> a = 2
> [mm]a^{p-1}[/mm] = [mm]2^{82}[/mm]
>
>
> Hat da jemand eine Idee wie ich das machen kann?
Hallo,
es ist
[mm] 2^{167}=2^{2*82+3}.
[/mm]
Vielleicht bringt Dich das auf Ideen - Potenzgesetze nicht vergessen!
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:45 Mo 25.10.2010 | | Autor: | anno |
Also da müsste ja dann folgendes herauskommen:
[mm] (2^{2})^{82}*2^{3} \gdw 4^{82}*8
[/mm]
Als Rest kommt dann 8 heraus, kann das sein?
|
|
|
| |
|
> Also da müsste ja dann folgendes herauskommen:
>
> [mm](2^{2})^{82}*2^{3} \gdw 4^{82}*8[/mm]
>
> Als Rest kommt dann 8 heraus, kann das sein?
Ja.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:10 Mo 25.10.2010 | | Autor: | anno |
| Aufgabe | Berechnen Sie möglichst effizient:
[mm] 3^{167} [/mm] mod 17 |
Also ich würde es hier dann wieder so rechnen:
[mm] 3^{167} \gdw 3^{9*17+14} \gdw (3^{9})^{17} [/mm] * [mm] 3^{14}
[/mm]
Allerdings kommt mir hier das [mm] 3^{14} [/mm] doch etwas groß vor. Denn der Rest müsste eigentlich ja 11 ergeben und [mm] 3^{14} [/mm] ist ja dann doch schon einiges > 11...
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:18 Mo 25.10.2010 | | Autor: | abakus |
> Berechnen Sie möglichst effizient:
>
> [mm]3^{167}[/mm] mod 17
Hallo. es sollte möglich sein, den Rest von [mm] 3^{16} [/mm] mod 17 zu berechnen.
Vielleicht sogar von [mm] 3^{32}, 3^{48}...?
[/mm]
Gruß Abakus
> Also ich würde es hier dann wieder so rechnen:
>
>
> [mm]3^{167} \gdw 3^{9*17+14} \gdw (3^{9})^{17}[/mm] * [mm]3^{14}[/mm]
>
>
> Allerdings kommt mir hier das [mm]3^{14}[/mm] doch etwas groß vor.
> Denn der Rest müsste eigentlich ja 11 ergeben und [mm]3^{14}[/mm]
> ist ja dann doch schon einiges > 11...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:24 Mo 25.10.2010 | | Autor: | anno |
Ich glaube ich hatte da gerade einen Fehler gemacht:
a = 3
p = 17
[mm] a^{p-1} [/mm] = [mm] 3^{17-1} [/mm] = [mm] 3^{16}
[/mm]
[mm] 3^{167} [/mm] = [mm] 3^{10*16+7} [/mm] = [mm] (3^{10})^{16} [/mm] * [mm] 3^{7}
[/mm]
Allerdings auch noch etwas groß
edit:
wobei
[mm] 3^{7} [/mm] = 2184 [mm] \Rightarrow [/mm] 2184 mod 17 = 11
Ich weiß jetzt allerdings nicht genau ob das formal so korrekt ist. der Rest stimmt zumindest mal.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:31 Mo 25.10.2010 | | Autor: | abakus |
> Ich glaube ich hatte da gerade einen Fehler gemacht:
>
> a = 3
>
> p = 17
>
> [mm]a^{p-1}[/mm] = [mm]3^{17-1}[/mm] = [mm]3^{16}[/mm]
>
>
> [mm]3^{167}[/mm] = [mm]3^{10*16+7}[/mm] = [mm](3^{10})^{16}[/mm] * [mm]3^{7}[/mm]
>
> Allerdings auch noch etwas groß
Gehe schrittweise vor.
[mm] 3^3=27, [/mm]
also [mm] 3^3\equiv [/mm] 10 mod 17.
Daraus folgt [mm] 3^6 \equiv [/mm] 100 [mm] \equiv [/mm] -2 mod 17.
Somit gilt [mm] 3^7 \equiv [/mm] -2*3 [mm] \equiv [/mm] -6 [mm] \equiv [/mm] 11 mod 17.
Gruß Abakus
|
|
|
|
