Lemma › Guides › EGMO 2025 Problem 1: solution, and the one pair that breaks the rest
Guide

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 NN. It does not. One line handles every even NN, one line handles every power of 33, and for every other NN 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.

The problem. For a positive integer NN, let c1<c2<⋯<cmc_1 < c_2 < \cdots < c_m be all the positive integers smaller than NN that are coprime to NN. Find all N≥3N \ge 3 such that gcd⁡(N,ci+ci+1)≠1\gcd(N, c_i + c_{i+1}) \ne 1 for all 1≤i≤m−11 \le i \le m - 1. Here gcd⁡(a,b)\gcd(a, b) is the largest positive integer that divides both aa and bb. Integers aa and bb are coprime if gcd⁡(a,b)=1\gcd(a, b) = 1.

Answer: every even N≥4N \ge 4, and every power of three, N=3kN = 3^k with k≥1k \ge 1.

The signal in the statement

Three things in the wording tell you where to look.

Compute a few small cases before proving anything: N=3,4,6,8,9,10N = 3, 4, 6, 8, 9, 10 work, while N=5,7,15,21N = 5, 7, 15, 21 fail. That list already suggests the answer.

Solution

Every even N works.

  1. If NN is even, every number coprime to NN is odd.
  2. So every sum ci+ci+1c_i + c_{i+1} is even, and gcd⁡(N,ci+ci+1)≥2\gcd(N, c_i + c_{i+1}) \ge 2.

Every power of three works.

  1. If N=3kN = 3^k, the numbers coprime to NN are exactly those not divisible by 33, so the list runs 1,2,4,5,7,8,…1, 2, 4, 5, 7, 8, \ldots
  2. A neighbouring pair is either 3j+1,3j+23j+1, 3j+2, with sum 6j+36j+3, or 3j+2,3j+43j+2, 3j+4, with sum 6j+66j+6.
  3. Both sums are divisible by 33, so every gcd is at least 33.

Every other N fails. Now NN is odd and not a power of 33. We find one neighbouring pair whose sum is coprime to NN.

  1. Case 3 does not divide N. Since NN is odd, N≥5N \ge 5, and both 11 and 22 are coprime to NN. So c1=1c_1 = 1 and c2=2c_2 = 2, with sum 33. As 3∤N3 \nmid N, gcd⁡(N,3)=1\gcd(N, 3) = 1, and the condition fails at i=1i = 1.
  2. Case 3 divides N. Write N=3kmN = 3^k m with k≥1k \ge 1 and m>1m > 1 not divisible by 33. Since NN is odd, every prime factor of mm is at least 55, so m≥5m \ge 5.
  3. Exactly one of mm and 2m2m is congruent to 22 mod 33; call it tt. Then t≤2mt \le 2m.
  4. Look at the four numbers t−1, t, t+1, t+2t-1,\ t,\ t+1,\ t+2. All lie between 11 and 2m+22m + 2, and 2m+2<3m≤N2m + 2 < 3m \le N, so all four are smaller than NN.
  5. The middle two are not coprime to NN: tt is a multiple of mm, and t+1≡0(mod3)t + 1 \equiv 0 \pmod 3.
  6. The outer two are coprime to NN. Mod 33 they are 11 and 11. Mod any prime p∣mp \mid m, where t≡0t \equiv 0, they are −1-1 and 22, neither zero since p≥5p \ge 5.
  7. So t−1t - 1 and t+2t + 2 are neighbours in the list, and their sum is 2t+12t + 1. Mod 33 it is 22; mod each prime p∣mp \mid m it is 11. So gcd⁡(N,2t+1)=1\gcd(N, 2t+1) = 1 and the condition fails.

For example, N=15N = 15 gives m=5m = 5, t=5t = 5 and the pair 4,74, 7 with sum 1111; N=21N = 21 gives m=7m = 7, t=14t = 14 and the pair 13,1613, 16 with sum 2929. Both sums are coprime to NN.

That covers every N≥3N \ge 3, so the answer is all even NN and all powers of 33.

An independent check

The build behind this page does not trust the proof. It lists the coprime residues of every NN from 33 to 12001200, tests every neighbouring sum directly, and confirms that the NN satisfying the condition are exactly the even numbers and the powers of 33. It separately runs the pair t−1,t+2t - 1, t + 2 from the last case through every odd multiple of 33 up to 60006000 that is not a power of 33, and confirms each time that the two numbers are coprime neighbours whose sum is coprime to NN.

Where marks go missing

Practise the idea

The move here, split NN into its primes and ask what happens mod each one separately, is the same one that proves n5−nn^5 - n is divisible by 3030 in the archive: check 22, 33 and 55 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

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