eulersche Phi-Funktion < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich hätte da eine kleine Verständnisfrage zur eulerschen [mm] \phi [/mm] -Funktion:
man soll zeigen, dass [mm] \phi(m*n)=\phi(n)*\phi(m)
[/mm]
Beweis:
weil ggT(n,m)=1 [mm] \Rightarrow [/mm] d|m*n [mm] \gdw [/mm] d=r*s mit r|m und s|n
Somit: m*n = [mm] \summe_{d | m*n} \phi(d) [/mm] = [mm] \summe_{r|m} \summe_{s|n}\phi(r*s)
[/mm]
Dann ist mir nicht klar, warum dann folgt:
= [mm] \phi(m*n) [/mm] + [mm] \summe_{r|m, s|n, (r,s)\not=(m,n)} \phi(rs)
[/mm]
sowie warum das gilt:
[mm] =\phi(mn) [/mm] - [mm] \phi(m)\phi(n) [/mm] + [mm] \summe_{r|m}\phi(r)\summe_{s|n}\phi(s)
[/mm]
Warum daraus wieder die Behauptung folgt ist klar!
Vielen Dank!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:04 Di 15.06.2010 | | Autor: | felixf |
Moin
> Hallo,
> ich hätte da eine kleine Verständnisfrage zur eulerschen
> [mm]\phi[/mm] -Funktion:
> man soll zeigen, dass [mm]\phi(m*n)=\phi(n)*\phi(m)[/mm]
>
> Beweis:
> weil ggT(n,m)=1 [mm]\Rightarrow[/mm] d|m*n [mm]\gdw[/mm] d=r*s mit r|m und
> s|n
Das hat nichts damit zu tun, dass $ggT(n, m) = 1$ ist. Du brauchst $ggT(n, m) = 1$, damit $ggT(r, s) = 1$ ist.
> Somit: m*n = [mm]\summe_{d | m*n} \phi(d)[/mm] = [mm]\summe_{r|m} \summe_{s|n}\phi(r*s)[/mm]
>
> Dann ist mir nicht klar, warum dann folgt:
> = [mm]\phi(m*n)[/mm] + [mm]\summe_{r|m, s|n, (r,s)\not=(m,n)} \phi(rs)[/mm]
Na, du hast einen Summanden aus der Doppelsumme herausgezogen, naemlich den fuer $r = m, s = n$; fuer diesen ist [mm] $\phi(r [/mm] s) = [mm] \phi(m [/mm] n)$.
> sowie warum das gilt:
> [mm]=\phi(mn)[/mm] - [mm]\phi(m)\phi(n)[/mm] +
> [mm]\summe_{r|m}\phi(r)\summe_{s|n}\phi(s)[/mm]
Na, [mm] $\summe_{r|m, s|n, (r,s)\not=(m,n)} \phi(rs)$ [/mm] ist nach Induktionsvoraussetzung (die du freundlicherweise erst gar nicht erwaehnst) gleich [mm] $\summe_{r|m, s|n, (r,s)\not=(m,n)} \phi(r) \phi(s)$. [/mm] Dies ist jetzt [mm] $\sum_{r \mid m} \sum_{s \mid n} \phi(r) \phi(s) [/mm] - [mm] \phi(n) \phi(m)$ [/mm] -- da [mm] $\phi(n) \phi(m)$ [/mm] genau der Summand ist, der durch die Bedingung $(r, s) [mm] \neq [/mm] (m, n)$ weggelassen wurde.
LG Felix
|
|
|
| |
|
Vielen Dank,
ich glaub es lag einfach an der Notation, die mir nicht klar war!
|
|
|
|
