0 Daumen
626 Aufrufe

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:
Screenshot_1.png

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

Avatar von

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}) \)

2 Antworten

+1 Daumen
 
Beste Antwort

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)}\).

Avatar von 29 k

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.

0 Daumen

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.

Avatar von 289 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community