15. Остатки. Сравнения. Профильный уровень

Остатки и сравнения

Число 20 делится на 10, а числа 21 и 22 не делятся. Но не делятся они «по-разному», потому что дают разные остатки при делении:

;

;

.

С этой точки зрения число 22 больше похоже на 32, чем на 21:

.

Такие задачи решает теория сравнений.

Если число a делится на натуральное число , то оно представимо в виде:

.

Если же число не делится на , то при делении получится неотрицательный остаток, меньший : , где .

Если два числа дают один остаток при делении на число m, то говорят, что они сравнимы по модулю .

Записывается это следующим образом

.

Например,

.

Понятно, что сам остаток от деления 22 или 32 (то есть 2) тоже сравним с ними по модулю 10:

.

Если число 2 делить на число 10, которое его больше, то в остатке будет 2.

Мы уже сталкивались с похожей ситуацией ― вспомните про тригонометрические функции и периодичность. Когда мы рассматриваем поворот, то часто нам неважно, сколько оборотов совершил объект, а только поворот относительно начального положения (в пределах 360°). В таких задачах повороты на 25° и на 385°, 745° и так далее не отличаются друг от друга (см. рис. 1).

Аналогично и с остатками ― при решении некоторых задач, в которых важен только остаток, например при делении на 10, числа 12, 22, 32 и так далее тоже не отличаются друг от друга ― их можно записать в виде , при этом период не влияет на остаток:

;

;

.

(Период 10 не влияет на остаток 2.)

Несмотря на простоту определения, есть одна тонкость, с которой нужно сразу разобраться.

Задача:

Разделим (–32) на 10.

Решение:

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

Для вычисления остатка найдём ближайшее число, не превосходящее (–32) и делящееся на 5. Это число (–40).

Теперь запишем , то есть остаток от деления (–32) на 10 равен не (–2), а 8.

Иначе говоря, .

Внутренний протест против такой конструкции понятен, но посмотрим на числовую ось (см. рис. 2).

Числа 2, 12, 22, 32 сравнимы по модулю 10. Они находятся на расстоянии 10 друг от друга. Остаток ― это расстояние до ближайшего числа слева, делящегося на 10. Естественно эту конструкцию оставить и для отрицательной части. А расстояние от (–32) до ближайшего делящегося на 10 числа слева (–40) равно 8.

На самом деле, иногда удобно расширить понятие остатка, разрешив ему быть отрицательным. Числа (–32) и (–2) действительно сравнимы по модулю 10:

.

Можно сформулировать более общее утверждение: два числа сравнимы по модулю , если их разность кратна :

.

Тогда можно сказать, что .

Свойства сравнений

Для успешного применения сравнений рассмотрим несколько их свойств.

1) сравнимо с по модулю тогда и только тогда, когда разность и делится на :

.

В самом деле,  означает, что и имеют равные остатки при делении m:

, ;

.

Пример:

.

2) Два сравнения можно почленно сложить или вычесть.

То есть если  и , то :

и .

В самом деле, .

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

Пример:

;

.

Тогда , то есть .

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

Сравнение можно домножить на одно и то же число.

.

Пример:

.

Остатки равны единице. Домножим сравнение на 5:

;

.

В самом деле, остатки равны двум.

3) Два сравнения можно перемножить.

То есть если  и , то :

.

В самом деле, рассмотрим разность

.

Вычтем и добавим одно и то же слагаемое bc, сгруппируем всю сумму следующим образом:

.

Оба выражения в скобках делятся на m, значит, и вся сумма делится на m.

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

Обе части сравнения можно возвести в одну и ту же степень.

.

Пример:

(остатки 3);

;

(остатки 1).

4) Подумаем, можно ли сокращать сравнение.

То есть верно ли следующее утверждение: если , то ?

Простой пример убеждает, что это не так.

― верно, но утверждение  неверно.

Давайте перефразируем это утверждение:

.

Вынесем за скобку:

.

Мы не можем утверждать, что . Мы можем быть уверены в этом, если n и m не имеют общих делителей, то есть взаимно просты.

В этом случае  и .

Таким образом, получаем свойство:

.

Пример:

.

.

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

Пример:

Какой будет остаток от деления  на 26?

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

― это очень близко, что хорошо. Сделаем так, чтобы показатель степени делился на 3:

.

.

Тогда , то есть .

Тогда .

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

Малая теорема Ферма

Пьер Ферма ― великий французский математик XVII века. Он является одним из главных создателей теории чисел. Ферма более всего известен благодаря так называемой «Великой теореме Ферма», которую весь мир доказывал 350 лет и которую доказали относительно недавно. Рассказ об этой теореме можно легко найти в интернете.

Мы разберём Малую теорему Ферма, название которой не надо воспринимать как указание на меньшую важность по сравнению с «Великой». Используется эта теорема для проверки простоты больших чисел в теории шифрования. Из более простых примеров использования ― получение признаков делимости на различные числа.

Итак, Малая теорема Ферма утверждает:

Если ― простое число, и число не делится на , то .

Рассмотрим это утверждение на конкретном примере:

5 ― простое число, 8 не делится на 5.

Тогда , то есть давать остаток 1 при делении на 5.

В самом деле, .

При делении 4096 на 5 получим остаток 1, что и утверждает Малая теорема Ферма.

Доказательство теоремы можно посмотреть в ответвлении.

Доказательство Малой теоремы Ферма

Итак, ― простое число, и число не делится на .

Докажем, что .

Рассмотрим все вот такие числа: .

Так как не делится на и ― простое, то и взаимно просты. То есть и не имеют общих делителей, кроме единицы: .

Точно так же любое число, меньшее p, и p не имеют общих делителей.

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

.

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

,

,

……………….

.

Понятно, что все остатки меньше .

Мы уже сказали, что они все не равны нулю.

Покажем также, что они все разные.

Предположим, что это не так, и нашлись два одинаковых остатка:

;

, где .

Тогда ,.

Но и взаимно просты. Тогда  делится на , то есть .

Числа и находятся в интервале от 1 до :.

Значит, самое меньшее значение, которое может принять их разность, это когда минимально, а максимально. То есть ,.

Какие числа делятся на ?

То есть в интервале  только одно число делится на . Это ноль.

То есть .

А ведь мы их брали разными. То есть одинаковых остатков у разных чисел из набора не может быть.

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

При этом они все положительные, их  штук, и они все меньше или равны .

Но это значит, что в нашем наборе ,, ………………., .

Правые части принимают все значения от 1 до . То есть такие же, как коэффициенты перед слева. Правда, мы не знаем в каком порядке. Но это нам и не понадобится.

Перемножим все эти сравнения:

.

Коэффициенты слева и остатки справа дают один и тот же факториал:

.

Сократив на факториал, мы получим нужное нам условие. Но мы помним, сокращать можно только на величину, взаимно простую с .

Это показать легко.

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

Итак, сокращаем на факториал:

.

Теорема доказана.

Диофантовы уравнения

Греческий математик Диофант жил в начале нашей эры. Его труд «Арифметика» считают началом современной алгебры. Он отказался от геометрической интерпретации числовых задач, ввёл способ записи, на котором основана современная алгебраическая запись.

В своей книге «Арифметика» Диофант рассматривает уравнения, которые теперь так и называют ― диофантовы.

Мы рассмотрим простейший тип таких уравнений ― линейные диофантовы уравнения с двумя переменными.

Линейное уравнение с двумя переменными имеет вид .

Решением такого уравнения является пара чисел.

Например, найти решение уравнения не составляет труда.

Вместо мы можем подставить любое число, например 1:

.

Найдём :

.

Таким образом, решением уравнения будет пара .

Таких решений, понятно, существует бесконечно много.

Каждое из них называют частным решением уравнения.

Чтобы записать все решения, нужно взять любое значение и выразить через :

.

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

При  получим частное решение .

Диофантовым наше уравнение становится, если у него мы ищем только целые корни. Также все коэффициенты тоже должны быть целыми, в нашем примере это было с самого начала.

Решим снова наше уравнение, но уже как диофантовое:

.

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

Легко заметить, что из первого слагаемого можно сделать 40, а из второго 30. Разность будет как раз 10.

Таким образом, ;― частное решение диофантова уравнения.

Лёгкость, с которой мы его нашли, убеждает, что таких решений точно не одно.

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

.

По сути, мы имеем представление десятки в виде суммы. Заменим в уравнении 10 на это представление:

.

Понятно, что ничего не изменилось. Справа осталось число 10.

Перенесём в левую часть все слагаемые с двойкой, а в правую ― с тройкой:

.

Вынесем 2 и 3 за скобки:

.

Левая часть делится на 2. Но значит, и правая делится на 2, ведь они равны:

.

Но 3 и 2 взаимно просты (запомним этот факт ― коэффициенты взаимно просты, он важен будет в дальнейшем). Значит,  делится на 2.

То есть , где ― любое целое число.

Подставим это выражение в уравнение:

.

Сократим на 2:

.

Таким образом,

Мы нашли общее решение уравнения, то есть решили уравнение.

Подставляя различные целые , мы будем находить различные частные решения диофантова уравнения.

Например, при  получаем

(29, 16) является частным решением. Проверим это:

.

Всё верно.

Сделаем теперь всё то же самое, но уже в общем виде.

Рассмотрим уравнение .

В нашем примере коэффициенты и были взаимно просты. Всегда ли это так в диофантовом уравнении?

Давайте подумаем.

Пусть . Тогда делится на и делится на . То есть вся левая часть делится на :

.

Для может быть два случая:

1) не делится на . Но тогда диофантово уравнение не имеет решений, ведь левая часть при всех целых и делится на , а правая ― нет.

2) делится на . Тогда мы обе части уравнения можем сократить на . В итоге новые коэффициенты в левой части окажутся взаимно просты, ведь мы поделили их на наибольший общий делитель, других общих делителей не осталось.

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

Пример:

.

Коэффициенты слева имеют общий делитель 5, и правая часть позволяет на него сократить.

Сокращаем на 5:

.

Получили взаимно простые коэффициенты (2 и 3), можно решать уравнение дальше.

.

Коэффициенты слева имеют общий делитель 5, но правая часть не позволяет сократить на него. Значит, уравнение не имеет решений. Это и понятно, ведь левая часть всегда делится на 5, а правая ― нет.

Итак, нам осталось научиться решать диофантово уравнение со взаимно простыми коэффициентами:

Подберём любое частное решение . (Как мы видели, это не очень сложно сделать.)

Тогда .

Подставим это выражение для в уравнение:

.

Перенесём слагаемое с влево, с ― вправо:

.

Вынесем и за скобки:

.

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

То есть  делится на .

Тогда можем записать , где ― любое целое число.

Подставим это условие в уравнение .

Тогда .

Сократим на :

.

Запишем общее решение: где .

Пример:

Решить диофантово уравнение .

Уравнение можно сократить на 2:

.

Коэффициенты в левой части получились взаимно простыми. Значит, уравнение имеет решение.

Подбираем частное решение.

Нам нужна сумма 15.

Из первого слагаемого легко «сделать» 20, а из второго (–5).

Получаем частное решение (5; –1).

Теперь запишем общее решение по формулам, которые мы получили: где .

Проверим себя, возьмём .

(10, –5) является частным решением, что легко увидеть, подставив его в исходное уравнение.

Целая и дробная части числа

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

Такая функция есть ― это целая часть числа. Точнее, она выполняет один вид округления ― по недостатку. Обозначается она с помощью квадратных скобок: . Называется эта функция по-русски «целая часть числа », или по-французски ― “entier ” («антье от »). Буква подчёркивает, что значение функции целое.

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

.

Понятно, что у таких чисел, как 2,34 или 2,99, одно и то же значение антье:

;

.

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

.

В самом деле, это наибольшее целое число, не превосходящее (–2,34) (см. рис 3).

Несложно построить график функции . Очевидно, эта функция задана на всей вещественной оси, ведь целую часть можно найти для любого числа. Она представляет собой кусочно-постоянную функцию, и в каждой целой точке происходит скачок на единицу (см. рис. 4).

С целой частью числа связана вторая функция ― дробная часть числа.

Обозначается с помощью фигурных скобок: {}. Она равна разности самого числа и его целой части:

.

Например, найдём дробную часть числа 2,34. Имеем:

.

Что было ожидаемо.

Найдём дробную часть числа (–2,34). Получим:

.

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

.

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

Дробная часть представляет собой кусочно-линейную периодическую функцию с периодом, равным единице. График этой функции тоже достаточно легко построить (см. рис. 5).

Список литературы

1. Алимов Ш. А., Колягин Ю. М., Ткачёва М. В. и др. Алгебра и начала математического анализа (базовый и углублённый уровни). ― М.: АО «Издательство “Просвещение”», 2017–2019.

2. Никольский С. М., Потапов М. К., Решетников Н. Н. и др. Алгебра и начала математического анализа. 10 класс. Учебник. Базовый и профильный уровни. ― М.: АО «Издательство “Просвещение”», 2021.

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

1. Интернет-портал «microexcel.ru» (Источник).

2. Интернет-портал «ru.wikibooks.org» (Источник, Источник).

Домашнее задание

1. Является ли верным соотношение ? Ответ обоснуйте, используя одно из определений сравнения по модулю.

2. Используя сравнения по модулю, найдите остаток от деления выражения  на 7.

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

4. Вычислите значения выражения , где ― целая часть числа, ― дробная часть числа.