I like a slightly different version of this proof, where we take the function f_a:S->S which maps x to (ax)mod n, check it's well defined, see that it's inverse is f_{a^-1} and we get that every element in S can be "written" as ax, with a unique x, so we continue and do the final part.
One question: in 6:56 you use the fact that if a*b = 0 (mod n), then n must divide a or n must divide b. This is clearly true if n is prime. But for non primes it can be false. Example: 2 * 4 = 0 (mod 8). So how do we know that in this case, this statement is valid?
7:00 Why? If n=10, a=5, xi=7 and xj=3 Then 10|5(7-3) holds 10 does not divide 5 But according to him, this means 10|(7-3) ie. 10|4 which is false. n does not have to be prime, 5,7 and 3 are coprime to n. SO what am I missing?
In this example that n =10 and a=5, the condition given in the statement of the theorem fails i.e. the gcd (a,n) does not remain 1. Instead it becomes 5 according to your example, hence the conclusion follows.
@@RobbieKeyboard he still proves xi = xj by saying that the n does not divide a, which doesnt work all the time, this is a good question. Would love if someone could answer it
Could you please make a video on de Polignac's Formula? It would be really nice if you could make one explaining the formula along with a few sums as examples. :)
(1) shows that aS is a subset of S and then (2) shows that aS and S have the same number of elements. Since S and aS are finite sets this is enough to see that they are the same set. Thanks for the question, I could have been a bit more clear in that step!
@@somasahu1234 I have the similar feeling to you that the professor missed something here. I try to explain it. Take any one element from aS first. Then consider the remainder of that element (mod n). It is easy to prove that the remainder is coprime to "n". (Otherwise, the element will not be coprime to "n", which is impossible for elements from aS.) Therefore, the remainder belongs to S. We can replicate the procedure for every element from aS, and all their remainders (mod n) exactly construct the set S!!!. (Because each remainder is distinct!)
would this be the same thing as proving that set of euler's numbers, S = {1 ≤ x ≤ n | gcd(x,n = 1} and set the of the residues, R = { 0 ≤ y < n | ax = y mod n} are the same set? (using the definition of set equality?)
Let me understand your set R a bit better. Do you mean all multiples of a modulo n? In this case then the answer is no. For example, if n=8 and a=3 then 6=2*3 is in R but not in S.
I'm trying to go to set equality route because I don't really understand how showing all elements of aS are not congruent to each other and are all relatively prime to elements in S proves that they have the same modulo in different order
@@jungwookrlee I see, so the x's in the definition of R are related to those in S. In this case, this approach would work: You would end by taking the product over all elements of R = the product over all elements in S. As for the set equality, this should follow from the fact that a is invertible mod n, but that argument will probably be quite similar to the one in the proof. That being said, I often like arguments that use set equality so I'll keep this in mind.
Students- Last couple of lines Teachers- Last couple of pages Legends- Last couple of BOARDS 8:30 Thanks for the proof . Very less proofs of such topics are available generally.From india 🙏
Correct me if I'm wrong but, but isn't the property n| a(xi -xj) implies n divides a or n divides xi-xj is only applicable when n is a prime number, but in our proof we are assuming n to be an arbitrary natural number?
Nvm I just realized that if n divides ab And a,n are relatively prime then it must be that n divides b. we have ax + ny = 1 Then abx + bny = b So n divides b
@@awaiskhan8327 what about 10|5(7-3)? 10 doesn't divide 5 and it also doesn't divide 7-3=4. And 7,5,3 are all co-prime to 10 and it is true that 10|5(7-3) since 10|20
Suppose there exists a prime factor p, such that p divides ax_i, then p divides either a or x_i. Since x_i and n are relatively prime by construction of S, if p divides x_i, then p cannot divide n. Since a and n are also relatively prime as a constraint on the theorem, if p divides a, then p cannot divide n.
Because if the size of S is phi(n), but if multiplying the elements by a makes two of them congruent (mod n), then the size of aS will be smaller than phi(n), and he needs the size of aS to be the same as S.
Professor Michael Penn, thank you for an outstanding proof of Euler Theorem.
I like a slightly different version of this proof, where we take the function f_a:S->S which maps x to (ax)mod n, check it's well defined, see that it's inverse is f_{a^-1} and we get that every element in S can be "written" as ax, with a unique x, so we continue and do the final part.
I think it is Asgard!
Simple proof. Great video. Thanks Michael. (For some reason, I was expecting a more complex proof, given the structure of this theorem)
very very understandable. thanks!!
so glad to have again 61 videos to watch
A year after, for the second time I watch this video, already knowing Ferman's Little theorem, I finally get the ins and outs.
One question: in 6:56 you use the fact that if a*b = 0 (mod n), then n must divide a or n must divide b. This is clearly true if n is prime. But for non primes it can be false. Example: 2 * 4 = 0 (mod 8). So how do we know that in this case, this statement is valid?
I believe the answer is, since gcd(a, n) = 1, a has a unique inverse and a^-1*a*b = a^-1*0 (mod n), and therefore, b = 0 (mod n).
7:00
Why?
If n=10, a=5, xi=7 and xj=3
Then 10|5(7-3) holds
10 does not divide 5
But according to him, this means 10|(7-3) ie. 10|4 which is false.
n does not have to be prime, 5,7 and 3 are coprime to n. SO what am I missing?
In this example that n =10 and a=5, the condition given in the statement of the theorem fails i.e. the gcd (a,n) does not remain 1. Instead it becomes 5 according to your example, hence the conclusion follows.
@@RobbieKeyboard he still proves xi = xj by saying that the n does not divide a, which doesnt work all the time, this is a good question. Would love if someone could answer it
So clear and understandable. thank you so much!
Third times the charm for understanding. Thanks!
I love your videos just studying group theory
KING
Could you please make a video on de Polignac's Formula? It would be really nice if you could make one explaining the formula along with a few sums as examples. :)
Hi, why does it follow from (1) and (2) that S and aS are congruent sets mod n? Thx!
(1) shows that aS is a subset of S and then (2) shows that aS and S have the same number of elements. Since S and aS are finite sets this is enough to see that they are the same set. Thanks for the question, I could have been a bit more clear in that step!
@@MichaelPennMath Thank you!
@@MichaelPennMath Thank you very much!
@@MichaelPennMath set S and set aS are the same sets I got it , but still how aS ≡ S (mod n) ?!? Plz explain 🙏
@@somasahu1234 I have the similar feeling to you that the professor missed something here. I try to explain it. Take any one element from aS first. Then consider the remainder of that element (mod n). It is easy to prove that the remainder is coprime to "n". (Otherwise, the element will not be coprime to "n", which is impossible for elements from aS.) Therefore, the remainder belongs to S. We can replicate the procedure for every element from aS, and all their remainders (mod n) exactly construct the set S!!!. (Because each remainder is distinct!)
would this be the same thing as proving that set of euler's numbers, S = {1 ≤ x ≤ n | gcd(x,n = 1} and set the of the residues, R = { 0 ≤ y < n | ax = y mod n} are the same set? (using the definition of set equality?)
Let me understand your set R a bit better. Do you mean all multiples of a modulo n? In this case then the answer is no. For example, if n=8 and a=3 then 6=2*3 is in R but not in S.
@@MichaelPennMath R is the all the number such that elements of R are the least residues of aS modulo n
I'm trying to go to set equality route because I don't really understand how showing all elements of aS are not congruent to each other and are all relatively prime to elements in S proves that they have the same modulo in different order
@@jungwookrlee I see, so the x's in the definition of R are related to those in S. In this case, this approach would work: You would end by taking the product over all elements of R = the product over all elements in S. As for the set equality, this should follow from the fact that a is invertible mod n, but that argument will probably be quite similar to the one in the proof. That being said, I often like arguments that use set equality so I'll keep this in mind.
@@MichaelPennMath Oh ok I kinda get it. Thank you so much for your help!
Students- Last couple of lines
Teachers- Last couple of pages
Legends- Last couple of BOARDS
8:30
Thanks for the proof . Very less proofs of such topics are available generally.From india 🙏
In 7:11 why Xi and Xj both are smaller than n ?
By construction of the set S earlier
Correct me if I'm wrong but, but isn't the property n| a(xi -xj) implies n
divides a or n divides xi-xj is only applicable when n is a prime number, but in our proof we are assuming n to be an arbitrary natural number?
For example 4 divides 60 but doesn't divide 10 or 6
Nvm I just realized that if n divides ab
And a,n are relatively prime then it must be that n divides b.
we have ax + ny = 1
Then abx + bny = b
So n divides b
@@awaiskhan8327 what about 10|5(7-3)? 10 doesn't divide 5 and it also doesn't divide 7-3=4. And 7,5,3 are all co-prime to 10 and it is true that 10|5(7-3) since 10|20
@@tianlouw8505 10 divides 20 so
10|5*4 but 5 is not coprime to 10 and 4 is not coprime to 10 either so the theorem doesn't apply here
@@tianlouw8505 5 and 10 are not coprime.
could someone explain in detail why p has to be prime and why p can not divide a?
Suppose there exists a prime factor p, such that p divides ax_i, then p divides either a or x_i.
Since x_i and n are relatively prime by construction of S, if p divides x_i, then p cannot divide n.
Since a and n are also relatively prime as a constraint on the theorem, if p divides a, then p cannot divide n.
i am sad as you didn't said in the end "which is a good place to stop"
You are quite brilliant! I empathize with your angry sinuses but you don’t look like it’s any issue!
key point is the two sides of the equation share no common factor, so they cancels out
Great content Thanks :)
good job
Thanks!
And thats a good place to stop
Why do we have to prove that
No two elements are congruent mod n
Because if the size of S is phi(n), but if multiplying the elements by a makes two of them congruent (mod n), then the size of aS will be smaller than phi(n), and he needs the size of aS to be the same as S.
very good👍
a set is congruent to a set . hmmm
Thanks
Man! you are cool!
Great