Euler's Phi Function

**GoldendoodleMom** · March 26th 2009, 03:52 PM

Prove that if the integer n has r distinct odd prime factors, then 2^r |
Ф(n).

**o_O** · March 26th 2009, 04:42 PM

Suppose $n \geq 3$ has $r$ odd prime factors.

By definition, we have: $\phi (n) = n \cdot \prod_{p \mid n} \left(\frac{p-1}{p}\right) = \frac{n}{\displaystyle \prod_{p \mid n} p} \cdot \prod_{p \mid n} (p-1)$

We know that the fraction is an integer and that since $p$ is prime, then $p-1$ is even. So for every odd prime dividing $n$ , there is a corresponding even number (particularly $p-1$ ) that divides $\phi (n)$ . Since there are $r$ odd primes, the conclusion follows.

Thread: Euler's Phi Function

LinkBack

Thread Tools

Display

Euler's Phi Function

Similar Math Help Forum Discussions

Euler function

Euler Function phi(n)

Euler's phi function

Euler's phi function

Euler phi-Function

Search Tags