FUN Ecuadorian Math Olympiad Number Theory Problem
Вставка
- Опубліковано 16 бер 2023
- Normally, there'd be some WILD stuff here, and maybe there still is, but hear me out first...
This is a new and occasional format that we are trying out for the first time and absolutely want your feedback so, please, actually watch the entire video from start to finish and sound off in the comments about what you think of it.
If you don't do the above I cannot guarantee that Chalkboard, her best pal Eraser, and even the dastardly Chalk won't break down in a fit of uncontrollable wail-weeping whereby wispy winds wind willingly with well-wishing wizards wearing wetsuits, watches, wigs - whole wardrobe! Watch the dang video till the end and comment pls ok thx. It'd mean a lot to me, PLUS, did you see that sentence with all those words starting with "w". That's worth something right? RIGHT? Okay anyway, watch video, comment your thoughts on the new format.
-Stephanie
MP Editor
🌟Support the channel🌟
Patreon: / michaelpennmath
Merch: teespring.com/stores/michael-...
My amazon shop: www.amazon.com/shop/michaelpenn
🟢 Discord: / discord
🌟my other channels🌟
mathmajor: / @mathmajor
pennpav podcast: / @thepennpavpodcast7878
🌟My Links🌟
Personal Website: www.michael-penn.net
Instagram: / melp2718
Twitter: / michaelpennmath
Randolph College Math: www.randolphcollege.edu/mathem...
Research Gate profile: www.researchgate.net/profile/...
Google Scholar profile: scholar.google.com/citations?...
🌟How I make Thumbnails🌟
Canva: partner.canva.com/c/3036853/6...
Color Pallet: coolors.co/?ref=61d217df7d705...
🌟Suggest a problem🌟
forms.gle/ea7Pw7HcKePGB4my5
#prime #primes #cubes #cubicequation #numbertheory
He has room for backflips now
the comment section could pressure him into doing backflips at the beginning of every video
he is a rock climber, not a gymnast.
It explains the size of his forearms and biceps
Didn’t seem a hindrance before
i love this very formal number theoretic proof of a lemma that i would've summarized as "well it's gotta be somewhere"
Oh man you are giving me flashbacks to my number theory prof ranting about how mathematicians in the 1600s-1800s would assume p|ab implies p|a or p|b by assuming unique factorization into primes. Apparently only Gauss cared enough to note it's circular reasoning.
@@hybmnzz2658 Euclid also cared, since he proved unique factorization
I think the “well it’s gotta be somewhere” proof assumes unique factorization. Nonetheless, that proof still becomes important in integral domains, when we prove that in UFDs all irreducibles are prime.
@@hybmnzz2658 Eh, that depends heavily on how you define a number to be a prime. For commutative rings for example, p|ab -> p|a or p|b is the definition for a prime in any Principal Ideal Doman (the integers being an example of a PID).
I love it when you solve this kind of problems and teach such nice tricks which can be applied in similar situations and I also appreciate the idea of the two blackboards. The channel is getting better and better, I'm sure you'll get to pi-thousand subscribers soon!
I think that this new format has some potential but there are a few problems. The lighting is a little bit off and some parts of the board are more illuminated than others. Other thing is that you have always had previous steps summarised somewhere in the corner and now despite the fact that you have more space some previous facts were erased and it was harder to recall what was already done. Like the equation for n in terms of x and the problem statement itself that was only on one of the boards
I actually really like the new format! Feels a lot smoother
Working through the bonus problem where p² + p + 1 = n³, the steps are mostly the same but with an occasional sign flip.
Suppose p(p+1) = n³ - 1 = (n-1)(n² + n + 1). Then either p|(n-1) or p|(n² + n + 1)
Case 1 - Suppose p|(n-1), i.e. n-1 = px for some natural x.
Then p ≤ n-1 which implies p+1 ≤ n
But also p(p+1) = px(n² + n + 1) which implies p+1 = xn² + xn + x ≥ n² + n + 1 > n (since x and n are Natural numbers)
So n ≥ p+1 > n, which is a contradiction. Therefore p does not divide (n-1)
Case 2 - Suppose p | n² + n + 1, i.e. n² + n + 1 = px for some natural x
Then p(p+1) = px(n-1), so p = xn - x - 1
Plugging p in, we get n² + n + 1 = nx² - x² - x
Solving for x, we find that the discriminant f(x) = x⁴ - 6x² - 4x - 3 must be a perfect square. (Similar to the video except we have a -4x term instead of a +4x term.)
Similar to the video, set g(x) = (x² - 4)² and h(x) = (x² - 3)² (so instead of 3 and 2 we're using 4 and 3 as the differences for the consecutive squares).
f(x) - g(x) = 2x² - 4x - 19. Note that if you solve for x this is >0 if x>4 or x4 part.
h(x) - f(x) = 4x + 12, which is always >0 for all Natural x.
Therefore if x>4 we have h(x) > f(x) > g(x), which puts f(x) between two consecutive squares. So there can be no solutions where x>4 (just like the video, only with slightly different consecutive squares.)
So the only possible solutions are x = 1, 2, 3, or 4and only if f(x) is itself a perfect square. Recall above f(x) = x⁴ - 6x² - 4x - 3 for reference
f(1) = 1-6-4-3 = -12, not a perfect square
f(2) = 16 - 24 - 8 - 3 = -19, not a perfect square
f(3) = 81 - 54 - 12 - 3 = 12, also not a perfect square
f(4) = 141, not a perfect square
Therefore f(x) is never a perfect square for any natural number x, and thus there are no solutions.
It should be mentioned that n 1 (which is easily checked) in order to conclude
(in Case 1) that p | n -1 implies n -1 = px, where x is a natural number.
f(x) - g(x) = 2x² - 4x - 19 = 2x(x - 2) - 19 > 0, for x >= 5. So, you must also check
that f(4) = 141 isn't a perfect square.
I think you meant "solving for n" not "solving for x".
@@someperson188 Which is not a square.
Your arithmetic is perfect, except
that f(x) - g(x) should end in -19.
The expression is positive when
x is strictly greater than 4, so the
logic still holds.
@@georgelaing2578 Thanks, I corrected that and also added the f(4) case that needs to be explicitly checked.
Whyvdkesbt hevjustbuse this that you can rewrite as p(p-1)= n^3-1 and use that tpnsolve instead of a lemma I don't think most ppl have heard of or would deduce anyway if theyvhavent..cantnyoubthebsplve by saying either p equals n minus 1 and p minus 1 =(n^2 + n +1) or vice versa and you are done?
I never understood why this channel only has 251k, this is a gem!
So Stephanie is the name of our unsung heroine of the description short stories. Shoutout to her!
I'm also the editor lol :)
-Stephanie
MP Editor
I like your video and the format! Please keep going! Thank you!
Love how you are choosing problems that tie into your MathMajor channel and the recent proof writing series. Do continue this trend of having your problems tie into your lectures. Love it.
amazing quality and production, keep up the good work!
It first appeared in St. Petersburg olympiad in 90's, then appeared in Balkan Olympiad
The studio looks awesome!
I also like this problem a lot; Using trial and error on p, 19 is quite large (even for a prime, there's seven smaller ones) so if one tested seven or fewer of them, one would like to conclude that there is no solution, however in such a situation, one would be wrong.
Wow amazing video... Love the new format
Beautiful problem and excelent problem solving!
I would love a series from you doing more 'modern' multivariable calculus as to arrive to the generalized stokes theorem with differential forms
Thorough as ever. The first p|ab bit can be easily proven with prime factorisation.
what an amazing studio!!!
I like your videos
I have learned a lot of formulas from your courses
Thank you so much
Thank you, professor and congratulations on the new set-up.
Now that there is room, are the backflips making a comeback?
The new format is great
I agree. This is so nice. :)
I love the look of the space!
I did really like this one! Thanks
Hello everyone,
p^2-p+1=n^3...(*), as you said there exists a natural x>0 s.t.
px=n^2+n+1 ....(1)
p-1=×(n-1) .......(2)
we have from (1):
px=(n-1)(n+2)+3 multiplying both sides by x, one obtains:
px^2=x(n-1)(n+2)+3x . Using (2), one can write: px^2=(p-1)(n+2)+3x. This equation is equivalent to ,
p(x^2-n-2)=3x-n-2 (it is easy to prove the positivity of both sides). For x>3, we have : 3x^2-n-2>3x-n-2 and since p is a prime (greater than 1) the last equation does not have a solution. Now we need to check the last equation for the cases: x=1, x=2, and x=3. By easy calculation, the equation (*) has a solution for the case x=3 while there are not solutions for the two other cases. For x=3, one can easily determine p and n which they are : p=19 and n=7.
The answer to the question is : there is only one prime which is 19.
Thank you for this good problem.
15:31
this is a bit of minor nitpicking , but -3 is in fact a perfect square, if one works over the Eisenstein integers , specifically it's (1+2ω)^2
I like the new format.
I don't find any primes less than 10,000 for which p^2 + p + 1 works
That checks, I solved it using the same method as the video and the corresponding f(x) is never a perfect square for any natural x in the bonus problem, meaning no solutions.
Michael's previous solve of the same question can be found here: ua-cam.com/video/mYCVZitGsFQ/v-deo.html
Personally, I think his newer solution is cleaner and more elegant.
I love your videos! What is the best way to tackle writing proofs without getting any hints? Does it come with time? Where do most math people get these crazy intuitions to use certain lemmas? Thank you.
Awesome transition at 11:03.... I would like to see it "behind the scenes"
production quality is insane
The colors are excellent by the way
Really nice problem and solution. Two blackboards look optimal.
Beautiful!
What a setup man!
It should be mentioned that n 1 (which is easily checked) in order to conclude (in
Case 1) that p | n -1 implies n -1 = px, where x is a natural number.
True, but it is an easy check.
Nice studio 👌💥❤️
When getting to p | n²+n+1, I tried seeing if there was any way to use Eisenstein integers to solve the problem.
You can immediately deduce that p cannot be an Eisenstein prime, because if it were it would divide either n-j or n-j², meaning n-j = p(a+bj), so pb = -1. Not happening.
Therefore, p = qq* for some Eisenstein prime q.
From there, I was kind of stuck (I didn't try very hard though). If anyone comes up with anything coming from that, I'd be interested to hear about it.
Hey, Michael! The constant term of h(x)-f(x) should be positive seven, not negative seven.
Really good❤
The following solution maybe of interest since it only uses basic facts about divisibility, and the simple observation: if (4i+r)(4k+s)=4l+t, where 0=2 and
thus x>0. But then (n-1)(n-2)>= p(n-2)=p(px-1)>=
p(p-1)=(n-1)m>m and thus 0>-n^2+3n-2+m=4n-1>=11, a
contradiction. Hence m=px for some x>0 and thus
p(p-1)=(n-1)px, i.e., p-1=(n-1)x. Hence m=((n-1)x+1)x.
From 0==n(n+1)=(n-1)x^2+x-1==(n-1)x+x-1=nx-1 (mod 2) we get
n=2k+1 for some k>0 & x=2y+1 for some y>=0, and thus
m-1=n^2+n=4k^2+6k+2=2(2k+1)(k+1) &
m-1=((n-1)x+1)x-1=2k(2y+1)^2+2y=8ky^2+(8k+2)y+2k,
i.e., 2k(k+1)+1=y(4ky+4k+1). From 2 | k(k+1) we get y=4z+1
for some z>=0 and thus
2k^2+2k+1=2k(k+1)+1=(4z+1)(4k(4z+1)+4k+1)=4k(4z+1)^2+
16kz+4z+4k+1, i.e., k^2=2k(4z+1)^2+8kz+2z+k. Hence 2z=kl for
some l>=0 and thus k^2=2k(2kl+1)^2+(4k+1)kl+k, i.e.,
k=2(2kl+1)^2+(4k+1)l+1. Assume(!) that l>=1. Then
k>=2(2k+1)^2+4k+1+1>=2*3^2+4k+2, a contradiction. Hence
l=0 and thus k=3 & z=0 & y=1 & x=3. This gives n=2k+1=7 &
p-1=(n-1)x=6*3=18.
Nice bound on squares. I came to equation through simillar reasoning that (a^2-3)^2+4(a-3)=(a+x)^2 from wich I suspektes only a=3 leading to x=3 is possible solution. Otherwise one could investigate integers u^2+v^2=z^2 maybe?
Hi everyone. There is a writing mistake: h(x)-f(x)=2x^2-4x+7 for x>=4
Nice!
Did you know that there is quite similar problem from Romanian Masters 2023?
Solve x^3+y^3=p(xy+p) where p is prime, x, y are positive integers
Cool math coming from my home country, cool.
very nice ❤
If you wondering like I was, why can't p divide both n-1 and n²+n+1 its because this implies RHS has factor of p², but LHS has factor of only p which wouldn't work
spot on!!
37(n+n+n)=nnn for 0 < n < 10. Sin (666) + Cos (6*6*6) = -1.618... (golden ratio). Belphegor's prime is the palindromic prime number 1000000000000066600000000000001 (10^30 + 666 × 10^14 + 1).
I wonder why we spent time prove this lemma, while it's obvious from the "Fundamental theorem of arithmetic" by the factorization of a and b which gives the factorization of ab.
I suppose the lemma could be the considered as the basis for proving the Fundamental Theorem of Arithmetic.
2 boards are good. But do you know what is better? . Make a 3rd board on the ceiling. I doubt that Michael can climb !!!
What if I told you he's an avid rock climber? lol
-Stephanie
MP Editor
@@MichaelPennMath I think that it was a pretty funny joke based on this fact
343 came up in Domotro's camping/math live-stream last night ~@2:02:40, as a better alternative to 333, because 7*7*7, so that's a cool coincidence.
I know that p=3 is not a solution, but shouldn't we also check that case? Since p could divide both n-1 and n^2+n+1 and that happens when p=3.
the lemma proof is circular!
6:15 If we’re working with natural numbers, you should’ve dispatched (easily, I admit, but necessary nonetheless) with the case n=1 when n-1=0 and p|0 🥴
Great❤
you are right
I came up with a brute force solution by mentally checking all primes less than 100. The only values I could find were p = 19, n = 7. I tried to solve this one algebraically, got nowhere.
رائع قبل المشاهدة
That “W” alliteration though
How about p^2+p+8=n^3? I already found a solution by guess and check. But are there others?
yes, p=31... and can you find the solution to p^2 - p - 8 = n^3 ?
@@conntoolbox p=1801 Don't ever do that to me again.
Is it possible to prove the same if P is not a prime, but any positive integer? It seems. that result should be the same. If it is possible, then it is a part of positive integer solution of the equation y^2-x^3=1 in real numbers.
More difficult because if p is not prime then we can't say it divides a, b or both. One factor might divide a and the other factor might divide b.
What is the brand of your chalk?
For the homework p^2+p+1 = n^3 I get:
p(p+1)=(n-1)(n^2+n+1)
case 1) p|n-1 => n+1 n=1/2 (x^2-1+/- sqrtD) with D=x^4-6x^2-4x-3
Whenever x>=5 we have (x^2-4)^2 < x^4-6x^2-4x-3 < (x^2-3)^2, so try
x=1, D=-12
x=2, D=-19
x=3, D=12
x=4, D=256-96-16-3=141
so D is never a perfect square and there are no solutions
Hey I'm Ecuadorian!
@ 14:14 it should be (x^2-2)^2
Do Steiner math.
Sorry, the correct form is: if (4i+r)(4k+s)=4l+1, where 0
Still not correct, but now i have it: if (4i+r)(4k+s)=4l+1, where 0
😮😮😮niiice problem
The lemma is evident fact
0:33 But you needn't prove that. That is the definition of "prime".
I think I saw this kind of format in a ug entrance exam in India called the CMI entrance. I'd suggest you to have a look at those papers! You'd like them.
Which year's paper mate ?
@@physicorum7107 I'm really not sure bruv.
But I'm definitely sure about what the question was.
It was
p³-p= n⁷-n³.
Where p is a prime and n is any natural number.
The solution almost exactly used this concept in the video.
Do you have to prove the first lemma in the real Olympiad or can you just state it?
I misread the thumbnail at first and thought it was when is sqr(p) - p + 1 = a prime
which is an interesting question, but I couldn't see an obvious pattern, I got to p has to be 6m+1
as for 6m -1 it is divisible by 3 but there appear to be an infinite number of solutions,
thus I thought it seemed a little too difficult for an Olympiad question, so I went back to to
check the video and noticed my mistake.
2 3
3 7
7 43
13 157
67 4423
79 6163
My Solution to the actual:
so first note cube(n) = 1 (mod p)
thus 3 divides p-1 (Fermat's little theorem) as n is not 1 and less than p
thus p = 6m + 1
then cube(n) = 1 (mod 6) so n = 6q + 1
sqr( 6m + 1) - 6m = cube(6q + 1)
36sqr(m) + 6m + 1 = cube(6q)+ 3sqr(6q) + 3(6q) +1
some manipulation produces
6sqr(m) + m = 36cube(q) +18sqr(q) + 3q
thus m = 3k and p = 18k +1
18sqr(k)+k = 12cube(q) +6sqr(q) + q
pk = q(12sqr(q) +6q + 1)
gcd(q, 12sqr(q) +6q + 1) =1 and gcd(p, k) =1
so q divides p or 12sqr(q) +6q + 1 divides p
but p prime so if a number divides p then that number = 1 or p
12sqr(q) +6q + 1 can't be 1
so q = 1
so pk = 19
thus k =1
and p = 19 and n = 7
I saw a comment about a Test Problem:
sqr(p) + p + 1 = a cube
similarly 3 divides p-1
thus p = 6m + 1
then cube(n) = 3 (mod 6) so n = 6q + 3
thus cube(n) = 0 (mod 9)
but sqr(p) = 1 + 12m (mod 9)
then sqr(p) + p = 2 (mod 9)
and so sqr(p) + p + 1 = 3 (mod 9)
contradiction no such p and n exist
You went wrong at the point you said "so q divides p or 12sqr(q) +6q + 1 divides p". That doesn't follow from the gcd conditions you established.
Why such a convoluted proof for the lemma? The prime factorization of ab contains p (because p is a prime), and this guarantees p is a factor of either a, or b, or both.
How would you prove that the prime factorization of ab contains p?
@@YAWTonIt's given that p is a prime. It's given that p divides (=is a factor of) ab. If it's prime and it's a factor, it follows that it is a prime factor.
Is that proof enough?
@@whycantiremainanonymous8091 No, it isn't, unless if you _assume_ the fundamental theorem of arithmetic, which is a consequence of the lemma that that he proves in the first few minutes of the clip. But of course, in a Math Olympiad Problem you could probably assume knowledge of the fundamental theorem...
@@YAWTon Yeah, you should be able to assume it 😃 It's definitely a better known theorem than the one MP used. Otherwise, "Solve without relying on the fundamental theorem of arithmetic" should be typed in boldface all over the problem...
@@whycantiremainanonymous8091 Yes, I agree that one could assume the theorem. But the proof of the lemma wasn't "convoluted".
The two consecutive squares come out of the blue. Why have you chosen those squares?
Yeah, the solution is quite contrived, and far from obvious. It DOES depend a lot on you being lucky enogh to find quite a few saving ideas! I don't think it's a fair problem ....
niceeeeeeeeeeeeee
Couldn't that first lemma be proven in one step by just using the fundamental theorem of arithmetic?
that's circular reasoning
all the proofs of fta i have seen use p|ab implies p|a or p|b. i suppose it might be possible to prove it without using that though
The long shots of your new
environment are quite
dramatic!!!
h(x) - f(x) = 2x² - 4x + 7 ?
Not clear to me as well.
Were students expected to solve this problem from a standing start in an exam room?
Not exactly rigorous proof, but:
Lemma: all math-olympiad problems that ask you to find all numbers having a certain property have a finite set of answers :) (or a formula, but there is no formula for prime numbers [that we know of :) ].
Proof by exhaustive search of all problems in all math olympiads :)
Therefore, we start enumerating prime numbers and stop when 19 is reached. The proof that only one exists is left as an exercise to some other troll :)
Basado
I have met for the first Bezout Theorem when I was 19 and never really understood it. Thanks to this video and your explanations I finally got it...30 years later. Thank you so much.
guy's too smart for me ...
June emoji
Am I supposed to understand whats going on?
Case 1 you neglected n=1 case, in which case x is 0. It doesn't work, but you didn't rule it out.
p=19, n=7 🤪
How would you get such a time consuming problem done during a math olympiad??
Michael is really fleshing out the solution, in competition you’d not have to prove the lemma etc.
-Stephanie
MP Editor
@@MichaelPennMath oh okay! I was assuming the lemma proof was required lol
Why isn’t the proof of lemma just… write out the prime factorizations of a and b. What is it with this guy’s love of lengthy, obfuscating proofs?
You can't divide 57 by 3, 57 is a prime. Grothendieck told me so.
I remember this math problem pretty easy for even 9th grade
How stupid is, in order to try factorizing the equation pp-p+1=ppp , subtracting p from both sides of the equation and then:
pp-2p+1 = ppp-p = (p-1)^2 = p(pp-1) = (p-1)(p-1) = p(p-1)(p+1)
So p=1 (but is that a prime?) or p-1=pp+p
The latter solves the same as pp+1=0 so has no real solutions and hence no (extra) primes.
I boycott all products advertised on UA-cam #BoycottYTads
Going too fast. Got lost really quickly. Math experts make the worst teachers because they assume their audience already understands some fundamentals.