14th European Girls' Mathematical Olympiad (EGMO 2025)

Problem 1. For a positive integer N , let c₁ < c₂ < · · · < c_m be all the positive integers smaller than N that are coprime to N . Find all N ≥ 3 such that
gcd(N, ci + ci+1)̸ = 1
for all 1 ≤ i ≤ m − 1.
Here gcd(a, b) is the largest positive integer that divides both a and b. Integers a and b are coprime if gcd(a, b) = 1.

SOLUTION 1

The answer is all even $N$ and powers of $3$ .

Checking:

When $N$ is even, $c_i$ is odd for all $i$ so $2\mid c_i+c_{i+1}$ and hence $\gcd(N,c_i+c_{i+1})>1$ .

When $N$ is a power of $3$ , $c_i$ is precisely all the numbers not divisible by $3$ . As they alternate being $1,2\pmod{3}$ , we may deduce that $3\mid c_i+c_{i+1}$ for all $i$ , hence $\gcd(N,c_i+c_{i+1})>1$ .

Proof of necessity:

Now assume $N$ is odd and not a power of $3$ .

If $3\nmid N$ , then we choose $i=1$ , and we have $c_1=1$ , $c_2=2$ , so $\gcd(N,3)=1$ . We must have $3\mid N$ as a result.

Assume there exists some other prime that divides $N$ . Let $S=\{p_1,p_2,\dots,p_t\}$ be the set of primes that divide $N$ excluding $3$ . By CRT there exists some number $k$ with $1\leq k\leq N$ such that $3\mid k$ , $k\equiv 0 \pmod{p_i}$ for $i>1$ and $k\equiv -1 \pmod{p_1}$ .

Then we know that $\gcd(k-1,N)=\gcd(k+2,N)=1$ and that $\gcd(k,N),\gcd(k+1,N)\neq 1$ . A quick check yields that $k+2<N$ thus $(k-1,k+2)=(c_s,c_{s+1})$ for some $s$ . Now $c_s+c_{s+1}=2k+1$ which is not divisible by $3$ . It is also not divisible by any other prime that divides $N$ , thus it is coprime with $N$ . We may conclude that no other primes can divide $N$ , so we are done.

SOLUTION 2

We claim that the answer is all even positive integer and the power of $3$ .
Notice that if $2 \mid N$ , then $c_i$ is odd. That is $\gcd(c_i + c_{i+1}, N) = \gcd( 2k, N)$ is an even integer.
For the power of $3$ , note that $c_i, c_{i+1} \pmod 3 = \{1,2\}$ , hence $3 \mid c_i + c_{i+1}$

Now, suppose $N$ is an odd positive integer. Note that $c_1 =1, c_2 =2$ , so $3 \mid N$ .
Consider a set of prime divisors of $N$ , $P = \{3, p_1, p_2, \dots, p_z\}$ for some positive integer $z$ .
Wlog, $p_1$ is the second smallest element in $P$ . Consider the congruence $\begin{align*} A &\equiv 2 \pmod 3\\ A &\equiv p_1-2 \pmod {p_1}\\ A &\equiv 1 \pmod {p_2}\\ A &\equiv 1 \pmod {p_3}\\ &\vdots\\ A &\equiv 1 \pmod {p_z} \end{align*}$ By CRT, these congruence has a unique solution $\pmod {3p_1p_2\cdots p_z}$ .
Note that $A, A+3$ is coprime to $N$ , $3 \mid A+1$ and $p_1 \mid A+2$ .
Hence, for some $i$ , $A = c_i$ and $A+3 = c_{i+1}$ .
We have $\begin{align*} c_i + c_{i+1} &\equiv 1 \pmod 3\\ c_i + c_{i+1} &\equiv -1 \pmod {p_1}\\ c_i + c_{i+1} &\equiv 5 \pmod {p_2}\\ c_i + c_{i+1} &\equiv 5 \pmod {p_3}\\ &\vdots\\ c_i + c_{i+1} &\equiv 5 \pmod {p_z} \end{align*}$ Since, $3$ and $p_1$ is the $2$ smallest prime, $p_2, p_3, \dots p_z > 5$ . So, $c_i + c_{i+1}$ is coprime to $N$ .
That is $P = \{ 3 \}$ . Hence, we are done.