# Is this a valid proof of Euler's product formula for the totient function?

I will attempt the proof using induction. But first, a lemma:

Lemma 1: If $$n = p^{\alpha}$$, where $$p$$ is prime and $$\alpha\in\mathbb{N}$$, then $$\phi(n) = n(1-\frac{1}{p})$$.

$$\underline{Proof}$$: We wish to count the number of numbers from 1 to $$n$$ that are coprime with $$n$$. We can do this by taking $$n$$ and subtracting off the ones that aren't coprime with $$n$$. The ones that aren't are the mutiples of $$p$$, namely $$p, 2p, 3p, \dots, n-p$$. How many multiples of $$p$$ go into $$n$$? Precisely $$\frac{n}{p}$$. We therefore have

$$\phi(n) = n - \frac{n}{p} = n(1-\frac{1}{p})$$, as required. $$\hspace{9.5cm} \square$$

Lemma 1 tells us that the formula for $$\phi(n)$$ is invariant under any prime factors of $$n$$ having powers. Therefore, it suffices to prove the formula for when $$n$$ consists only of distinct factors. So suppose that $$n$$ is composite with prime factorization $$n = p_{1}p_{2}\dots{p_{r}}$$, where $$r\in\mathbb{N}$$ and each factor is distinct. Then $$\phi(n) = n\prod\limits_{i=1}^{r}(1-\frac{1}{p_{i}})$$.

$$\underline{Proof}$$: For $$S(1)$$: $$n = p_{1} \Longrightarrow \phi(n) = p_{1} - 1 = p_{1}(1-\frac{1}{p_{1}}) = n(1-\frac{1}{p_{1}})$$. Therefore true for $$S(1)$$.

Assume true for $$S(k)$$, for some $$k\in\mathbb{N}$$.

For $$S(k+1)$$: The value of $$\phi(n)$$ is equal to the number of primitive $$n$$-th roots of unity. That is, the primitive roots of the equation $$z^{n} - 1 = 0 \Longrightarrow (z^{p_{k+1}})^{m} = 1$$, where $$m = p_{1}\dots{p_{k}}$$.

Using $$S(k)$$, there are $$m\prod\limits_{i=1}^{k}(1-\frac{1}{p_{i}})$$ primitive $$m$$-th roots of unity in the variable $$z^{p_{k+1}}$$. Let $$\omega$$ be one of these roots. Then we have $$z^{p_{k+1}} = \omega \Longrightarrow \Big(\frac{z}{\omega^{\frac{1}{p_{k+1}}}}\Big)^{p_{k+1}} = 1$$. Since $$p_{k+1}$$ is prime, there are precisely $$p_{k+1}-1$$ primitive solutions for $$\frac{z}{\omega^{\frac{1}{p_{k+1}}}}$$ and hence for $$z$$. And this occurs for each of the $$m\prod\limits_{i=1}^{k}(1-\frac{1}{p_{i}})$$ possible choices of $$\omega$$. Therefore, we multiply the former with the latter to find the total number of primitive roots, giving

$$\phi(n) = (p_{k+1}-1)\cdot m\prod\limits_{i=1}^{k}(1-\frac{1}{p_{i}}) = mp_{k+1}\prod\limits_{i=1}^{k+1}(1-\frac{1}{p_{i}}) = n\prod\limits_{i=1}^{k+1}(1-\frac{1}{p_{i}})$$.

Therefore true for $$S(k+1)$$, and hence this is true for all of $$r \in\mathbb{N}. \hspace{5cm} \square$$

Is my proof correct?

• It would be reasonable if you'd write what you're trying to prove at the very beginning of the post...Function's aren't provable. And such a proof by induction in this case should be, imo, on the number of prime divisors of $\;n\;$ (or of different prime divisors), not induction on $\;n\;$ ... – DonAntonio Feb 20 at 11:14
• What I meant was that I was attempting to prove the formula for the function. Sorry if that wasn't clear. And I was doing induction on $r$, not $n$, which is the number of divisors. – A.Abbas Feb 20 at 11:17
• "Lemma 1 tells us that the formula for $ϕ(n)$ is invariant under any prime factors of $n$ having powers." What does it mean and why? – user Feb 20 at 11:21
• That was meant to mean that the formula is the same regardless of the value of $\alpha$, since $\alpha$ does not appear in the expression for $\phi(n)$. – A.Abbas Feb 20 at 11:24
• It is not yet a reason to expect that $\alpha$ will not appear if some other prime divisors of $n$ are present. – user Feb 20 at 11:27