Теория чисел на Межведе

Поскольку произведение первых 6 натуральных чисел равно то искомое число не больше

Осталось доказать, что произведение любых подряд идущих 6 натуральных чисел делится на . Поделим:

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

Вычислим

То есть нужно найти остаток по модулю Рассмотрим первое слагаемое.

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

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

Тогда получаем

Следовательно, остаток равен

Предположим, что Преобразуем уравнение:

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

Домножим на

Пусть Если то Значит, тогда Получим что, или Откуда получим ответ.

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

Заметим, что Далее проверкой до целой части от соответствующего арифметического корня проверяем оба множителя на простоту. Разложение получено.

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

Заметим, что Тогда

Следовательно, пары чисел или имеют общие делители, отличные от 1. Найдём наибольший общий делитель чисел по алгоритму Евклида:

Следовательно, — простое число. Остаётся разделить на

Чтобы понять сколько цифр содержится в записи натурального числа , надо найти такое неотрицательное целое число что будет справедливым неравенство Такое число очевидно, единственно. (Например, поэтому в записи числа 992 три цифры.)

Итак, надо найти такое целое неотрицательное что По условию Возведя обе части в степень получим Значит, в десятичной записи числа содержится 31 цифра.

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

Пусть пара натуральных чисел удовлетворяет исходному уравнению

(1)

Тогда

1.

Положив и подставив в получим

Очевидно, что . Поэтому . Без ограничения общности можно считать, что в этой паре . Будем это записывать как

2.

По условию, число является корнем многочлена

(2)

По теореме Виета, этот многочлен еще имеет корень причем

Отсюда следует, что и Поэтому уравнение имеет еще одно решение в натуральных числах

Это означает, что для многочлена справедливы равенства

Заметим, что

Поэтому число лежит между корнями многочлена а именно:

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

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

Если то

Если то правая часть кратна трём, а левая — нет. Значит, Если то вновь придём к противоречию : кратное трём число не может быть никакой степенью двойки, в том числе нулевой. Остаётся только вариант в котором есть решение

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

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

В итоге обе части равенства

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

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

Каждое 100-значное натуральное число может быть получено дописыванием двух цифр справа к 98-значному числу. Пусть — некоторое 98-значное число. Посмотрим какие справа две цифры (каждая из которых равна 1 или 2) нужно к числу приписать, чтобы получившееся 100значное число делилось на 3. Воспользуемся тем, что остаток от деления натурального числа на 3 равен остатку от деления на 3 суммы его цифр. Пусть наше число при делении на 3 дает остаток . Тогда

- если , то припишем 12 или 21 ;

- если , то припишем 11 ;

- если , то припишем 22 ;

Таким образом, из каждого 98-значного числа, кратного 3, можно получить два кратных трем 100 -значных числа. Каждое не кратное трем 98-значное число порождает только одно кратное трем 100-значное число.

Всего 98-значных чисел . Пусть среди них чисел кратно трем. (Далее символом будем обозначать количество n-значных чисел, кратных 3.) Тогда количество кратных трем 100 -значных чисел может быть найдено по формуле

Верны, таким образом, следующие соотношения:

Сложив эти равенства (величины при этом сокращаются), получим

Остается просуммировать геометрическую прогрессию и заметить, что . Тогда

Пусть пара чисел удовлетворяет уравнению

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

Более того, будем предполагать, что

Итак, пусть пара ( ) удовлетворяет (1), а также усл. (2), (3). Из (1) находим, что

Это равенство можно трактовать как квадратное уравнение относительно неизвестной . По теореме Виета, помимо, собственно, , это уравнение еще имеет корень такой, что

________________________________________________________________________________________________________________________________________________________________________________________________________

Утверждение.

Этот новый корень удовлетворяет условиям:

________________________________________________________________________________________________________________________________________________________________________________________________________

Доказательство.

Числа и удовлетворяют (1), поэтому (иначе правая часть (1) была бы отрицательной, так как, по условию задачи и в силу (2), ). Из (4) следует, что неотрицательное является целым, а из (5) — что

Установим, что . Действительно,

В силу (3) получаем

________________________________________________________________________________________________________________________________________________________________________________________________________

Таким образом, пара , удовлетворяющая уравнению (1) и ограничениям (2), (3), порождает новую пару (см. (4)) вида ( , которая также удовлетворяет (1), (2), (3) (если, конечно, ; так как, согласно (5), еще может быть найден по формуле , так что, если , то (3) не будет выполнено). Будем эту новую пару обозначать как . Затем по тем же формулам можно из пары получить еще решение и т.д. Символически полученный результат представим следующим образом:

Сразу же отметим и формулы обратного преобразования

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

(Цепочку (8) вправо продолжать смысла нет, так как далее .) А вот что предшествует паре ? Согласно , на предыдущем шаге и это тоже решение уравнения (1)! Можно продолжить, получая новые решения: и так далее. Значит, всего решений у уравнения (1) бесконечно много, так как цепочку (8) можно продолжить влево сколь угодно далеко.

Поясним почему (8) содержит все решения (1), удовлетворяющие условию (3). Пусть ( ) - какое-то (удовлетворяющее (3)) решение уравнения (1). Было показано, что с помощью формул (7) из решения ( ) можно получить цепочку новых решений (см. (6)), которая непременно закончится решением . Но это и означает, что ( ) содержится в (8), ведь, приняв теперь решение за отправную точку, мы с помощью обратных преобразований ( ) вернемся к ( ) (а цепочка (8) именно так и устроена: начав с , мы с помощью ( ) получаем ее всю).

Чтобы записать ответ несколько поменяем нумерацию: положим и двинемся с помощью по цепочке (8) влево (у нас будет ( ) и т.д.).

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

По условию количество делителей равно Следовательно, получим неравенство Решая его в натуральных числах, получаем, что Перебирая чётные находим подходящие и

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

По условию число делителей равно Следовательно,

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

Из условия на количество делителей

следует, что при правая часть строго больше левой:

Поэтому и каждая из скобок в левой части меньше 5, так что остаётся перебрать три случая в равенстве

• быть не может, так как тогда левая часть чётна, а правая часть нечётна.
• при единственным решением является
• при единственным решением является

Заметим, что из этого неравенства следует, что

Пусть . Тогда . Мы знаем, что не может давать остаток 3 при делении на 9, так как тогда делится на 3, но не делится на 9. Значит, может быть равно только . Заметим, что и . Число не равно 135 и 136 , так как . Значит, и подходит.