Делимость и делители (множители)

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

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

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

Можно взять , , , . Легко видеть, что , и ни одно из чисел не делится ни на какое из чисел .

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

Надо разбить это произведение на две группы: часть множителей войдёт в исходное число, а другая часть будет его цифрами. Ясно, что 19 войдёт в искомое число, ведь цифры “19” нет. Произведение цифр числа 19 не равно поэтому в число должен войти хотя бы ещё один множитель из 3,5,7. При этом все три множителя входить не могут, потому что тогда получится само число 1995, у которого произведение цифр не равно 1.

Если 5 входит в исходное число, то по признаку делимости это число может оканчиваться только на 0 или на 5. Если оно оканчивается на 0, то при умножении на цифры должно было получиться 0, а не 1995. Если оно оканчивается на 5, то с произведением цифр должно получиться уже кратное 25 число, но 1995 не делится на 25.

Остаётся проверить три варианта:

Решение

Независимо от расстановок знаков умножения правая часть равенства делится на 5, а значит, и левая часть должна делиться на 5, тогда после цифры 0 в левой части стоит знак умножения. Но тогда левая часть делится на 2, поэтому в правой части знак умножения должен стоять после какой-то четной цифры. Единственный вариант поставить знак умножения после 6. Далее несложным перебором легко убедиться, что последний знак нужно поставить перед цифрой 6 в правой части.

Рассмотрим 16 различных простых чисел. Обозначим их через . Через обозначим квадрат их произведения. Возьмем наши 16 чисел, равными . Заметим, что в произведение двух любых наших чисел каждое из 16 простых чисел входит хотя бы во второй степени. Но в каждом из наших чисел каждое простое входит в 1 или во второй степени, поэтому произведение любых 2 чисел будет делиться на любое число. Сами числа друг на друга очевидно не делятся (у каждого свое уникальное простое входит в разложение в первой степени, остальные простые — во второй).

Обозначим через и степени вхождения числа в и соответственно. Тогда из равенства степени вхождения 3 в правую и левую части получаем, что . Из этого условия легко видеть, что , . Проделаем аналогичные рассуждения для числа 5. Введя аналогичные обозначения, получаем, что , откуда , . Таким образом, мы доказали, что , . Тогда . Легко видеть, что такая сумма могла оказаться, так как .

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

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

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

Найдем наибольший общий делитель многочленов, стоящих в числителе и знаменателе, используя алгоритм Евклида.

Для этого поделим с остатком знаменатель на числитель:

В результате деления получили остаток Теперь числитель (который сейчас выступал в роли делителя) поделим (например, «уголком») на остаток:

Далее надо опять разделить делитель на остаток. В этот раз остаток от деления оказывается равным нулю:

Это означает, что многочлен является искомым наибольшим общим делителем числителя и знаменателя исходной дроби и он может быть «вынесен за скобки» (чтобы избежать появления дробных коэффициентов, будет удобнее использовать многочлен

Итак,

Обозначим число По условию значит, одна из этих цифр равняется а две другие равны Поскольку и не делятся на Число поэтому получаем два трёхзначных числа и Число откуда получаем два трёхзначных числа и Окончательно получаем числа.

Давайте для начала докажем вспомогательную лемму: произведение подряд идущих чисел делится на

Заметим, что количество способов выбрать человек из равно

Но количество способов - целое число, поэтому числитель делится на знаменатель. Лемма доказана.

Так как то можно представить в виде произведения подряд идущих чисел на следующих чисел на последних чисел:

Произведение подряд идущих чисел делится на поэтому делится на произведение факториалов

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

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

Вспомним, что сумма делителей числа равняется

Следовательно

В неравенстве мы заменили конечную сумму геометрической прогрессии на бесконечную.

Пусть теперь — некоторое число. Если у то

поскольку число тем больше, чем меньше

Аналогично, если то

Итак, если то в разложение входит хотя бы 3 простых числа. Поскольку уже то нас интересуют лишь в разложении которых ровно три простых числа.

Если среди этих простых чисел нет если среди них нет и то значит есть; если нет то значит и есть; если нет то значит и есть. Тогда (добавление ещё одного простого сделает больше ), сумма делителей которого равна Значит, обязательно делится на

Пусть третий простой делитель Заметим, что поскольку мы ищем то домножить мы можем максимум на Итак, получили всего немного вариантов: или , или , или

В первом случае при получаем при получаем а

Во втором случае,

Если то

Отсюда что неверно.

Аналогично, в третьем случае

Отсюда должно быть хотя бы что неверно при

При любом натуральном n данное произведение делится на , так как среди любых четырёх последовательных натуральных чисел одно делится на и еще одно – на . Следовательно, достаточно найти наименьшее , для которого данное произведение делится на . Так как на может делиться только один из множителей, то – наименьшее, если множитель, делящийся на , –– наибольший. Значит, , то есть .

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

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

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

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

Возьмём простое число большее Рассмотрим числа Любая сумма нескольких из этих чисел имеет вид где меньше а потому и не кратно То есть любая сумма делится на но не делится на а значит не является квадратом.

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

Пусть, не умаляя общности, , тогда и . Следовательно, при некотором натуральном , и

Значит, и , и удвоенные квадраты натуральных чисел, что и требовалось.

Запишем разложение чисел и на простые множители: показатели целые неотрицательные.

Количество общих делителей двух чисел равно количеству делителей их наименьшего общего делителя, тогда количество общих делителей и равно:

Аналогично выражается количество общих делителей чисел и чисел и

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

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

Теперь пусть Докажем задачу индукцией по количеству простых чисел, входящих в

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

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

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

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

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

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

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