# Prime Factorization Proof

I’ve been working through some number theory proofs and have encountered a problem that’s giving me trouble. The proof involves Euler’s phi function and basically re-writing it in an alternative form. So I know that Euler’s phi function can be written as:

$$\phi(n) = n \prod_{p | n, \text{p is prime}} ( 1 - \frac{1}{p})$$

But let's says the prime factorization of n can be written as $p^{a_1}_1 \cdot p^{a_2}_2 \ldots \cdot p_{m-1} \cdot p^{a_m}_{m}$ where each is a distinct prime. How would you shouw that:

$$\phi(n) = p^{a_1 - 1}_1 \cdot p^{a_2 - 1}_2 \ldots \cdot p^{a_m - 1}_{m} \cdot \prod^{m}_{i = 1} (p_i -1)$$

So far just tried tinkering a bit with the original definition, but have failed thus far.

• $p^a(1-\frac1p) = p^{a-1}(p-1)$. – lhf Feb 20 '13 at 0:41

To prove it, start by showing that $\phi$ is multiplicative, i.e., that if $\gcd(m, n) = 1$ then $\phi(m n) = \phi(m) \phi(n)$. The proof of this goes through the chinese remainder theorem, the pairs of residues modulo $m$ and $n$ that are relatively prime to each are in a biyection with the residues modulo $m n$ that are relatively prime to the later.
Then to prove $\phi(p^k) = p^{k - 1} (p - 1)$ for $p$ prime, note that the numbers that are not relatively prime to $p^k$ are exactly the $p^{k - 1}$ multiples of $p$ from 1 to $p^k$, so $\phi(p^k) = p^k - p^{k - 1}$.