In Euler's Totient function, the calculation is basically $$n\prod \left(1-\frac{1}{p_i}\right)$$ where $n=\prod p_i^{\alpha_i}$

How do we prove it in this fashion? We observe that among every $p_i$ consecutive integers, there are $p_i-1$ coprimes. But when there are more than one prime, I can't apply this idea.

See, if primes are 2 and 5 and n=10. Then, we can say that four-fifth of 10 are coprime with 10 wrt 5. And they're 1,2,3,4,6,7,9. And then, half of these (really? They aren't consecutive?) are coprime to 2. And so the answer is 10(4/5)(1/2). But the proof isn't concrete because we are getting non consecutive numbers.

Can you show a proof using this idea? (Please don't show the proof using principle of exclusion inclusion or the multiplicative functions. I don't want any of those number theoretic proofs or even using the fact that Chinese Remainder Theorem will maintain the isomorphism and stuffs)

  • $\begingroup$ $\phi$ is a multiplicative function. Whether you want to say you are using this fact or not, the product stems from that fact. The best you can do is just prove why you can split $\phi(n)$ into a product over its prime factors, which is essentially a proof of why $\phi$ is a multiplicative function. $\endgroup$ – Manuel Guillen Mar 25 '18 at 20:36
  • $\begingroup$ @ManuelGuillen But what about that? That every p-1 out of p consecutive numbers are coprimes? Can you do a proof that way? Yes, I understand what you mean but that idea seems different and not directly linked to this method $\endgroup$ – Mathejunior Mar 25 '18 at 20:39
  • $\begingroup$ Can anyone have a look at this? Thank you! $\endgroup$ – Mathejunior Mar 26 '18 at 2:41

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.