#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
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).
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
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.
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.
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.
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?
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!
