Summe über Teiler, Euler-Phi < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:00 Di 03.05.2011 | | Autor: | Teufel |
| Aufgabe | | Zeige: [mm] \summe_{d|n}^{}\varphi(d)=n. [/mm] |
Hi!
Eine kurze und knackige Aufgabe. Aber leider weiß ich nicht, wie ich sie in aller Allgemeinheit lösen kann. Ich konnte zeigen, dass die Aussage für Primzahlpotenzen gilt. Dann habe ich mir gedacht, dass man vielleicht Induktion anwenden kann.
Also ich stelle n dar durch [mm] n=p_1^{r_1}*...*p_k^{r_k}. [/mm] Für k=1 stimmt die Aussage (Primzahlpotenz). Nun müsste ich noch den Induktionsschritt machen.
Sei die Aussage also für [mm] n=p_1^{r_1}*...*p_k^{r_k} [/mm] wahr. Zu zeigen: Sie gilt auch für [mm] n'=p_1^{r_1}*...*p_k^{r_k}*p_{k+1}^{r_{k+1}}. [/mm]
Aber hier hört es nun auf. Ich muss die Teiler von n' dann sicher irgendwie gut einteilen, sodass ich gut die Induktionsvoraussetzung anwenden kann, aber auch nicht zu viele wilde neue Summen erzeuge. Kann mir da jemand helfen? Oder sollte ich es gar ohne Induktion machen?
PS: Man soll [mm] \varphi(p^r)=p^r-p^{r-1} [/mm] und die Multiplikativität der Funktion benutzen. Damit fällt der einzige Beweis weg, der mir sonst so im Internet untergekommen ist. :)
Vielen Dank.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:30 Di 03.05.2011 | | Autor: | felixf |
Moin!
> Zeige: [mm]\summe_{d|n}^{}\varphi(d)=n.[/mm]
> Hi!
>
> Eine kurze und knackige Aufgabe. Aber leider weiß ich
> nicht, wie ich sie in aller Allgemeinheit lösen kann. Ich
> konnte zeigen, dass die Aussage für Primzahlpotenzen gilt.
> Dann habe ich mir gedacht, dass man vielleicht Induktion
> anwenden kann.
>
> Also ich stelle n dar durch [mm]n=p_1^{r_1}*...*p_k^{r_k}.[/mm] Für
> k=1 stimmt die Aussage (Primzahlpotenz). Nun müsste ich
> noch den Induktionsschritt machen.
> Sei die Aussage also für [mm]n=p_1^{r_1}*...*p_k^{r_k}[/mm] wahr.
> Zu zeigen: Sie gilt auch für
> [mm]n'=p_1^{r_1}*...*p_k^{r_k}*p_{k+1}^{r_{k+1}}.[/mm]
> Aber hier hört es nun auf. Ich muss die Teiler von n' dann
> sicher irgendwie gut einteilen, sodass ich gut die
> Induktionsvoraussetzung anwenden kann, aber auch nicht zu
> viele wilde neue Summen erzeuge. Kann mir da jemand helfen?
> Oder sollte ich es gar ohne Induktion machen?
Induktion ist schon eine gute Idee, denke ich. Unterteile doch die Menge der Teiler von $n$ in folgende Mengen:
* die Teiler, die nicht durch [mm] $p_{k+1}$ [/mm] teilbar sind;
* die Teiler, die genau einmal durch [mm] $p_{k+1}$ [/mm] teilbar sind;
* die Teiler, die genau zweimal durch [mm] $p_{k+1}$ [/mm] teilbar sind;
* ...
* die Teiler, die genau [mm] $r_{k+1}$ [/mm] durch [mm] $p_{k+1}$ [/mm] teilbar sind.
Jeder solche Teiler ist eindeutig in der Form $d' [mm] \cdot p^i$ [/mm] schreibbar, wobei $i$ die Nummer ist von der Klasse (0 bis [mm] $r_{k+1}$), [/mm] und wobei $d'$ ein Teiler von $n / [mm] p_{k+1}^{r_{k+1}}$ [/mm] ist.
> PS: Man soll [mm]\varphi(p^r)=p^r-p^{r-1}[/mm] und die
> Multiplikativität der Funktion benutzen. Damit fällt der
> einzige Beweis weg, der mir sonst so im Internet
> untergekommen ist. :)
Das passt doch gut mit meinem Vorschlag zusammen. Es ist [mm] $\varphi(d' \cdot p^i) [/mm] = [mm] \varphi(d) \cdot (p^i [/mm] - [mm] p^{i-1})$ [/mm] fuer $i > 0$ und [mm] $\varphi(d' \cdot p^0) [/mm] = [mm] \varphi(d')$. [/mm] Damit kannst du fuer [mm] $\sum_{d'} \varphi(d')$ [/mm] die Induktionsvoraussetzung nehmen, da $d'$ ueber alle Teiler von $n / [mm] p_{k+1}^{r_{k+1}}$ [/mm] laeuft, und du kannst jeweils [mm] $\varphi(p^i)$ [/mm] ausklammern aus dieser Summe.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:18 Di 03.05.2011 | | Autor: | Teufel |
Hallo!
Ah, super, vielen Dank!
Damit ist jetzt alles klar. Ich bin einfach nicht auf eine vernünftige Partitionierung gekommen, aber mit deiner geht das super!
Danke nochmals.
|
|
|
|
