Es sei
und
.
Nach
Fakt (3)
gilt
,
sodass also
zu zeigen ist. Betrachte
-
Diese Menge besitzt Elemente, und
,
da ja und teilerfremd sind. Es seien die negativen Elemente aus und die positiven Elemente aus . Es ist
genau dann, wenn
-
ist, was genau für
der Fall ist. Zu jedem
, ,
gibt es also genau Elemente in . Damit hat genau
-
Elemente. Die entsprechende Überlegung liefert, dass genau Elemente besitzt, woraus
-
folgt.