Задание №149675: Задание 11.6

11.6. На доску выписаны 2026 попарно различных натуральных чисел, больших 1. Оказалось,
что для любого выписанного числа a найдутся хотя бы k пар выписанных чисел b < c,
для которых bc − 1 делится на a − 1. Найдите наибольшее возможное значение k.
Ответ: k = 1012.
Решение. Для начала приведём пример для k = 1012. Пусть на доску выписаны числа
1 2 2026
2 ,2 ,...,2 .
n
Рассмотрим одно из выписанных чисел a = 2 . Если m ∈ {1,2,...,2026}, то в этом мно-
жестве найдётся число k ̸= m такое, что m + k делится на n, возможно, за исключением
случаев m = n и 2m = n. Действительно, если r — остаток от деления m на n, можно взять
n k Tm Tm−1
k = m − r. Пусть k + n = Tm. Тогда 2 · 2 − 1 = 2 − 1, что делится на 2 . Таким
образом, для каждого выписанного числа a хотя бы 2024 выписанных числа участвуют
хотя бы в одной искомой паре, поэтому таких пар не менее 1012.
Далее докажем оценку. Пусть a — наибольшее из чисел, выписанных на доске. Рас-
смотрим пары выписанных чисел b < c, для которых bc − 1 делится на a. Покажем, что

LII Всероссийская математическая олимпиада школьников

число a не участвует ни в одной из рассмотренных пар, а любое из оставшихся чисел —
не более чем в одной такой паре, отсюда последует, что 2k ⩽ 2025 и k ⩽ 1012.
Пусть an − 1 делится на a − 1, где 1 < n < a. Поскольку a ≡ 1 (mod a − 1), то n − 1
делится на a − 1, но 0 < n − 1 < a − 1, противоречие. Теперь пусть числа mk − 1 и mn − 1
делятся на a − 1, где m,n,k — различные выписанные числа. Тогда число m взаимно
просто с a − 1 и mk − mn = m(k − n) кратно a − 1. Значит, k − n делится на a − 1, однако
|k − n| ⩽ max(k,n) − 2 < a − 1, полученное противоречие завершает решение задачи.

Ответ: На доску выписаны 2026 попарно различных натуральных чисел, больших 1. Оказалось,