Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Eulersche Phi-Funktion gerade für n > 2?

Eulersche Phi-Funktion gerade für n > 2?

Universität / Fachhochschule

Gruppen

Ringe

Tags: eulersch, eulersche Phi-Funktion, Gruppen, phi-funktion, Ring

Dreemer aktiv_icon

15:41 Uhr, 09.12.2019

Hallo,

ich habe mir vor kurzem einen Eintrag in Wikipedia über die Eulersche Phi-Funktion angeschaut und mich interessiert die folgende Anmerkung:

"

φ (n)

ist für

n > 2

stets eine gerade Zahl. "

Ich würde gerne wissen, wie diese Eigenschaft zustande kommt.
Ich weiß soweit, dass

φ (n)

die Anzahl der zu

n

teilerfremden Zahlen

x

mit

x \leq n

beschreibt, weiß aber nicht, wie man damit ansetzen kann.

Liebe Grüße

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

HAL9000

16:22 Uhr, 09.12.2019

Eine relative einfache Erklärung:

Für

k

mit

1 \leq k < \frac{n}{2}

ist

k

genau dann zu

n

teilerfremd, wenn dies auch auf

(n - k)

zutrifft. Die Zahl

\frac{n}{2}

selbst muss nun zum einen nur für gerade

n

betrachtet werden, und sie ist aber auch in diesen Fällen für kein gerades

n > 2

n

teilerfremd, genauer gesagt ist dann ja

ggT (n, \frac{n}{2}) = \frac{n}{2} > 1

.

Durch diese Paarzuordnung

(k, n - k)

ist klar, dass die Anzahl der zu

n

teilerfremden Zahlen im Bereich

1 \dots n

gerade sein muss.

Dreemer aktiv_icon

16:38 Uhr, 09.12.2019

Hallo,

ich danke schon mal für die schnelle Rückmeldung. Ich verstehe nur nicht, warum für

k

mit

1 \leq k < \frac{n}{2}

die oben genannte Äquivalenz gilt. Und die Paarzuordnung

(k, n - k)

macht es mir auch nicht wirklich klar, warum dann

φ (n)

gerade ist.

Liebe Grüße

HAL9000

16:51 Uhr, 09.12.2019

Dann vergiss es - wenn ich das noch lang und breit erklären muss, dann ist es mit der Einfachheit vorbei. Dann geh lieber algebraisch über

φ (p^{k}) = (p - 1) p^{k - 1}

usw.

Dreemer aktiv_icon

18:09 Uhr, 09.12.2019

Hallo,

ich schreibe mal eben meine Ideen auf:

Sei

n \in ℕ

. Zeige nun:

\forall n \geq 3 : φ (n)

ist gerade.

Fall

1 : n

ist prim. Dann gilt

φ (n) = n - 1

. Da

n

als Primzahl aber ungerade ist, folgt, dass

n - 1 = φ (n)

gerade ist.

Fall

2 : n

ist nicht prim.
Dann lässt sich

n

eindeutig in Primfaktoren zerlegen in der Form

n = p_{1}^{r_{1}} \cdot p_{2}^{r_{2}} \dots p_{k}^{r_{k}}, r_{i} \in ℕ, i \in {1, \dots, k}

und

p_{i} \neq p_{j} \forall i \neq j

.
Daraus folgt dann ja:

φ (n) = φ (p_{1}^{r_{1}} \cdot p_{2}^{r_{2}} \dots p_{k}^{r_{k}}) = φ (p_{1}^{r_{1}}) φ (p_{2}^{r_{2}}) \dots φ (p_{k}^{r_{k}}) = (p_{1}^{r_{1}} - p_{1}^{r_{1} - 1}) \dots (p_{k}^{r_{k}} - p_{1}^{r_{k} - 1})

= p_{1} p_{2} \dots p_{k} (1 - \frac{1}{p_{1}}) \dots (1 - \frac{1}{p_{k}}) = n (1 - \frac{1}{p_{1}}) \dots (1 - \frac{1}{p_{k}})

.

Ab diesem Punkt komme ich nicht mehr weiter. Ist der Ansatz in Ordnung? Falls nein, wo sollte ich eher ansetzen?

HAL9000

18:21 Uhr, 09.12.2019

Ja, ist aber nach meinem Empfinden total überdimensioniert. Ich würde so rangehen:

1.Fall:

n

enthält einen ungeraden Primfaktor

p

Dieser sei genau

r

-mal in

n

enthalten, es ist dann

n = p^{r} \cdot m

mit einem

m

, das nicht durch

p

teilbar ist. Damit ist dann

φ (n) = φ (p^{r}) \cdot φ (m) = (p - 1) p^{r - 1} \cdot φ (m)

durch die gerade Zahl

(p - 1)

, und somit auch durch 2 teilbar.

2.Fall:

n

ist eine Zweierpotenz, d.h.,

n = 2^{r}

, wegen

n > 2

ist

r \geq 2

.

Hier ist

φ (2^{r}) = 2^{r - 1}

auf jeden Fall ja auch gerade.

Trotzdem finde ich den ersten Beweis oben viel schöner, weil weniger formellastig. Allerdings muss man bei dem bereit sein, über Teilerfremdheit ein wenig nachzudenken, und das bist du leider nicht.

Dreemer aktiv_icon

18:31 Uhr, 09.12.2019

Hallo,

danke nochmal für die schnelle Rückmeldung und den Notationsvorschlag. Das macht das ganze natürlich übersichtlicher. Ich kann mir vorstellen, dass die Angehensweise über die Teilerfremdheit auch schön ist, aber - wie schon erwähnt - bin ich noch nicht tief genug in der Materie, um es perfekt nachzuvollziehen.

Liebe Grüße

1489576

1489547

	Status: nicht eingeloggt	Noch nicht registriert?