Европейская математическая олимпиада среди девочек (EGMO). 2025 год. Косово

Для положительного целого числа $N$ обозначим через $c_1 < c_2 < \ldots < c_m$ все положительные целые числа, меньшие $N$ и взаимно простые с $N$. Найдите все такие $N \geqslant 3$, что $$\text{НОД}(N,\, c_i + c_{i+1}) \ne 1$$ для всех $1 \leqslant i \leqslant m - 1$. Здесь $\text{НОД}(a,b)$ это наибольший общий делитель. Числа $a$ и $b$ называются взаимно простыми, если $\text{НОД}(a,b)=1$.

Комментарий/решение

Юниорка 23 год когда выйдет?

Ух, новая олимпиада в matol!!!!

1) Если $N$ четный тогда все ${c_1,c_2,,c_m}$ нечетные и сумма любых двух делится на два что подходит.

2) Если $N$ нечетный тогда замечаем что $c_1=1, c_2=2$ значит $N$ делится на $3$. Пусть $N=3^t \cdot k$ где $(3,k)=1$. Если $k > 1$ то:

2.1) $k = 1 (mod 3)$:

$(N,k-2)=(N,k+1)=1$ но $(N,(k-2)+(k+1))=(N,2k-1)=1$ что невозможно.

2.2) $k = 2 (mod 3)$

$(N,k-1)=(N,k+2)=1$ но $(N,(k-1)+(k+2))=1$ что не возможно.

Отсюда $N=3^t$ и пример $c_1,c_2,…,c_m = 1,2,1,2… (mod 3)$.

А не норм