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

Решаю эту задачу, довольно быстро приходит на ум хороший пример: когда все выбранные числа сами являются точными квадратами. В таком случае чисел так как а Теперь сделаем оценку. Для этого нам пригодится ввести новое понятие: бесквадратная часть числа. Рассмотрим, например, число Выделим в нём наибольший квадрат: мы можем взять и Оставшиеся множители, а именно как раз и образуют бесквадратную часть. Более строго: бесквадратной частью будем называть произведение тех простых множителей числа, что входят в него в нечётной степени. Если число является квадратом, будем считать, что его бесквадратная часть равна

С этой бесквадратной частью связано такое интересное свойство: произведение двух чисел является квадратом тогда и только тогда, когда их бесквадратные части равны. Докажем эту лемму. Во-первых, в одну сторону это очевидно: если у чисел равны бесквадратные части (обозначим их через ), то числа можно представить как и Тогда их произведение равно Теперь в обратную сторону: допустим, что произведение чисел является квадратом. Получается, что если у одного числа какой-то простой множитель входил в него в нечётной степени, то и у другого этот множитель должен присутствовать в нечётной степени, иначе в произведении этот простой множитель так и останется в нечётной степени, и произведение не станет точным квадратом. Таким образом, наборы простых чисел, которые входят в эти два числа в нечётных степенях, совпадают, значит, будут равны и бесквадратные части.

Теперь воспользуемся доказанной леммой. Из условия сразу следует, что бесквадратные части всех чисел равны. Обозначим эту бесквадратную часть через Тогда все числа представимы в виде и во всех числах обязательно разные Если бы чисел было хотя бы то один из был бы не меньше а само число не меньше что больше ведь противоречие.