Уравнения в целых числах

Сначала разделим все уравнение на и обозначим и Уравнение примет вид

Переставим и перегруппируем слагаемые:

Рассмотрим это уравнение как квадратное относительно откуда

Тогда Чтобы были решения, необходимо и достаточно откуда и то есть По формуле корней

Итак, и Пусть (условие делимости на необходимо, иначе в отношениях не будет множителя тогда и при целом

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

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

Пусть и решения уравнения Рассмотрим теперь числа и Тогда

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

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

Если при некотором верно, что то мы можем перейти к новому набору обнадеживающих чисел, в котором -ое будет представлено в виде

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

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

Осталось рассмотреть полученное равенство по модулю Для произвольного совершенного числа в котором не кратно верно, что

а те, что были поделены имеют вид и

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

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

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

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

то есть

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

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

Обозначим тогда где и взаимно просты. Получим

Сократим на

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

Пусть Тогда

Отсюда

Число 67 — простое, значит,

Перебрав все варианты от 1 до 8, получим и или наоборот. Также откуда или наоборот.

Поскольку а то числа и имеют общий делитель Таким образом, общее число фишек, которое Петя уберет со стола, делится на

Наибольшее число, делящееся на и не превосходящее равно (поскольку Значит, более фишек Петя забрать не сможет.

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

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

Пусть для некоторого целого Подставив это в уравнение, получим:

Это линейное диофантово уравнение. Его частное решение можно найти подбором, например, (проверка: ). Общее решение в целых числах имеет вид:

Поскольку то общее решение для и в неотрицательных целых числах:

где может принимать значения

Видим, что убрать со стола фишек можно различными способами. Например, при получаем и Этот вариант соответствует ходам. Схема действий может быть такой:

Этот вариант возможен: после каждой из девяти пар ходов (взять вернуть число фишек на столе уменьшается на После этого делается десятый ход (взять фишки). Итоговое изменение составит фишек, а на столе останется фишек.

Заметим, что при в левой части кратно пяти, так что вся левая часть даёт остаток по модулю

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

Остаются Вручную совершая проверку, находим единственное решение

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

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

Домножим на

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

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

Последнее неравенство следует из разложения по биному Ньютона для Действительно:

Значит,

логарифмируя и деля на получаем:

Пусть Заметим, что убывает при и (у этой функции производная равна и она отрицательна при Поэтому нет решений с и с

С другой стороны, можно проверить, что

при Действительно, при это

и производная выражения равна

Но (так как при

так что

уже при Таким образом, уравнение не имеет решений при

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

Рассмотрим наше равенство по модулю . Поскольку делится на , то по малой теореме Ферма даёт остаток или при делении на . При этом делится на . Тогда левая часть уравнения может давать остатки или при делении на , в то время как правая часть может давать остатки , то есть или . Значит, решений нет.

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

где Но это сравнение невозможно ни при каком (проверку осуществляем с перебора остатков по модулю Значит,

1.

В случае имеем уравнение Если то При решений нет. Далее считаем Имеем и откуда для некоторого натурального Из равенства следует, что делится на 3 (иначе правая часть не будет делиться на 9). Тогда делится на Следовательно, делится на 7. Но тогда так что Однако что дает противоречие.

2.

Рассмотрим случай При из уравнения находим Пусть далее и, как следствие, Имеем Отсюда следует, что делится на 7. Это возможно только при условии Но тогда что приводит к противоречию.

Уравнение равносильно

Если то запишем эту пару в ответ.

Теперь рассмотрим Тогда это натуральное число и на него делится левая часть уравнения

А значит, для некоторого натурального числа

После подстановки и сокращения на получим уравнение:

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

должно быть целым.

Более того, поскольку это равносильно неравенству которое верно при

Действительно, если то что невозможно при

Таким образом, а значит,

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

Если то число будет целым только при однако пара не удовлетворяет уравнению

При уравнение переписывается в виде Отсюда находим, что и затем

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

Пусть и где и тогда число определяется однозначно, а именно Получается, необходимо посчитать число допустимых пар Всего их

Формула суммы квадратов первых натуральных чисел известна:

Применим эту формулу и получим

Совершенно очевидно, что если , то левая часть делится на , значит, и правая часть должна делиться на , но 1 точно на не делится.

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

Замечание. А что произойдет, если справа написать не 1, а ? Во-первых, на можно сократить. Если после этого не делится на , то решений, очевидно, нет. Если делится, то решения есть по тому же алгоритму Евклида. В конце надо лишь домножить на . Более интересен вопрос найти все решения подобного ЛДУ, но этот вопрос мы оставим для самостоятельных размышлений.

Посмотрим на равенство по модулю Как известно, квадраты при делении на дают остатки кубы — четвёртые степени — Пут̈eм перебора остатков понимаем, что возможны только случаи

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

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

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

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

Если то

а значит, и — степени двойки. На два могут отличаться только и то есть

Если то посмотрим на равенство по модулю и заметим, что чётен (так как квадраты дают остатки при делении на а степени — ). Теперь мы имеем

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

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

Если имеем откуда Иначе делится на то есть чётно и

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

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

Ясно, что иначе правая часть больше левой. Если равенство примет вид то есть решений не будет. Если то и эта пара подходит. Пусть теперь Следовательно, (выражение на натуральных числах возрастает). Это неравенство равносильно следующему: Очевидно, оно решений в простых числах не имеет.