Лемма об уточнении показателя

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

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

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

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

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

В первом случае получаем, что Тогда является квадратичным вычетом по модулю а — не является, откуда является квадратичным невычетом по модулю но

откуда получаем противоречие.

Во втором случае получаем, что делится на откуда Тогда имеем уравнение Заметим, что откуда По лемме об уточнении показателя получаем, что

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

Разберем случай четного Пусть то есть Заметим, что делит откуда

Заметим, что при откуда Тогда Тогда

С другой стороны

откуда

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

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

Заметим, что при

Если то — нет решений.

Если то откуда

Вернемся к исходному уравнению

Посмотрев по модулю получаем Далее Но по лемме об уточнении показателя

откуда что не может быть правдой. Значит,

Из признака делимости на (необходимо рассмотреть знакочередующуюся сумму блоков по цифре с конца) следует, что числа в которых количество в записи отличается на четное число имеют одинаковые остатки при делении на
Заметим, что а еще по лемме об уточнении показателя не делится на поэтому у есть простой делитель отличный от
Достаточно сделать так, чтобы и делились на и на соответственно. Такое существует и не превосходит по китайской теореме об остатках.

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

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

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

В силу LTE, с другой стороны, произведение 50 натуральных чисел кратно но в силу теоремы Лежандра

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

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

Решение 1.

Лемма. Для любого натурального найдётся натуральное такое что

Доказательство. Индукция по База индукции: Годится Переход индукции. Если то

Лемма доказана.

_________________________________________________________________________________________________________________________________________________________________________________

Утверждение задачи тоже доказываем индукцией по База: делится на . Переход. Пусть делится на Хотим добиться делимости на Пусть таково, что Можем считать, что не делится на а также что Тогда рассмотрим разность

Так как оба числа и делятся на и не делятся на то делится на

______________________________________________________________________________________________________________________________________________________

Решение 2.

Покажем, что является показателем числа по модулю (при условии Этот показатель является делителем числа т.е. является степенью двойки. Но при любом натуральном верно Значит, показатель в самом деле равен

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

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

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

Если является нечетным, то число

так же нечетно, что невозможно, следовательно кратно

Предположим, что кратно Степень вхождения в правую часть равна что, в силу LTE для числа равно следовательно, а значит С другой стороны,

что влечет противоречие.

Таким образом, дает остаток при делении на — четно. Тогда то есть кратно а значит, в силу LTE,

то есть степень вхождения 2 в левую часть исходного уравнения что не превосходит

Таким образом, верна серия неравенств

При верны неравенства и сложив которые получим противоречие.

Если то уравнение имеет вид

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

кратно что невозможно в силу простоты а значит — так же простое число.

При уравнение имеет решение, количество делителей числа равно

Если то число делителей числа равно (делителями являются числа и ).

Запишем выражение в виде Пусть — некоторый простой делитель тогда по имеем:

Следовательно, степень вхождения во всё выражение равна для каждого простого делителя Получается, что степень вхождения равна

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

Итак, теперь и не делятся на а — делится (доказывается так же, как мы это делали в начале). Тогда по имеем:

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

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

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

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

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

Таким образом, двойка — действительно первообразный корень по этому модулю. Следовательно, по модулю степени двойки дают различных остатков — в точности те, что взаимно просты с (так как степень двойки не кратна пяти). Значит, существуют степени двойки, сравнимые по модулю с То есть существуют степени двойки, сравнимые по модулю с

(домножаем все предыдущие степени и их остатки на это можно сделать, поскольку и взаимно просты).

Заметим теперь, что каждый следующий остаток отличается от предыдущего не более чем на Значит, на каждом шаге -ая с конца цифра соответствующей степени двойки увеличивается не более, чем на а отсюда следует, что такими шагами мы получим на местах с по любую комбинацию цифр. Собственно, выберем степень двойки, на которой мы получили данную комбинацию — она и будет искомой, которая получается дописыванием цифр.

Пусть — наименьший простой делитель числа Тогда и Получаем, что Обозначим через показатель числа 2 по модулю Тогда и Значит, и потому либо либо (иначе в найдется простой делитель меньший ). При получаем, что — противоречие. Поэтому и Значит,

Теперь применим LTE:

откуда следует, что

Пусть Если то — ответ. В противном случае — нечетно, и пусть — наименьший простой делитель Тогда Получаем: и ) Пусть — порядок двойки по модулю Тогда и Ho поэтому значит, Если то — противоречие. При получаем, что — противоречие. Если то и — противоречие. Значит, Тогда и

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

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

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

Замечание.

— неверное рассуждение

Будем вести индукцию по .

(a) Докажите базу для .

Решение. Заметим, что . Поскольку
, правая скобка по модулю сравнима с , что, очевидно, не кратно .

(b) Докажите, пожалуйста, базу и для . Это пригодится в дальнейшем.

Решение. Докажем для . Аналогично предыдущему пункту, заметим, что

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

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

складываем все члены с и замечаем, что нечётно, а значит, эта сумма делится на

(c) Докажите индукционный переход.

Решение. Пусть . Тогда заметим, что

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

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

Но это, согласно первому пункту, равно

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