Beweis: Summe der eulerschen Phi-Funktion

Question

Aufgabe:

Ich würde gerne nachvollziehen, warum in der eulerschen Phi-Funktion gilt: \(\varphi(d)= \varphi(\frac{n}{d}) \) für ein \(d \mid n \). Dazu habe ich folgendes Tafelbild:

Text erkannt:

\( \begin{array}{l} \begin{array}{r} \text { proof } \# S_{d}=\varphi\left(\frac{n}{d}\right), \bigcup_{d n} S_{d}=\{1, \ldots, n\} \\ S_{d} \cap S_{d^{\prime}}=\phi,{ }^{f} d \neq d^{\prime} . \end{array} \\ \text { So } \quad n=\sum \limits_{d n}+S_{d}=\sum \limits_{d n} \varphi\left(\frac{n}{d}\right) \\ \end{array} \)
note. \( d \mid n \Rightarrow n=d e \Rightarrow d=\frac{n}{e} \) for sime eln
\( \begin{array}{l} S_{0:}\{d \mid d \ln \}= \\ S_{0} \quad n=\sum \limits_{d n} \varphi(d) \end{array} \)

Ich verstehe da nicht so wirklich, warum aus den Eigenschaften der Teilbarkeit jetzt die Gleichheit der Mengen folgt. Wäre mega, wenn mir da jemand weiterhelfen könnte

Comments

Es wird doch nirgendwo behauptet, dass \(\varphi(d)=\varphi(n/d)\) für
\(d\; | \; n\) ist.

---

Entschuldige bitte, es geht natürlich um die Aussage: \(\sum \limits_{d|n}\varphi(d)=\sum \limits_{d|n}\varphi(\frac{n}{d}) \)

Answer 1

Sei \(T(n)\) die Menge aller pos. Teiler von \(n\).

Dann ist \(f:\; T(n)\rightarrow T(n),\; d\mapsto n/d\) eine Bijektion; denn

\(f\circ f=id_{T(n)}\).

Comments

Aus der Bijektion zwischen den Mengen kann ich ja zumindest schonmal folgern, dass sie gleichmächtig sind. Aber woher weiß ich denn, dass tatsächlich in beiden Mengen die selben Elemente sind? @mathelf hatte das ja ganz gut veranschaulicht, da frage ich mich jetzt, ob eine Bijektion reicht, um dies zu formalisieren

---

Es ist doch eine Bjektion von \(T(n)\) auf sich selbst,

also nur eine "Permutation" der Menge der Teiler.

Answer 2

Wenn du eine Zahl n hast, die einige Teiler hat, etwa n=12

Dann gibt es die Teiler 1,2,3,4,6,12. Und zu jedem Teiler gibt

es den sog. komplementären Teiler, also

zur 1  die 12

zur 2  die 6

zur 3 die 4

zur 6 die 2

zur 12 die 1 .

Der komplementäre Teiler zu d ist also n:d.

Die Mengen sind also die gleichen.