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!!👍
Super! Thank you so much, Professor Mu! I’m a girl from Shanghai, and my name is Claire. I’ve also made some movies on my channel. Thank you again for helping me with this problem. I spent two days on it, trying lots of different ideas, but every time it felt like I was walking into a dark room and losing sight of my goal. I have to say that the "x mod a" approach is brilliant-it’s not just a clever idea, but a profound observation about the Cartesian product and remainders. I'm very excited to learn more marvelous ideas from you.😸
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.
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???
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.
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?
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!
Yes, there is a constructive way to get x from the pair. It involves finding inverses mod n, which we can do using the extended Euclidean algorithm. If you're interested, I would recommend looking up proofs of the Chinese remainder theorem. Some proofs will give an explicit algorithm to find the solution x.
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!!👍
Super! Thank you so much, Professor Mu! I’m a girl from Shanghai, and my name is Claire. I’ve also made some movies on my channel. Thank you again for helping me with this problem. I spent two days on it, trying lots of different ideas, but every time it felt like I was walking into a dark room and losing sight of my goal.
I have to say that the "x mod a" approach is brilliant-it’s not just a clever idea, but a profound observation about the Cartesian product and remainders. I'm very excited to learn more marvelous ideas from you.😸
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.
Awesome video man.
You explain very well.
wow you've saved me - thanks so much for making such a clear, thorough proof! 😅
better than my professor and chatgpt. Thank you very much!
Absolutely excellent explanation!
Great video, you are really likeable to me, therefore it makes double fun to watch your videos!
Cristal clear explaination
So simple..Thanks u very much..
The way u proved the bijection was very cool....God bless..
Man!!You are great. Thanks for the video❤️❤️
Brilliantly explained. Thanks a lot.
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???
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.
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?
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!
That was Awesome , thanks
Is there a constructive way to go from the pairs to the actual remainder x. Can we find x explicitly?
Yes, there is a constructive way to get x from the pair. It involves finding inverses mod n, which we can do using the extended Euclidean algorithm. If you're interested, I would recommend looking up proofs of the Chinese remainder theorem. Some proofs will give an explicit algorithm to find the solution x.
My god that's a rigorous proof
Wow. This is brilliant.
Amazing proof
Isn't it arguable that 1 is not co-prime to anything?? I don't understand having the 1 in there.
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.
you are my hero
you rock
👍
That was Awesome , thanks
That was Awesome , thanks