International Mathematical Olympiad | 1999 Q4

[@ivarangquist9184]

Just wanted to say that this is IMO problem I've ever solved :D I'm very happy, but since I don't really have anyone to share it with, I will share it with you guys!

[@leofilmont2631]

Amazing video !! This is definitely one of the hardest problems I came across on this channel. I ended up finding a much longer solution than this one (after struggling for hours and hours 😳), but not uninteresting for all that. I started by solving the case where x is divisible by p right the same way as in the video, wich allows then to assume that x is coprime with p, and that way to have m×x + n×p = 1 for some whole numbers m and n (Bezout). Then the fact that x^(p-1) divides (p-1)^x + 1 implies x| (p-1)^x +1 which implies x | (n^x) ×((p-1)^x +1) x| (np-n)^x + n^x x| (1 - mx -n)^x + n^x x| (1-n)^x + n^x and given that x is odd, x | n^x - (n-1)^x So I proved that this is impossible except if x=1, which is also a pretty interesting result : the difference of two consecutive numbers raised to the power x is not divisible by x unless x is equal to one. So yeah if anyone is interested in this problem...😁😁 it's worth a try. Great video anyway, great problems, great channel...hope it'll continue like that.

[@rgqwerty63]

Small correction at 12:05, (q-1,x) = 1 because q is the smallest prime divisor of x, not because q is any old divisor of x. eg x=20 q=5

[@rahafa3382]

also q-1 is even , x is odd and q-1 is less than x

[@kt3pkmn27]

A (probably) easier way to finish is to square both sides by the time we get to: (p-1)^x = -1(mod q) (p-1)^(2x) = 1(mod q) By Fermat's Little, (q-1) must divide 2x (do you see why?). Since q is the smallest odd prime divisor of x, (q-1) will not divide x (on other problems, be careful when q can be 2); Therefore, (q-1) must divide 2. It follows q=3. Once we get q | p, we're done.

[@otakurocklee]

I like your idea, but I think you're slightly off. We don't know that (q-1) must divide 2x from Fermat's little theorem. We know that a common factor d of (q-1) and 2x has (p-1)^d = 1 (mod q). The only common factors of (q-1) and 2x are 1 and 2. We know that since (p-1)^x = -1(mod q), we know d is not 1. Hence d is 2 and (p-1)^2 = 1 (mod q). That gives us (p-1) = -1 (mod q). So we get p=q. But we still need the additional part in the video to get p=3.

[@kt3pkmn27]

@@otakurocklee You're right. I was trying to use the concept of orders, but I think I wasn't too careful about it. Here's a more correct line of reasoning to get q=3: x = 0 (mod q) (x-1) = -1 (mod q) (x-1)^2 = 1 (mod q) We deduce 2 is the order of (x-1) mod q; hence, 2 | q-1 q=3.

[@otakurocklee]

@@kt3pkmn27 But how do you get from 2|q-1 to q=3. 2|q-1 can also mean q=7 or q=11.

[@Miguel-xd7xp]

@@otakurocklee q is the smallest prime that q|x I think that is for that

[@digxx]

@@Miguel-xd7xp I don't see it. q=7 could be the smallest prime...

[@antoniopalacios8160]

It is really elegant how you resolve the ambiguity (p-1) congruent with +- 1 (mod q), obtaining p-1 congruent with -1 (mod q) by having to be a=odd.

[@limerent]

Amazing solution! It was an unexpected use of Bezouts gcd trick, good job.

[@leif1075]

Is that the only solution?

[@leif1075]

Isnt there a way to solve it without Bezoutz trick?

[@supercube3523]

The combination of Bezout's with Fermat is so beautiful!! By the way, it seems we can also get to x=p without using Bezout's theorem. starting from (p-1)^x + 1 = 0 (mod x) we have (p-1)^x = -1 (mod x) and then x will not divide p-1 Fermat's little therom: (p-1)^(x-1) = 1 (mod x) (p-1)^x = p-1 (mod x) and (p-1)^x = p-1 = -1 (mod x) p=0 (mod x) x will divide p (odd prime) and x>=3 means x = p

[@tonyha8888]

You assume x is a prime, which is not true.

[@appleyuan8710]

@@tonyha8888 x is actually a prime when p >= 3, x > 1. Obviously, x is odd, since (p - 1)^x + 1 is odd. A more reasonable way using Fermat's little theorem might be: Let x = m*n where m is an odd prime factor and n is an odd factor. (p-1)^x + 1 can be divided by x means it can be divided by m. We have (p-1)^x + 1 = (p-1)^(m*n) + 1 = ((p-1)^m)^n + 1 = 0 (mod m). According to Fermat's little theorem: (p-1)^m = (p-1) (mod m) and we have (p-1)^n = -1 (mod m). Since n is odd, p - 1 = -1 (mod m) and p = 0 (mod m), which means p can be divided by m (>=3). So m = p and x = np. Note that x

[@josephgrossenbacher7642]

Michael , yours are some of the best maths-vids here on "youtube" , so thanks : i always enjoy them if i can spare some time ... !!!

[@sirgog]

A problem from my second IMO! Got 5/7 for it, which usually means I solved most of the problem but missed a non-trivial but not too complex case. Can't remember the solution I had in the exam. Questions 1 and 3 were so much more memorable from this IMO.

[@adrianamor8472]

11:54 let x = 54, q = 3, then we have x = 18 q, so q | x. Also q - 1 = 2 and q-1 shares a common divisor with x, which is 2. I think he should be more clear when these facts are stated as to what conditions exactly x and q must meet (independently of previous facts assumed in a different context).

[@최용휘-n8k]

재밌어요! 24분동안 지루하지 않게 이해가 잘 되면서 들었습니다. 감사해요

[@hoangkhongngo]

In fact, Order of an integer and Lifting the exponent Lemma can be used to shorten the solution. Besides, using the above tools helps us ignore the hypothesis that x

[@3manthing]

Very nice. Love the approach and your explanation. :)

[@sumukhhegde6677]

Great!! Please make videos more of this kind

[@sumukhhegde6677]

@Bigblrman75 Surya 😁😁😁

[@rd-bz8dg]

Good work man! Luv ur vids 😊😀😄

[@jakobus5098]

LTE destroy the problem : suppose p > 3 and so x odd and > 1. Since x^(p-1) divides (p-1)^x + 1, we have v_p(x^(p-1)) = (p-1)v_p(x) = 1, this is trivially false, so v_p(x) must be equal to 0. So p doesnt divide x and x^(p-1), but divides (p-1)^x + 1 (since v_p((p-1)^x +1)>0), impossible bc x > 1. So p

[@goodplacetostop2973]

24:09

[@aleksapupovac]

Nice

[@stefanstojkovic8712]

Nice

[@cletushumphrey9163]

Nice

[@dheerdaksh]

Nice

[@helo3827]

Nice

[@ArunIyerS]

Very interesting use of Bezout's with Fermat!

[@POOJASingh-mq6kx]

Seeing your videos makes me feel that even imo problems are very easy😂

[@drpkmath12345]

Love number theory for sure!

[@lucassandleris4486]

Maybe an easier way to finish it off could've been to use Lifting the expoment Lemma, by arguing that vp(1^p+(p-1)^p)=vp(p)+vp(p-1+1)=2 therefore p-1≤2 thus p≤3. Checking the case p=3 finishes it.

[@shokan7178]

Small nitpick: Whenever you say "Give this problem ago with the hints", you have stood in front of the problem for about a minute by now and I can't remember the problem! :)

[@yashvardhan2093]

Sir I did that part you told if x=2 then the divisor is even but that implies that the rhs is also even now -2(p-1) is even and for the entire term to be even p^2 is even but that clearly implies p =2 and x=2 is only such solution

[@irbesbayan-aula7374]

Brilliant Solution. Thank You.

[@vtvtify]

12:51 but what about the case where the x coefficient is negative and the q-1 coefficient is positive?

[@yassinezaoui4555]

Excellent 👏👏👏

[@JoGurk]

how the hell are you supposed to solve this right away, even if you are IMO partitipant?!

[@justforfun2238]

Why would u expect an IMO participant to solve it right away?

[@nurtasshyntas7745]

@@justforfun2238 because it's problem #4. I would say that it's just experience - one familiar with orders modulo primes will in no time recognize the solution.

[@roboto12345]

Literally you just play with LTE lemma if you have no idea of how to proceed and as @Nurtas Shyntas said it is just order of an element

[@leif1075]

@@nurtasshyntas7745 but if you have NEVER heard of Fermat or Bezout isnt this impossible tonsolve and so not a fair test of intelligence or problem solving ability?

[@justforfun2238]

@@leif1075 mathematical knowledge is definitely needed in IMO

[@ThePharphis]

This one seems difficult. Thanks for sharing

[@petros_adamopoulos]

Could we call it a "Chalk drop"?

[@VishnuSrivatsava]

what an amazing approach

[@rogueartist9419]

isnt bezouts Identity ax+by=1 ... why he wrote ax-by=1?

[@aweebthatlovesmath4220]

bezouts identity is ax+by=gcd(x,y) He decided to take b a negative number that's allowed if we don't have b.

[@djvalentedochp]

I am jubilant right now

[@leif1075]

Why?

[@djvalentedochp]

@@leif1075 because of the stunning solution Michael Penn had to this problem

[@leif1075]

@@djvalentedochp oh ok

[@rksemwal8116]

yo man no views?

[@donaldbiden7927]

how r u 1 week earlier ? u a patreonn ?

[@djvalentedochp]

Wait.... how is that possible? 😂😂

[@xriccardo1831]

He leaves them unlisted and then makes them public

[@djvalentedochp]

Oh now I see

[@g_g9078]

1 is a prime number, kinda cringe