A community for students. Sign up today!
Here's the question you clicked on:
 0 viewing
 2 years ago
Prove the multiplicativity of the totient function. For His sake, don't use fields or rings T_T.
 2 years ago
Prove the multiplicativity of the totient function. For His sake, don't use fields or rings T_T.

This Question is Closed

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.2What I mean is I wanna prove this:\[\phi(ab\cdots yz) = \phi(a) \cdot \phi(b) \cdots \phi(y) \cdot \phi(z) \]

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.2If \(\gcd(a,b\cdots,y,z) = 1\)

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.2@amistre64 @sauravshakya @experimentX

sauravshakya
 2 years ago
Best ResponseYou've already chosen the best response.0dw:1361115089981:dw

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.2No... coprime numbers.

sauravshakya
 2 years ago
Best ResponseYou've already chosen the best response.0dw:1361115307691:dwU mean

sauravshakya
 2 years ago
Best ResponseYou've already chosen the best response.0dw:1361115408680:dw

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.2LOL wait, I realized it lol

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.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.

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.2Too lazy to type it out, you get the point.

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.2I realized the proof, but I am pretty lazy at the moment. I'd explain to you how it works.

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.2It 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)

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.2Too lazy to do LaTeX.

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.2Maybe I'd write a whole document on this someday. Not now, just.

sauravshakya
 2 years ago
Best ResponseYou've already chosen the best response.0dw:1361117190858:dwBut how

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.2I 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

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.2Correction dw:1361117896513:dw

terenzreignz
 2 years ago
Best ResponseYou've already chosen the best response.2It 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) = p1, 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)(p1) which is not equal to (p1)(p1) = 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 pq1 of them. (pq  1) But you have to take away all the multiples of p, up to (q1)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 (p1)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!!!

terenzreignz
 2 years ago
Best ResponseYou've already chosen the best response.2I may have been overenthusiastic with that one... my bad :)

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.0that seems okay .. use induction on that.

terenzreignz
 2 years ago
Best ResponseYou've already chosen the best response.2That's where I'm lost, unfortunately :(

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.0i 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.

terenzreignz
 2 years ago
Best ResponseYou've already chosen the best response.2Maybe you can do more with my little result than I'm capable of :)

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.0dw:1361120997117:dw

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.0rest of the number ... say a number z is just a product of distinct prime number, of course it should hold.

terenzreignz
 2 years ago
Best ResponseYou've already chosen the best response.2I wasn't aware of the probability bit that Parth mentioned, so... poor me :( Good thing you guys could make use of it :D

experimentX
 2 years ago
Best ResponseYou've already chosen the best response.0dw:1361121296399:dw

ParthKohli
 2 years ago
Best ResponseYou've already chosen the best response.2@experimentX That was my proof...
Ask your own question
Ask a QuestionFind more explanations on OpenStudy
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
 Engagement 19 Mad Hatter
 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.