Eulerfunktion & Prinzip der Inklusion und Exklusion

17.07.2014, 08:19	Z3R0	Auf diesen Beitrag antworten »
Eulerfunktion & Prinzip der Inklusion und Exklusion Meine Frage: Hallo liebes Mathe Board, ich bin gerade mit algorithmischer Mathematik im Studium beschäftigt und da meine Mathekenntnisse ein wenig eingerostet sind versuche ich mir alles an Beispielen ein bisschen bildhafter darzustellen. Dabei hab ich jetzt folgende Schwierigkeiten: $\begin{eqnarray} \varphi(n) = n\sum\limits_{I\subseteq \{1,2,...,r\}}(-1)^{\|I\|}\frac{1}{\prod \limits_{i\in I}^{}p_{i}} \end{eqnarray}$ Wenn mir das jemand an einem oder am besten 2 unterschiedlichen Beispielen mit Zahlen erklären könnte? Z.b. 15 & 18... Meine Ideen: Das Grundprinzip habe ich verstanden: $\begin{eqnarray} \varphi(18)=18(1-\frac{1}{2})(1-\frac{1}{3})=6 \end{eqnarray}$ bloß ich weiß nicht, wie ich das in der oben genannten Formel anwenden muss... Danke für eure Hilfe! Gruß Christian
17.07.2014, 10:37	Huggy	Auf diesen Beitrag antworten »
RE: Eulerfunktion & Prinzip der Inklusion und Exklusion Unten hast du die übliche Formel zur Berechnung von $\begin{eqnarray} \varphi (n) \end{eqnarray}$ benutzt. Die obige Formel ist aber eine andere. Bei der obigen Formel Formel nummeriert man zunächst die Primfaktoren von n von 1 bis r durch und bildet die Indexmenge $\begin{eqnarray} M=\{1, ..., r\} \end{eqnarray}$ . Summiert wird dann über alle Teilmengen $\begin{eqnarray} I \subseteq M \end{eqnarray}$ . Sei n = 18. n hat die Primfaktoren $\begin{eqnarray} p_1=2 \end{eqnarray}$ und $\begin{eqnarray} p_2=3 \end{eqnarray}$ . Es ist also $\begin{eqnarray} M = \{1,2\} \end{eqnarray}$ . Die Teilmengen von M sind: $\begin{eqnarray} \emptyset , \quad \{1\}, \quad \{2\},\quad \{1,2\} \end{eqnarray}$ Das ergibt für die Formel: $\begin{eqnarray} \varphi (n)=n \left ( (-1)^{\|\emptyset \|} \frac {1}{1} +(-1)^{\|\{1\}\|} \frac {1}{2}+(-1)^{\|\{2\}\|} \frac {1}{3} +(-1)^{\|\{1,2\}\|} \frac {1}{2 \cdot 3}\right) =18 \left (1-\frac {1}{2}-\frac {1}{3}+\frac {1}{6}\right ) =6 \end{eqnarray}$
17.07.2014, 11:33	Z3R0	Auf diesen Beitrag antworten »
Ah, jetzt hat es Klick gemacht! Besten Dank, das hat mir echt weiter geholfen!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »