04 Euler

$\phi (m)=|{\mathbb{Z}}_m^{\ast }|$ (Anzahl Teilerfremd)

$\phi (11)=10$ $\phi (12)=4$

1 zählt dazu ;) z.B. $\phi (21)=(3-1)(7-1)=2\cdot 6=12$

Aber $\phi (1)=1$

Wenn p prim, p und q teilerfremd

Rechenregeln

• $\phi (p)=p-1$
• $\phi (p^i)=p^i-\frac{p^i}{p}=p^{i-1}(p-1)$ (jede p-te zahl ist nicht teilerfremd)
• $\phi (p\cdot q)=\phi (p)\cdot \phi (q)$
• $\phi (1)=1$
• $p^{\phi (q)}{\equiv }_{q}1$

The number of generators for the cyclic group ${\mathbb{Z}}_{49}$ is $\phi (49)=42$. The number of generators of ${\mathbb{Z}}_{49}^{\ast }$ is $\phi (\underline{42})=12$. An element is a generator, if the gcd of the Gruppenordnung and the element is 1.

Satz von Euler

Rest berechnen

→ siehe auch Zahlentheorie

Transclude of Zahlentheorie#beispiele-für-restklassen