Задача 6.
Расстояние между городами А и Б составляет целое число километров. На дороге между городами каждый километр стоит табличка: на одной стороне написано расстояние до города А, на другой — до города Б. Слава шёл пешком из города А в город Б. В течение своего путешествия Слава посчитал для каждой таблички НОД чисел, написанных на ней. Оказалось, что среди посчитанных НОДов встречаются только числа 1, 3 и 13. Чему равняется расстояние между городами?
Ответ на Задачу 6.
Ответ: 39 километров.
Решение:
Предположим, мы стоим около таблички, на которой написаны числа 𝑥 и 𝑦. Если НОД(𝑥, 𝑦) = 𝑑, то (𝑥 + 𝑦) ⫶ 𝑑, т.е. расстояние между городами делится на все посчитанные НОДы.
Теперь предположим, что расстояние между городами (назовём его 𝑆) делится на некоторое натуральное число 𝑑. Тогда на расстоянии 𝑑 километров от города А на табличке написаны числа 𝑑 и 𝑆 − 𝑑, НОД которых равен в точности 𝑑.
Из всего этого мы делаем вывод, что 1, 3 и 13 — это полный список делителей расстояния между городами (не считая самого расстояния). Значит, расстояние равно 39 километров.
