Разделы 
Дополнительно
Задача по математике - 1929
2019-01-22 
По окружности расставлено 100 натуральных чисел, взаимно простых в совокупности. Разрешается прибавлять к любому числу наибольший общий делитель его соседей. Докажите, что при помощи таких операций можно сделать все числа попарно взаимно простыми.
Решение:
Положим для удобства изложения $a_{n+100} = a_n$ при $n = 1, 2,\cdots, 100$. Заметим, что при описанной процедуре числа остаются взаимно простыми в совокупности.
Лемма. Пусть $a_1, a_2, a_n$ и $d$ - натуральные числа. Тогда существует натуральное число $к$ такое, что $\:НОД(a_1 + kd, a_i) \leq d$ для любого $i = 2, 3, \cdots, n$.
Доказательство. Существует некоторое число, кратное $a_2a_3 \cdot a_n$, - скажем, $la_2a_3 \cdot a_n$, которое больше $a_1$. Тогда среди тех $к$, для которых $a_1 + kd > la_2a_3 \cdots a_n$, существует наименьшее число $k_0$. Положим $a_1^{\prime} = a_1 + k_0d$. Тогда $0 < a_1^{\prime} - la_2a_3 \cdot a_n \leq d$, и наибольший общий делитель $a_1$ и каждого из $a_i$ не превосходит $d$. Лемма доказана.
Пусть теперь $M > 1$ - наибольший из попарных общих делителей чисел $a_i$. Докажем, что с помощью операций, описанных в условии, мы сможем заменить исходный набор чисел на набор, в котором все попарные общие делители меньше $M$. Действительно, так как числа $a_1, a_2, \cdots, a_{100}$ взаимно просты в совокупности, найдутся два соседних числа $a_i$ и $a_{i+1}$, первое из которых делится на $M$, а второе - нет. Тогда $d =\:НОД(a_{i-1}, a_{i+1}) < M$. Применяя лемму, прибавим к $a_i$ такое кратное $d$, чтобы наибольшие общие делители $a_i$ с каждым из остальных чисел стали не больше $d$. В полученном наборе по-прежнему все попарные наибольшие делители не превосходят $M$, а чисел, кратных $M$, меньше, чем в исходном. Повторяя при необходимости эту операцию, мы добьемся, что останется ровно одно число, кратное $M$, и тогда, очевидно, все попарные наибольшие общие делители станут меньше $M$.
Итак, если наибольший из попарных общих делителей чисел набора больше 1, его можно уменьшить. Поэтому его можно уменьшить до 1, что и требовалось.
По окружности расставлено 100 натуральных чисел, взаимно простых в совокупности. Разрешается прибавлять к любому числу наибольший общий делитель его соседей. Докажите, что при помощи таких операций можно сделать все числа попарно взаимно простыми.
Решение:
Положим для удобства изложения $a_{n+100} = a_n$ при $n = 1, 2,\cdots, 100$. Заметим, что при описанной процедуре числа остаются взаимно простыми в совокупности.
Лемма. Пусть $a_1, a_2, a_n$ и $d$ - натуральные числа. Тогда существует натуральное число $к$ такое, что $\:НОД(a_1 + kd, a_i) \leq d$ для любого $i = 2, 3, \cdots, n$.
Доказательство. Существует некоторое число, кратное $a_2a_3 \cdot a_n$, - скажем, $la_2a_3 \cdot a_n$, которое больше $a_1$. Тогда среди тех $к$, для которых $a_1 + kd > la_2a_3 \cdots a_n$, существует наименьшее число $k_0$. Положим $a_1^{\prime} = a_1 + k_0d$. Тогда $0 < a_1^{\prime} - la_2a_3 \cdot a_n \leq d$, и наибольший общий делитель $a_1$ и каждого из $a_i$ не превосходит $d$. Лемма доказана.
Пусть теперь $M > 1$ - наибольший из попарных общих делителей чисел $a_i$. Докажем, что с помощью операций, описанных в условии, мы сможем заменить исходный набор чисел на набор, в котором все попарные общие делители меньше $M$. Действительно, так как числа $a_1, a_2, \cdots, a_{100}$ взаимно просты в совокупности, найдутся два соседних числа $a_i$ и $a_{i+1}$, первое из которых делится на $M$, а второе - нет. Тогда $d =\:НОД(a_{i-1}, a_{i+1}) < M$. Применяя лемму, прибавим к $a_i$ такое кратное $d$, чтобы наибольшие общие делители $a_i$ с каждым из остальных чисел стали не больше $d$. В полученном наборе по-прежнему все попарные наибольшие делители не превосходят $M$, а чисел, кратных $M$, меньше, чем в исходном. Повторяя при необходимости эту операцию, мы добьемся, что останется ровно одно число, кратное $M$, и тогда, очевидно, все попарные наибольшие общие делители станут меньше $M$.
Итак, если наибольший из попарных общих делителей чисел набора больше 1, его можно уменьшить. Поэтому его можно уменьшить до 1, что и требовалось.
