|
|
 |
Условие
По окружности расставлено 100 натуральных чисел, взаимно простых в совокупности. Разрешается прибавлять к любому числу наибольший общий делитель его соседей. Докажите, что при помощи таких операций можно сделать все числа попарно взаимно простыми.
Решение
Положим для удобства an+100 = an при n = 1, 2, ..., 100. Заметим, что при описанной процедуре числа остаются взаимно простыми в совокупности.
Лемма. Пусть a1, a2, ...,
an и d – натуральные числа. Тогда существует такое натуральное k, что НОД(a1 + kd, ai) ≤ d для любого i = 2, 3, ..., n.
Доказательство. Существует некоторое число, кратное a2a3...an, скажем,
la2a3...an, которое больше a1. Тогда среди тех k, для которых a1 + kd > la2a3... an, существует наименьшее число k0.
Положим b = a1 + k0d.
Тогда 0 < b – la2a3... an ≤ d, и НОД(b, ai) ≤ d.
Пусть теперь M > 1 – наибольший из попарных общих делителей чисел ai. Докажем, что с помощью операций, описанных в условии, мы сможем заменить исходный набор чисел на набор, в котором все попарные общие делители меньше M. Действительно, так
как числа a1, a2, ..., a100 взаимно просты в совокупности, найдутся два соседних числа ai и ai+1, первое из которых делится
на M, а второе – нет. Тогда d = НОД(ai–1, ai+1) < M. Применяя лемму, прибавим к ai такое кратное d, чтобы наибольшие общие делители bi с каждым из остальных чисел стали не больше d. В полученном наборе по-прежнему все попарные наибольшие делители не превосходят M, а чисел, кратных M, меньше, чем в исходном. Повторяя при необходимости эту операцию, мы добьёмся, что останется ровно одно число, кратное M, и тогда, очевидно, все попарные наибольшие общие делители станут меньше M.
Итак, если наибольший из попарных общих делителей чисел набора больше 1,
его можно уменьшить. Поэтому его можно уменьшить до 1, что и требовалось.
