05. Уравнения в целых числах. Решение задач С6

Понятие деления с остатком, некоторые определения и свойства

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

Напомним определение деления с остатком.

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

, где q – неполное частное, а r – остаток. Причем остаток изменяется от нуля до частного, уменьшенного на единицу, включительно: .

Справедлива другая запись:

Это значит, что a дает остаток r при делении на b.  

Определение:

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

Свойства сравнимостей и остатков:

Если  и , то  и

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

и

От выполнения вышеперечисленных манипуляций сравнимость не исчезает.

Строгое доказательство свойств сравнимости

Строгое доказательство первого свойства сравнимостей.

Дано: и

Доказать:

Доказательство: если числа сравнимы, то их разность кратна b, так как их остатки от деления на b одинаковы и при вычитании уничтожатся. То есть,  и . Докажем, что . Раскроем скобки и составим их несколько иначе:

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

Свойство доказывается аналогично.

Дано: и

Доказать:

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

Теперь сгруппируем первые два члена между собой и вторые два члена между собой:

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

Зная доказательство свойства про умножение, легко доказать свойство о степени, так как – это умноженное на себя n раз.

Делимость квадратов натуральных чисел на три и четыре

Докажем очень важное свойство, что квадраты натуральных чисел дают при делении на 3 или на 4 только остатки 0 и 1.

Рассмотрим для начала делимость на 3. Натуральное число a при делении на 3 может дать остатки 0, 1 или 2.

Число  будет давать такие же остатки, но возведенные в квадрат. Так, остаток 0 превратится в остаток 0 \\cdot 0=0 . Остаток 1 превратится в остаток . Остаток 2 превратится в остаток , но такого остатка при делении на три быть не может, число 4 при делении на три даст остаток 1. Таким образом, мы видим, что квадраты натуральных чисел дают только остатки 0 и 1 при делении на 3.

 Аналогично дело обстоит и с делимостью на 4.

Делимость квадратов натуральных чисел на четыре

Рассмотрим делимость на 4. Натуральное число a при делении на 4 может дать остатки 0, 1, 2 или 3.

Число будет давать такие же остатки, но возведенные в квадрат. Так, остаток 0 превратится в остаток . Остаток 1 превратится в остаток . Остаток 2 превратится в остаток , но такого остатка при делении на 4 быть не может, число 4 при делении на 4 даст остаток 0. Остаток 3 превратится в остаток , но такого остатка при делении на 4 быть не может, число 9 при делении на 4 даст остаток 1. Таким образом, мы видим, что квадраты натуральных чисел дают только остатки 0 и 1 при делении на 4.

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

Примеры решения уравнений в целых и натуральных числах

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

Натуральное число a при делении на 5 может дать остатки 0, 1, 2, 3 или 4.

Число будет давать такие же остатки, но возведенные в квадрат. Так, остаток 0 превратится в остаток . Остаток 1 превратится в остаток . Остаток 2 превратится в остаток , остаток 3 превратится в остаток , но такого остатка при делении на 5 быть не может, число 9 при делении на 5 даст остаток 4, остаток 4 превратится в остаток , но такого остатка при делении на 5 быть не может, число 16 при делении на 5 даст остаток 1. Таким образом, мы видим, что квадраты натуральных чисел дают только остатки 0, 1 и 4 при делении на 5.

Пример 1: решить уравнение в целых числах:

Здесь х и у целые числа

Разберем несколько случаев.

1. Пусть , в этом случае левая часть, очевидно, не целое число. Мы тройку возводим в отрицательную степень, получаем число меньше единицы и прибавляем к целому числу. А правая часть – число целое, т. к. квадрат целого числа – целое число. Значит, равенства быть не может.

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

Ответ:или  

Пример 2: решить уравнение в натуральных числах:

Натуральные числа – это целые положительные числа. Факториал – это произведение всех чисел от 1 до данного числа.

Попробуем и здесь применить остатки от деления на три.

Правая часть дает либо остаток 0, либо остаток 1.

Рассмотрим левую часть:

1. Если , то , так как будет произведением чисел, содержащим тройку. Тогда

   . Правая часть остатка два дать не может, поэтому равенство невозможно.

2.  . В этом случае , тогда имеем , но ноль не является натуральным числом, данный случай нас тоже не устраивает.

3. , В этом случае , тогда имеем . Минус единица не является натуральным числом, имеем единственный ответ.

Ответ:

Пример 3: решить уравнение:

и  

Прежде всего попробуем применить признак деления на при делении на 3 дает остатки 0 и 1; но может давать любой остаток. Поэтому здесь признак делимости на 3 нам абсолютно не поможет.

Попробуем рассмотреть делимость на при делении на 4 дает остатки 0 и 1; даст остаток ноль, так как содержит множитель 4; при делении на 4 дает остатки 0 и 1

Тогда вся левая часть может при делении на 4 дать остатки 0, 1 или 2.

Когда мы складываем эти три числа, второе слагаемое ни на что не влияет – это 0. А сумма первого и третьего может быть нулем, когда это два нуля, единицей, когда в одном случае это 0, в другом 1, либо двойкой, когда это две единицы.

Определим остаток при делении правой части на 4.

Есть признак, который говорит, что, чтобы найти остаток от деления числа на 4, достаточно рассмотреть число, состоящее из его двух последних цифр. В данном случае 11. Можно разделить число 2011 в столбик на 4. Так или иначе, мы получаем, что остаток от деления правой части на 4 равен трем, то есть заданное равенство невозможно ни при каких целых х и у.

Ответ: нет решений.

Комментарий: чтобы догадаться, что здесь нужно рассматривать именно остатки от деления на 4, нужно заметить выражение 4ху, которое очевидно при делении на 4 дает остаток 0. При делении, скажем, на 3 или 5 остатки могут быть принципиально разными. Кроме того, подсказка – это квадраты. Квадраты, как мы знаем, очень своеобразно себя ведут при делении на 3 и 4.

Дополнительный пример – уравнение в натуральных числах

Дополнительный пример: решить уравнение в натуральных числах:

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

    получается в четных степенях, остаток 2 – в нечетных степенях. Правая же часть при делении на три дает только остатки ноль и один. В левой части стоит сумма. Одно слагаемое всегда дает остаток ноль, второе – единицу, третье – единицу или двойку, поэтому сумма дает остатки два или три, остатка три быть не может, он превращается в остаток ноль. Правая часть дает остатки ноль и один. Есть совпадение – остаток ноль. Оно достигается при нечетных значениях x.

2. Рассмотрим остатки от деления на дает остаток ноль; дает остаток 2 при и остаток 0 при в таких случаях будет содержать множитель рассмотрим подробно слагаемое . При остаток при остаток при остаток при остаток . несложно заметить, что остатки чередуются и могут быть либо тройкой, либо единицей, причем остаток 1 получается в четных степенях, остаток 3 – в нечетных степенях. Правая часть по-прежнему дает остатки ноль и один. Из первого этапа мы знаем, что нечетное число, поэтому

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

Итак, мы познакомились с методом остатков при решении задач на целые числа.

Список рекомендованной литературы

1. Мордкович А.Г. Алгебра и начала математического анализа. – М.: Мнемозина.

2. Муравин Г.К., Муравина О.В. Алгебра и начала математического анализа. – М.: Дрофа. 

3. Колмогоров А.Н., Абрамов А.М., Дудницын Ю.П. и др. Алгебра и начала математического анализа. – М.: Просвещение.

Проверьте себя

1. Решить уравнение в целых числах:

а) ;

б) ;

в) ;

г) ;

д) ;

е) .