Eulersche Phi-Funktion

03.05.2008, 19:07

Eule99

Eulersche Phi-Funktion

Ich soll folgendes zeigen:

$\begin{eqnarray*} 2 \leq n \in \mathbb{N}: \sum_{1 \leq a \leq n, ggT(a,n)=1} a = \frac{1}{2} n \varphi(n) \end{eqnarray*}$

Ich finde da keinen Zusammenhang. Zuerst wollte ich von rechts nach links rechnen. Dazu habe ich es mit Multiplikativität und eindeutiger Primfaktorzerlegung soweit auseinandergeschrieben:

$\begin{eqnarray*} \frac{1}{2} n \varphi(n) = \dots = \frac{1}{2} n \prod_{p \in \mathbb{P}} p^{\nu(n,p)} (1-\frac{1}{p}) \end{eqnarray*}$

Aber wie ich auf diese Summe kommen soll ist mir rätselhaft.

03.05.2008, 19:58

Auf diesen Beitrag antworten »

RE: Eulersche Phi-Funktion
Geh anders vor:

$\begin{eqnarray*} a \end{eqnarray*}$ ist genau dann teilerfremd zu $\begin{eqnarray*} n \end{eqnarray*}$ , wenn $\begin{eqnarray*} (n-a) \end{eqnarray*}$ teilerfremd zu $\begin{eqnarray*} n \end{eqnarray*}$ ist (warum?). Diese Bijektion nutzend - genauer: drüber summierend! - ergibt direkt die gewünschte Aussage.

04.05.2008, 13:36

Eule99

Auf diesen Beitrag antworten »

Danke. Um die Bijektion zu sehen muss man nur den ggT(n-a,n) ausschreiben (also als Produkt...). Da ggT(n,a)=1 sind die Potenzen der Primfaktoren des ausgeschriebenen ggT(n-a,n) alle 0 und damit ggT(n-a,n)=1.

Aber ich habe leider noch ein ähnliches Problem: Man soll auch zeigen, dass

$\begin{eqnarray*} \limsup_{n \to \infty} \frac{\varphi(n)}{n} = 1 \end{eqnarray*}$

ist. Da habe ich auch die Definition der Phi-Funktion eingesetzt und erhalte:

$\begin{eqnarray*} \limsup_{n \to \infty} \prod_{p \mid n} (1- \frac{1}{p}) \overset{?}{=} 1 \end{eqnarray*}$

Es ist wahrscheinlich auch nicht einfacher zu zeigen, dass $\begin{eqnarray*} \limsup_{n \to \infty} \varphi(n) = n \end{eqnarray*}$ ist nehme ich an. Kannst du mir hier auch nochmal helfen?

04.05.2008, 13:41

Auf diesen Beitrag antworten »

Zitat:

Original von Eule99
Danke. Um die Bijektion zu sehen muss man nur den ggT(n-a,n) ausschreiben (also als Produkt...). Da ggT(n,a)=1 sind die Potenzen der Primfaktoren des ausgeschriebenen ggT(n-a,n) alle 0 und damit ggT(n-a,n)=1.

Das geht auch viel, viel einfacher, z.B. mit der Eigenschaft $\begin{eqnarray*} \operatorname{ggT}(u,v) = \operatorname{ggT}(u,v+uw) \end{eqnarray*}$ für beliebige ganze Zahlen $\begin{eqnarray*} u,v,w \end{eqnarray*}$ .

Zitat:

Original von Eule99
Man soll auch zeigen, dass

$\begin{eqnarray*} \limsup_{n \to \infty} \frac{\varphi(n)}{n} = 1 \end{eqnarray*}$

ist. Da habe ich auch die Definition der Phi-Funktion eingesetzt und erhalte:

$\begin{eqnarray*} \limsup_{n \to \infty} \prod_{p \mid n} (1- \frac{1}{p}) \overset{?}{=} 1 \end{eqnarray*}$

Es ist wahrscheinlich auch nicht einfacher zu zeigen, dass $\begin{eqnarray*} \limsup_{n \to \infty} \varphi(n) = n \end{eqnarray*}$ ist nehme ich an.

Letzteres ist falsch, da stets $\begin{eqnarray*} \varphi(n)\leq n-1 \end{eqnarray*}$ gilt. Und das ist zusammen mit der Gleichheit $\begin{eqnarray*} \varphi(p)=p-1 \end{eqnarray*}$ für Primzahlen $\begin{eqnarray*} p \end{eqnarray*}$ auch der Schlüssel zur Lösung.

Neue Frage »

Antworten »

Eulersche Phi-Funktion

Verwandte Themen