Aufgabe zur Eulerschen Phi Funktion

27.10.2013, 16:29	Raphael89	Auf diesen Beitrag antworten »
Aufgabe zur Eulerschen Phi Funktion Meine Frage: Hallo zusammen, habe da eine Aufgabe zur Eulerschen-Phi-Funktion: Sei n eine natürliche Zahl >1, zu zeigen ist, dass $\begin{eqnarray} $\sum{a}=\frac{1}{2}n\varphi\left(n\right)$ \end{eqnarray}$ gilt. Dabei soll die Summe über alle natürlichen Zahlen a laufen, welche teilerfremd zu n sind und gleichzeitig sollen diese Zahlen <n sein. Meine Ideen: Leider habe ich keine großen Ideen zu dieser Aufgabe zu verzeichnen. Ich habe gesagt bekommen, dass es sich hierbei um eine Aufgabe handelt, die mit vollständiger Induktion gelöst werden soll...ich bitte dringend um Hilfe!
27.10.2013, 18:49	Captain Kirk	Auf diesen Beitrag antworten »
Hallo, ich seh nicht wie man diese Aufgeb (bzw. den ganzen Typus an Aufgaben) mit vollständiger Induktion lösen könnte. Allerdings geht strukturelle Induktion (bzw. dem Prinzip der guten Mengen): - Zeige die Aussage für Primzahlpotenzen - Zeige, dass die Summe auf der linken Seite, ich nenn sie mal f(n), eine multiplikativ im zahlentheoretische Sinne ist, also f(nm)=f(n)f(m) falls (n,m)=1 Da die rechte Seite auch multiplikativ ist ist damit die Gleichheit bereits gezeigt.
28.10.2013, 08:20	tmo	Auf diesen Beitrag antworten »
Die rechte Seite ist doch nicht multiplikativ. Der Faktor 1/2 macht das kaputt. Man sollte sich lieber mal vom kleinen Gauß inspirieren lassen...Schließlich ist $\begin{eqnarray} a \mapsto n-a \end{eqnarray}$ eine Involution der Menge, über die summiert wird... $\begin{eqnarray} 2 \sum_{(a,n)=1}a = \sum_{(a,n)=1} (a + (n-a)) = ... \end{eqnarray}$

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »