Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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).$$
