Eulersche Funktion

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

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:

Kann auch verwendet werden um zu testen ob eine Zahl $n$ eine Primzahl ist. Man testet:

Also in Python:

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

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

Körper

Wenn $n$ keine Primzahl ist, dann haben wir

Damit gilt also in

, dass $ab=0$ wobei $a\neq 0$ und $b\neq 0$. Es ist also kein Integritätsring