Here's the question you clicked on:
ParthKohli
Prove the multiplicativity of the totient function. For His sake, don't use fields or rings T_T.
What I mean is I wanna prove this:\[\phi(ab\cdots yz) = \phi(a) \cdot \phi(b) \cdots \phi(y) \cdot \phi(z) \]
If \(\gcd(a,b\cdots,y,z) = 1\)
@amistre64 @sauravshakya @experimentX
|dw:1361115089981:dw|
No... coprime numbers.
|dw:1361115307691:dw|U mean
|dw:1361115408680:dw|
LOL wait, I realized it lol
\[\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.
Too lazy to type it out, you get the point.
I realized the proof, but I am pretty lazy at the moment. I'd explain to you how it works.
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)
Too lazy to do LaTeX.
Maybe I'd write a whole document on this someday. Not now, just.
|dw:1361117190858:dw|But how
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
Correction |dw:1361117896513:dw|
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!!!
I may have been overenthusiastic with that one... my bad :)
that seems okay .. use induction on that.
That's where I'm lost, unfortunately :(
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.
Maybe you can do more with my little result than I'm capable of :)
|dw:1361120997117:dw|
rest of the number ... say a number z is just a product of distinct prime number, of course it should hold.
I wasn't aware of the probability bit that Parth mentioned, so... poor me :( Good thing you guys could make use of it :D
|dw:1361121296399:dw|
@experimentX That was my proof...