Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

ParthKohli

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

  • one year ago
  • one year ago

  • This Question is Closed
  1. ParthKohli
    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) \]

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

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

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

    @amistre64 @sauravshakya @experimentX

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

    |dw:1361115089981:dw|

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

    No... coprime numbers.

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

    |dw:1361115307691:dw|U mean

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

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

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

    |dw:1361115408680:dw|

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

    Yeah.

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

    LOL wait, I realized it lol

    • one year ago
  11. ParthKohli
    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.

    • one year ago
  12. ParthKohli
    Best Response
    You've already chosen the best response.
    Medals 2

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

    • one year ago
  13. ParthKohli
    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.

    • one year ago
  14. ParthKohli
    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)

    • one year ago
  15. ParthKohli
    Best Response
    You've already chosen the best response.
    Medals 2

    Too lazy to do LaTeX.

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

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

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

    |dw:1361117190858:dw|But how

    • one year ago
  18. ParthKohli
    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

    • one year ago
  19. ParthKohli
    Best Response
    You've already chosen the best response.
    Medals 2

    Correction |dw:1361117896513:dw|

    • one year ago
  20. terenzreignz
    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!!!

    • one year ago
  21. terenzreignz
    Best Response
    You've already chosen the best response.
    Medals 2

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

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

    that seems okay .. use induction on that.

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

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

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

    Is my proof OK?

    • one year ago
  25. experimentX
    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.

    • one year ago
  26. terenzreignz
    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 :)

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

    |dw:1361120997117:dw|

    • one year ago
  28. experimentX
    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.

    • one year ago
  29. terenzreignz
    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

    • one year ago
  30. experimentX
    Best Response
    You've already chosen the best response.
    Medals 0

    |dw:1361121296399:dw|

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

    @experimentX That was my proof...

    • one year ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.