Eulersche Phi-Funktion < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 18:24 So 22.11.2015 | | Autor: | Marcel |
| Aufgabe | Es gilt
[mm] $n=\sum_{0 < d, d | n}\varphi(d)$. [/mm] |
Hallo,
bzgl. der obigen Formel steht ein relativ kurzer Beweis etwa in "Buchmann,
Einführung in die Kryptographie, Theorem 3.8.4".
Der Beweis dort ist mir vollkommen klar. 
Mir geht es darum, dass ich mir gedacht habe, dass es doch auch möglich
sein müßte, den Beweis anders zu führen, und leider bekomme ich das
Ganze nicht ganz zu Ende gedacht bzw. aufgeschrieben.
Ich würde gerne versuchen, diese Formel aus der Primfaktorzerlegung
einer natürlichen Zahl zu gewinnen. Wenn ich mit [mm] $p=(p_n)_{n=1}^{\infty}=(p_1,p_2,...) \in \IP^{\IN}$ [/mm] die
einzige Folge [mm] $\IN \to \IP$ [/mm] bezeichne, die sowohl streng wächst als auch
bijektiv ist, so weiß ich doch folgendes:
Ist
[mm] $n=\prod_{k=1 \atop p_k|n}^n p_k^{v_k}$ [/mm] (ja, das Produkt rechterhand ist sicher viel zu groß aufgebläht
im Sinne, dass dort viel zu viele Primzahlen vorkommen; es sollen
alle [mm] $v_k \in \IN_0$ [/mm] sein!)
so ist die Menge [mm] $T(n)\,$ [/mm] der positiven Teiler von [mm] $n\,$ [/mm] gegeben durch
[mm] $T(n)=\left\{t \in \IN: \;\;t=\produkt_{{k=1\atop p_k|n} \atop \alpha_k \in \{0,...,v_k\}}^n p_k^{\alpha_k}\right\}$.
[/mm]
Jetzt weiß man ja, dass
[mm] $\varphi(m \cdot n)=\varphi(m)\;\varphi(n)$ [/mm] für [mm] $\ggT(m,n)=1$
[/mm]
sowie
[mm] $\varphi(p^r)=p^{r-1} \cdot [/mm] (p-1)$ für $p [mm] \in \IP$ [/mm] und $r [mm] \in \IN=\IN\setminus \{0\}$
[/mm]
gelten.
Für
[mm] $\sum_{t \in T(n)} \varphi(t)$
[/mm]
bzw. zur Berechnung von
[mm] $\varphi(t)$ [/mm] für $t [mm] \in [/mm] T(n)$
ist die zweite Formel aber nicht immer schön. Sie ist dann schön, wenn für
jeden Primteiler [mm] $p_k$ [/mm] von [mm] $n\,$ [/mm] auch [mm] $p_k [/mm] | t$ gilt.
Wenn $t [mm] \in [/mm] T(n)$ aber so ist, dass es ein [mm] $\ell \in \{1,...,n\}$ [/mm] so gibt, dass zwar
[mm] $p_\ell [/mm] | n$, nicht aber [mm] $p_\ell [/mm] | t$ (also [mm] $\alpha_\ell=0$), [/mm] gilt, dann ist das etwas blöd
hinzuschreiben; jedenfalls verliere ich dabei etwas den Überblick.
Hat vielleicht jemand 'ne Idee? Ich demonstriere mal an 'nem Beipsiel, was
ich eigentlich mache und wie der Beweis (dann halt nur allgemein) hoffentlich
aufgeschrieben werden kann/soll:
Betrachten wir [mm] $n=18\,.$ [/mm] Dann ist
[mm] $n=2^1 3^2\,.$
[/mm]
Ich schreibe nur noch die Exponentenkombinationen hin, die die Teiler von
18 darstellen - im Sinne, dass bspw. [mm] $(1,2)\widehat{=}2^1 3^2=18$ [/mm] und [mm] $(1,1)\widehat{=}2^1 3^1=6$ [/mm] gilt;
der Rest ist sicher klar.
Dann ist
[mm] $T(n)\widehat{=}\{(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)\}=\{1,3,9,2,6,18\}\,.$
[/mm]
Weiter ist etwa
[mm] $\varphi(2)=2-1=1$,
[/mm]
[mm] $\varphi(6)=\varphi(2 \cdot [/mm] 3)=(2-1) (3-1)=2$,
[mm] $\varphi(18)=\varphi(2 \cdot 3^2)=(2-1) \cdot (3^1 \cdot (3-1))\,.$
[/mm]
(Hier sieht man etwa
[mm] $\varphi(6)+\varphi(18)=(3^0+3^1)\cdot [/mm] (2-1) (3-1)$.)
Ich dachte eigentlich auch, dass ich den Beweis zumindest schonmal in
ähnlicher Form irgendwo gesehen habe... vielleicht weiß das ja jemand?
Edit: Nachdem mir, denke ich, der Induktionsbeweis so gelungen ist,
wie ich es erhofft hatte, wäre es dennoch gut, wenn vielleicht jemand
eine Literaturangabe hat, wo der Beweis in dieser Form drinsteht.
Gruß,
Marcel
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:11 So 22.11.2015 | | Autor: | Thomas_Aut |
Hallo Marcel,
Willst du es für Primzahlpotenzen zeigen oder vollkommen allgemein?
Hast du schon mal an Induktion gedacht?
$n = [mm] \produkt_{k}p_{k}^{v_{k}}$ [/mm] für k = 1 stimmt das natürlich (sofern die Aussage $ [mm] n=\sum_{0 < d, d | n}\varphi(d) [/mm] $ für Primzahlpotenzen gilt)
puh, aber ich hab für den Induktionsschritt jetzt keine Ideen.... Eventuell indem man die Menge der Teiler geschickt unterteilt...
Ich krame mal mein Algebra Buch raus
Lg
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:15 So 22.11.2015 | | Autor: | Marcel |
Hallo,
> Hallo Marcel,
>
> Willst du es für Primzahlpotenzen zeigen oder vollkommen
> allgemein?
allgemein.
> Hast du schon mal an Induktion gedacht?
>
>
> [mm]n = \produkt_{k}p_{k}^{v_{k}}[/mm] für k = 1 stimmt das
> natürlich (sofern die Aussage [mm]n=\sum_{0 < d, d | n}\varphi(d)[/mm]
> für Primzahlpotenzen gilt)
>
>
> puh, aber ich hab für den Induktionsschritt jetzt keine
> Ideen.... Eventuell indem man die Menge der Teiler
> geschickt unterteilt...
Gute Frage.
Es gibt allerdings vielleicht einen anderen Ansatz: Mit den eben genannten
Hilfsmitteln kann man zeigen, dass
[mm] $\varphi(n)=n*\prod_{p \in \IP \atop p | n} \left(1-\frac{1}p\right)$
[/mm]
gilt.
Übrigens ist die Aussage für $p [mm] \in \IP$ [/mm] trivial; denn dann ist [mm] $T(p)=\{1,p\}$ [/mm] und
[mm] $\varphi(1)=1$ [/mm] und [mm] $\varphi(p)=p-1$ [/mm] und [mm] $1+(p-1)=p\,$ [/mm] ist klar.
Im nächsten Schritt kann man sicher die Aussage auch schnell für [mm] $p^r$ [/mm] zeigen:
[mm] $T(p^r)=\{1,p,p^2,...,p^{r-1},p^r\}$ [/mm] und [mm] $\varphi(p^m)$ [/mm] für $m [mm] \in \{1,...,r\}$ [/mm] können wir
ja hinschreiben.
Das Problem bei "mehreren Primteilern" ist einfach, dass da noch mehrere
andere Primzahlen mit verschiedenen Kombinationen in deren Exponenten
auftauchen.
Nebenbei: Welches Algebrabuch benutzt Du? Ich habe das von Meyberg
und Karpfinger. (Nutze ich nur zum Selbststudium, da ich weder Algebra
noch Zahlentheorie im Studium gehört habe - okay, Zahlentheorie ein
wenig... aber Algebra wurde noch nicht mal angeboten.)
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:24 So 22.11.2015 | | Autor: | Marcel |
Hallo nochmal,
einfach, weil das schon so schön ist, hier mal nur der Beweis für Primzahlpotenzen
der Bauart [mm] $n=p^r$ [/mm] mit $p [mm] \in \IP$ [/mm] und positivem $r [mm] \in \IN$:
[/mm]
Es ist [mm] $T(n)=T(p^r)=\{1,p,p^2,...,p^r\}$ [/mm] und daher folgt
[mm] $\sum_{t \in T(n)}\varphi(t)=\sum_{k=0}^r \varphi(p^k)=\varphi(1)+\sum_{k=1}^r \varphi(p^k)=1+\sum_{k=1}^r p^{k-1}\cdot [/mm] (p-1)$
[mm] $=1+(p-1)*\sum_{k=0}^{r-1}p^k=1+(p^r-1)*\frac{p^r-1}{p-1}=1+(p^r-1)=p^r=n$.
[/mm]
(Könnte mir durchaus vorstellen, dass manch' einer genau diese Aufgabe
als Übungsaufgabe stellt, wobei 'nur' diese Lösung erwartet wird!)
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:40 So 22.11.2015 | | Autor: | Marcel |
Hallo Thomas,
ich glaube, ich habe den Ansatz, wie man den Beweis mithilfe der Primfaktor-
Zerlegung vielleicht doch geschickt führen kann:
Wir nehmen an, dass wir $k [mm] \in \IN$ [/mm] Primzahlen [mm] $q_\ell$ [/mm] gegeben haben; es seien also
[mm] $q_1,..., q_k$
[/mm]
mit [mm] $q_\ell=p_{h(\ell)}$ [/mm] für [mm] $\ell=1,...,k$ [/mm] und $h [mm] \colon \{1,...,k\} \to \IN$ [/mm] sei o.E. streng wachsend und damit auch
injektiv.
Wir nehmen nun an, dass die Behauptung für jede Zahl der Bauart
[mm] $q_1^{\alpha_1}*...*q_k^{\alpha_k}$
[/mm]
wobei alle [mm] $\alpha_j \in \IN_0$ [/mm] seien, schon gilt.
Jetzt überlegen wir uns, was passiert, wenn wir eine weitere Primzahl
hinzunehmen - also, welche "neuen Zahlen" dadurch entstehen und wie
wir für diese dann auch die Induktionsvoraussetzung zu verbraten haben,
so dass der Induktionsschritt klappt.
(Die alten Teiler bleiben ja erhalten, es kommen nur einige neue Teiler
hinzu - das ist aber überschaubar.)
Der Induktionsbeweis zeigt danach dann auch schon, dass die Behauptung
dann für alle natürlichen Zahlen stimmt. Einfach, weil es für jede natürliche
Zahl eine (eindeutig bis auf Reihenfolge, sofern wir nur die positiven primen
Elemente als Primfaktoren bezeichnen) Primfaktorzerlegung gibt.
So wäre bspw.
[mm] $108=2^2*3^3$,
[/mm]
d.h. im Induktionsbeweis wäre die Behauptung nach der Vollendung des
Schrittes $k [mm] \to [/mm] k+1$ mit $k=1$ gelungen.
Im Prinzip habe ich eben auch schon den Induktionsanfang gemacht, wo
ich die Behauptung für [mm] $n=p^r$ [/mm] gezeigt habe. Ansonsten sollte man vielleicht
nur dran denken, den Fall [mm] $n=1\,$ [/mm] nochmal separat zu behandeln (der ist
wegen [mm] $T(1)=1\,$ [/mm] und [mm] $\varphi(1)=1$ [/mm] aber langweilig).
So, ich denke, dass das vielleicht ein vernünftiger Ansatz ist - kurz:
Beweis per Induktion über die Anzahl der Primteiler einer Zahl!
Wobei ich mir nicht vorstellen kann, dass das noch niemand so gemacht
hat. Literaturangabe reicht, dann lese ich das mal nach, ansonsten denke
ich es vielleicht doch selber noch mit obigem Fahrplan zu Ende. Beides
schadet nicht.
Gruß,
Marcel
|
|
|
| |
|
Mir ist die Notation leider viel zu kompliziert. Mir würden mindestens drei Ansätze einfallen, um diese Formel zu beweisen: 1) Die zyklische Gruppe der Ordnung $n$ geschickt in Äquivalenzklassen zerlegen, 2) Mit Möbiusinversion aus der Formel für [mm] $\varphi(n)$ [/mm] ableiten, 3) zeigen, dass die Summenformel eine multiplikative zahlentheoretische Funktion definiert und die Behauptung auf den Spezialfall von Primzahlpotenzen zurückführen.
Ist Variante 3) das, was du machen möchtest? Falls ja, könnte ich das noch etwas ausführen.
Edit: Oh, ich habe irgendwie übersehen, dass es hier schon mehr als den Themenstart gab, und den Rest nicht durchgelesen. Eventuell ist diese Mitteilung also ziemlich dämlich.
Liebe Grüße,
UniversellesObjekt
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:50 So 22.11.2015 | | Autor: | Marcel |
Hallo,
> Mir ist die Notation leider viel zu kompliziert.
na, eigentlich nicht wirklich.
> Mir würden mindestens drei Ansätze einfallen, um diese Formel
> zu beweisen: 1) Die zyklische Gruppe der Ordnung [mm]n[/mm]
> geschickt in Äquivalenzklassen zerlegen, 2) Mit
> Möbiusinversion aus der Formel für [mm]\varphi(n)[/mm] ableiten,
> 3) zeigen, dass die Summenformel eine multiplikative
> zahlentheoretische Funktion definiert
Das kann man als gegeben und bewiesen voraussetzen.
Ach Quatsch, natürlich nicht. Du meintest die Summenformel aus der
zu zeigenden Aussage?
Das verstehe ich nicht ganz, was Du da machen und wie Du das dann benutzen
willst.
Aber das [mm] $\varphi$ [/mm] darf als multiplikative zahlentheoretische Funktion benutzt
werden!
> und die Behauptung auf den Spezialfall von Primzahlpotenzen
> zurückführen.
Okay.
> Ist Variante 3) das, was du machen möchtest? Falls ja,
> könnte ich das noch etwas ausführen.
Ich denke, im Wesentlichen schon. Ich habe nun einen Induktionsbeweis
geschrieben, der über die Anzahl der Primteiler läuft. Das funktioniert ganz
gut, ich schreibe gleich mal den Gedankengang dazu auf, wobei ich das nur
an einem Beispiel demonstriere - das reicht, da der allgemeine Beweis
dann wirklich analog geht.
Einzige Voraussetzung: Das, was ich an anderer Stelle schon gezeigt habe,
nämlich den Induktionsanfang für "genau einen Primteiler", kann man noch
ergänzen - weil er halt zum Induktionsbeweis dazugehört.
> Edit: Oh, ich habe irgendwie übersehen, dass es hier schon
> mehr als den Themenstart gab, und den Rest nicht
> durchgelesen. Eventuell ist diese Mitteilung also ziemlich
> dämlich.
Ne, gar nicht. In dem erwähnten Buch findet man übrigens einen sehr
schönen, kurzen Beweis. Dort wird im Wesentlichen
[mm] $\varphi(d)=\varphi(m/d)$ [/mm] für $d|m$ (bitte [mm] $m/d\,$ [/mm] als m durch d lesen; das überliest
man schnell, wenn zugleich d|m (d teilt m) irgendwo steht)
benutzt - und dass
[mm] $\{1,...,m\}$
[/mm]
als disjunkte Vereinigung der Mengen
[mm] $\{b \in \{1,...,m\}: \ggT(a,m)=d\}$ [/mm] (über die d mit $d|m$)
geschrieben werden kann.
Aber jetzt zu obigen Gedankengang: Betrachten wir erstmal
[mm] $m=18\,.$
[/mm]
Diese Zahl hat 2 Primteiler: [mm] $2\,$ [/mm] und [mm] $3\,$.
[/mm]
Die "Teilermenge" ist
[mm] $T(18)=\{2^03^0, 2^03^1,2^03^2,2^13^0, 2^13^1,2^13^2,\}=\{1,3,9,2,6,18\}$
[/mm]
(Schön: [mm] $\varphi(18)=\varphi(2^1\cdot 3^2)=(2-1)*3^{2-1}*(3-2)=2*3*1=6\,.$
[/mm]
Das ist identisch mit $|T(18)|$.)
Jetzt betrachten wir
[mm] $18*5^4=11250\,.$
[/mm]
Offenbar ist
[mm] $T(11250)=T(18*5^4)=5^0*T(18) \cup 5^1*T(18)\cup 5^2*T(18)\cup 5^3*T(18)\cup 5^4*T(18)$
[/mm]
Diese Vereinigung rechterhand ist disjunkt, manche schreiben dann + anstatt
[mm] $\cup$. [/mm] Und das [mm] $a*M:=\{am: m \in M\}$ [/mm] für $a [mm] \in \IN$ [/mm] und $M [mm] \subseteq \IN$ [/mm] sein soll, ist hoffentlich
klar, ansonsten habe ich es ja nun erwähnt.
Damit gilt nun
[mm] $\sum_{t \in T(18*5^4)}\varphi(t)=\sum_{t \in T(18)} \varphi(t)+\sum_{t \in 5*T(18)} \varphi(t)+\sum_{t \in 5^2*T(18)} \varphi(t)+\sum_{t \in 5^3*T(18)} \varphi(t)+\sum_{t \in 5^4*T(18)} \varphi(t)=:(\*)$
[/mm]
Nun sei [mm] $P_1:=5^4$ [/mm] und [mm] $P_2:=18$. [/mm] Alle Zahlen [mm] $5^\ell$ [/mm] für [mm] $\ell=0,...,4$ [/mm] sind dann
teilerfremd zu [mm] $P_2$. [/mm] Also folgt mit I.V. wegen der Multiplikativität der Phi-Fkt.
[mm] $(\*)=18+\varphi(5)*18+...+\varphi(5^4)*18=18+((5^0+...+5^3)*(5-1)*18)=18+\frac{1-5^4}{1-5}*(5-1)*18=18+(5^4-1)*18=18*5^4=P_2*P_1=11250$
[/mm]
Ich kann den Beweis auch mal sauber und vollständig aufschreiben, aber
dann steht halt nur das, was ich hier etwas speziell gemacht habe, allgemeiner
da.
Nur, damit ich nun keinen gedanklichen Schnellschuß gemacht habe oder
irgendwo etwas übersehe, wäre es trotzdem gut, wenn vielleicht jemand
einen derartigen Induktionsbeweis schonmal gesehen hat und mir
entsprechende Literatur nennt.
Ist übrigens eine rein private Neugier - nur, weil ich eben ab und an auch
mal gerne in Kryptographie reingucke und mir dann denke, dass es da doch
sicher auch alternative Beweismethoden gibt, wäre es gut, wenn ich die
dann auch finde. Rein zur Befriedigung meiner eigenen Neugier.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:21 Mi 25.11.2015 | | Autor: | Marcel |
Hi nochmal,
> Mir ist die Notation leider viel zu kompliziert. Mir
> würden mindestens drei Ansätze einfallen, um diese Formel
> zu beweisen: ...
> 3) zeigen, dass die Summenformel eine multiplikative
> zahlentheoretische Funktion definiert und die Behauptung
> auf den Spezialfall von Primzahlpotenzen zurückführen.
achso, ich glaube, Du wolltest darauf hinaus, dass man, wenn man
[mm] $f(1):=1\,$ [/mm]
und
[mm] $f(n):=n-\sum_{t \in \IN\red{\setminus \{n\}} \atop t |n}f(t)$ [/mm] für $n [mm] \in \IN$ [/mm]
setzt, dann eine auf [mm] $\IN$ [/mm] definierte Funktion hat und willst dann - wie auch
immer - zeigen, dass [mm] $f=\varphi$ [/mm] ist.
Das ist der Grundgedanke, oder?
Gruß,
Marcel
|
|
|
| |
|
Hi,
ich wollte eher darauf hinaus, dass mit [mm] $f(n)=\sum_{d\mid n}\varphi(d)$ [/mm] gilt: $f(mn)=f(m)f(n)$ für $m$, $n$ teilerfremd (das ist natürlich ein Spezialfall der Aussage, die wir zeigen wollen, aber ein einfacher).
Liebe Grüße,
UniversellesObjekt
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:20 Di 24.11.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
