Proving A Crazy GCD Identity

Поделиться
HTML-код
  • Опубликовано: 5 сен 2024

Комментарии • 22

  • @eliasmai6170
    @eliasmai6170 5 месяцев назад +16

    I love your math videos and your soothing British accent.

  • @omaduck5583
    @omaduck5583 5 месяцев назад +2

    Another way to prove this is to show that gcd(x,y) is the unique function from Z x Z \{(0,0)} to Z>0 such that it is symmetric, gcd(x,0)=|x| and gcd(x,y)=gcd(x,y-x). Then you only have to show that f(x,y)=log_n(1+gcd(n^x-1,n^y-1)) also satisfies these constraints (although you might have to be a little more detailed and restrict to Z>=0 for your domain) the advantage of this is that you can also prove things for the fibonacci numbers also this way.

  • @azai.mp4
    @azai.mp4 5 месяцев назад +9

    I found this identity fairly intuitive after noting that n^b - 1 is a repdigit in base n (it's b copies of the digit n-1),
    and then imagining what happens when you apply the Euclidean algorithm to e.g. 10^2 - 1 = 99 and 10^5 - 1 = 99999.
    Each step of the algorithm ends up being the same as if you were calculating gcd(2, 5) and the nines were just tally marks.

    • @bowlteajuicesandlemon
      @bowlteajuicesandlemon 5 месяцев назад

      How do intuit that each step is just the same as GCD(a,b), I can't see how you view the 9s as tally marks?

    • @azai.mp4
      @azai.mp4 5 месяцев назад

      @@bowlteajuicesandlemonBy breaking them up into smaller steps.
      Instead of going 99999 - 99990 = 9 (where 99990 = 99 * 1010),
      (which corresponds to 5 - 2*2 = 1),
      I do 99999 - 99000 = 999, and then 999 - 990 = 9,
      (which more clearly corresponds to 5 - 2 = 3, and then 3 - 2 = 1).
      But also notice that the greatest multiple of 99 that fits into 99999 has to be 99990 (a bunch of nines followed by 5 mod 2 zeroes),
      because (1) that is a multiple of 99 (because 4 is a multiple of 2) and (2) if you added another 99 you would overflow to >99999 (you'd need at least 2 zeroes at the end, but you've only got 5 mod 2 zeroes).
      Does that make sense?

    • @azai.mp4
      @azai.mp4 5 месяцев назад +4

      @@bowlteajuicesandlemon By breaking each step up into smaller steps.
      Instead of going 99999 - 99990 = 9 (where 99990 = 99 * 1010),
      (which corresponds to 5 - 2*2 = 1),
      I do 99999 - 99000 = 999, and then 999 - 990 = 9,
      (which corresponds to 5 - 2 = 3, and then 3 - 2 = 1).
      But also notice that the greatest multiple of 99 that fits into 99999 has to be 99990 (a bunch of nines followed by 5 mod 2 zeroes),
      because (1) that is a multiple of 99 (because 4 is a multiple of 2) and (2) if you added another 99 you would overflow to > 99999 (you'd need at least 2 zeroes at the end, but you've only got 5 mod 2 zeroes).
      Does that make sense?

  • @geoffreytrang8670
    @geoffreytrang8670 5 месяцев назад +15

    Interestingly, the same identity is also true for the Fibonacci sequence. Namely, Fib(gcd(a, b)) = gcd(Fib(a), Fib(b)).

    • @DrBarker
      @DrBarker  5 месяцев назад +5

      This is really interesting - I'd need to spend some time thinking about this to convince myself, but it would be really cool to see a proof of this result!

    • @jmathg
      @jmathg 5 месяцев назад +5

      ​@@DrBarker​ This is true for any Lucas sequence because they are "strong divisibility" sequences. So the important thing to consider in the proof is that form of linear recurrence relation. It's this recurrence that gets you nice properties modulo n, which is indeed very cool!

    • @DrBarker
      @DrBarker  5 месяцев назад +4

      Turns out Michael Penn has a video on this exact result! It will show up if you search for "greatest common divisor of Fibonacci numbers".

  • @alipourzand6499
    @alipourzand6499 5 месяцев назад +8

    Hard tobelieve with all these -1 but it works!
    a = 8, b = 12, n = 3
    gcd(8, 12) = 4
    LHS : 3^4 - 1 = 80
    RHS: gcd(3^8 - 1, 3^12 - 1)
    = gcd(6560, 531440)
    = 80
    👑👑👑

  • @gametimewitharyan6665
    @gametimewitharyan6665 5 месяцев назад +3

    Amazing work Dr Barker, I learnt a new proving technique today :D

  • @FaranAiki
    @FaranAiki 5 месяцев назад +2

    That's the beauty of math ❤

  • @dakcom-mk6mp
    @dakcom-mk6mp Месяц назад

    Cool

  • @tioulioulatv9332
    @tioulioulatv9332 5 месяцев назад +1

    الله يحفظك

  • @user-yi4qk9rv1l
    @user-yi4qk9rv1l 5 месяцев назад

    I proved it using bezout's theoreme too
    Can you make a video about newton's method to approximate roots ??

  • @GreenMeansGOF
    @GreenMeansGOF 2 месяца назад

    It bothered me that you claimed that n^{qb} and n^{qb}-1 can’t have any common factors. Maybe the gcd is 1. Then I realized that if the gcd is 1 then of course the RHS divides the LHS. QED😅

    • @GreenMeansGOF
      @GreenMeansGOF 2 месяца назад

      Corollary: RHS=1 iff n=2 and gcd(a,b)=1.

  • @chair7728
    @chair7728 5 месяцев назад

    This can be proved with induction right? You can note that you can basically apply Euclidean algorithm on the exponents, then you just need to prove the Euclidean algorithm works with induction

    • @bowlteajuicesandlemon
      @bowlteajuicesandlemon 5 месяцев назад

      How would you use the Euclidean algorithm on the exponents?

    • @chair7728
      @chair7728 5 месяцев назад

      @@bowlteajuicesandlemon Actually I just realized that the problem I was working with was a specific case of the more general problem shown in the video where n=2, but I think it may work for n>1,
      We have gcd(n^a - 1, n^b - 1), lets assume WLOG that a>b (if a=b then the gcd is just n^a-1), then
      gcd(n^a-1, n^b-1) = gcd(n^a-1 - (n^b-1), n^b-1) = gcd(n^b(n^(a-b)-1), n^b-1), now assuming that n^b and n^b-1 are coprime, we can "cancel" them out in the gcd to get gcd(n^(a-b)-1, n^b - 1), which is like our original expression, but we have subtracted the exponents, and since we can do this, we can apply the Euclidean algorithm to eventually get to gcd(n^gcd(a,b)-1, n^0 - 1) = n^gcd(a,b)-1.
      In the case of n=2, its clear that n^b and n^b-1 are coprime, but as for the general case, this might be a valid proof:
      Assume for a contradiction that x and x-1 are not coprime, then gcd(x, x-1)=y > 1, so y | x and y | x - 1 => x = ya, x-1 = yb for some integers a,b, but then x = ya = yb + 1, but this cannot be true as y>1

  • @mr.nicolas4367
    @mr.nicolas4367 5 месяцев назад

    I proved It in 6 minutes. Kneel before me punny humans