Prove that if the integer n has r distinct odd prime factors, then 2^r |
Ф(n).
Suppose has odd prime factors.
By definition, we have:
We know that the fraction is an integer and that since is prime, then is even. So for every odd prime dividing , there is a corresponding even number (particularly ) that divides . Since there are odd primes, the conclusion follows.