Another proof (back to the original ) :
Let where is the greatest integer dividing such that .
Adding to this that , we have that and must share the exact same prime divisors (and too) . Thus in fact, any number coprime to is coprime to and viceversa. It follows then that (*).
Finally since and are coprime, we have: , and since we are done.
In each set for we have exactly numbers coprime to . These sets form a partition of so indeed .