Разложение на множители, основная теорема арифметики

Первое решение.

Операция постановки восклицательного знака, применённая к числу даёт возможность добавить в произведение множители от до включительно.

Заметим, что если число простое, то как бы мы ни расставляли восклицательные знаки, в произведении всё равно останется простой множитель в первой степени, так что получить квадрат не удастся.

При составном будем действовать следующим образом. Разложим произведение в виде произведения степеней простых и посмотрим, какие простые числа входят в нечётных степенях. Если таких чисел нет, то перед нами уже квадрат. Иначе обозначим наибольшее из этих простых за Поставим восклицательный знак после числа Так мы добавили в произведение все числа от до так что степень простого числа увеличилась на и стала чётной. Кроме того, степени вхождения простых чисел, больших не изменились. Для нового произведения сделаем ту же операцию, то есть пересчитаем степени вхождения простых чисел и упорядочим те простые, что входят в нечётных степенях, в порядке убывания, и снова “исправим” наибольшее. Такими операциями мы в итоге придём к числу, являющимся точным квадратом.

Второе решение.

Предположим, что простое. Тогда степень вхождения в произведение будет равна (как бы мы ни приписывали восклицательные знаки). Тогда число не является точным квадратом. Предположим, что Тогда можно приписать факториал после В итоге останется — точный квадрат.

Теперь предположим, что где и Не нарушая общности, Рассмотрим два случая.

Если то припишем факториал к и (эти три числа различны). Останется

Если же то припишем факториал к (все эти числа различны). Получится

что также является точным квадратом.