ParthKohli
  • ParthKohli
Prove the multiplicativity of the totient function. For His sake, don't use fields or rings T_T.
Mathematics
jamiebookeater
  • jamiebookeater
See more answers at brainly.com
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this
and thousands of other questions

ParthKohli
  • ParthKohli
What I mean is I wanna prove this:\[\phi(ab\cdots yz) = \phi(a) \cdot \phi(b) \cdots \phi(y) \cdot \phi(z) \]
ParthKohli
  • ParthKohli
If \(\gcd(a,b\cdots,y,z) = 1\)
ParthKohli
  • ParthKohli

Looking for something else?

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

More answers

anonymous
  • anonymous
|dw:1361115089981:dw|
ParthKohli
  • ParthKohli
No... coprime numbers.
anonymous
  • anonymous
|dw:1361115307691:dw|U mean
ParthKohli
  • ParthKohli
No.\[\phi(7) = 6\]
anonymous
  • anonymous
|dw:1361115408680:dw|
ParthKohli
  • ParthKohli
Yeah.
ParthKohli
  • ParthKohli
LOL wait, I realized it lol
ParthKohli
  • ParthKohli
\[\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
  • ParthKohli
Too lazy to type it out, you get the point.
ParthKohli
  • ParthKohli
I realized the proof, but I am pretty lazy at the moment. I'd explain to you how it works.
ParthKohli
  • ParthKohli
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)
ParthKohli
  • ParthKohli
Too lazy to do LaTeX.
ParthKohli
  • ParthKohli
Maybe I'd write a whole document on this someday. Not now, just.
anonymous
  • anonymous
|dw:1361117190858:dw|But how
ParthKohli
  • ParthKohli
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
ParthKohli
  • ParthKohli
Correction |dw:1361117896513:dw|
terenzreignz
  • terenzreignz
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!!!
terenzreignz
  • terenzreignz
I may have been overenthusiastic with that one... my bad :)
experimentX
  • experimentX
that seems okay .. use induction on that.
terenzreignz
  • terenzreignz
That's where I'm lost, unfortunately :(
ParthKohli
  • ParthKohli
Is my proof OK?
experimentX
  • experimentX
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.
terenzreignz
  • terenzreignz
Maybe you can do more with my little result than I'm capable of :)
experimentX
  • experimentX
|dw:1361120997117:dw|
experimentX
  • experimentX
rest of the number ... say a number z is just a product of distinct prime number, of course it should hold.
terenzreignz
  • terenzreignz
I wasn't aware of the probability bit that Parth mentioned, so... poor me :( Good thing you guys could make use of it :D
experimentX
  • experimentX
|dw:1361121296399:dw|
ParthKohli
  • ParthKohli
@experimentX That was my proof...

Looking for something else?

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