Eulersche Identität < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei [mm] \phi [/mm] die eulersche Phi-Funktion. Zeige folgende Identität:
Für [mm] n\in \IN [/mm] ohne die Null gilt:
[mm] \summe_{d| n} \phi(d)=n, [/mm] wobei d alle positiven Teiler von n durchläuft. |
Hallo erstmal
Ich habe zu dieser Aufgabe einen Beweis gefunden, den ich nicht so ganz verstehe.
Also es wurde für 1 [mm] \le [/mm] d [mm] \le [/mm] n folgende Menge definiert:
[mm] M_{d}(Z_{n}):=(a \in Z_{n}:ord a=d)cZ_{n}
[/mm]
Dann steht da:
Offensichtlich ist [mm] M_{d}(Z_{n}) \not= [/mm] leere Menge genau dann, wenn d | n und man hat eine disjunkte Zerlegung [mm] Z_{n}=\bigcup_{d | n} M_{d}(Z_{n}).
[/mm]
Für mich ist das leider nicht offensichtlich. Weder die eine Richtung, noch die andere Richtung. Ich seh nicht den Zusammenhang zwischen der Ordnung und der Teilbarkeit zweier Zahlen.
Kann mir bitte einer die Äquivalenz in Worten erklären, sodass ich wenigstens im Ansatz verstehe, warum das gilt.
Vielen Dank für jede Hilfe schonmal
Gruß
TheBozz-mismo
|
|
| |
|
moin Bozz,
Welche Ordnung genau ist da gemeint?
Die Ordnung in [mm] $(E(\IZ_n),*)$ [/mm] ?
Das wage ich zu bezweifeln, da ja nicht alle Elemente von [mm] $\IZ_n$ [/mm] multiplikativ invertierbar sind...
Oder die Ordnung in [mm] $(\IZ_n,+)$?
[/mm]
Da würde ich mich aber auch fragen, was die denn mit Teilbarkeit zu tun hat...
Bist du dir sicher, dass das genau so im Skript stand?
Ich hab mal in meinem Skript geblättert und da war die Menge so definiert:
[mm] $M_d(n) [/mm] := [mm] \{ m \in \IN | m \leq n \text{ und } ggT(m,n)=d \}$
[/mm]
Da der Rest deines Beweises bei mir im Skript praktisch genauso steht solltest du dringend nochmal nachgucken welche Ordnung da gemeint ist oder was genau da steht.
lg
Schadow
|
|
|
| |
|
Hallo
Ich habe den Beweis aus dem Buch "Lehrbuch der Algebra" von Fischer Seite 62 und dort steht [mm] M_{d}(Z_{n}):=\{a \in Z_{n}: ord(a)=d\}cZ_{n}.
[/mm]
Vielleicht weiß ja irgendwer anderer Rat oder hat ne Idee...
Naja, vielleicht versuch ich es mal mit deiner definierten Menge nachzuvollziehen.
Danke schonmal für deine Antwort
Gruß
TheBozz-mismo
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:35 Sa 14.01.2012 | | Autor: | felixf |
Moin!
> Welche Ordnung genau ist da gemeint?
> Die Ordnung in [mm](E(\IZ_n),*)[/mm] ?
Nein, die Ordnung in der additiven Gruppe [mm] $(\IZ_n, [/mm] +)$.
> Das wage ich zu bezweifeln, da ja nicht alle Elemente von
> [mm]\IZ_n[/mm] multiplikativ invertierbar sind...
> Oder die Ordnung in [mm](\IZ_n,+)[/mm]?
> Da würde ich mich aber auch fragen, was die denn mit
> Teilbarkeit zu tun hat...
Die hat ziemlich direkt etwas mit Teilbarkeit zu tun 
LG Felix
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:40 Sa 14.01.2012 | | Autor: | felixf |
Moin!
> Sei [mm]\phi[/mm] die eulersche Phi-Funktion. Zeige folgende
> Identität:
> Für [mm]n\in \IN[/mm] ohne die Null gilt:
> [mm]\summe_{d| n} \phi(d)=n,[/mm] wobei d alle positiven Teiler von
> n durchläuft.
>
> Ich habe zu dieser Aufgabe einen Beweis gefunden, den ich
> nicht so ganz verstehe.
> Also es wurde für 1 [mm]\le[/mm] d [mm]\le[/mm] n folgende Menge
> definiert:
> [mm]M_{d}(Z_{n}):=(a \in Z_{n}:ord a=d)cZ_{n}[/mm]
> Dann steht da:
> Offensichtlich ist [mm]M_{d}(Z_{n}) \not=[/mm] leere Menge genau
> dann, wenn d | n und man hat eine disjunkte Zerlegung
> [mm]Z_{n}=\bigcup_{d | n} M_{d}(Z_{n}).[/mm]
>
> Für mich ist das leider nicht offensichtlich. Weder die
> eine Richtung, noch die andere Richtung.
Erstmal: ist $ord(g) = d$ fuer ein $g [mm] \in \IZ_n$, [/mm] so ist nach Lagrange $d$ ein Teiler von der Gruppenordnung, und die ist $n = [mm] |\IZ_n|$. [/mm] Damit folgt, dass aus [mm] $M_d(\IZ_n) \neq \emptyset$ [/mm] folgen muss, dass $d [mm] \mid [/mm] n$ gilt.
Ist nun $d$ ein Teiler von $n$, so hat die Restklasse [mm] $\frac{n}{d} [/mm] + [mm] n\IZ$ [/mm] in [mm] $(\IZ_n, [/mm] +)$ gerade die Ordnung $d$: es gilt $d [mm] \cdot (\frac{n}{d} [/mm] + n [mm] \IZ) [/mm] = n + [mm] n\IZ [/mm] = [mm] n\IZ [/mm] = 0 + [mm] n\IZ$, [/mm] also das neutrale Element, und fuer jedes $0 < k < d$ ist $k [mm] \cdot (\frac{n}{d} [/mm] + [mm] n\IZ) [/mm] = [mm] \frac{n k}{d} [/mm] + [mm] n\IZ \neq [/mm] 0 + [mm] n\IZ$, [/mm] da [mm] $\frac{n k}{d}$ [/mm] kein Vielfaches von $n$ ist.
> Ich seh nicht den
> Zusammenhang zwischen der Ordnung und der Teilbarkeit
> zweier Zahlen.
In einer allgemeinen Gruppe $G$ gilt: hat $g [mm] \in [/mm] G$ die Ordnung $n$, und ist $k [mm] \in \IN$, [/mm] so hat [mm] $g^k$ [/mm] die Ordnung [mm] $\frac{n}{ggT(n, k)}$.
[/mm]
In [mm] $\IZ_n$ [/mm] hat jedes Element die Form $k [mm] \cdot [/mm] (1 + n [mm] \IZ) [/mm] = k + [mm] n\IZ$, [/mm] und die Ordnung von $1 + [mm] n\IZ$ [/mm] ist $n$. Damit ist die Ordnung von $k [mm] \cdot [/mm] (1 + [mm] n\IZ)$ [/mm] gerade [mm] $\frac{n}{ggT(n, k)}$.
[/mm]
Insbesondere ist also [mm] $M_d(\IZ_n) [/mm] = [mm] \{ k + n\IZ \mid 0 \le k < n, \; \frac{n}{ggT(n, k)} = d \}$. [/mm] Damit kannst du jetzt die Anzahl der Elemente in [mm] $M_d(\IZ_n)$ [/mm] genauer untersuchen.
LG Felix
|
|
|
| |
|
Vielen Dank für deine wieder mal ausführliche Antwort.
Wenn ich noch Fragen hab, dann meld ich mich.
Gruß
TheBozz-mismo
|
|
|
|
