Proof that the Totient Function is Multiplicative

[@paul21353]

Your proof has the great quality of not only proving the multiplicativity of phi, after seeing this proof you totally understand why this property is the way it is. Nobody who saw this proof will ever forget it. Chapeau!!👍

[@alokkumarthakur4141]

I would like to add a summary to the proof provided in the video for easier understanding : Define A = set of numbers coprime to ab and lying between 1 and ab. Define B = cross product of phi(a) and phi(b). (Only here, I am abusing the notation of phi(n) to denote the set of numbers coprime to n and lying in {1,2,3,...,n}.) Now, consider the function f : A --> B, defined by f(x) = (x mod a, x mod b). 1) f(x) is shown to be an into function 2) every element of B is shown to have atleast one preimage in A by chinese remainder theroem, implying f is surjective. 3) every element of B is shown to have a unique preimage in A by chinese remainder theroem. Now, no two elements in the codomain can have the same preimage because then f(x) would not remain a valid function. But we know that f(x) is a valid function because it maps each input of A to exaclty one output in B. Hence f is injective also. Hence, f is shown to be a bijection. Hence phi(ab) = phi(a) * phi(b) if gcd(a,b) = 1.

[@marcc1179]

better than my professor and chatgpt. Thank you very much!

[@slavinojunepri7648]

Cristal clear explaination

[@mr.entropic7356]

Awesome video man. You explain very well.

[@jamesflagg6695]

wow you've saved me - thanks so much for making such a clear, thorough proof! 😅

[@alejandrosalazarmejia2801]

Absolutely excellent explanation!

[@eamon_concannon]

Brilliantly explained. Thanks a lot.

[@khalilbsfic]

So simple..Thanks u very much.. The way u proved the bijection was very cool....God bless..

[@NikooLabbafimazraehshahi]

That was Awesome , thanks

[@turabzaidi9651]

Man!!You are great. Thanks for the video❤️❤️

[@matti1610]

Great video, you are really likeable to me, therefore it makes double fun to watch your videos!

[@weisanpang7173]

Hi @Mu Prime Math, please consider doing a series on Number Theory. There are not many such content in youtube, and most if not all of them poorly explain.

[@skonark18]

Sir I am from India.Your explanation explicitly described how the system of congruences work and proof of euler totient function.Can I apply for any USMO from India???

[@sabyasachi36]

Amazing proof

[@tsunningwah3471]

you are my hero

[@ronelalday2472]

Wow. This is brilliant.

[@yanlashchev8721]

I am wondering why you were allowed to just state the constraints gcd(k,a) = 1 , gcd(k,b)= 1. I have been trying to make this video into a structural proof but I am stuck on the reasoning behind why we can create such a restraint. I understand it was for the sake of having those elements belong in the set but is that allowed?

[@MuPrimeMath]

The point of that part of the proof is to show that f is a bijection. That means that for every element in the codomain, there is exactly one element in the domain that maps to it. But every element of the codomain is a pair (k,n) with gcd(k,a)=1 and gcd(n,b)=1. That is true by definition when we look at φ(a) and φ(b). Therefore we just want to consider values k,n with those properties!

[@debalghosh5412]

My god that's a rigorous proof

[@supergsx]

Isn't it arguable that 1 is not co-prime to anything?? I don't understand having the 1 in there.

[@MuPrimeMath]

The definition of coprime is that a,b are coprime iff gcd(a,b) = 1. Clearly gcd(1,n) = 1, so by definition 1 is coprime to every positive integer.

[@djvalentedochp]

you rock

[@ojas3464]

👍

[@NikooLabbafimazraehshahi]

That was Awesome , thanks

[@NikooLabbafimazraehshahi]

That was Awesome , thanks