Задача 4. НОД и НОК большой пары

Раскладываем 16! на простые множители

$16! = 1 \cdot 2 \cdot 3 \cdots 16$. Простые числа до $16$: $2, 3, 5, 7, 11, 13$; больших простых делителей у $16!$ нет. Посчитаем степень каждого.

• Двойка. Чётных чисел от $1$ до $16$ восемь, каждое даёт хотя бы одну двойку. Делятся на $4$ четыре числа — они дают ещё по одной. На $8$ — два числа ($8$ и $16$), ещё по одной. На $16$ — одно, ещё одна. Итого $8 + 4 + 2 + 1 = 15$.
• Тройка. Делятся на $3$: $3, 6, 9, 12, 15$ — пять чисел, и $9$ даёт ещё одну тройку: $6$.
• Пятёрка: $5, 10, 15$ — степень $3$. Семёрка: $7, 14$ — степень $2$. $11$ и $13$ — по одному разу.

Как НОД и НОК видны в разложениях

Если разложить $a$ и $b$ на простые множители, то

• НОД берёт каждое простое число в меньшей из двух его степеней;
• НОК — в большей.

Пример: $12 = 2^2 \cdot 3$ и $18 = 2 \cdot 3^2$. НОД $= 2^1 \cdot 3^1 = 6$, НОК $= 2^2 \cdot 3^2 = 36$.

Любой простой делитель $a$ или $b$ делит их НОК, то есть $16!$. Поэтому в $a$ и $b$ могут входить только $2, 3, 5, 7, 11, 13$.

Для каждого простого — две возможности

Для каждого простого числа меньшая степень должна совпасть со степенью в $30$, а большая — со степенью в $16!$ (таблица ниже).

• Двойка: меньшая $1$, большая $15$. Значит, одно из чисел $a$, $b$ содержит $2^1$, другое — $2^{15}$: два способа, смотря какое.
• Тройка: $3^1$ и $3^6$ — два способа. Пятёрка: $5^1$ и $5^3$ — два способа.
• Семёрка: в $30$ её нет, значит, меньшая степень $0$, а большая $2$: одно число содержит $7^2$, другое не делится на $7$. Два способа.
• $11$ и $13$: степени $0$ и $1$ — по два способа.

У каждого простого числа меньшая и большая степени разные, поэтому вариантов ровно два, а не один. Промежуточные степени, например $2^7$, не подходят: тогда НОД или НОК получит не ту степень двойки. В модели видно, как такая проба ломает НОД или НОК.

Считаем пары

Выбор для разных простых чисел делается независимо, и каждый набор выборов даёт свою упорядоченную пару $(a, b)$: разложение на простые множители единственно. Поэтому пар

Например, $a = 2 \cdot 3 \cdot 5 \cdot 7^2 \cdot 11 \cdot 13$ и $b = 2^{15} \cdot 3^6 \cdot 5^3$: НОД $= 2 \cdot 3 \cdot 5 = 30$, НОК $= 16!$. Пара $(b, a)$ — уже другая: порядок учитывается.

Проверка другим способом

Запишем $a = 30u$, $b = 30v$. Тогда $\operatorname{НОД}(u, v) = 1$, а из $ab = \operatorname{НОД}(a, b) \cdot \operatorname{НОК}(a, b)$ получаем

Взаимно простые $u$ и $v$ не могут делить степень одного простого числа между собой: каждый из шести «блоков» $2^{14}$, $3^5$, $5^2$, $7^2$, $11$, $13$ целиком уходит в $u$ или в $v$. Снова $2^6 = 64$.