*Proof*.
If

and

then there exists a unique

. with

and

(by
theorem (

8.1)). Such a

is prime to

, since it is
prime to

and to

. Conversely, any

arises in
this way, from the

and

such that

,

. Thus

as required.

*Proof*.
Multiply each residue

by

and reduce modulo

. The

numbers thus obtained are prime to

and are all distinct.
So the

new numbers are just

in a
different order. Therefore

Since

we can divide to obtain the
result.

**Remark 6.9.5** (For algebraists)
This can also be seen as a consequence of Lagrange's Theorem, since

is a group under multiplication modulo

.