Number Theory | Euler's Theorem Proof

Поділитися
Вставка
  • Опубліковано 10 гру 2024

КОМЕНТАРІ • 59

  • @georgesadler7830
    @georgesadler7830 3 роки тому +10

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

  • @N9199
    @N9199 3 роки тому +6

    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.

  • @ayushkumar2310
    @ayushkumar2310 Рік тому +5

    I think it is Asgard!

  • @vishalmishra3046
    @vishalmishra3046 3 роки тому +3

    Simple proof. Great video. Thanks Michael. (For some reason, I was expecting a more complex proof, given the structure of this theorem)

  • @lephuocthang3913
    @lephuocthang3913 5 років тому +22

    very very understandable. thanks!!

  • @fredpim11
    @fredpim11 4 роки тому +3

    so glad to have again 61 videos to watch

  • @guogeorge7956
    @guogeorge7956 3 роки тому

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

  • @skleon
    @skleon Рік тому +1

    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
      @skleon Рік тому

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

  • @tianlouw8505
    @tianlouw8505 Рік тому +1

    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
      @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
      @kirkmanjordan1554 Рік тому +1

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

  • @deepankulandaisami9544
    @deepankulandaisami9544 4 місяці тому

    So clear and understandable. thank you so much!

  • @sesar_5467
    @sesar_5467 4 роки тому +1

    Third times the charm for understanding. Thanks!

  • @snipergranola6359
    @snipergranola6359 4 роки тому +1

    I love your videos just studying group theory

  • @alemdetudoemaisumpouco6194
    @alemdetudoemaisumpouco6194 3 роки тому +2

    KING

  • @tisyarawat3638
    @tisyarawat3638 3 роки тому +2

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

  • @yiliangliang5694
    @yiliangliang5694 5 років тому +5

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

    • @MichaelPennMath
      @MichaelPennMath  5 років тому +11

      (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
      @yiliangliang5694 5 років тому +2

      @@MichaelPennMath Thank you!

    • @Mohamova
      @Mohamova 4 роки тому +2

      @@MichaelPennMath Thank you very much!

    • @somasahu1234
      @somasahu1234 3 роки тому +2

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

    • @deathdemonthe2597
      @deathdemonthe2597 3 роки тому +4

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

  • @jungwookrlee
    @jungwookrlee 5 років тому +4

    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
      @MichaelPennMath  5 років тому

      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
      @jungwookrlee 5 років тому +1

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

    • @jungwookrlee
      @jungwookrlee 5 років тому +1

      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
      @MichaelPennMath  5 років тому

      @@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
      @jungwookrlee 5 років тому

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

  • @anantsingh3902
    @anantsingh3902 3 роки тому +3

    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 🙏

  • @mehrajulabadin4350
    @mehrajulabadin4350 2 роки тому

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

    • @Kokurorokuko
      @Kokurorokuko Рік тому

      By construction of the set S earlier

  • @awaiskhan8327
    @awaiskhan8327 2 роки тому +1

    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
      @awaiskhan8327 2 роки тому

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

    • @awaiskhan8327
      @awaiskhan8327 2 роки тому

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

    • @nikolas_mavr07
      @nikolas_mavr07 Рік тому

      @@tianlouw8505 5 and 10 are not coprime.

  • @qedmath1729
    @qedmath1729 4 роки тому +1

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

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

  • @AnuragSingh-mo5nb
    @AnuragSingh-mo5nb 3 роки тому

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

  • @TheStargazer1980
    @TheStargazer1980 Рік тому

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

  • @guogeorge7956
    @guogeorge7956 Рік тому

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

  • @tarikabdelhadibenaouda
    @tarikabdelhadibenaouda 6 місяців тому

    Great content Thanks :)

  • @noureddineettalhi9825
    @noureddineettalhi9825 5 років тому +2

    good job

  • @ccg8803
    @ccg8803 4 роки тому +2

    And thats a good place to stop

  • @PrinceKumar-yo9lr
    @PrinceKumar-yo9lr 3 роки тому

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

    • @skleon
      @skleon Рік тому +1

      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.

  • @henryguan1756
    @henryguan1756 3 роки тому

    very good👍

  • @marlonbrade9004
    @marlonbrade9004 4 роки тому

    a set is congruent to a set . hmmm

  • @Triskelion345
    @Triskelion345 3 роки тому

    Thanks

  • @soroushfarrokhnia331
    @soroushfarrokhnia331 Рік тому

    Man! you are cool!

  • @PrinceKumar-yo9lr
    @PrinceKumar-yo9lr 3 роки тому

    Great