Satz von Euler-Fermat < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Bestimme das Ergebnis von:
[mm] 5^{256} [/mm] mod 17
mit Hilfe vom Satz von Euler-Fermat |
Hallo,
zu Erst bestimme ich phi von 17
phi(17) = [mm] 17^{0} [/mm] * (17-1) = 16
dann muss ich 256 durch phi(17)=16 zerlegen, aber:
256 = 16*16 + 0 ... also mit diesem null kann ich nicht weiter machen! Wie soll ich den prozedieren?
Bitte um Hilfe
|
|
| |
|
> Bestimme das Ergebnis von:
> [mm]5^{256}[/mm] mod 17
> mit Hilfe vom Satz von Euler-Fermat
> Hallo,
> zu Erst bestimme ich phi von 17
>
> phi(17) = [mm]17^{0}[/mm] * (17-1) = 16
>
> dann muss ich 256 durch phi(17)=16 zerlegen, aber:
>
> 256 = 16*16 + 0 ... also mit diesem null kann ich nicht
> weiter machen! Wie soll ich den prozedieren?
>
> Bitte um Hilfe
Hallo,
der Satz sagt doch, daß [mm] a^{16}\equiv [/mm] 1mod 17 ist.
[mm] 5^{256}=5^{16*16}=(5^{16})^{16}= [/mm] ???
Gruß v. Angela
|
|
|
| |
|
Also dann:
[mm] 5^{256} [/mm] = [mm] (5^{16})^{16} [/mm] * [mm] 5^{0} \equiv 5^{0} [/mm] = 1 mod 17
also [mm] 5^{256} [/mm] = 1 mod 17
Ist das richtig?
|
|
|
| |
|
Hallo fittipaldi,
> Also dann:
>
> [mm]5^{256}[/mm] = [mm](5^{16})^{16}[/mm] * [mm]5^{0} \equiv 5^{0}[/mm] = 1 mod 17
>
> also [mm]5^{256}[/mm] = 1 mod 17
>
> Ist das richtig?
![[ok]](/images/smileys/ok.gif "[ok]")
ja, aber wieso hast du da [mm] $\cdot{}5^{0}$ [/mm] drangeschrieben?
Es ist doch [mm] $a^{\varphi(n)}\equiv 1\mod(n)$
[/mm]
Also [mm] $5^{\varphi(17)}=5^{16}\equiv 1\mod(17)$ [/mm] usw.
LG
schachuzipus
|
|
|
|
