Let be a natural number, such that . Let be a reduced residue system for . Prove that:

Let . Modulo , we have , because is coprime to . Therefore,

But is also coprime to so we can divide that equivalence by . This gives

which is what we wanted to prove.