Introduction to number theory lecture 3: Divisibility and Euclid's algorithms.

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

КОМЕНТАРІ • 40

  • @cmargir
    @cmargir 2 роки тому +40

    Not a big deal (you can understand everything fine) but there's a bit more echo than usual in the sound

  • @DiracComb.7585
    @DiracComb.7585 2 роки тому +26

    27:06 Physicists definitely approve this approximation

    • @unalcachofa
      @unalcachofa 2 роки тому +2

      That took a laugh out of me!
      Loved the lecture.

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

    0:00 Divisibility
    7:08 Euclid's Division Algorithm
    10:54 Ideals
    13:36 Greatest Common Divisor
    19:42 Euclid's Algorithm
    25:48 Fibonacci Numbers (worst case for Euclid's algorithm)
    31:43 Formula for fibonacci numbers

  • @yannicko.5936
    @yannicko.5936 Рік тому +8

    "Everything about the Fibonacci numbers in popular perception is non-sense, except in Witchcraft" xD

    • @cyriacus73
      @cyriacus73 2 місяці тому

      man had me rolling laughing

  • @martinepstein9826
    @martinepstein9826 2 роки тому +9

    The golden ratio appears everywhere in art... if you take "golden ratio" to mean any number between 1/2 and 2/3. The artists who use the number intentionally only do so because they've heard the same baloney as the rest of us (and this is fine; lots of great art is inspired by fiction).
    I once read an entertaining blog post by someone trying to prove that nautilus spirals have golden proportions. The author had a golden spiral overlayed on a nautilus shell and it wasn't lining up, so they kept tweaking parameters trying to make it fit. Finally, they centered the spiral somewhere _other_ _than_ the center of the shell and it lined up OK in some places, so they declared victory. You could see how the insanity had taken hold because, in their mind, the harder they had to work to find a golden proportion the deeper and more sophisticated the connection must be.

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

    23:00
    Euclid Algorithm is based on the following property:
    For any number x < y and y = xq + r, r < x, we get
    gcd(x,y) = gcd(x, xq + r) = gcd(x,r). ( I did not know this until I watch this video)
    In fact, set d := (x,y) and d' := (x,r).
    Because left hand side of y = xq + r is divided by d', we get d'| y. And obviously, d'|x.
    Therefore by the definition of d, we get d'

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

      Hi hausdorff
      I dont understand what you mean for your first point ?
      choose k elements in a set of N elements= N!/(k!*(N-k)!)
      if k=3 and N=n+2=> ((n+2)!/(3!*(n+2-3)!))=1/6*(n + 2)*(n + 1)*n=1/6*n^3 + 1/2*n^2 + 1/3*n
      =1/6*(n^3 + 3*n^2 + 2*n)

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

      Where does the 6 elements set come from?

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

      @@yunjiangjiang6146 Hi, I forget about it. So, I remove the sentence. I regret that I wrote something boring....

  • @awsumone1234
    @awsumone1234 2 роки тому +13

    Minor correction at 3:26: (n + 2)* element set
    Thank you for the great lecture!

  • @malharmanagoli
    @malharmanagoli 2 роки тому +6

    40:24 Fibonacci numbers in biology is not total nonsense.
    For example, if you look at seeds at the center of a sunflower, they seem to be arranged in a spiral-like pattern. If you count the number of spirals going one way and the number of spirals going the other way, most likely they are going to be consecutive Fibonacci numbers like 21 and 34 or 34 and 55. You can't really call 34 "small"; certainly not a lot of numbers near 34 are Fibonacci.
    Turns out, that these kind of spiral-y patterns are efficient in their use of space - you can fit a lot of seeds in a small circle this way.
    Suppose you have put a bunch of seeds in a circle and want add another. You add it to the least crowded place on the boundary. If you repeat this process many many times, you will end up with a Fibonacci spiral pattern.
    Vi Hart did a video series on this topic several years ago, which I found very interesting:
    Part 1: ua-cam.com/video/ahXIMUkSXX0/v-deo.html
    Part 2: ua-cam.com/video/lOIP_Z_-0Hs/v-deo.html
    Part 3: ua-cam.com/video/14-NdQwKz9w/v-deo.html

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

      And that has to do with the fact that phi is the "least rational" in some sense. Basically, phi is the irrational number worst approximated by rational numbers. Well, there are a few more of these badly approximated irrational numbers, but you can generate all of them by taking phi and applying integer addition or multiplication.
      Relevant Mathologer video: ua-cam.com/video/CaasbfdJdJg/v-deo.html

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

      @@blairkilszombies fun fact: you can as well call it "almost rational", because rational numbers are even worse approximated by other rationals

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

    I like his bluntness.

  • @ethanbove629
    @ethanbove629 2 роки тому +2

    Thank you! Very good stuff

  • @JTurfie
    @JTurfie 11 місяців тому +1

    @3:27 How come ((n+2) choose 3) equals choosing 3 elements from a 6 element set.
    How did we come to n+2 = 6? So n = 4?

    • @cyriacus73
      @cyriacus73 2 місяці тому

      nPr is n!/r!... (n+2)!/3! must be a whole number, so (n+2)! must be divisible by 3!=6.

  • @junghyunkim2247
    @junghyunkim2247 9 місяців тому

    how is the binomial expression when n=n+2 and k=3 equal to the statement "number of ways to choose 3 elements from 6 element set?" wouldn't that expression equal to the number of ways to choose 3 elements from an n+2 element set? 3:40

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

    Great lecture thank you very much

  • @IvanHe-gc7bf
    @IvanHe-gc7bf 3 місяці тому

    Professor:
    Its fairly ez to proof.
    *Me looking at my 10 wasted papers that don't give my shit*: Thats ez?

    • @cyriacus73
      @cyriacus73 2 місяці тому

      I'll try solving em later today... hopefully it'll infact be easy.

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

    Why is the worst case when q=1? With the numbers 100 and 101, we have 101 = 100*1 + 1. Q is 1, but we've already reduced the number down to 1 in just one step.

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

      Worst case is when we dont know the number yet, just the steps

    • @boutiquemaths
      @boutiquemaths 7 місяців тому +1

      I was wondering the same thing. He said "we want r to be small" but he means "we want r to be small if we want the algorithm to be as fast as possible". We want it to be as slow as possible, so we want r to be as big as possible. To make r as big as possible we need to make b as big as possible in relation to a, so we take q=1.

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

    4:11 he says "8 divides n squared minus n ..." when (as immediately shown in the examples) he means n squared minus one.

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

    I like how he slipped and said "ideals". What are those, lol?

  • @mastershooter64
    @mastershooter64 4 місяці тому +1

    Lol the golden ratio is useful in witchcraft. very funny

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

    Do you notice the humour in him?

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

    👏

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

    31:22 🇮🇳😍

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

    yeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee

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

    Is this taught in college? Learned some of these things in the 6th-7th grade. Of course, not about Fibonacci sequences which the lecturer mixes in an incoherent and sloppy way with elementary-school topics. A shabby course overall!

    • @SaveSoilSaveSoil
      @SaveSoilSaveSoil 2 роки тому +2

      Well... you certainly didn't learn EVERYTHING covered in this video in the 8th grade, did you? If so, good for you. Did you complete elementary studies in France then? I hear that five-year-olds can hold fairly intelligent conversations about rings and fields there. I never verified whether that's fact or myth (I think it's most likely a friendly exaggeration. They may be explicitly told that addition and multiplication over integers are closed and commutative. Rings and fields? I don't think so, not for an average five-year-old at least). As someone who didn't formally study these things (of course I heard about them in high school) until the first year of college, I was very intimidated and sometimes apologetic because of what I learned and hadn't learned. Tao in his blog says (and I paraphrase) "always relearn mathematics". If you haven't experienced moments like "holy *** (insert God's name), why haven't I seen it this way before?", you are truly, fundamentally missing out on the joy of mathematics.

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

      @@SaveSoilSaveSoil It is 100% a lie, not even an exaggeration

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

      Well you learn only the basic... not the whole course (part 20++). The point of this in college is to get everyone on the same car, so there is no one lost in the middle of the course. Yes you may had learnt this in highschool, but you can’t treat everyone the same, some of them maybe didn’t understand math in early days but want to take this course, maybe they are’nt as good as you but they want to learn too! (Sorry for my english btw, have a nice day)

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

      If you think back to the course where you learned this in eighth grade, I bet the first month of that eighth month math course, you could have complained, "Is this taught in eighth grade? I learned such things in fourth grade."
      Every properly taught course usually starts by reviewing what the student should have already learned. This particular lesson was probably the first week of the college course, so yes, a professor would expect that everyone would have been exposed to this.
      However, for purposes of argument, I took all the advanced math courses in high school one year ahead (did five years high school math grade 8 to 12, 1965-1969) then took all the Advanced Math courses at a regional technical college in retirement (2014-2020), yet there's things he's said in the first two lessons that are new to me, but much is a review.

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

      this is lecture 3...