Proof that the Totient Function is Multiplicative

Coprime numbers mod n: • Coprime Numbers and Re...
Chinese remainder theorem: • Chinese Remainder Theorem
Surjection and bijection: • Surjections and Biject...
Explanation of why Euler's totient function of a product of coprime numbers is equal to the product of the totients of those relatively prime numbers. Understanding the relationship between those two totients is awesome!
Modular Arithmetic playlist: • Modular Arithmetic
Subscribe to see more new math videos!
Music: OcularNebula - The Lopez

[@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.

[@khalilbsfic]

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

[@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! 😅

[@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.

[@alejandrosalazarmejia2801]

Absolutely excellent explanation!

[@NikooLabbafimazraehshahi]

That was Awesome , thanks

[@tsunningwah3471]

you are my hero

[@turabzaidi9651]

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

[@eamon_concannon]

Brilliantly explained. Thanks a lot.

[@matti1610]

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

[@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!

[@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

[@ronelalday2472]

Wow. This is brilliant.

[@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

[@debalghosh5412]

My god that's a rigorous proof

[@ojas3464]

👍

[@NikooLabbafimazraehshahi]

That was Awesome , thanks

[@NikooLabbafimazraehshahi]

That was Awesome , thanks