0
$\begingroup$

Is there intuitive proof of Euler's product formula in number theory (not searching for probabilistic proof) which is used to compute Euler's totient function?

$\endgroup$
  • $\begingroup$ What product formula? The one related to the zeta function? $\endgroup$ – Michael Morrow May 21 at 22:20
  • $\begingroup$ @MichaelMorrow the one which is used to compute Euler's totient function $\endgroup$ – 1b3b May 21 at 22:25
  • 5
    $\begingroup$ The phrase "Euler's product formula" means the factorization of the zeta function. That's why you have three answers now all about the zeta function. If you mean the factorization of Euler's totient function, you need to say that in your question, not just hide it in your tags... $\endgroup$ – runway44 May 21 at 22:33
  • 1
    $\begingroup$ At any rate, I'd say the probabilistic proof is the intuitive proof; $\phi(n)/n$ is the chance an integer in $[1,n]$ is coprime to $n$, which is equivalent to not being divisible by any prime divisor of $n$, which are independent events for each prime hence we multiply $(1-1/p)$ factors. This notion of sieving is fundamental to much of number theory and is important to understand. $\endgroup$ – runway44 May 21 at 22:36
  • $\begingroup$ The OP isn't asking about this but for the Euler product I'd like people stop with fancy proofs and use thisone $$\prod_{p \ prime \le k} (1+\sum_{m\ge 1} (p^m)^{-s}) = \sum_{n\ge 1,Lpf(n)\le k} n^{-s}$$ where $Lpf$ is the largest prime factor. It is boring when searching on google, wikipedia, MSE to find only a mess whereas the proof takes one line. $\endgroup$ – reuns May 21 at 22:48
1
$\begingroup$

One intuition uses Inclusion-Exclusion. For example, if $n$ is divisible by three distinct primes $p$, $q$, and $r$, then

$$n-\left({n\over p}+{n\over q}+{n\over r}\right)+\left({n\over pq}+{n\over pr}+{n\over qr} \right)-{n\over pqr}$$

counts all the numbers less than $n$ that are not divisible by $p$, $q$, or $r$, which is to say the numbers that are relatively prime to $n$. But we see that this is equal to the product

$$n\left(1-{1\over p} \right)\left(1-{1\over q} \right)\left(1-{1\over r} \right)$$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Intuitively $$\frac1{1-p_i^{-s}} = 1+p_i^{-s} + \left(p_i^{-s}\right)^2 + \cdots =\left(p_i^0\right)^{-s}+\left(p_i^1\right)^{-s} + \left(p_i^2\right)^{-s} + \cdots$$

so

$$\prod\limits_{i=1}^\infty \frac1{1-p_i^{-s}} \\=\left(\left(2^0\right)^{-s}+\left(2^1\right)^{-s} + \left(2^2\right)^{-s} + \cdots \right) \times \left(\left(3^0\right)^{-s}+\left(3^1\right)^{-s} + \left(3^2\right)^{-s} + \cdots \right) \\ \times \left(\left(5^0\right)^{-s}+\left(5^1\right)^{-s} + \left(5^2\right)^{-s} + \cdots \right) \times \cdots \\=\left(2^0\right)^{-s} \left(3^0\right)^{-s} \left(5^0\right)^{-s}\cdots + \left(2^1\right)^{-s} \left(3^0\right)^{-s} \left(5^0\right)^{-s}\cdots + \left(2^0\right)^{-s} \left(3^1\right)^{-s} \left(5^0\right)^{-s}\cdots \\ + \left(2^2\right)^{-s} \left(3^0\right)^{-s} \left(5^0\right)^{-s}\cdots + \left(2^0\right)^{-s} \left(3^0\right)^{-s} \left(5^1\right)^{-s}\cdots + \cdots \\ = \left(2^0 3^0 5^0\right)^{-s} +\left(2^1 3^0 5^0\right)^{-s} +\left(2^0 3^1 5^0\right)^{-s} +\left(2^2 3^0 5^0\right)^{-s} +\left(2^0 3^0 5^1\right)^{-s} +\cdots \\ = 1^{-s} + 2^{-s} + 3^{-s} +4^{-s} +5^{-s} + \cdots \\ = \sum\limits_{n=1}^\infty \frac{1}{n^s}$$

though for a proof you will want to use convergence and the fundamental theorem of arithmetic

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Presumably you mean $\phi(n)=n\prod_{p|n}(1-1/p)$. Well, I think the best intuition is to understand it.

First, let's look at $\phi(p^n)$. It's easy to see that you can multiply $p$ with any number less than $p^{n-1}$, to get precisely all the numbers less than $p^n$ not relatively prime to $p^n$. Thus we get $\phi(p^n)=p^n-p^{n-1}=p^n(1-1/p)$.

From here all we need is the content of a very famous theorem, called the Chinese Remainder Theorem. It implies that the totient function is multiplicative. That is, when $(m,n)=1$, we have $\phi(mn)=\phi(m)\phi(n)$. As to CRT, it is not that difficult given Bezout's identity.

From these two facts the result follows.

| cite | improve this answer | |
$\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.