Eulersche-Phi-Funktion < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:36 Mi 16.02.2011 | | Autor: | MrRom |
| Aufgabe | | Zeigen Sie für a,b [mm] \in \IN [/mm] mit ggt(a,b)=1 gilt [mm] a^{phi(b)}+b^{phi(b)}\equiv [/mm] 1 mod ab |
Hallo.
Ich habe ein Problem mit dieser Aufgabe und komme nicht weiter, ich würde mich freuen, wenn mir jemand helfen könnte.
Mit dem Satz von Euler kann man ja folgern, dass gilt:
[mm] a^{phi(b)}=1 [/mm] mod b und [mm] b^{phi(a)}=1 [/mm] mod a
Jetzt habe ich an dieser stelle das Problem, dass ich nicht weiterkomme. Ich habe woanders gelesen, dass man wohl den Chinesischen Restsatz zur Hilfe nehmen soll, doch da habe ich ein Problem dann entsprechend die Inversen Elemente zu bestimmen.
Ich hoffe mir kann jemand weiterhelfen, ich würde mich freuen.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:54 Mi 16.02.2011 | | Autor: | felixf |
Moin!
> Zeigen Sie für a,b [mm]\in \IN[/mm] mit ggt(a,b)=1 gilt
> [mm]a^{phi(b)}+b^{phi(b)}\equiv[/mm] 1 mod ab
>
> Ich habe ein Problem mit dieser Aufgabe und komme nicht
> weiter, ich würde mich freuen, wenn mir jemand helfen
> könnte.
>
> Mit dem Satz von Euler kann man ja folgern, dass gilt:
>
> [mm]a^{phi(b)}=1[/mm] mod b und [mm]b^{phi(a)}=1[/mm] mod a
>
> Jetzt habe ich an dieser stelle das Problem, dass ich nicht
> weiterkomme. Ich habe woanders gelesen, dass man wohl den
> Chinesischen Restsatz zur Hilfe nehmen soll,
Genau den brauchst du!
> doch da habe
> ich ein Problem dann entsprechend die Inversen Elemente zu
> bestimmen.
Welche inversen Elemente? Du brauchst da nichts konkret zu rechnen!
Du weisst doch, dass $x [mm] \equiv [/mm] y [mm] \pmod{a b}$ [/mm] genau dann gilt, wenn $x [mm] \equiv [/mm] y [mm] \pmod{a}$ [/mm] und $x [mm] \equiv [/mm] y [mm] \pmod{b}$ [/mm] gilt. (Falls $ggT(a, b) = 1$.) Diese Aussage bekommst du vom chinesischen Restsatz (also eine Implikation davon, die andere ist trivial).
Um also $1 [mm] \equiv a^{phi(b)} [/mm] + [mm] b^{phi(a)} \pmod{a b}$ [/mm] zu zeigen, musst du $1 [mm] \equiv a^{phi(b)} [/mm] + [mm] b^{phi(a)} \pmod{b}$ [/mm] und $1 [mm] \equiv a^{phi(b)} [/mm] + [mm] b^{phi(a)} \pmod{a}$ [/mm] zeigen. Und das hast du schon fast...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:16 Mi 16.02.2011 | | Autor: | MrRom |
Super, vielen Dank. Stand da irgendwie auf dem Schlauch, das hat mir weitergeholfen :)
|
|
|
|
