Олимпиадная задача по теории чисел: взаимная простота чисел на окружности для 8-10 классов

  Положим для удобства  a_n+100 = a_n  при  n = 1, 2, ..., 100.  Заметим, что при описанной процедуре числа остаются взаимно простыми в совокупности.   Лемма. Пусть a₁, a₂, ..., a_n и d – натуральные числа. Тогда существует такое натуральное k, что  НОД(a₁ + kd, a_i) ≤ d  для любого i = 2, 3, ..., n.

  Доказательство. Существует некоторое число, кратное a₂a₃...a_n, скажем, la₂a₃...a_n, которое больше a₁. Тогда среди тех k, для которых  a₁ + kd > la₂a₃... a_n,  существует наименьшее число k₀. Положим  b = a₁ + k₀d.  Тогда  0 < b – la₂a₃... a_n ≤ d,  и НОД(b, a_i) ≤ d.   Пусть теперь  M > 1  – наибольший из попарных общих делителей чисел a_i. Докажем, что с помощью операций, описанных в условии, мы сможем заменить исходный набор чисел на набор, в котором все попарные общие делители меньше M. Действительно, так как числа a₁, a₂, ..., a₁₀₀ взаимно просты в совокупности, найдутся два соседних числа a_i и a_i+1, первое из которых делится на M, а второе – нет. Тогда  d = НОД(a_i–1, a_i+1) < M.  Применяя лемму, прибавим к a_i такое кратное d, чтобы наибольшие общие делители b_i с каждым из остальных чисел стали не больше d. В полученном наборе по-прежнему все попарные наибольшие делители не превосходят M, а чисел, кратных M, меньше, чем в исходном. Повторяя при необходимости эту операцию, мы добьёмся, что останется ровно одно число, кратное M, и тогда, очевидно, все попарные наибольшие общие делители станут меньше M.

  Итак, если наибольший из попарных общих делителей чисел набора больше 1, его можно уменьшить. Поэтому его можно уменьшить до 1, что и требовалось.

Ответ задачи отсутствует