While using a four-fours solver I wrote to solve a different problem, I came across this interesting find: sqrt(29 - 4) = 29 - 4! = 5 Using a Python program, I brute-forced every pair of numbers a and b (a >= b) that could be substituted instead of 29 and 4 (from 0
It's actually extremely useful and comes up in group theory, too. It's used to prove that various groups have distinct orders unless when the groups are known to be the same.
It is also easy to solve with LTE because if p divides a then p also divides c and the biggest power of p dividing c is shown to be at least b-1, so c is bigger than p^(b-1) who gets quickly bigger than b, and so (a+1)^c gets quickly bigger than a^b+1.
Solution without powerful theorems: Focusing on the case a, b ≥ 2 (the others are trivial), take both sides mod a^2 to get 1 = 1 + ca mod a^2 -> a|c, Thus, we can let c = a^r s where a doesn't divide s and r>0 to get a^b = a^(r+1) s + a^(r+2) s (a^r s - 1)/2 + ... If a is odd or s is even, take mod a^(r+2) to get a^b = a^(r+1) s mod a^(r+2). The only possibility is b = r+1, so a^(r+1)(s-1) = 0 mod a^(r+2) -> s = 1 mod a -> a^(r+1) = a^(r+1) s + a^(r+2) s (a^r s - 1)/2 ≥ a^(r+1) + a^(r+2) 1(3-1)/2 > a^(r+1), contradiction. If a is even and s is odd, take both sides mod a^(r+2)/2 to get a^b = a^(r+1) s mod a^(r+2)/2. If b ≥ r+2, then we can reduce further to a^(r+1) s = 0 mod a^(r+2)/2 -> s = 0 mod a/2. If a isn't a power of 2, repeating the same argument but choosing an odd prime p|a, c = p^r s where p doesn't divide s leads to s = 0 mod p, contradiction. Else, choosing the prime 2 gives s odd, but also s = 0 mod a/2 again, contradiction unless a = 2. This subcase finally leads to 2^b = 2^(r+1) s + 2^(r+1) s(2^r s - 1) + 2^(r+2) s(2^r s - 1)(2^r s - 2)/3 + ... = 2^(2r+1) s^2 + 2^(r+3) s(2^r s - 1)(2^(r-1) s - 1)/3 + ... If r = 1, we obtain 2^b = 8s^2 + 16s(2s-1)(s-1)/3 + ...., and taking mod 8 gives 2^b = 8s^2 = 8 mod 16 -> b = 3, so we recover the solution a=2, b=3, c=2. If r = 2, we obtain 2^b = 32(s^2+s(2s-1)) + 2^(r+4) s(2^r s - 1)(2^r s - 2)(2^r s - 3)/24 + ... = 32(3s^2-s) + 16s(4s-1)(2s-1)(4s-3)/3, taking mod 16 gives b = 4 which doesn't work. Else r>2 -> 2r+1 > r+3 and taking mod 2^(r+4) gives 2^b = 2^(r+3) s(2^r s - 1)(2^(r-1) s - 1)/3 + ... mod 2^(r+4) -> b = r+3 -> 2^(r+3) = 2^(2r+1) s^2 + ... ≥ 2^(r+4), contradiction. Otherwise a^b (1 - a^(r+1-b) s) = 0 mod a^(r+2)/2 -> a^(r+1-b) s = 1 mod a^(r+2-b)/2. If r ≥ b, then reducing further mod 2 gives 0 = 1 mod 2, contradiction, so b = r+1 -> a^(r+1) = a^(r+1) s + a^(r+1) = a^(r+1) s + a^(r+2) s (a^r s - 1)/2 + ... ≥ a^(r+1) + a^(r+2) > a^(r+2), contradiction.
I'm sure i'm wrong, but i think you can close the problem easier. When you get s=0 mod (a/2) you can say that this means a/2|s, but a doesn't, this is only possible if a/2 and s in their prime factorization have the same power of 2, but since s is odd also a/2 has to be odd, so a is either 2 or 2*d, where d is an odd number. If a is not 2 choose an odd prime p s.t. p|a, and you can finish the problem as you said. Now there is only the case a=2, so 2^b+1=3^c, mod(3) we have b=2x+1, now we have 2*4^x+1=3^c, mod(3) we have c=2y, which means 2*4^x+1=9^y, mod(5) we have x=2k+1 and y=2h+1, so 8*16^k+1=9*81^h, now if k is not 0 we have 1=9 mod(16), which is impossible, but if k=0 we have h=0, so x=y=1, so b=3 and c=2.
I think in the Zsigmondy's theorem, x and y should has more restriction. For example if x = y = 1, then 2 | x^n+y^n and 2 | x^m + y^m for any m. This theorem fails.
For any natural number a , a^3 +1 will always be less than (a+1)^3. And since (a+1)^c is equal to a^3+1, c< 3 so this only leaves us with the exponent 2. Hope this helps!
I think things went off the rails at 4:00. The theorem he is working with states that "there exists some prime p such that..." not "for all primes p..." but at 4:00 he has not established that the p he is working with is one such prime, so there is no implication that p does not divide a^m+1^m for all m < n. Counterexample: a is any odd number and p is 2, clearly p divides both a^b+1 and a+1. The correct path would be to take the theorem, and make the special case where n=b, y=1 and m=1, at which point the theorem states that for any b != 3 there exists a p that divides a^b+1 but does not divide a+1. From there you get that there exists a prime p that divides a^b+1 but does not divide (a+1)^c thus a^b+1 can never equal (a+1)^c.
He maybe didn't make it super clear but he really meant "Take p to be a prime such that it satisfies the theorem. Then p divides a^b + 1 but p does not divide a + 1. Therefore a^b + 1 cannot be equal to (a+1)^c for any c." That is, you only need one prime to show inequality.
Not saying that your solution is wrong, but using that theorem feels like cheating. In these kind of contests what are the participants supposed to know?
apparently Zsigmondy is pronounced with a 'j' at the beginning (according to one of the other comments)... I'm not sure it's just Americans find this hard.
For Catalan's conjecture you also need m,n > 1, otherwise any consecutive integers are a solution.
7:19 Don’t let what you cannot do interfere with what you can do. Have a good day! 👍
While using a four-fours solver I wrote to solve a different problem, I came across this interesting find:
sqrt(29 - 4) = 29 - 4! = 5
Using a Python program, I brute-forced every pair of numbers a and b (a >= b) that could be substituted instead of 29 and 4 (from 0
this was great... i've come across Zsigmonty's theorem before but never seen it used before. Very neat
But if youbsidnt come across it i don't see why ir how anyone would derive it..so there must be ankther waybto to solve.
It's actually extremely useful and comes up in group theory, too. It's used to prove that various groups have distinct orders unless when the groups are known to be the same.
this example highlights how good theorems can easily solve hard problems 😁
You should have explained how we got to b = 3 better.
If we can find 1 value of m that breaks the for all m
yeah I had to think through this in my head a bit.. kind of gives a proof by contradiction vibe
It is also easy to solve with LTE because if p divides a then p also divides c and the biggest power of p dividing c is shown to be at least b-1, so c is bigger than p^(b-1) who gets quickly bigger than b, and so (a+1)^c gets quickly bigger than a^b+1.
Fun channel He pulls these theorems out of nowhere. Makes me want to start a math PhD program
Without the theorem it will be a pretty complicated problem. Nicely done
2:43 In hungarian 'zs' is pronuonced like 'j' in "journal", not like 's' in "Sigmund" (which is basically the same name as "Zsigmond").
Thanks, I wondered what nationality a name like "Zsigmondy" would be.
Dont worry, Euclid and Archemedes are not pronounced the same way in Greek as are usually called, but that is just a convention :)
Thank you so much
Solution without powerful theorems: Focusing on the case a, b ≥ 2 (the others are trivial), take both sides mod a^2 to get 1 = 1 + ca mod a^2 -> a|c, Thus, we can let c = a^r s where a doesn't divide s and r>0 to get a^b = a^(r+1) s + a^(r+2) s (a^r s - 1)/2 + ...
If a is odd or s is even, take mod a^(r+2) to get a^b = a^(r+1) s mod a^(r+2). The only possibility is b = r+1, so a^(r+1)(s-1) = 0 mod a^(r+2) -> s = 1 mod a -> a^(r+1) = a^(r+1) s + a^(r+2) s (a^r s - 1)/2 ≥ a^(r+1) + a^(r+2) 1(3-1)/2 > a^(r+1), contradiction.
If a is even and s is odd, take both sides mod a^(r+2)/2 to get a^b = a^(r+1) s mod a^(r+2)/2. If b ≥ r+2, then we can reduce further to a^(r+1) s = 0 mod a^(r+2)/2 -> s = 0 mod a/2. If a isn't a power of 2, repeating the same argument but choosing an odd prime p|a, c = p^r s where p doesn't divide s leads to s = 0 mod p, contradiction. Else, choosing the prime 2 gives s odd, but also s = 0 mod a/2 again, contradiction unless a = 2.
This subcase finally leads to 2^b = 2^(r+1) s + 2^(r+1) s(2^r s - 1) + 2^(r+2) s(2^r s - 1)(2^r s - 2)/3 + ... = 2^(2r+1) s^2 + 2^(r+3) s(2^r s - 1)(2^(r-1) s - 1)/3 + ... If r = 1, we obtain 2^b = 8s^2 + 16s(2s-1)(s-1)/3 + ...., and taking mod 8 gives 2^b = 8s^2 = 8 mod 16 -> b = 3, so we recover the solution a=2, b=3, c=2. If r = 2, we obtain 2^b = 32(s^2+s(2s-1)) + 2^(r+4) s(2^r s - 1)(2^r s - 2)(2^r s - 3)/24 + ... = 32(3s^2-s) + 16s(4s-1)(2s-1)(4s-3)/3, taking mod 16 gives b = 4 which doesn't work. Else r>2 -> 2r+1 > r+3 and taking mod 2^(r+4) gives 2^b = 2^(r+3) s(2^r s - 1)(2^(r-1) s - 1)/3 + ... mod 2^(r+4) -> b = r+3 -> 2^(r+3) = 2^(2r+1) s^2 + ... ≥ 2^(r+4), contradiction.
Otherwise a^b (1 - a^(r+1-b) s) = 0 mod a^(r+2)/2 -> a^(r+1-b) s = 1 mod a^(r+2-b)/2. If r ≥ b, then reducing further mod 2 gives 0 = 1 mod 2, contradiction, so b = r+1 -> a^(r+1) = a^(r+1) s + a^(r+1) = a^(r+1) s + a^(r+2) s (a^r s - 1)/2 + ... ≥ a^(r+1) + a^(r+2) > a^(r+2), contradiction.
a dividing c does not imply c = a^r
very hard time following this. Why do the additional term cancel when you take mod a^(r+2) ???
Right in the first case why would additional terms cancel and you be left with a^b = a^(r+1) s mod a^(r+2) ???
I'm sure i'm wrong, but i think you can close the problem easier.
When you get s=0 mod (a/2) you can say that this means a/2|s, but a doesn't, this is only possible if a/2 and s in their prime factorization have the same power of 2, but since s is odd also a/2 has to be odd, so a is either 2 or 2*d, where d is an odd number.
If a is not 2 choose an odd prime p s.t. p|a, and you can finish the problem as you said.
Now there is only the case a=2, so 2^b+1=3^c, mod(3) we have b=2x+1, now we have 2*4^x+1=3^c, mod(3) we have c=2y, which means 2*4^x+1=9^y, mod(5) we have x=2k+1 and y=2h+1, so 8*16^k+1=9*81^h, now if k is not 0 we have 1=9 mod(16), which is impossible, but if k=0 we have h=0, so x=y=1, so b=3 and c=2.
@@thiantromp6607 We let c = a^r s, not c = a^r, and the integer s will always exist.
I think in the Zsigmondy's theorem, x and y should has more restriction.
For example if x = y = 1, then 2 | x^n+y^n and 2 | x^m + y^m for any m. This theorem fails.
x > y > 0
05:24 I didn't understand the "note" part. Why is it suddendly "less than"?
For any natural number a , a^3 +1 will always be less than (a+1)^3.
And since (a+1)^c is equal to a^3+1, c< 3 so this only leaves us with the exponent 2.
Hope this helps!
I think things went off the rails at 4:00. The theorem he is working with states that "there exists some prime p such that..." not "for all primes p..." but at 4:00 he has not established that the p he is working with is one such prime, so there is no implication that p does not divide a^m+1^m for all m < n. Counterexample: a is any odd number and p is 2, clearly p divides both a^b+1 and a+1.
The correct path would be to take the theorem, and make the special case where n=b, y=1 and m=1, at which point the theorem states that for any b != 3 there exists a p that divides a^b+1 but does not divide a+1. From there you get that there exists a prime p that divides a^b+1 but does not divide (a+1)^c thus a^b+1 can never equal (a+1)^c.
He maybe didn't make it super clear but he really meant "Take p to be a prime such that it satisfies the theorem. Then p divides a^b + 1 but p does not divide a + 1. Therefore a^b + 1 cannot be equal to (a+1)^c for any c." That is, you only need one prime to show inequality.
I think that they intend for the high school students to use Binomial theorem to solve it.
That’s kind of amazing that there aren’t any more x,y,m, and n that work for the Catalan equation.
error at 4:00 .. he needs to back up and apply the theorem correctly: there *exists* a prime p, such that .. not "for all p .. "
Not saying that your solution is wrong, but using that theorem feels like cheating. In these kind of contests what are the participants supposed to know?
I commented a solution without advanced tools, presumably the official solution resembles it.
Can i suggest a problem?
You can, use the first link in the video description.
@@goodplacetostop2973 thanks!
so if you filled each sphere with paint you would then paint each surface from the inside with finite amount of paint.
これはすぐに分かった
そこのきみ、
なかなかやるな （ ' ‘ω‘ )っ
@@Tomohiko_JPN_1868
Zsigmondyはつい最近勉強したのでね^_^
Foreign names are really hard for Americans... Mihailescu should be something like M-ee-h-uh-ee-l-e-s-k-oo .... Goog video otherwise.
apparently Zsigmondy is pronounced with a 'j' at the beginning (according to one of the other comments)... I'm not sure it's just Americans find this hard.
@@richardfredlund3802 Well the English j has a bit of a d right at the beginning. The Hungarian Zs is without that.
Woww
🤓
In fact, the only exception of Zsigmondy's theorem is 2^3+1^3=9, which is exactly the solution of this problem. So this is 100% cheating.😂
MICHAEL, NOW HOMEWORK TO FIND AN INTEGER AND POST YOUR COMMENTS! 😁👍
Do not write your post in all caps. It is a form of yelling, and it is rude.
@@robertveith6383 GOOD 👍
@@robertveith6383 DO WRITE YOUR POST IN ALL CAPS!!! 😁😁👍👍
Bad proof
I was born in 2002