## ParthKohli Group Title Prove the multiplicativity of the totient function. For His sake, don't use fields or rings T_T. one year ago one year ago

1. ParthKohli Group Title

What I mean is I wanna prove this:$\phi(ab\cdots yz) = \phi(a) \cdot \phi(b) \cdots \phi(y) \cdot \phi(z)$

2. ParthKohli Group Title

If $$\gcd(a,b\cdots,y,z) = 1$$

3. ParthKohli Group Title

@amistre64 @sauravshakya @experimentX

4. sauravshakya Group Title

|dw:1361115089981:dw|

5. ParthKohli Group Title

No... coprime numbers.

6. sauravshakya Group Title

|dw:1361115307691:dw|U mean

7. ParthKohli Group Title

No.$\phi(7) = 6$

8. sauravshakya Group Title

|dw:1361115408680:dw|

9. ParthKohli Group Title

Yeah.

10. ParthKohli Group Title

LOL wait, I realized it lol

11. ParthKohli Group Title

$\phi(a) = \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)\cdots\left(1 - \frac{1}{p_n}\right)$And when you multiply all those phis, you get another phi.

12. ParthKohli Group Title

Too lazy to type it out, you get the point.

13. ParthKohli Group Title

I realized the proof, but I am pretty lazy at the moment. I'd explain to you how it works.

14. ParthKohli Group Title

It basically says that if $$a$$ has factors $$a_1,a_2\cdots a_n$$ then phi(a) is obviously (1 - 1/a1)(1 - 1/a2)...(1/an) Same for phi(b) and so on Since a * b ... y * z's set of factors the union of the sets of factors of each a,b....y,z, so the factors are a1,a2...b1,b2.......x1,x2...y1,y2...y_n and the phi of that is (1 - a1)(1 - a2)...(1 - b1)....... = phi(a) * phi(b) ... phi(y) * phi(z)

15. ParthKohli Group Title

Too lazy to do LaTeX.

16. ParthKohli Group Title

Maybe I'd write a whole document on this someday. Not now, just.

17. sauravshakya Group Title

|dw:1361117190858:dw|But how

18. ParthKohli Group Title

I don't remember the proof but it's related to how $$\dfrac{\phi(N)}{N}$$ is the probablity that a number less than or equal to $$N$$ is coprime to it

19. ParthKohli Group Title

Correction |dw:1361117896513:dw|

20. terenzreignz Group Title

It may suffice to show that it is multiplicative for any two distinct prime numbers. First, let's get rid of the case where the prime numbers are the same. Let p and q be distinct prime numbers. It can be shown that T(p) = p-1, for all primes. T(p*p) = Well, consider all numbers less than p squared, and there are p^2 - 1 of them p^2 - 1 But p^2 - 1 = (p+1)(p-1) which is not equal to (p-1)(p-1) = T(p)T(p) Then it doesn't hold for two prime numbers which are the same. Consider T(pq) Well, now consider all positive integers less than pq, and there are pq-1 of them. (pq - 1) But you have to take away all the multiples of p, up to (q-1)p, since these are not coprime with pq, obviously. (pq - 1) - (q - 1) You also have to take away all the multiples of q, up to (p-1)q, since these are not coprime with pq, clearly (pq - 1) - (q - 1) - (p - 1) And everything else will be coprime with pq, since both p and q are prime. = pq -1 - q + 1 - p + 1 = pq - q - p + 1 = (p - 1)(q - 1) = T(p)T(q) It holds for any two distinct prime numbers!!!

21. terenzreignz Group Title

I may have been overenthusiastic with that one... my bad :)

22. experimentX Group Title

that seems okay .. use induction on that.

23. terenzreignz Group Title

That's where I'm lost, unfortunately :(

24. ParthKohli Group Title

Is my proof OK?

25. experimentX Group Title

i didn't read all your post ... i think it should be something like ... if it holds for two prime number, then rest of integers are just product of primes, i should hold for any number.

26. terenzreignz Group Title

Maybe you can do more with my little result than I'm capable of :)

27. experimentX Group Title

|dw:1361120997117:dw|

28. experimentX Group Title

rest of the number ... say a number z is just a product of distinct prime number, of course it should hold.

29. terenzreignz Group Title

I wasn't aware of the probability bit that Parth mentioned, so... poor me :( Good thing you guys could make use of it :D

30. experimentX Group Title

|dw:1361121296399:dw|

31. ParthKohli Group Title

@experimentX That was my proof...