Решение задачи 479

Условие:

Найдите НОД всех шестизначных чисел, составленных из цифр 1, 2, 3, 4, 5, 6 без повторений.

Решение:

Через (n, m) обозначим НОД натуральных чисел n и m. Пусть n > m, нетрудно доказывается, что (n, m) = (n − m, m). Возьмем пару чисел из нашего набора: 345621 и 345612. Их НОД равен (345621, 345612) = (9, 345612), то есть НОД равен либо 1, либо 3, либо 9. Значит и НОД всех чисел равен либо 1, либо 3, либо 9.

Но сумма цифр всех чисел одинаковая и равна 21, что не делится на 9, но делится на 3. Значит, НОД всех нужных чисел равен 3.

Ответ: 3.