That first chart has an error... for n = 4 and m = 2 we have m^2 + 9 = 4 + 9 = 13, not 15. m = 6 does work, though, since 6^2 + 9 = 45 and that is a number divisible by 15 (45 = 3*15).
Nice solution, this problem is from the 1998 shortlist N5, and I think that it is somekind classical. By the way the number theory problem that came at the contest was Find all x,y positive integers such that xy^2+y+7|x^2y+x+y
OPEN PROBLEM : I often found interesting problems but because I haven’t found solutions, I’ve ditched them... until today. From now I will post them as open problems and I will not provide solutions or answers. The sequence is {s(n)}, n from 1 to infinity, is defined by s(n) = ∑(-1)^(m-1) x m^(n-(m-1)), m from 1 to n. * s(1) = 1^1 = 1 * s(2) = 1^2 - 2^1 = -1 * s(3) = 1^3 - 2^2 + 3^1 = 0 * s(4) = 1^4 - 2^3 + 3^2 - 4^1 = -2 Does s(n) = 0 ever occur again for some n > 3? SOURCE : Crux Mathematicorum Vol. 10, No. 9
Wrt why it possibly was not chosen as an actual IMO task: It seems to me, that solving this would take a lot of time, e.g. even calculating the chart that you magically put on the board. Without the chart though, it might be vey hard to get to the right solution. Also there are so many details about the solutions, that dividing the 10points would seem fairly ambigious (don't know if that's a good term anyway). Also, (I do not know, if it is a good reason after all) , solving this must make anyone feel like they are not on the right track the whole time, because it all seems so sketchy.
The chart is the real issue indeed. Don't forget that all N/A entries are actually miniproofs in their own right and actually getting the m for n=8 I assume is qute tricky ( without knowing the constructive proof with CRT )
Another highly interesting, educational and enjoyable video! How on earth did you manage to store up enough videos while your setup is being worked on? Are the outdoor/ whiteboard videos still ‘live’?
Very nice problem. What I like is a related theorem u have used. The amount of ways to express a number as a sum of two squares. The number of representations of n as a sum of two squares is four times the difference between the number of divisors of n congruent to 1 modulo 4 and the number of divisors of n congruent to 3 modulo 4. How to come up with such a claim and then Proof it? This is insane.
The proof uses the supplement of the law of quadratic reciprocity (cf. en.wikipedia.org/wiki/Quadratic_reciprocity#q_=_±1_and_the_first_supplement ), which determines if -1 is a quadratic residue or not.
I searched further and I found that it can also be show easily by "Sum of two squares theorem." (cf. en.wikipedia.org/wiki/Sum_of_two_squares_theorem ) SPS. a^2 + b^2 = kp (k in N and p: prime; p≡3 (mod 4)) Using the facts a^2 ≡ (a+zp)^2 (mod p) and a^2 ≡ (p-a)^2 (mod p), we can show there exist integers a', b' in [0, (p-1)/2] s.t. a'^2 + b'^2 = k'p, a≡a' (mod p), and b≡b' (mod p). By the sum of two squares theorem, k' is divisable by p and a'^2 + b'^2 = lp^2 (l in N; k'=lp). However, 0
Just to clarify: let p be a prime number congruent to 3 mod 4. Then p= 4k+3 for some integer k. Then m^2=-9 mod p and m^(2*(2k+1)) = - 3^(2*(2k+1)) mod p so m^(4k+2) = -3^(4k+2) mod p but from Fermat's Little Therom we know that 1=m^(4k+2) = -3^(4k+2) = - 1, so 2=0 mod p which is impossible
There is also a very theoretical proof of the fact that the powers of two works. It suffices to show that the 2^2^n-1 has only comprised of primes of the form 4k+1 (except for a single 3) via the Chinese remainder theorem and the fact that any prime of the form 4k+1 divides some m^2+1. And for that just notice that 2^2^n-1=(2^2^(n-1)+1)(2^2^(n-2)+1)*17*5*3 i.e. the product of the fermat numbers. And it is again well known that all prime divisors of 2^2^n+1 for n>=2 is of the form 2^(k+2)+1 which is a much stronger statement than just 2^2+1 (the fact that they have to be of the form 2^k+1 can be proved easily via the orders mod p where p is the divisor of the fermat number, to improve it one has to for example notice that 2 has to be a quadratic residue mod this prime).
I thought that proving that p doesn't divide m^2+9 could be checked in a more satisfying way by considering quadratic residues. Clearly p divides m^2+9 iff m^2+9 ≡ 0 mod p. Then m^2 ≡ -9 mod p. In other words -9 is a quadratic residue mod p. So we need only compute the Legendre symbol L(-9,p). Now L(-9,p) = L(-1,p) L(9,p) = L(-1,p) L(3,p)^2. So if p ≠ 3, then L(3,p)^2 = 1, since L(3,p) is in {-1,1}. Therefore if p ≠ 3, L(-9,p) = L(-1,p). And L(-1,p) = 1 iff p ≡ 1 mod 4. So if p ≠ 3 and p ≡ 3 mod 4, then we have L(-9,p) = -1, so -9 is a quadratic non-residue mod p, so p doesn't divide m^2+9.
Before video: any n such that 9 mod 2^n-1 +( x mod 2^n-1)^2 = 0, has a solution if (2^n-1) - 9 mod (2^n-1) < ( 2^n-1) /2 For instance, when n=3, 2^n-1= 7, therefore we have 7-9 mod 7, = 5, 5> 7/2 so there are no valid solutions. n=4, 2^n-1=15, 15-9=6, 6 31/2, there will not exist such a number. Since 9 never increases, we know from now on, (2^n-1) - 9 >( 2^n-1) /2 so there are no possible valid solutions above n=5. round off with 1 and 2, 1-9 mod 1 is arbitrary/ meaningless to say, but essentially it = 0. So yes it must have a valid solution. 0
This problem was kind of the first imo problem I was able to solve at least an 80% of. Looks like this problem was relatively easier due to which it wasn't added.
@4:20, if n is not a power of 2 then it has an odd divisor. That divisor could be 1, for example, if n=7 or any other prime which is not a power of 2. In the above calculation that corresponds to d=1. This means the factor that u are interested in 2^d-1=1; which as we know divides all numbers. In order to show that 2^d-1 does not divide m^2+9, you had to assume d>1 in the claim of your proof that p divides 2^d-1. Also for all "things" after this, you assumed that d>1.
That first chart has an error... for n = 4 and m = 2 we have m^2 + 9 = 4 + 9 = 13, not 15. m = 6 does work, though, since 6^2 + 9 = 45 and that is a number divisible by 15 (45 = 3*15).
What I thought
And 2^5 - 1 = 31 not 33
Lift your game, Michael 😉
At 2:51 m is not 2 when n is 4. In fact, in that case m should be 6, because 6²+9=45=15×3. Anyway really good problem!!
More generally: it can be any number congruent to 6 or 9 mod 15.
Nice solution, this problem is from the 1998 shortlist N5, and I think that it is somekind classical.
By the way the number theory problem that came at the contest was
Find all x,y positive integers such that
xy^2+y+7|x^2y+x+y
wow i remember solving it and i really love ur channel
Nice try to catch us with 2²+9=15 but it's actually equal to 13 ;)
No, but it's wrong but correct answer is 2²+9=13. Yes.
17:07
2:56 how 2^2+9=15?
4+9 is not equals to 15 right?
Finally, some high quality problem!!!! thanks :D
Best explanation ever
if m=2 it becomes 2^2 + 9 = 13 and not 15
OPEN PROBLEM : I often found interesting problems but because I haven’t found solutions, I’ve ditched them... until today. From now I will post them as open problems and I will not provide solutions or answers.
The sequence is {s(n)}, n from 1 to infinity, is defined by s(n) = ∑(-1)^(m-1) x m^(n-(m-1)), m from 1 to n.
* s(1) = 1^1 = 1
* s(2) = 1^2 - 2^1 = -1
* s(3) = 1^3 - 2^2 + 3^1 = 0
* s(4) = 1^4 - 2^3 + 3^2 - 4^1 = -2
Does s(n) = 0 ever occur again for some n > 3?
SOURCE : Crux Mathematicorum Vol. 10, No. 9
Do you mean besides s(5)=s(1)?
@@hyperboloidofonesheet1036 Oof the typo happened at the worst place, my bad. We’re looking for a n such that s(n) = 0, n > 3.
@@goodplacetostop2973 Ah. Okay. Good one. I get the feeling there is a characteristic polynomial associated with the answer.
Nice video, learning number theory rn :D
Wrt why it possibly was not chosen as an actual IMO task:
It seems to me, that solving this would take a lot of time, e.g. even calculating the chart that you magically put on the board. Without the chart though, it might be vey hard to get to the right solution.
Also there are so many details about the solutions, that dividing the 10points would seem fairly ambigious (don't know if that's a good term anyway).
Also, (I do not know, if it is a good reason after all) , solving this must make anyone feel like they are not on the right track the whole time, because it all seems so sketchy.
The chart is the real issue indeed. Don't forget that all N/A entries are actually miniproofs in their own right and actually getting the m for n=8 I assume is qute tricky ( without knowing the constructive proof with CRT )
Another highly interesting, educational and enjoyable video! How on earth did you manage to store up enough videos while your setup is being worked on? Are the outdoor/ whiteboard videos still ‘live’?
For the application of CRT you need to say the divisors are coprime. They clearly are in this case but would be nice to mention it
does anybody know the name of the theorem that states that an odd sum of squares divisible by prime p requires all squares divisible by p
i think its zsigmody's theorem
There is a mistake in the chart m=2 is not a solution bc m²+9=13 not 15
0:29 😂😂😂😂
I like the way you put memes in some vidios
very helpful
Trade offer
I receive: some natural number
You receive: solution to mathematical problem
2^2+9 doesn’t equal 15
Very nice problem.
What I like is a related theorem u have used.
The amount of ways to express a number as a sum of two squares.
The number of representations of n as a sum of two squares is four times the difference between the number of divisors of n congruent to 1 modulo 4 and the number of divisors of n congruent to 3 modulo 4.
How to come up with such a claim and then Proof it?
This is insane.
Also, 2^5-1 is not equal to 33.
2^2 + 9 is not equal to 15, also 2^5 -1 = 32-1 = 31 so not 33 michael
8:18 Does some know why p|m^2+9 implies p|m^2 and p|9 ? Why we don't need to consider the cases p|m^2-2 and p|11, p|m^2-4 and p|13, or ...?
math.stackexchange.com/questions/2442921/if-a-prime-of-the-form-4k3-divides-the-sum-of-two-squares-then-it-divides
Had to look it up myself
@@dimy931 Thanks a lot. Does that property have a name?
@@HideyukiWatanabe Not that I know of. Looks like one of these small unnamed lemas/theorems number theory is full of
The proof uses the supplement of the law of quadratic reciprocity (cf. en.wikipedia.org/wiki/Quadratic_reciprocity#q_=_±1_and_the_first_supplement ),
which determines if -1 is a quadratic residue or not.
I searched further and I found that it can also be show easily by "Sum of two squares theorem." (cf. en.wikipedia.org/wiki/Sum_of_two_squares_theorem )
SPS. a^2 + b^2 = kp (k in N and p: prime; p≡3 (mod 4))
Using the facts a^2 ≡ (a+zp)^2 (mod p) and a^2 ≡ (p-a)^2 (mod p), we can show there exist integers a', b' in [0, (p-1)/2] s.t.
a'^2 + b'^2 = k'p, a≡a' (mod p), and b≡b' (mod p).
By the sum of two squares theorem, k' is divisable by p and
a'^2 + b'^2 = lp^2 (l in N; k'=lp).
However, 0
Astonishing that a man that knows all this number theory states 4+9=15 🤣🤣🤣
Just to clarify: let p be a prime number congruent to 3 mod 4. Then p= 4k+3 for some integer k. Then m^2=-9 mod p and m^(2*(2k+1)) = - 3^(2*(2k+1)) mod p so m^(4k+2) = -3^(4k+2) mod p but from Fermat's Little Therom we know that 1=m^(4k+2) = -3^(4k+2) = - 1, so 2=0 mod p which is impossible
Thanks. That's what I was looking for.
Are they Mersenne numbers?
Breach, broach, tomato, tomato.
There is also a very theoretical proof of the fact that the powers of two works. It suffices to show that the 2^2^n-1 has only comprised of primes of the form 4k+1 (except for a single 3) via the Chinese remainder theorem and the fact that any prime of the form 4k+1 divides some m^2+1. And for that just notice that 2^2^n-1=(2^2^(n-1)+1)(2^2^(n-2)+1)*17*5*3 i.e. the product of the fermat numbers. And it is again well known that all prime divisors of 2^2^n+1 for n>=2 is of the form 2^(k+2)+1 which is a much stronger statement than just 2^2+1 (the fact that they have to be of the form 2^k+1 can be proved easily via the orders mod p where p is the divisor of the fermat number, to improve it one has to for example notice that 2 has to be a quadratic residue mod this prime).
Some of the tricks are not available to average high school students, so this problem could not be included in IMO.
The imo is not for high school students
It is for high school students, but definitely not average high school students :)
I thought that proving that p doesn't divide m^2+9 could be checked in a more satisfying way by considering quadratic residues. Clearly p divides m^2+9 iff m^2+9 ≡ 0 mod p. Then m^2 ≡ -9 mod p. In other words -9 is a quadratic residue mod p. So we need only compute the Legendre symbol L(-9,p). Now L(-9,p) = L(-1,p) L(9,p) = L(-1,p) L(3,p)^2. So if p ≠ 3, then L(3,p)^2 = 1, since L(3,p) is in {-1,1}. Therefore if p ≠ 3, L(-9,p) = L(-1,p). And L(-1,p) = 1 iff p ≡ 1 mod 4. So if p ≠ 3 and p ≡ 3 mod 4, then we have L(-9,p) = -1, so -9 is a quadratic non-residue mod p, so p doesn't divide m^2+9.
Yeah precisely bro
Isn’t this competition for 17/18 year olds, so they are not going to know about Legendre symbols?
@@AlephThree idk, I know many ppl my age (16/17) who know about quadratic residues
Basically like this problem reduces it self to finding all n for which -1 is a quadratic residue mod 2ⁿ-1
Like using this it's fairly easy to show that it works for when n is a power of two
Before video:
any n such that 9 mod 2^n-1 +( x mod 2^n-1)^2 = 0, has a solution if (2^n-1) - 9 mod (2^n-1) < ( 2^n-1) /2
For instance, when n=3, 2^n-1= 7, therefore we have 7-9 mod 7, = 5, 5> 7/2 so there are no valid solutions.
n=4, 2^n-1=15, 15-9=6, 6 31/2, there will not exist such a number. Since 9 never increases, we know from now on, (2^n-1) - 9 >( 2^n-1) /2
so there are no possible valid solutions above n=5.
round off with 1 and 2,
1-9 mod 1 is arbitrary/ meaningless to say, but essentially it = 0. So yes it must have a valid solution. 0
2^5 - 1 = 31
This problem was kind of the first imo problem I was able to solve at least an 80% of. Looks like this problem was relatively easier due to which it wasn't added.
4+9=13
2^5-1 = 31 not 33
n=4 requires m=6 not 2
Help me int(z^2/(z^4+2z^2+5,0,∞ )
I can confidently state you were drunk making this video.
LOL
@4:20, if n is not a power of 2 then it has an odd divisor. That divisor could be 1, for example, if n=7 or any other prime which is not a power of 2. In the above calculation that corresponds to d=1. This means the factor that u are interested in 2^d-1=1; which as we know divides all numbers. In order to show that 2^d-1 does not divide m^2+9, you had to assume d>1 in the claim of your proof that p divides 2^d-1. Also for all "things" after this, you assumed that d>1.
This question is not easy.
Very nice video sir.You can't miss the maths and science tutorials. hurry and check it out. THANKS
I don't get the sum of squares bit. Doesn't seem to work for 3^2 + 4^2.
The statement is that if p|a^2+b^2 and p is 3 mod 4, then p|a and p|b. In your example, 3^2+4^2=25, and no prime that is 3 mod 4 divides 25.
@@willnewman9783 Thanks, missed the first bit.
this became my favorite number theory problem, what a beautiful result!
Does anybody know where is this problem from?
hats off to the guy who proposed this problem, so many ideas at once damn, very hard and beautiful indeed.
Alternative solution:
Use excel try thousands of values of m and dozens of values of n.
You made hella mistakes today 🤔
Problems in number theory can be understood by a non mathematician. Some problems are annoyingly difficult. Somethings in number theory are ad hoc.