Eulersche Phi Funktion

28.04.2018, 13:51	Sarah160695	Auf diesen Beitrag antworten »
Eulersche Phi Funktion Meine Frage: Zu zeigen: n hat r ungerade Primteiler, so gilt $\begin{eqnarray} 2^{r} \end{eqnarray}$ teilt n) Meine Ideen: Zunächst kann man sagen die Menge aller Teiler von n sind {1, p1,..., pr,n) Dann ist mein Ansatz: $\begin{eqnarray} phi(n) = n(1-\frac{1}{p1}) ...(1-\frac{1}{pr}) \end{eqnarray*}$ Ich bin gerade nicht fähig das irgendwie umzuschreiben. Wie kann ich das jetzt umformen, damit klar wird 2^{r} teilt dieses Produkt?
28.04.2018, 14:04	HAL 9000	Auf diesen Beitrag antworten »
Na vielleicht einfach $\begin{eqnarray} \varphi(n) = \frac{n}{p_1\cdot p_2\cdot \ldots \cdot p_r}\cdot \left(p_1-1\right)\left(p_2-1\right)\cdot \ldots \cdot \left(p_r-1\right) \end{eqnarray}$ : Für ungerade Primzahlen $\begin{eqnarray} p_k \end{eqnarray}$ ist $\begin{eqnarray} \left(p_k-1\right) \end{eqnarray}$ jeweils gerade...
28.04.2018, 14:12	Sarah160695	Auf diesen Beitrag antworten »
ahh okay und dann sind alle Faktoren (p-1) gerade und davon habe ich r viele faktoren deswegen teilt 2^r mein phi(n). Richtig?
28.04.2018, 14:14	HAL 9000	Auf diesen Beitrag antworten »
Ja. Eine kleine Unsauberkeit ist noch in deinen Überlegungen: Es könnte durchaus auch $\begin{eqnarray} n \end{eqnarray}$ gerade sein, d.h. auch den Primfaktor 2 enthalten. In dem Fall stimmt deine $\begin{eqnarray} \varphi \end{eqnarray}$ -Formel nicht, aber die Grundidee des Nachweises klappt natürlich auch in diesem Fall.
28.04.2018, 14:22	Sarah160695	Auf diesen Beitrag antworten »
Die Unsauberkeit sehe ich gerade nicht. Wir hatten diese Formel in der Vorlesung für beliebige n definiert nicht nur für ungerade n ??
28.04.2018, 14:26	HAL 9000	Auf diesen Beitrag antworten »
$\begin{eqnarray} p_1,\ldots,p_r \end{eqnarray}$ sind aber nur die ungeraden Primfaktoren von $\begin{eqnarray} n \end{eqnarray}$ . Du tust aber so, als wären das alle. Vielleicht macht dir ein Beispiel deinen Fehler klar: $\begin{eqnarray} n=14 \end{eqnarray}$ hat nur einen ungeraden Primfaktor, das ist $\begin{eqnarray} p_1=7 \end{eqnarray}$ , es ist somit $\begin{eqnarray} r=1 \end{eqnarray}$ . Nun ist aber $\begin{eqnarray} \varphi(14)=6 \end{eqnarray}$ , während du sagst $\begin{eqnarray} \varphi(14) \stackrel{?}{=} \frac{n}{p_1} (p_1-1) = \frac{14}{7} (7-1) = 12 \end{eqnarray}$ . Und das ist nun mal falsch.
Anzeige

28.04.2018, 14:37	Sarah160695	Auf diesen Beitrag antworten »
ahh okay sorry da stand ich auf dem schlauch. Das heißt ich muss in dem Produkt noch mehr Faktoren hinzunehmen. Diese sind dann aber (p-1) ungerade. Aber änder dann ja nichts an dem Schluss dass ich r gerade Fakoren habe und deswegen den Teiler 2^r. $\begin{eqnarray} phi(n) = n(1-\frac{1}{p1})...(1-\frac{1}{pr})(1-\frac{1}{ps})...(1-\frac{1}{pq} )<br /> = \frac{n}{p1...pq} (p1-1)...(pr-1)(ps-1)...(pq-1) \end{eqnarray*}$ Dabei sind die Faktoren (p1-1) bis (pr-1) gerade. Von diesen geraden Faktoren gibt es r Stück. Daraus folgt die Teilbarkeit durch 2^r.
28.04.2018, 14:41	HAL 9000	Auf diesen Beitrag antworten »
Jetzt übertreibst du gleich wieder: Es gibt nur eine gerade Primzahl, nämlich $\begin{eqnarray} p=2 \end{eqnarray}$ , und die ist in $\begin{eqnarray} n \end{eqnarray}$ drin oder nicht. Letzteren Fall hast du oben diskutiert, während in ersterem Fall dann abweichend $\begin{eqnarray} \varphi(n) = \frac{n}{{\color{red}2\cdot} p_1\cdot p_2\cdot \ldots \cdot p_r}\cdot \left(p_1-1\right)\left(p_2-1\right)\cdot \ldots \cdot \left(p_r-1\right) \end{eqnarray}$ gilt, was die sonstige Argumentation in keinster Weise beeinträchtigt.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »