Restklassenring (Z)/Einheit/Charakterisierung/Teilerfremd/Fakt mit Beweisklappe

Satz

Genau dann ist ${}a\in \mathbb {Z}$ eine Einheit modulo ${}n$ (d.h. ${}a$ repräsentiert eine Einheit in $\mathbb {Z} /(n)$), wenn ${}a$ und ${}n$ teilerfremd sind.

Beweis

Sind ${}a$ und ${}n$ teilerfremd, so gibt es nach Fakt eine Darstellung der ${}1$, es gibt also ganze Zahlen ${}r,s$ mit

${}ra+sn=1\,.$

Betrachtet man diese Gleichung modulo ${}n$, so ergibt sich ${}ra=1$ in ${}\mathbb {Z} /(n)$. Damit ist ${}a$ eine Einheit mit Inversem ${}a^{-1}=r$.

Ist umgekehrt ${}a$ eine Einheit in ${}\mathbb {Z} /(n)$, so gibt es ein ${}r\in \mathbb {Z} /(n)$ mit ${}ar=1$ in ${}\mathbb {Z} /(n)$. Das bedeutet aber, dass ${}ar-1$ ein Vielfaches von ${}n$ ist, sodass also

${}ar-1=sn\,$

gilt. Dann ist aber wieder ${}ar-sn=1$ und ${}a$ und ${}n$ sind teilerfremd.

$\Box$