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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .