formel für die eulersche phi funktion

23.11.2008, 13:02	wanoek	Auf diesen Beitrag antworten »
formel für die eulersche phi funktion servus, nun ... mal soll folgende formel für die eulersche $\begin{eqnarray} \varphi \end{eqnarray}$ -funktion zeigen: $\begin{eqnarray} \sum_{k\|n}\varphi(k) = n \end{eqnarray}$ ist n eine primzahl dann ist der fall klar. wie zeig ich denn die formel für die restlichen n's. $\begin{eqnarray} \varphi(k) \end{eqnarray}$ gibt ja die anzahl der einheiten des restklassenrings $\begin{eqnarray} \mathbb Z/k\mathbb Z \end{eqnarray}$ an ... wie hilft mir das weiter ?
23.11.2008, 13:30	AD	Auf diesen Beitrag antworten »
Es kommt darauf an, die Zahlen von $\begin{eqnarray} 1 \end{eqnarray}$ bis $\begin{eqnarray} n \end{eqnarray}$ geeignet zu klassifizieren und dann abzuzählen, z.B. so: $\begin{eqnarray} n = \sum_{d:\; d\|n} \left\| \left\{ k \bigm\| 1\leq k\leq n,\; \operatorname{ggT}(k,n)=d \right\} \right\| \end{eqnarray}$ , d.h. alle Zahlen $\begin{eqnarray} k \end{eqnarray}$ mit einem festen ggT bzgl. $\begin{eqnarray} n \end{eqnarray}$ werden zu einer Menge zusammengefasst, und dann deren Umfang bestimmt.
23.11.2008, 18:50	wanoek	Auf diesen Beitrag antworten »
hm ... das ist ja im grunde ja nur eine andere definition ... mit : $\begin{eqnarray} \varphi(n):=\|\{k\in \mathbb N \| 1\le k\le n, ggT(k,n)=1\}\| \end{eqnarray}$ mein problem ist jetzt die elemente jeder einzelnen dieser mengen abzuzählen ...
23.11.2008, 19:03	AD	Auf diesen Beitrag antworten »
Die Elemente von $\begin{eqnarray} \left\{ k \bigm\| 1\leq k\leq n,\; \operatorname{ggT}(k,n)=d \right\} \end{eqnarray}$ sind sämtlich durch $\begin{eqnarray} d \end{eqnarray}$ teilbar. Da liegt es doch nahe, über $\begin{eqnarray} k=d\cdot k' \end{eqnarray}$ und $\begin{eqnarray} n=d\cdot n' \end{eqnarray}$ eine Bijektion zur Menge $\begin{eqnarray} \left\{ k' \bigm\| 1\leq k' \leq n',\; \operatorname{ggT}(k',n')=1 \right\} \end{eqnarray}$ aufzubauen...
23.11.2008, 20:35	wanoek	Auf diesen Beitrag antworten »
kapier ich nicht ...
23.11.2008, 20:36	AD	Auf diesen Beitrag antworten »
Soll vorkommen, dass manche die Lösung selbst dann nicht erkennen, wenn sie auf dem Silbertablett vor ihnen liegt. Dann streng dich mal an!
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »