1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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\;$ ... $\endgroup$ – DonAntonio Feb 20 at 11:14
  • $\begingroup$ 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. $\endgroup$ – A.Abbas Feb 20 at 11:17
  • $\begingroup$ "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? $\endgroup$ – user Feb 20 at 11:21
  • $\begingroup$ 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) $. $\endgroup$ – A.Abbas Feb 20 at 11:24
  • 1
    $\begingroup$ It is not yet a reason to expect that $\alpha$ will not appear if some other prime divisors of $n$ are present. $\endgroup$ – user Feb 20 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.