Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

ParthKohli

  • 3 years ago

Prove the multiplicativity of the totient function. For His sake, don't use fields or rings T_T.

  • This Question is Closed
  1. ParthKohli
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  3. ParthKohli
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    @amistre64 @sauravshakya @experimentX

  4. sauravshakya
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1361115089981:dw|

  5. ParthKohli
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    No... coprime numbers.

  6. sauravshakya
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1361115307691:dw|U mean

  7. ParthKohli
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    No.\[\phi(7) = 6\]

  8. sauravshakya
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1361115408680:dw|

  9. ParthKohli
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Yeah.

  10. ParthKohli
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    LOL wait, I realized it lol

  11. ParthKohli
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    \[\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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  13. ParthKohli
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  14. ParthKohli
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Too lazy to do LaTeX.

  16. ParthKohli
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  17. sauravshakya
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1361117190858:dw|But how

  18. ParthKohli
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Correction |dw:1361117896513:dw|

  20. terenzreignz
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  22. experimentX
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    that seems okay .. use induction on that.

  23. terenzreignz
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  24. ParthKohli
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Is my proof OK?

  25. experimentX
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

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

  27. experimentX
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1361120997117:dw|

  28. experimentX
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  29. terenzreignz
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1361121296399:dw|

  31. ParthKohli
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    @experimentX That was my proof...

  32. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy