Задача 76543
|
|
 |
Условие
Докажите, что каково бы ни было целое число n, среди чисел n, n + 1, n + 2, ..., n + 9 есть хотя бы одно, взаимно простое с остальными девятью.
Решение
Среди данных чисел есть пять нечётных. Рассмотрим остатки от деления этих пяти чисел на 3, 5 и 7. Среди остатков от деления на 3 нет трёх одинаковых, а среди остатков от деления на 5 и на 7 нет двух одинаковых. Поэтому среди указанных пяти чисел можно выбрать три числа, не кратных 3, а среди них выбрать число, не кратное ни 5, ни 7. Это число взаимно просто с остальными девятью числами.
