Oh hey, I am (one of) the author(s) of this problem! (as in, I came up with this problem on my own and submitted it to the Austrian math olympiad, and only later found out that other people considered this problem before) Made me quite happy to see the problem appear here. :D My original solution is essentially the same as yours. What I can add maybe is that there's another more "brute force"-like solution which is mainly based on the LTE lemma. At the Austrian contest (basically semifinals), the majority of participants who solved the problem actually did it through the LTE method.
@@uffe997 Basically, it goes like this: If k-1 is odd, then LTE says that v_2((n-1)!) = v_2(n^(k-1)-1) = v_2(n-1), which doesn't work for large enough n since clearly (n-1)! is divisible by 2 more often than n-1. If k-1 is even, then LTE says that v_2((n-1)!) = v_2(n^(k-1)-1) = v_2(n-1) + v_2(n+1) + v_2(k-1) - 1. The idea is again to show that the leftmost side is bigger than the rightmost side, which can be done by estimating v_2((n-1)!) using Legendre's formula and estimating all other occurrences of v_2 using logarithms base 2. The variable k can be bounded above by n, since if k>n one gets a contradiction just like in the video. Now the left-hand side grows roughly linearly in n, whereas the right-hand side grows roughly logarithmically in n, so it becomes a matter of checking enough small cases to see that equality cannot hold for large enough n. The full solution (and some minor variants) can be found on the website of the Austrian math olympiad, but is unfortunately only included in the German solutions. (under Wettbewerbe > Aufgaben und Lösungen > 54. Österreichische Mathematik-Olympiade 2023 > Bundeswettbewerb - Vorrunde > Lösungen)
Do you technically have to check the n = 1 case as well since it's a possibility with Wilson's? It's trivial to see it doesn't result in any answers but for a formal proof you'd need it, right?
Could someone elaborate on what mike says about the factorization of powers at 6:40? He seems to say that there's a way to factor n^k - m^k in general. I can see how to generalize the factorization of n^k - n^m, but not the other way.
Yes, it generalizes. n^k - m^k = (n-m)(n^(k-1) + n^(k-2) m + ... + n m^(k-2) + m^(k-1)). You can check that this works by multiplying out the right side. Everything cancels except the extreme left and right terms which are n^k - m^k. You can also see that this matches the difference of squares and difference of cubes factorizations you might have learned in high school. And yes, n = k = 0 is another solution, if you consider 0 to be a natural number.
@@EebstertheGreat Thank you! Also I found out that when you have (n+m) as the factor on the left of the product and alternate signs on the right side, you get a factorization of the sum of two powers if the exponent is odd, and a different factorization for the difference of powers if the exponent is even.
I handled it slightly differently: Case 1 - Let k = 1. n!+n=n => n! = 0 so no solution. Therefore, we can assume that the RHS is n^2 or larger for all future cases. Case 2 - Assume n is even and take everything mod n^2. If we assume n is large enough, then n! = 1*2*...*(n/2)*...*n = a*n^2 for some integer a. What does large enough mean? Well we need our factorial to contain 2, n/2, and n i.e. we need 2 < n/2 ==> 4 < n. Since we assumed n even, we're assuming n >= 6. So for n >= 6, we get 0+n = 0 mod(n^2), which has no solution. From here, you can quickly check n = 2, k = 2 is a solution and n = 4 is no solution. Case 3 - Assume n odd and k >= n. Clearly for n = 1, there is no solution. For n >= 3, the idea here is the RHS will blow up so fast that the LHS can't keep up with it and you can't get a solution. Can be shown via induction with n = 3 as the base case. Case 4 - Assume n odd and k < n. We can manipulate the equation into n! = n^k - n = n(n^[k-1] - 1) = n(n-1)(1 + n + ... + n^[k-2]) ==> (n-2)! = 1 + n + ... + n^[k-2]. Assuming n is large enough, (n-2)! = 1*2*...*(n-1)/2*...*(n-2) = a*(n-1) for some integer a. Specifically, we need 2 < (n-1)/2 < (n-2) ==> n > 5. Since we assume n odd, we're assuming n >= 7. Taking everything mod(n-1), we get 0 = 1 + ... + 1 = k-1. We assumed k < n so k-1 < n-1 and thus can't be 0 mod(n-1). So we get no solutions for n >= 7. From here, you can quickly check n = 3, k = 2 and n = 5, k = 3 are the other 2 solutions.
i think this problem illustrates an interesting sort-of corollary to the strong law of large numbers ("There aren't enough small numbers to meet the many demands made of them.") -- here there's a regularity that holds when the numbers involved are big enough but for the small numbers there isn't enough "space" for that regularity to hold
yep: as brilliantly demonstrated by the Fermat numbers: numbers of the form 2^p-1 where p is itself a prime of the form 2^k-1 for some prime k. Fermat proved the first five were prime, and stopped there as they get very big, very quickly, but he theorized they are all prime. In modern times computers have tested several dozen... and so far, only the first five that Fermat tested are prime, the rest appear to be composite!
If n is a prime number, then n-1 = 1, n-1 = 2 or n-1 is a composite number. This is since if n-1, n are both prime, one of them has to be even, so equal to 2.
I think this is a much simpler problem given that z^w is the same as exp(w*log(z)) so taking the logarithm on both sides we end up with: log(Gamma(z) + z) = log(z^w) = log(exp(w*log(z))) = w*log(z) => w = log(Gamma(z) + z) / log(z). i.e we have a solution for all z where Gamma is defined (i.e. avoiding the negative integers and 0 EDIT: and Gamma(z) + z =/= 0 END EDIT). To get all possible w we need to account for which branch of the logarithm we are taking, but this should just result in: log(Gamma(z) + z) = w*log(z) +2*k*pi*i w = (log(Gamma(z) + z) - 2*k*pi*i) / log(z). with k integer and log representing the principal value of the logarithm. So in essence by allowing the exponent to be in C we just needed to take the logarithm on both sides, removing all complexity of requiring integer solutions.
Ah, just saw the company name on the front of the T shirt. Something for folks who are more athletic than I am. (I cannot erase a chalkboard by doing a backflip! Well, maybe I could if I could do a backflip.)
Start of the video “came from an Austria math Olympia in 2023, so this year if you’re watching this now…” People watching it in 2024 onwards will also be watching it “now” 😂
Oh hey, I am (one of) the author(s) of this problem! (as in, I came up with this problem on my own and submitted it to the Austrian math olympiad, and only later found out that other people considered this problem before) Made me quite happy to see the problem appear here. :D
My original solution is essentially the same as yours. What I can add maybe is that there's another more "brute force"-like solution which is mainly based on the LTE lemma. At the Austrian contest (basically semifinals), the majority of participants who solved the problem actually did it through the LTE method.
Can you sketch the LTE solution?
@@uffe997 Basically, it goes like this: If k-1 is odd, then LTE says that v_2((n-1)!) = v_2(n^(k-1)-1) = v_2(n-1), which doesn't work for large enough n since clearly (n-1)! is divisible by 2 more often than n-1. If k-1 is even, then LTE says that v_2((n-1)!) = v_2(n^(k-1)-1) = v_2(n-1) + v_2(n+1) + v_2(k-1) - 1. The idea is again to show that the leftmost side is bigger than the rightmost side, which can be done by estimating v_2((n-1)!) using Legendre's formula and estimating all other occurrences of v_2 using logarithms base 2. The variable k can be bounded above by n, since if k>n one gets a contradiction just like in the video. Now the left-hand side grows roughly linearly in n, whereas the right-hand side grows roughly logarithmically in n, so it becomes a matter of checking enough small cases to see that equality cannot hold for large enough n.
The full solution (and some minor variants) can be found on the website of the Austrian math olympiad, but is unfortunately only included in the German solutions. (under Wettbewerbe > Aufgaben und Lösungen > 54. Österreichische Mathematik-Olympiade 2023 > Bundeswettbewerb - Vorrunde > Lösungen)
Do you technically have to check the n = 1 case as well since it's a possibility with Wilson's? It's trivial to see it doesn't result in any answers but for a formal proof you'd need it, right?
yes
At 3:10, he does that in words since it's incredibly simple
No. Any integer mod 1 is congruent to 0, so there is no integer congruent to -1 (mod 1).
@@RexxSchneider every integer is congruent to any other integer mod 1. so any integer is congruent to -1 mod 1
@@RexxSchneidercongruence is transitive
This is very hard and very technical. This math Olympiad problem must have stumped most.
Nice application of Wilson's theorem :)
271 000 subscribers... will there be a special event when you reach e times 100 000 subscribes, Michael? :)
How about n!+1=m^2 next? :)
Ramanujan Brocard problem goes hard.
Could someone elaborate on what mike says about the factorization of powers at 6:40?
He seems to say that there's a way to factor n^k - m^k in general. I can see how to generalize the factorization of n^k - n^m, but not the other way.
Yes, it generalizes. n^k - m^k = (n-m)(n^(k-1) + n^(k-2) m + ... + n m^(k-2) + m^(k-1)). You can check that this works by multiplying out the right side. Everything cancels except the extreme left and right terms which are n^k - m^k. You can also see that this matches the difference of squares and difference of cubes factorizations you might have learned in high school.
And yes, n = k = 0 is another solution, if you consider 0 to be a natural number.
@@EebstertheGreat Thank you!
Also I found out that when you have (n+m) as the factor on the left of the product and alternate signs on the right side, you get a factorization of the sum of two powers if the exponent is odd, and a different factorization for the difference of powers if the exponent is even.
I handled it slightly differently:
Case 1 - Let k = 1. n!+n=n => n! = 0 so no solution. Therefore, we can assume that the RHS is n^2 or larger for all future cases.
Case 2 - Assume n is even and take everything mod n^2. If we assume n is large enough, then n! = 1*2*...*(n/2)*...*n = a*n^2 for some integer a. What does large enough mean? Well we need our factorial to contain 2, n/2, and n i.e. we need 2 < n/2 ==> 4 < n. Since we assumed n even, we're assuming n >= 6. So for n >= 6, we get 0+n = 0 mod(n^2), which has no solution. From here, you can quickly check n = 2, k = 2 is a solution and n = 4 is no solution.
Case 3 - Assume n odd and k >= n. Clearly for n = 1, there is no solution. For n >= 3, the idea here is the RHS will blow up so fast that the LHS can't keep up with it and you can't get a solution. Can be shown via induction with n = 3 as the base case.
Case 4 - Assume n odd and k < n. We can manipulate the equation into n! = n^k - n = n(n^[k-1] - 1) = n(n-1)(1 + n + ... + n^[k-2]) ==> (n-2)! = 1 + n + ... + n^[k-2]. Assuming n is large enough, (n-2)! = 1*2*...*(n-1)/2*...*(n-2) = a*(n-1) for some integer a. Specifically, we need 2 < (n-1)/2 < (n-2) ==> n > 5. Since we assume n odd, we're assuming n >= 7. Taking everything mod(n-1), we get 0 = 1 + ... + 1 = k-1. We assumed k < n so k-1 < n-1 and thus can't be 0 mod(n-1). So we get no solutions for n >= 7. From here, you can quickly check n = 3, k = 2 and n = 5, k = 3 are the other 2 solutions.
i think this problem illustrates an interesting sort-of corollary to the strong law of large numbers ("There aren't enough small numbers to meet the many demands made of them.") -- here there's a regularity that holds when the numbers involved are big enough but for the small numbers there isn't enough "space" for that regularity to hold
yep: as brilliantly demonstrated by the Fermat numbers: numbers of the form 2^p-1 where p is itself a prime of the form 2^k-1 for some prime k. Fermat proved the first five were prime, and stopped there as they get very big, very quickly, but he theorized they are all prime. In modern times computers have tested several dozen... and so far, only the first five that Fermat tested are prime, the rest appear to be composite!
Handle with Care - this Way Up!😂🤣😁
11:43
2:30 you forgot to check the case k=0, which gives n=0 as a solution
Generally the definition of N for these problems is the set of strictly positive integers
Isn't n=0,k=0 a 4th solution?
0^0 is undefined
Why does n-1 = 1 and n-2=2 at 3:38?
If n is a prime number, then n-1 = 1, n-1 = 2 or n-1 is a composite number. This is since if n-1, n are both prime, one of them has to be even, so equal to 2.
how can you know what Diophantus considered when most of his work has been lost
how do you expand (n - 2)! into a sum of powers n^(k-2) + .. + n + 1?
He expanded n^(k-1) - 1 which in in this case happens to be equal to (n - 1)!, then reduced by n - 1
Now solve Gamma(z) + z = z^w for z,w in Complexes
I think this is a much simpler problem given that z^w is the same as exp(w*log(z)) so taking the logarithm on both sides we end up with:
log(Gamma(z) + z) = log(z^w) = log(exp(w*log(z))) = w*log(z) =>
w = log(Gamma(z) + z) / log(z).
i.e we have a solution for all z where Gamma is defined (i.e. avoiding the negative integers and 0 EDIT: and Gamma(z) + z =/= 0 END EDIT).
To get all possible w we need to account for which branch of the logarithm we are taking, but this should just result in:
log(Gamma(z) + z) = w*log(z) +2*k*pi*i
w = (log(Gamma(z) + z) - 2*k*pi*i) / log(z).
with k integer and log representing the principal value of the logarithm.
So in essence by allowing the exponent to be in C we just needed to take the logarithm on both sides, removing all complexity of requiring integer solutions.
Very neat!
I did not follow the last board for some reason. What am I missing in knowledge?
The last board is all standard modular arithmetic. Is there a particular step where you got lost?
Nice!
Does anyone know what Michael's T shirt is?
Looks like the symbol in electrical circuits to indicate ground. So, is Michael saying he is grounded?)
Ah, just saw the company name on the front of the T shirt. Something for folks who are more athletic than I am. (I cannot erase a chalkboard by doing a backflip! Well, maybe I could if I could do a backflip.)
{(2,2),(5,3),(3,2)} by guessing
I guessed them all before watching
Start of the video “came from an Austria math Olympia in 2023, so this year if you’re watching this now…”
People watching it in 2024 onwards will also be watching it “now” 😂
Me in 2024: I 𝘢𝘮 watching this now. Wtf?
😳
SFG
Or... instead of n=1 or n is prime, you could just say n is prime :>
See now not only is reality against you once, but twice :>>>>>>>>
asnwer= n isit
🇧🇩🇧🇩🇧🇩🇧🇩
….it’s not super interesting ❤️
Nice video thanks