Eulersche Phi Funktion

Beschreibung

Die Eulersche $\phi$-Funktion $\phi (n)$ gibt die Anzahl der Teilerfremden Zahlen zwischen $1$ und $n$ zurück

Definition

$\phi (n)=|\{k\in \mathbb{Z}|0\le k<n,ggT(k,n)=1\}|$

Eigenschaften

Primzahlen

Für jede Primzahl $p$ kommt als Ergebnis $\phi (p)=p-1$ da jede Zahl Teilerfremd zu einer Primzahl ist

Rechenregeln

Sind $n,m$ teilerfremd und $m,n\ge 2$. Dann gilt: $\phi (mn)=\phi (m)\phi (n)$ Beweis: Auf Grund des chinesischen Restsatzes und der Produkteigenschaft der Einheitengruppe gilt: $\mathbb{Z}/mn\mathbb{Z}\cong (\mathbb{Z}/m\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}{)}^{\times }\cong (\mathbb{Z}/m\mathbb{Z}{)}^{\times }\times (\mathbb{Z}/n\mathbb{Z}{)}^{\times }$ Die Prime Restklassengruppe links enthält $\phi (mn)$, die Menge rechts enthält $\phi (n)\phi (m)$ Elemente.¹

Summatorische Funktion

Siehe Eulersche Phi Funktion

Berechnung

Mit Möbiusschen Umkehrsatz

Der Möbiussche Umkehrsatz gibt eine Möglichkeit, die Summatorische Funktion umzukehren. Tun wir das, erhalten wir: $\varphi (n)={\sum }_{d\mid n}\mu (d)id(\frac{n}{d})=n{\sum }_{d\mid n}\frac{\mu (d)}{d}$

Übungen

McEliece Übung 5-5

Sei $p$ eine Primzahl. Berechne $\varphi (p^n)$. Nach Vorlesung $\varphi (p^n)=(p-1)p^{n-1}$

Das sieht sehr nach Induktion aus. Induktionsanfang $n=1$ $\varphi (p^1)=p-1$ Induktionsschritt: $n+1$ $p^{n+1}={\sum }_{d\mid p^{n+1}}\varphi (d)={\sum }_{d\mid p^n}\varphi (d)+\varphi (p^{p+1})=p^n+\varphi (p^{n+1})⟹=\varphi (p^{p+1})=(p-1)p^n$ Huch, ich habe gar keine Induktion gebraucht…

McElice Übung 6-3

Berechne mit Möbiusschen Umkehrungssatz:

• $\varphi (11)=n{\prod }_{p\mid n}(1-\frac{1}{p})={\prod }_{i=1}^m{p}_i^{e_i-1}(p_i-1)=11-1=10$
• $\varphi (101)=100$
• $\varphi (1001)=6\ast 10\ast 12=720$

Die oben stehende Formel habe ich auf von McElice, ich habe die Herleitung aber nicht ganz verstanden.

McEliece 6-6

Nutze $\varphi (n)=n{\prod }_{p\mid n}(1-\frac{1}{p})={\prod }_{i=1}^m{p}_i^{e_i-1}(p_i-1)$ um folgendes zu zeigen:

a)

$\underset{n\to \infty }{\mathrm{limsup}}\frac{\varphi (n)}{n}=1$ $\underset{n\to \infty }{\mathrm{liminf}}\frac{\varphi (n)}{n}=0$ Zum ersten: Es gibt unendlich viele Primzahlen. Demnach wird immer irgendwann ein $n$ auftauchen für das gilt $\varphi (n)=n-1$. Für die Teilfolge der Primzahlen gilt daher $\underset{n\to \infty }{\mathrm{limsup}}\frac{\varphi (n)}{n}=\underset{n\to \infty }{\mathrm{limsup}}\frac{n-1}{n}=1$ Zum Zweiten: Oben haben wir Primzahlen verwendet, vielleicht können wir hier dann Anti-Primzahlen benutzen. Definiere $P_n:=p_1...p_m$, wobei $p_1...p_{m_n}$ die Primnahlen bezeichnet, die kleiner sind als $n$. Dann ist $\varphi (P_n)=(p_1-1)...(p_{m_n}-1)$. Was ist dann $\underset{n\to \infty }{\mathrm{limsup}}\frac{\varphi (P_n)}{n}$? Bemerkung: Zwischen $2^m$ und $2^{m+1}$ gibt es für $m>1$ immer mindestens eine Primzahl. Das ist das Bertrandsche Postulat.²

Für alle Primzahlen $p_i,...,p_j$ zwischen $2^n$ und $2^{n-1}$ gilt $\frac{p_i-1}{p_i}...\frac{p_j-1}{p_j}\le \frac{2^{n+1}-1}{2^{n+1}}...\frac{2^{n+1}-1}{2^{n+1}}\le \frac{2^{n+1}-1}{2^{n+1}}$ Damit lässt sich eine obere Schranke finden. $\underset{n\to \infty }{\mathrm{limsup}}\frac{\varphi (P_n)}{n}=\underset{n\to \infty }{\mathrm{limsup}}\frac{(p_1-1)...(p_{m_n}-1)}{p_1...p_{m_n}}\le \underset{n\to \infty }{\mathrm{limsup}}{\prod }_{l\in \mathbb{N}athbbN,2^l<p_{m_n}}\frac{2^l-1}{2^l}$ Ich komme nicht drauf, vielleicht mache ich etwas falsch…

b)

Finde das kleinste $n$, sodass $\varphi (n)/n>0,99$. $n$ muss eine Primzahl sein, denn sonst gäbe es eine Zerlegung in $n=p^{m}a$, wobei $p$ eine Primzahl ist und es gilt $\varphi (n)/n<\varphi (p^m)/p^m<\varphi (p)/p$. Das heißt es gab davor schon eine Zahl, deren Phi Funktion größer war. Suche die erste Primzahl, die größer ist als $100$. Diese ist $101$. Damit ist $\varphi (101)/101=100/101>0,99$

c)

Finde das kleinste $n$, sodass $\varphi (n)/n<0,1$. Nach ähnlichem Argument, wie in b), muss $n$ eines dieser $P_n$ aus a) sein. Probiere einfach ein bisschen herum, bis eine Zahl gefunden ist, die gut genug ist:

• $1/2\ast 2/3\ast 4/5\ast 6/7\ast ...$

Ich denke, so etwas müsste ich programmieren, da habe ich aber echt keine Lust drauf.

y

Footnotes

1. Gerkmann - Proposition 9.6 ↩

2. https://de.wikipedia.org/wiki/Bertrandsches_Postulat ↩