IMO 2024 Problem 2 - If you LOVE *number theory* and HATE *geometry*, it's a field day!

#mathematics #olympiad #math
International Mathematical Olympiad (IMO) 2024 Day 1
Solutions and discussion of problem 2
65th International Mathematical Olympiad Bath UK
Problem 2 - Number Theory

[@valentioiverson599]

This is my problem! Great explanation and motivation :) Hope you enjoy the problem.

[@JoPaskalis]

Kerennnn🔥🔥

[@dedekindcuts3589]

Amazing!!

[@Linhkinhbrods]

could u stop capping? everyone knows it's just a cap

[@JoPaskalis]

@@Linhkinhbrods no bro, he isnt lie. in my country, he is a gold medalist and absolute winner in our National Olympiad.

[@bamsuth9650]

hes our gold medalist ​@@Linhkinhbrods

[@zmaj12321]

q=ab+1 felt natural to me because of that lcm problem from the Japan Math Olympiad you posted recently (in that video, we set n+f(m)=mf(m)+1 to make gcd(n+f(m), m)=gcd(n+f(m), f(m))=1).

[@dedekindcuts3589]

That's great to hear! Yeah doing similar problems before helps!

[@PetersLabAviation]

really clear explanation and solution! looking forward to turbo the snail :D

[@dedekindcuts3589]

😂

[@dedekindcuts3589]

I think this is a quite an elegant problem! At the same time, it is not impossible. What do you think?

[@user-mt3qb9pr1f]

This video was very helpful to turn back my sense of imo problems.

[@wesleydeng71]

Can be a little quicker in the end: if q | a-1 then a-1=0 since q>a.

[@wintersfan]

I love Number Theory but failed to solve this in the IMO 😢

[@Ephemeral_EuphoriaYT]

Damn u went to imo?

[@awkwardhamster8541]

i proved for (a,b) with gcd=1 , setting x=a+b , for every n=T*(ord of b modulo x)+1 , g=(a multiple of x) . And otherwise , g =1 . Then i had to prove for wlog a1 and I divided it into 2 cases being 1)k=a and 2) k

[@vlv5434]

I found the solution in this way:
let q>2 is prime and not divide a,b. We want q | GSD(n). Then a^n=-b mod q, b^n = (-a^n)^n = (-1)^n * a^(n^2) = -a , a^(n^2-1) = a^((n-1)*(n+1)) = (-1)^(n+1) mod q.
It is easy to see that n=q-2 is ok, because a^(q-1)=1 mod q.
Then b = -a^(q-2) = -1/a mod q. a*b = -1 mod q.
We can use nay prime divisor of the a*b+1 as q.

[@ayoubaassou4361]

nice solution but at the end q can be equal to 1 in case a = 0 or b = 0 . in reverse, for ( a , 0 ) ( 0 , b ) that works to .

[@dedekindcuts3589]

a and b need to be positive. That's why I said verbally in the solution that q can be 1 or 2, but the only solution is q =2 with a=b=1.

[@justmath.1533]

I think this problem was too easy for p2. but it was very nice, it took me around 1 hour.

[@dedekindcuts3589]

Yeah! I think it's pretty manageable and suitable as a great P2!

[@mihailgrecu654]

But what if I LOVE *geometry* and am scared of NT ?

[@dedekindcuts3589]

Let's just say this year's problem set isn't very favourable to those strong in geometry! Only a P4 geometry!!

[@vukdjokic8798]

@@dedekindcuts3589 im never placing to the imo(got 4 years left) but there is no way id ever get this lucky

[@shamilkhusnullin3363]

Drop maths, geometry is for nerds only

[@RSTATHER]

Tried it for 2 hrs but didn’t quite get there, I am very pleased with how far I got however

[@dedekindcuts3589]

As long as progress is made!

[@theller2k375]

My solution:
Let’s take the gdc of the smallest value of n:
gdc( a^1 + b, b^1 + a) = a + b
Logically, a + b is the gdc so it has to divide every value of n in the values of a and b we want.
a + b | a^n + b
a + b | b^n + a
=> a + b | a^n + b^n + a + b
=> a + b | a^n + b^n
=> a + b | ba^(n-1) + b^n
=> a + b | b^2a^(n-2) + b^n
•••
=> a + b | 2b^n
Let’s suppose that an and b aren’t equal.
Rewriting a as b + x we have:
2b + x | 2b^n
For n=1
2b + x | 2b
Contradiction.
Therefore, a=b.
gdc( a^n + a, a^n + a) = g
g = a^n + a
The only value which is constant for every value of n is 1.
So, a = b = 1.

[@dedekindcuts3589]

The gcd only has to be *eventually* constant. It need not be constant from n=1. So even though a+b is the gcd when n=1, it does not mean a+b need to divide all the gcd for larger values of n.

[@theller2k375]

@@dedekindcuts3589 indeed. Thank you for pointing the mistake.

[@narayansareekuthir5330]

Honestly I am preparing for first stage of imo but I solved problem 1 and 2 because I learnt only number theory

[@dedekindcuts3589]

It's a good start!

[@tomykill5232]

Good problem

[@dedekindcuts3589]

I agree!

[@sagnikbiswas3268]

I had all the intuition you did until the 10th minute of the video. I just really struggled with developing a construction. Any insights how to improve on this?

[@dedekindcuts3589]

The construction is the hardest part of this problem. Someone pointed out a similar past problem where you want the power to be -1 mod and -1 mod b, so you use ab-1. I think doing more problems can help!

[@IneidSmz-qz4nq]

But only a=b is necessary...... Need not be equal to 1 as g don't meant to be same in every case!!

[@andrea-mj9ce]

@@IneidSmz-qz4nqg has to be the same for every n

[@berlinisvictorious]

Can you elaborate how q|a^N +b and q|b^N +a implies q|a^N+1 +b q|b^N+1 +a at 12:42

[@il_caos_deterministico]

I suppose for hypothesis since for all n>=N the gcd is g and q divides g.

[@andrea-mj9ce]

Why does one have :
b^n = (- 1)^n mod(b + 1)

[@dedekindcuts3589]

b is one less than b+1, so b = -1 (mod b+1)

[@narayansareekuthir5330]

Why imo is giving easy problems

[@mathwithHikmat-mr9hk]

How do you write? What do you use to make videos?

[@dedekindcuts3589]

I simply use powerpoint (: