To make this easy to follow, suppose we're dealing with , the standard residue system modulo . Given any composite, we're always guaranteed two residues with this property since and .

Let be a residue modulo (where ) with and let . Then by Euler's Theorem. Keeping in mind that when , we see that . Thus, is a residue that satisfies this property. Consequently, is also another residue. This one generates a residue different from since we required and it can't generate ; if it did, then , which isn't possible given the restrictions we made on the problem.

This shows that we are guaranteed four different residues modulo with this property. We then allow for the possibility of more residues as we allow to increase.

Does this make sense?