Proving A Crazy GCD Identity

We prove that n^{gcd(a,b)} - 1 = gcd( n^a - 1, n^b - 1) for all positive integers n, a, and b. Some trivial cases, for example where n = 1, are omitted from the proof.
I found this problem in Gelca and Andreescu's book, Putnam and Beyond.
Bézout's identity:
en.wikipedia.org/wiki/B%C3%A9...
proofwiki.org/wiki/B%C3%A9zou...
00:00 Intro
00:18 Idea for the proof
01:01 A sufficient condition
03:37 Proof of sufficient condition
06:48 Bézout's identity
08:24 RHS divides LHS
12:32 Dealing with n^{qb}

[@eliasmai6170]

I love your math videos and your soothing British accent.

[@azai.mp4]

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]

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]

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

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

[@omaduck5583]

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.

[@gametimewitharyan6665]

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

[@FaranAiki]

That's the beauty of math ❤

[@geoffreytrang8670]

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

[@DrBarker]

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]

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

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]

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

[@user-yi4qk9rv1l]

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

[@tioulioulatv9332]

الله يحفظك

[@GreenMeansGOF]

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]

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

[@chair7728]

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]

How would you use the Euclidean algorithm on the exponents?

[@chair7728]

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

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