Пояснение к таблице. В самом левом столбце (первом) стоят простые числа, которые являются множителями хотя бы одного из чисел F, B, C, D.

Пояснение к таблице. В самом левом столбце (первом) стоят простые числа, которые являются множителями хотя бы одного из чисел F, B, C, D.

Посмотрим на число А. Во втором столбце указано, какие из простых чисел первого столбца попадают в мешок числа А (т.е. в М(А)). Мы видим, что простое число 5 в этот мешок вообще не попадает – ноль штук. Простое число 7 попадает в этот мешок дважды, простое число 29 – попадает в этот мешок один раз, и так далее.

В результате М(А) = [7, 7, 29, 61, 61, 61, 61, 61, 103, 127]

Это значит, что

А = 7² 29 61⁵ 103 127

Таким образом, мешок простых множителей числа А – это всего-навсего другая форма записи разложения числа А на простые множители.

При перемножении двух чисел А и В их мешки, очевидным образом ссыпаются в один общий мешок («складываются»).

При нахождении НОД(А, В) мешок М(НОД(А, В)) представляет собой пересечение М(А) и М(В).

Это значит, что каждое простое число, войдет в разложение НОД(А, В) в наименьшей из степеней, в которых оно входило в разложения чисел А и В. Например, число 29 войдет в разложение НОД(А, В) в первой степени. Это, в свою очередь, равносильно тому, что в мешок М(НОД(А, В)) число 29 войдет один раз.

При нахождении НОК (А, В) мешок М(НОК(А, В)) представляет собой объединение М(А) и М(В).

Это значит, что каждое простое число войдет в разложение НОК(А, В) в наибольшей из степеней, в которых оно входило в разложения чисел А и В. Например, число 29 войдет в разложение НОК(А, В) в третьей степени. Это, в свою очередь, равносильно тому, что в мешок М(НОД(А, В)) число 29 войдет три раза.

Дата добавления: 2015-08-29