EGMO 2025 Problem 1: solution, and the one pair that breaks the rest
13 November 2026
EGMO 2025 Problem 1 looks like it needs the whole structure of the numbers coprime to . It does not. One line handles every even , one line handles every power of , and for every other a single well-chosen pair of neighbours is enough to break the condition. Here is the statement, the answer, the full proof, an independent check, and the part most write-ups skip: what in the wording points at the method.
Answer: every even , and every power of three, with .
The signal in the statement
Three things in the wording tell you where to look.
- "Find all N such that ... for all i." The condition has to hold for every neighbouring pair, so it is easy to break and hard to satisfy. That shape means the answer is a small family that works for a structural reason, and the real work is showing that everything else fails, usually by exhibiting one bad pair.
- "Coprime to N" plus "a sum shares a factor with N". The sum only needs one prime in common with . So go prime by prime: for which single prime dividing could every neighbouring sum be divisible by ? That is a question about residues mod , which is the modular arithmetic toolkit.
- The smallest primes. Every number coprime to avoids residue mod for each . For that leaves only one residue, so all the are odd. For it leaves two residues, and , which add to . For there is too much room. So expect and to be the whole answer.
Compute a few small cases before proving anything: work, while fail. That list already suggests the answer.
Solution
Every even N works.
- If is even, every number coprime to is odd.
- So every sum is even, and .
Every power of three works.
- If , the numbers coprime to are exactly those not divisible by , so the list runs
- A neighbouring pair is either , with sum , or , with sum .
- Both sums are divisible by , so every gcd is at least .
Every other N fails. Now is odd and not a power of . We find one neighbouring pair whose sum is coprime to .
- Case 3 does not divide N. Since is odd, , and both and are coprime to . So and , with sum . As , , and the condition fails at .
- Case 3 divides N. Write with and not divisible by . Since is odd, every prime factor of is at least , so .
- Exactly one of and is congruent to mod ; call it . Then .
- Look at the four numbers . All lie between and , and , so all four are smaller than .
- The middle two are not coprime to : is a multiple of , and .
- The outer two are coprime to . Mod they are and . Mod any prime , where , they are and , neither zero since .
- So and are neighbours in the list, and their sum is . Mod it is ; mod each prime it is . So and the condition fails.
For example, gives , and the pair with sum ; gives , and the pair with sum . Both sums are coprime to .
That covers every , so the answer is all even and all powers of .
An independent check
The build behind this page does not trust the proof. It lists the coprime residues of every from to , tests every neighbouring sum directly, and confirms that the satisfying the condition are exactly the even numbers and the powers of . It separately runs the pair from the last case through every odd multiple of up to that is not a power of , and confirms each time that the two numbers are coprime neighbours whose sum is coprime to .
Where marks go missing
- Stopping at "even works". Even is the obvious half. The powers of three are the part that separates a full answer from a partial one, and missing them costs most of the marks.
- A failing pair that is not adjacent. It is not enough to find two numbers coprime to whose sum is coprime to . They must be consecutive in the list, so you must say why everything strictly between them shares a factor with . In the last case that is step 5.
- Forgetting the range. The pair has to be smaller than . The inequality is one line, and leaving it out leaves a gap.
- Assuming m is prime. Nothing above needs to be prime, which is why is chosen as a multiple of all of rather than of one prime factor.
Practise the idea
The move here, split into its primes and ask what happens mod each one separately, is the same one that proves is divisible by in the archive: check , and one at a time and combine. The method is written up in full under modular arithmetic, and the techniques index lists the other ideas that recur in olympiad number theory. The daily problem posts a new one every day, no account needed.
Related guides
- EGMO 2020 Problem 1: solution, and the power of 2 that cannot hideA full solution to EGMO 2020 Problem 1: track the power of 2 in each term, show it climbs by 2 or falls by 1, and count the terms.
- Lifting the exponent lemma explained for competitionsThe lifting the exponent lemma in one line, the p = 2 version that catches almost everyone, and the signals that tell you a contest problem wants it.
- gcd(2^m − 1, 2^n − 1): the proof, and how to spot itWhy gcd(2^m − 1, 2^n − 1) = 2^gcd(m,n) − 1: run Euclid's algorithm on the exponents. A full proof, a second proof by orders, and where it turns up.
- How to build a problem-solving notebook that actually worksMost problem notebooks are copied solutions nobody reopens. Index yours by the clue in the statement, not by topic, and test it from the clue side.
Train it on Lemma
Every technique here is taught explicitly, in order. 128 lessons, 1237 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and the paid plan opens with 3 free days.
Find your level