Beweis
Sind
und
teilerfremd,
so gibt es nach
Fakt
eine Darstellung der
, es gibt also ganze Zahlen
mit
-
![{\displaystyle {}ra+sn=1\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/53a6fef44b385bf64502b33656fa15503809abf9)
Betrachtet man diese Gleichung modulo
, so ergibt sich
in
. Damit ist
eine Einheit mit Inversem
.
Ist umgekehrt
eine Einheit in
, so gibt es ein
mit
in
. Das bedeutet aber, dass
ein Vielfaches von
ist, so dass also
-
![{\displaystyle {}ar-1=sn\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d3d5cefe5548b17d5c244d7051e9b1a9a8e289d)
gilt. Dann ist aber wieder
und
und
sind teilerfremd.