19.05 Основная теорема арифметики (ОТА)

Разложим каждое число на простые множители:

Чтобы произведения в двух группах были равны, нужно разделить одинаковые простые множители поровну между двумя группами.

Отметим, что простой множитель 11 встречается всего в двух числа 22 и 66 по одному разу. Значит, эти числа должны быть в разных группах.

Точно так же с простым множителем 3: он встречается только в числах 6 и 66. Значит, они должны быть тоже в разных группах. Поэтому пока что мы получаем, что в одной группе находятся числа 22 и 6, а в другой — число 66.

Посмотрим на простой множитель 5. Он встречается в числах суммарно 4 раза. Сразу две пятерки встречаются в числе 25. Значит, число 25 должно быть в одной группе, а числа 10 и 40 — в другой.

Рассмотрим два случая: когда числа 66 и 25 в одной группе и когда они в разных группах.

Случай 1.

Числа 66 и 25 в одной группе. Тогда в другой группе, как уже было доказано выше, находятся числа 6, 22, 10 и 40. В них суммарно находится 6 множителей 2: по одному в 6, 22 и 10 и сразу три в числе 40. Всего двоек во всех восьми числах в сумме

Поэтому на другую группу остается не более четырех двоек. Значит, произведения в двух группах точно не будут равны, так как в одной группе двоек будет больше, чем в другой. Этот случай невозможен.

Случай 2.

Числа 66 и 25 в разных группах. Тогда в одной группе находятся числа 66, 10 и 40, а в другой — 6, 22, 25. Остались нераспределенными только числа 2 и 4. В группе 66, 10 и 40 суммарно пять двоек. Как мы уже считали, всего двоек десять. Это значит, что все остальные двойки должны быть в другой группе. Поэтому в этом случае мы получаем единственное возможное распределение:

Нетрудно проверить, что оно подходит.

Итак, мы рассмотрели оба возникших случая. В одном доказали, что подходящих распределений нет. В другом доказали, что возможно одно распределение, и проверили, что оно подходит. Значит, есть единственный способ разбить числа на две группы с одинаковыми произведениями.