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

Обозначим через все простые числа, меньшие 1000. Заметим, что по условию каждое выписанных чисел раскладывается в произведение в некоторых степенях. Каждое из наших простых чисел входит в одно выписанное число в четной или нечетной степени. Сопоставим каждому выписанному числу последовательность из 0 и 1 длины . Число на - ой позиции будет равно 1, если в ходит в выписанное число в нечетной степени и 0 в противном случае (на самом деле это и есть бесквадратная часть, про которую мы говорили в теории). Предположим, что среди последовательностей выписанных чисел есть три различные. Тогда для трех соответствующих этим последовательностям чисел не выполнено условие (два числа в произведении могут давать точный квадрат, только если четности вхождения каждого - ого одинаковые).

То есть мы показали, что различных последовательностей может быть не больше 2. Обозначим эти последовательности через и . Обозначим через , . Очевидно что . Считаем. что , тогда , , так как при мы получим, что числа являются квадратами — по условию, квадратов среди выписанных чисел нет. Каждое из выписанных чисел дает точный квадрат либо при делении на , либо при делении на . Причем для чисел, которым соответствуют одинаковые последовательности, эти квадраты должны быть различными. Рассмотрим наибольшее выписанное число, которому соответствует последовательность -шек. Оно равно для некоторого натурального , откуда , то есть . Но тогда количество выписанных чисел, которым соответствует первая последовательность, не превосходит 22. Аналогично поступаем со второй последовательностью. Опять рассматривает наибольшее число , откуда , то есть , откуда таких чисел не больше 18. То есть всего чисел не больше, чем .

Пример строится из доказательства, а именно берем все точные квадраты от 1 до 22, умноженные на 2, и все точные квадраты чисел от 1 до 18, умноженные на 3.