Find all Integer Solutions - A Modular Arithmetic Trick

We find all integer solutions to the equation 6^m - 5^n = 11. This involves a trick using modular arithmetic, which we explore in more depth at the end.
00:00 Intro
00:50 Solution
04:22 Choice of modulo k
07:50 Euler's theorem
09:54 Summary

[@GaetanoDiCaprio]

Very nice solution, but the extraordinary value of this video is the last part: an in-depth analysis of the heuristics underlying the resolution process. Wonderful!

[@pableraspfgpfg468]

Hi @DrBarker, According to this logic, why not using mod 12? It shares also the same prime factors than 6, (so it will get 6^m mod 12 to be 0 even before) and it also will get 5^n mod 12 to loop between 1 and 5, making it quite easy to spot the solution. Is there any reason I am not seeing?

[@barutjeh]

I thought about 12 too; I think the main problem is that when you use 12, there is no easy way to spot that n=m=2 is the only solution. Since it reduces to 6^m = 5^n-1 (mod 12) When m>1, 6^m = 0 (mod 12). But also, for all even n, 5^n-1 = 0 (mod 12). In that case, all the possibilities are still left open. So yes, 12 would be the first thing to try, but you have to move on after it fails to prove useful.

[@tidadmathsci]

Thanks for the mod trick. One can also find the solution with a basic method. Notice that 11 = 1*11 = 6^m - 5^n = (6^(m/2))^2 - (5^(n/2))^2 = (6^(m/2) - 5^(n/2))(6^(m/2) + 5^(n/2)) the only possibility is 6^(m/2) - 5^(n/2) = 1 and 6^(m/2) + 5^(n/2) = 11 which can be solved easily to get m=2 and n=2

[@DrBarker]

I'm not sure if this argument works for ruling out all solutions - we don't know that 6^(m/2) ± 5^(n/2) are necessarily integers, since m and n don't have to be even. For example, if we applied this argument to e.g. 4^m - 2^n = 32, then we might miss the solution m = 3, n = 5.

[@rstrelba]

@@DrBarker Actually no because in first situation we have 11 as 1*11 only but with 32 we will have to investigate 1*32, 2*16, 4*8 variants

[@PatKinson]

You are on the right track, but you have to square each terms: (6^m/2)^2 - (5^n/2)^2 = 11, you can eliminate 6^m/2 + 5^n/2 = 11.... It is really from an initial point: (6^m)^2/2 - (5^n)^2/2 = 11 ; The 2/2 is used as a factor of 1 to keep the equation constant let (6^m/2) = a and 5^n/2 = b a^2 - b^2 = 11 (a + b)(a - b) = 11: {11 x 1 } a + b = 11 a - b = 1 ; add both eqns 2a = 12, a =6 a + b = 11 6 + b = 11 , b= 5 when a = 6, 6^m/2 = 6 , (6^m/2)^2 = 6^2 , 6^m = 6^2, now m = 2 when b = 5, 5^m/2 = 5 , (5^m/2)^2 = 5^2 , 5^m = 5^2, now n = 2

[@mrigayu]

Great approach and explanation

[@primsiren1740]

I had success attacking modulo 7. I don't really know anything about number theory so at first I just randomly tried mod 5 but that wasn't useful at all (I don't think taking mod of any of the bases is useful, so mod 5,6 and 11 wouldn't be useful) then I tried mod 7 which works well. 6^m ~ (-1)^m mod7 5^n ~ (-2)^n mod 7 both of these can be seen from binomial expansion or recursion like you did in the video to see the pattern. 11 ~ 4 mod 7 or 11 ~ -3mod 7 there are 4 cases: case 1: -1 - (-2)^n =4 no sols (parity) case 2: 1- (-2)^n =4 no sols (parity) case 3: -1 - (-2)^n =-3 => (-2)^n = -2 no sols case 4: 1 - (-2)^n =-3 => (-2)^n =4 => n=2 a quick check reveals m=2 and of course this is the only solution. This makes me wonder whether in general it is a good idea to take modulo of the (highest base + 1) as it ensures the +- 1 mod (highest base + 1) on one term. For example for the general a^m - b^n = L where L,a,b are positive integers. Take mod(a+1) => a^m ~ (-1)^m mod(a+1) suppose b (-1)^m - (-c)^n = L mod(a+1) which may or may not have solutions (?) but it should be finite anyway so you can check all cases. Please tell me what you think and please make some more videos on number theory (especially abusing modular arithmetic).

[@mcwulf25]

So I started mod 6 and figured n must be even, -(-1)^n == -1 (mod 6) I then used mod 25 to knock out 5^n and 6^m == 1,6,11,16,21,1,6... etc (mod 25). As we want 6^m = 11 then m=2 also. I didn't get round to proving it was the only solution! Would never have chosen mod 24!

[@MyOneFiftiethOfADollar]

The modular truths are necessary but not sufficient. conjecture: k should have all the prime divisors of one of the bases. Will make up a problem and see if the conjecture is useful like it was here where 6 and 24 have the same prime factors.

[@DrBarker]

If k doesn't have all of the prime divisors of one of the bases, then that base raised to successive powers will never become 0, 0, 0, ... after a certain point. This property is helpful when it occurs, but I can imagine even if k doesn't have all prime divisors of either base, then we could still get loops which don't coincide, e.g. 3, 7, 3, 7, ... for one, and 5, 9, 5, 9, ... for the other. We could maybe still rule out solutions with this structure, although as the length of each loop increases, the likelihood of overlap increases (unless k also increases a lot).

[@AT-zr9tv]

Neat trick! Would you have the time to consider generalizing the approach to solving / attempting to solve a^m - b^n = c, where (a,b,c) is given?

[@DrBarker]

I'm not certain, but I feel like that might be an open research question to solve in general. Even the method in this video isn't guaranteed to give a useful value of k (e.g. k = 12 seems suitable, but when we try it, it doesn't actually help rule out all further solutions), but it can be a useful guide, rather than just trial and error considering every possible value of k.

[@AT-zr9tv]

@@DrBarker Understood (and thanks for responding). Perhaps attempting to generalize your approach of narrowing down the realm of solutions of a^m - b^n = c would already be an interesting exercise.

[@holyshit922]

m=n=2 This is my guess before watching There are probably no more solutions