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

Найдите все пары $(a, b)$ положительных целых чисел, для которых существуют такие положительные целые $g$ и $N$, что $$ \text{НОД}\left(a^{n}+b, b^{n}+a\right)=g$$ для всех целых чисел $n \geqslant N$. (Здесь НОД $(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).

Ответ: $(1,1)$

Не трудно доказать что для $a$ и $b$ существует бесконечно много натуральных $k_a$ и $k_b$ что:

$$ab+1 \mid a^{k_a}-1$$

$$ab+1 \mid b^{k_b}-1$$

Тогда:

$$ab+1\mid a^{k_a}-1\mid a^{k_a \cdot k_b}-1$$

$$ab+1\mid b^{k_a}-1\mid b^{k_a \cdot k_b}-1$$

Другими словами, существует бесконечно много натуральных $k$ что:

$$ab+1 \mid a^k-1$$

$$ab+1 \mid b^k-1$$

Берем достаточно большие $k$. Заметим что:

$$a(a^{k-1}+b)-(ab+1)=a^k-1$$

$$b(b^{k-1}+a)-(ab+1)=b^k-1$$

Тогда $ab+1$ делит $a^{k-1}+b$ и $b^{k-1}+a$, значит $ab+1 \mid g$.

Для $n=k$, выражения при делении на $ab+1$ дают остатки:

$$a^k+b \equiv 1+b \equiv 0 \mod{ab+1}$$

$$b^k+a \equiv 1+a \equiv 0 \mod{ab+1}$$

Выводим что $ab+1 \leq a+1$ и $ab+1 \leq b+1$, откуда $a,b \leq 1$.