Международная олимпиада 2024, Бат, Великобритания, 2024 год

Барлық $n \geqslant N$ сандары үшін $$ \text{ЕҮОБ}\left(a^{n}+b, b^{n}+a\right)=g$$ теңдігі орындалатындай етіп $g$ және $N$ натурал сандары табылатындай, барлық натурал $(a, b)$ сандар жұбын табыңыздар. (Мұнда ЕҮОБ$(x, y)$ бүтін $x$ пен $y$ сандарының ең үлкен ортақ бөлгішін білдіреді.)

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

Ответ: (1,1). Несложно убедиться, что эта пара чисел подходит.

Теперь рассмотрим выражение вида $ab + 1$

Лемма 1: $ab + 1$ - не имеет простых нечетных делителей

Доказательство: Заметим, что $a \equiv -b^{-1}\pmod {p} $ и $ -a^{-1} \equiv b\pmod {p}$

Теперь для любого $n$ вида $(p-1)k + (p-2)$, $a^n + b$ и $b^n + a$ делятся на $p$, поэтому эти два выражения должны всегда делится на $p$.

Возьмём $n=(p-1)l$ , тогда $a\equiv b\equiv-1\pmod {p}$, $ab + 1\equiv 2\pmod {p}$, чего быть не может.

Лемма 2: $ab + 1$ - не делится на 4

Доказательство: Предположим противное, тогда $a$, $b$ - нечетные числа, поэтому, не нарушая общности, $a \equiv 1\pmod {4}$ $b \equiv -1\pmod {4}$.

Тогда при четных $n$, $4 \nmid g$, а при нечетных - $4 \mid g$. Противоречие.

Из двух лемм следует, что $ab+1 = 2$, тогда нам подходит только пара (1,1).