Satz: Euler Fermat < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Ubung 58. Berechne ohne Taschenrechner in [mm] Z_{50}
[/mm]
[mm] 3^{2^{32}} [/mm] |
Hallo leute,
ich hab heute ein problem mit dem Satz Euler Fermat ich weiß das wenn die modulo zahl eine primzahl ist dann ist es (p-1)
mein problem aber was tun wenn es keine primzahl ist dann steh ich auf der leitung folgendes Beispiel:
2^32 modulo 11
phi(11) = 10
dann hab ich als lösung 4 mod 11
jetzt hab ich aber das problem beim oben geposteten Beispiel das ich nicht weiß was mein phi ist.
Wie berechne ich das?
mfg
Christoph
|
|
| |
|
Hallo Christoph,
> Ubung 58. Berechne ohne Taschenrechner in [mm]Z_{50}[/mm]
> [mm]3^{2^{32}}[/mm]
> Hallo leute,
>
> ich hab heute ein problem mit dem Satz Euler Fermat ich
> weiß das wenn die modulo zahl eine primzahl ist dann ist
> es (p-1)
>
> mein problem aber was tun wenn es keine primzahl ist dann
> steh ich auf der leitung folgendes Beispiel:
>
> 2^32 modulo 11
>
> phi(11) = 10
>
> dann hab ich als lösung 4 mod 11
>
> jetzt hab ich aber das problem beim oben geposteten
> Beispiel das ich nicht weiß was mein phi ist.
>
> Wie berechne ich das?
Nun, falls [mm]\operatorname{ggT}(a,m)=1[/mm], so gilt [mm]a^{\varphi(m)} \ \equiv \ 1 \ \operatorname{mod}(m)[/mm]
Hier mit [mm]a=3[/mm] und [mm]m=50[/mm] gilt also [mm]\operatorname{ggT}(3,50)=1[/mm], mithin
[mm]3^{\varphi(50)} \ \equiv \ 1 \ \operatorname{mod}(50)[/mm]
Es ist [mm]50=2\cdot{}25=2\cdot{}5^2[/mm], also - da die [mm]\varphi[/mm]-Funktion multiplikativ ist:
[mm]\varphi\left(2\cdot{}5^2\right)=\varphi(2)\cdot{}\varphi\left(5^2\right)[/mm]
Hilft das schon weiter?
>
> mfg
> Christoph
Gruß
schachuzipus
|
|
|
| |
|
Tut es leider nicht 
ich weiß nehmlich nicht wie man das berechnet ^^ also der phi wert. Wenn du vlt. mir das kurz erklären könntest anhand irgend einer allgemeinen formel wikipedia war auch net sehr hilfreich :-(
mfg
Christoph
ps: ich hab das beispiel genommen weil wir es in der vorlesung durchgerechnet hatten da kam phi = 20 raus. Warum oder weshalb matscheibe.
|
|
|
| |
|
Hallo nochmal,
> Tut es leider nicht
>
> ich weiß nehmlich nicht wie man das berechnet ^^ also der
> phi wert. Wenn du vlt. mir das kurz erklären könntest
> anhand irgend einer allgemeinen formel wikipedia war auch
> net sehr hilfreich :-(
Na, du bist ja lustig. Auf wikipedia unter "Eulersche [mm]\varphi[/mm]-Funktion" steht doch genau, wie man das ausrechnet.
[mm]\varphi(2)[/mm] solltest du so ablesen können. Wie man [mm]\varphi\left(p^k\right)[/mm] für [mm]p[/mm] prim, [mm]k\in\IN[/mm], ausrechnet, steht auf wikipedia, sollte man aber auch so wissen, wenn man im Thema ist!
Also schaue mal nach, dann siehst du, dass da rechnerisch auch wirklich [mm]\varphi(50)=20[/mm] rauskommt!
>
> mfg
> Christoph
>
> ps: ich hab das beispiel genommen weil wir es in der
> vorlesung durchgerechnet hatten da kam phi = 20 raus. Warum
> oder weshalb matscheibe.
Siehe wikipedia oder Mitschrift deiner VL ...
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:39 Di 27.03.2012 | | Autor: | bonzai0710 |
ok also ich hab jetzt das durchgelesen ^^ hab mich da auf der falschen wikiseite bewegt bzw. heute das falsche thema gelesen.
da es sich bei der anwenung um den satz von euler fermat handelt. hab ich diesen artikel gelesn :)
http://de.wikipedia.org/wiki/Satz_von_Euler
dieser hilft natürlich nicht wirklcih weiter. Aber ich hab jetzt mal dein beitrag gelesen und ich glaube ja es ist jetzt klar wie das geht.
Ich bedanke mich bei dir für deine geduld.
|
|
|
|
