Professor Michael Penn, thank you for an outstanding proof of Euler Theorem.

Thank you for the most simplified proof of eulers theorem. It helps so much!🥰❤️

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

Third times the charm for understanding. Thanks!

so glad to have again 61 videos to watch

I love your videos just studying group theory

So clear and understandable. thank you so much!

KING

A year after, for the second time I watch this video, already knowing Ferman's Little theorem, I finally get the ins and outs.

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. :)

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?

@RobbieKeyboard

Жыл бұрын

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.

@kirkmanjordan1554

9 ай бұрын

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

Great content Thanks :)

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?)

@MichaelPennMath

4 жыл бұрын

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.

@jungwookrlee

4 жыл бұрын

​@@MichaelPennMath R is the all the number such that elements of R are the least residues of aS modulo n

@jungwookrlee

4 жыл бұрын

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

@MichaelPennMath

4 жыл бұрын

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

@jungwookrlee

4 жыл бұрын

@@MichaelPennMath Oh ok I kinda get it. Thank you so much for your help!

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?

@skleon

8 ай бұрын

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).

i am sad as you didn't said in the end "which is a good place to stop"

Hi, why does it follow from (1) and (2) that S and aS are congruent sets mod n? Thx!

@MichaelPennMath

4 жыл бұрын

(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!

@yiliangliang5694

4 жыл бұрын

@@MichaelPennMath Thank you!

@Mohamova

4 жыл бұрын

@@MichaelPennMath Thank you very much!

@somasahu1234

3 жыл бұрын

@@MichaelPennMath set S and set aS are the same sets I got it , but still how aS ≡ S (mod n) ?!? Plz explain 🙏

@deathdemonthe2597

3 жыл бұрын

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

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 🙏

good job

@MichaelPennMath

4 жыл бұрын

Thanks!

could someone explain in detail why p has to be prime and why p can not divide a?

@fangjiunnewe3634

3 жыл бұрын

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.

key point is the two sides of the equation share no common factor, so they cancels out

very good👍

You are quite brilliant! I empathize with your angry sinuses but you don’t look like it’s any issue!

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?

@awaiskhan8327

Жыл бұрын

For example 4 divides 60 but doesn't divide 10 or 6

@awaiskhan8327

Жыл бұрын

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

@tianlouw8505

Жыл бұрын

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

@awaiskhan8327

Жыл бұрын

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

@nikolasm77

Жыл бұрын

@@tianlouw8505 5 and 10 are not coprime.

a set is congruent to a set . hmmm

Thanks

And thats a good place to stop

Great

Man! you are cool!

In 7:11 why Xi and Xj both are smaller than n ?

@Kokurorokuko

Жыл бұрын

By construction of the set S earlier

Why do we have to prove that No two elements are congruent mod n

@skleon

8 ай бұрын

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.