1
$\begingroup$

I have memorized the Euler product formula but don't actually understand the proof of it given in the Wikipedia and in several books.

The formula I am referring to is $$\varphi(n) = n\prod_{p\mid n}\left(1-\frac{1}{p}\right),$$ where $\varphi$ is the Euler totient function.

Is there a particularly intuitive alternative proof? Failing that, can anyone explain the proof, say the one given on Wikipedia here, perhaps by providing motivation for the key steps?

$\endgroup$
2
  • $\begingroup$ I have edited your question; if you feel I have incorrectly interpreted it, please feel free to edit it to your liking. Is there anything in particular you can say you don't understand about the proof on Wikipedia? $\endgroup$
    – Will R
    Aug 9, 2016 at 14:18
  • $\begingroup$ The Wikipedia proof shows the result first for prime powers $n=p^r$, and then uses $\phi(nm)=\phi(n)\phi(m)$ for coprime prime powers $n$ and $m$. This gives the formula - directly and intuitively. Also, the example $n=36$ is given, which helps a lot to see what happens. $\endgroup$ Aug 9, 2016 at 14:33

1 Answer 1

6
$\begingroup$

You can use probability to see this. Let $S = \{1,2, \ldots,n\}.$ The probability that a random number $m$ chosen from $\{1,\ldots,n\}$ is relatively prime to $n$ is $$\frac{\#\{\text{numbers that are co-prime to $n$}\}}{\#\{\text{Total numbers\}}} =\frac{\phi(n)}{n} .$$ This happens precisely when $m$ is not divisible by any of the prime factors of $n$. Now probability that $m$ is divisible by $p$ is $1/p,$ so the probability that $m$ is not divisible by $p$ is $1-\frac{1}{p},$ and you want this to happen all prime divisors of $n.$ So the probability can also be written as $$\prod_{p|n}\left(1-\frac{1}{p}\right).$$ Since both are probabilities for the same event thus $$\frac{\phi(n)}{n}= \prod_{p|n}\left(1-\frac{1}{p}\right).$$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.