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

Заметим, что делитель числа не может иметь простые множители кроме 2 и 3, так как само имеет только эти простые числа в своем каноническом разложении. Отсюда любой делитель имеет вид где и

Тогда так же имеет вид с аналогичными условиями на и Отсюда

Рассмотрим отношение чисел и

Получившееся число является целым, так как делится на по условию. Это значит, что и то есть и

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

Заметим, что

Пусть Тогда выражение примет вид

Нам необходимо проверить делимость на

Одна из скобок уже равна осталось проверить делимость второй на А это верно, так как каждая из разностей вида делится на а, значит, и сумма тоже делится.

Выделим полный квадрат:

По условию

кратно 11, кроме того и тоже кратно 11. Значит, тоже обязано быть кратно 11. Так как 11 — это простое число, то это означает, что кратно 11.

Теперь распишем как разность квадратов и получим , а, так как ранее определили, что множитель кратен 11, то и все произведение тоже будет делиться на 11.

a) Сумма всех чисел от 1 до 20 равна 210. Очевидно, что во второй группе больше одного числа, так как в противном случае оно было бы равно сумме оставшихся 19 чисел, тоесть не меньше, чем Покажем, что на самом деле во второй группе больше двух чисел. Действительно, в противном случае для чисел и из второй группы выполнялось бы равенство

Раз 211 — простое число, следовательно, данное уравнение не имеет решений на промежутке от 1 до 20. Приведем пример второй группы из 3 чисел. Сначала возьмем единицу, будет верно, что

Нам подойдут тройки и

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

Получили противоречие с равенством произведения чисел второй группы и суммы чисел первой группы. Подберем пример для случая, когда во второй группе 5 чисел. Предположим, что подойдет пятерка вида где Должно выполниться условие

Подойдет набор

Заметим, что число делится на Тогда числа и тоже делятся на Также на делится и число Откуда следует, что число

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

__________________________________________________________________________________________________

Лемма. Число кратно числу где — натуральные, — неотрицательное целое.

Доказательство. По формуле сокращенного умножения

Значит, кратно

______________________________________________________________________________________________________________________________________________________

Заметим, что при этом 17 и 19 взаимнопростые, откуда число делится на 323 тогда и тогда тогда, когда оно делится на 17 и на 19.

Для начала рассмотрим делимость на 17. По лемме кратно то есть наше число делится на 17 тогда, когда кратно 17. При этом то есть кратно 17 только при чётном

Теперь рассмотрим делимость на 19. По лемме делится на а при число делится на

Итак, исходное число делится на 323 при чётных

Предположим, что является квадратом натурального числа. Пусть Рассмотрим произвольное Пусть понятно, что Тогда, если делит то делит и так как Но — противоречие. Значит, если у есть хотя бы три разных простых делителя, то есть хотя бы два индекса для которых число не делится на — противоречие. Также понятно, что у должно быть хотя бы два простых делителя, иначе таких индексов бы не было, поскольку было бы степенью простого числа.

Осталось разобрать случай, когда у ровно два различных простых делителя Если то Как мы знаем, для число не делится на Поэтому для всех остальных индексов должна быть выполнена делимость. Это в частности означает, что она выполнена для то есть делится на Тогда он равен и это больше А значит, у нет делителя то есть Теперь пусть Тогда То есть не делит — противоречие!

Заметим, что если и — два соседних делителя числа то и — тоже два соседних делителя числа Применяя для этих двух делителей условие задачи, получаем, что делится на то есть

Предположим, что такое возможно. Пусть где не делится на 3. Тогда тоже является точным квадратом, причём делители не кратные 3, совпадают с делителями У как у точного квадрата, нечётное число делителей, все они не делятся на 3, так что разбить на две равные группы их точно не получится.

Пусть — разложение на простые множители, причём …< Ясно, что а По условию не делится на поэтому Вспомним, что делители разбиваются на пары Отсюда следует, что

Так как то это выражение делится на

Отсюда видно, что, вычеркнув мы получим квадрат числа

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

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

Но раз квадрат делится на 2 и на 3, то и само делится на 2 и на 3. Тогда , значит,

Но раз квадрат делится на 2 и на 5, то и само делится на 2 и на 5. Тогда , значит,

Но раз квадрат делится на 3 и на 5, то и само делится на 3 и на 5. Тогда , значит,

В итоге причём при , , достигается равенство.

Для утверждение задачи очевидно, ведь числа — разной четности. Далее считаем

Сразу заметим, что

при этом то есть подходит на роль значит,

Заметим, что

Значит, делит один из множителей. Если делится на то — противоречие. Если делится на то откуда Если

делится на то также делится на что противоречит минимальности Наконец, если

делится на то делится на

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

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

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

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

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

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

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

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

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

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

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

Итак,

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

Предположим противное. Пусть последовательные числа имеют вид (). Их произведение равно Заметим, что числа и взаимно просты. Следовательно, если их произведение равно где , то Таким образом, Нетрудно видеть, что делится на а значит это число делит единицу. То есть Подставим вместо в уравнение и получим

Ясно, что для натурального и справедливо неравенство поскольку оно сводится к неравенству которое очевидно верное. Таким образом, при Если же то откуда но тогда число не натуральное, пришли к противоречию.

Разложим число 20222022 на простые множители: . Предположим, что такой набор существует. Тогда легко видеть, что сумма кубов не меньше, чем — противоречие.

Предположим, противное, тогда существует конечное множество простых делителей чисел вида Заметим, что число не кратно для всеx следовательно кратно некоторому простому числу которое не принадлежит — противоречие.

(a) Рассмотрим числа Для любых разных простых чисел оно подходит под пункт

(b) Допустим, что можно, и нам подходят числа Тогда Значит, Но тогда и но в этом случае но тогда условие, что ни одно из них не делится на другое, не выполняется.