Eulersche Funktion

Die Anzahl an $a$ zwischen $0$ und $n$, für die gilt, dass der ggT mit $n$ gleich $1$ ist.

$\phi (n)=\#\{a:0\le a\le n-1,\mathrm{ggT}(a,n)=1\}=\#(\mathbb{Z}/n\mathbb{Z}{)}^{\ast }$

Einfache Implementierung in Python:

def euler(n):
    c = 0
    for a in range(n):
        ggt, _ = ggT(a, n)
        if ggt == 1:
            c += 1
    return c

Dieser Algorithmus ist sehr langsam für großes $n$. Mit dem naiven Faktorisierungsverfahren lässt sich die eulersche Funktion auch wie folgt bestimmen: $\phi (n)={\prod }_i{p}_i^{e_i-1}\left(p_i-1\right)=n\left(1-\frac{1}{p_1}\right)\dots \left(1-\frac{1}{p_r}\right)=n{\prod }_{p\mid n}\left(1-\frac{1}{p}\right)$

Kann auch verwendet werden um zu testen ob eine Zahl $n$ eine Primzahl ist. Man testet: $\phi (n)=n-1.$ Also in Python:

def is_prime(n):
	return euler(n) == n-1

Für $n$ gelten die folgenden Äquivalenzen:

$n\text{ ist Primzahl }⟺\phi (n)=n-1⟺\mathbb{Z}/n\mathbb{Z}\text{ ist Ko¨rper. }$ Körper

Wenn $n$ keine Primzahl ist, dann haben wir $n=ab.$ Damit gilt also in $\mathbb{Z}/n\mathbb{Z}$ , dass $ab=0$ wobei $a\ne 0$ und $b\ne 0$. Es ist also kein Integritätsring