"Алгебра (в 3 частях)", Петерсон Л.Г., Абраров Д.Л., Чуткова Е.В.
При делении целого числа на натуральное n остаток может быть только одним из чисел 0, 1, …, n − 1. По этим остаткам все целые числа разбиваются на n классов: например, числа одного класса отличаются на число, кратное n. Такая классификация помогает описывать бесконечные множества чисел коротко и доказывать свойства сумм, разностей и произведений, даже если сами числа неизвестны или очень велики.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Деление с остатком целого числа a на натуральное число n записывают в виде a = nq + r, где q — целое число, а 0 ≤ r < n. Например, 17 = 5 · 3 + 2. Такая запись показывает, сколько полных групп по n содержится в числе и что осталось.
Число r называют остатком от деления: это единственное неотрицательное число, меньшее делителя n, для которого верно равенство a = nq + r. Условие на r помогает точно договориться, какой остаток считать правильным. Оно особенно полезно, когда делимое отрицательное.
Класс чисел по остатку r при делении на n — это все целые числа вида nk + r, где k — любое целое число. Например, при делении на 4 числа 2, 6 и 10 принадлежат одному классу, поскольку каждое можно записать как 4k + 2. Такая форма сразу описывает целую бесконечную группу чисел.
Классами вычетов по модулю n называют n групп целых чисел, соответствующих остаткам 0, 1, 2, …, n − 1. Слово «модуль» здесь указывает на делитель, по которому сравнивают остатки. Классы нужны, чтобы распределить все целые числа по конечному числу групп.
При делении на n остаток не может быть равен n или быть больше него. Если бы он был таким, из остатка можно было бы вычесть ещё одно n, а к частному прибавить 1. Значение числа не изменилось бы, но остаток стал бы меньше. Повторяя это, приходим к остатку от 0 до n − 1.
Теорема о делении с остатком утверждает, что для целого числа a и натурального n существуют целые q и r, для которых a = nq + r и 0 ≤ r < n, причём такая пара единственна. Единственность означает, что нельзя получить два разных допустимых остатка для одного числа и делителя. Поэтому каждому целому числу соответствует ровно один остаток, а значит, ровно один класс.
Если остаток равен r, число имеет вид nk + r: это следует прямо из записи деления, где q можно обозначить буквой k. Обратно, число вида nk + r при 0 ≤ r < n при делении на n оставляет остаток r. Например, числа, делящиеся на n, имеют вид nk: у них остаток 0, и все они составляют один класс.
При фиксированном n возможны только n остатков — от 0 до n − 1, поэтому образуются ровно n классов. Два числа a и b принадлежат одному классу тогда и только тогда, когда их остатки совпадают. Если a = nq + r и b = np + r, то a − b = n(q − p), то есть разность делится на n. И наоборот, если разность делится на n, у чисел одинаковые остатки: иначе их разность не могла бы быть кратна n.
Классификация позволяет вместо самого числа учитывать только его остаток, если изучаемое свойство зависит от деления на n. Для суммы достаточно сложить остатки слагаемых, а для произведения — перемножить остатки; затем результат снова представляют с остатком меньше n. Например, при делении на 5 числа с остатками 3 и 4 дают произведение с тем же остатком, что и 3 · 4, то есть с остатком 2. Это удобно, когда числа большие или заданы не конкретным значением, а своим классом.
| Остаток | Общий вид чисел | Примеры при n = 4 | Связь с делимостью |
|---|---|---|---|
| 0 | nk | …, −8, −4, 0, 4, 8, … | Числа делятся на n |
| 1 | nk + 1 | …, −7, −3, 1, 5, 9, … | При делении на n дают остаток 1 |
| 2 | nk + 2 | …, −6, −2, 2, 6, 10, … | При делении на n дают остаток 2 |
| 3 | nk + 3 | …, −5, −1, 3, 7, 11, … | При делении на n дают остаток 3 |
| r, где 0 ≤ r < n | nk + r | Общий случай | Все целые числа разбиваются на n классов |
Для делителя 4 каждая строка с остатком перечисляет целые числа, которые отличаются друг от друга на 4. В общем случае вместо 4 подставляют выбранное n, а возможный остаток r выбирают от 0 до n − 1. По таблице можно определить класс числа или записать все числа этого класса.
Найти остаток от деления −23 на 5 и указать класс, которому принадлежит число −23. Остаток должен быть неотрицательным и меньше 5, поэтому нельзя просто назвать отрицательную часть числа. Сначала ищем такую запись −23 = 5q + r, где q — целое, а r удовлетворяет условию.
Ответ: остаток равен 2; число −23 принадлежит классу чисел вида 5k + 2. Проверка равенства подтверждает результат, а условие на остаток — что он записан правильно. Отрицательное частное здесь допустимо, потому что делимое отрицательное.
Записать в общем виде все целые числа, которые при делении на 4 дают остаток 2, и определить классы чисел 18, 27 и 40. Для общего вида используем формулу nk + r, подставив делитель и остаток. Затем найдём остаток каждого числа при делении на 4.
Ответ: общий вид чисел — 4k + 2; число 18 относится к классу 2, число 27 — к классу 3, а число 40 — к классу 0. При проверке остаток должен быть меньше 4. Числа могут находиться в разных классах, даже если они близки друг к другу.
Докажите, что квадрат любого целого числа при делении на 4 имеет остаток только 0 или 1. Для доказательства рассмотрим все возможные остатки исходного числа: их ровно четыре. Поэтому достаточно возвести в квадрат числа каждого вида и привести результат к виду 4q + r.
Ответ: квадрат целого числа при делении на 4 может иметь остаток только 0 или 1. Мы проверили все четыре возможных класса, поэтому других случаев быть не может. Это и завершает доказательство.
Иногда остатком называют число, равное делителю или больше него. Так получается, если забыть проверить условие 0 ≤ r < n. Для самопроверки раздели этот остаток ещё раз: если из него можно вычесть n, запись не завершена.
При делении отрицательного числа могут назвать отрицательное число остатком, например −3 при делении на 5. Так происходит, если ориентироваться только на ближайшее кратное и не учитывать школьное определение остатка. Проверь запись a = nq + r: частное должно быть целым, а остаток — неотрицательным и меньше делителя.
Одинаковый последний разряд не означает, что числа всегда относятся к одному классу. Этот признак может помогать для делителей 2 или 5, но для другого делителя последняя цифра не определяет остаток. Проверка простая: раздели оба числа на нужный делитель или сравни их разность с кратными этого делителя.
Записи nk + r при разных значениях k не обязательно задают разные классы: они дают разные числа внутри одного класса. Ошибка возникает, когда переменную k принимают за номер класса, хотя она просто выбирает число из группы. Убедись, что остаток r один и тот же, а k меняется среди целых чисел; именно так получается весь класс.
Для работы с классами остатков нужно знать целые числа, деление с остатком и признаки делимости. Эта тема подготавливает к сравнениям по модулю и доказательствам делимости, где сравнивают остатки чисел. Она также помогает исследовать чётность, квадраты целых чисел и свойства сумм и произведений. В таких задачах часто достаточно разобрать ограниченное число возможных остатков вместо бесконечного множества чисел.
Почему остаток не может быть равен делителю?
Если остаток равен n или больше, из него можно вычесть делитель n и увеличить частное на 1. Получится другая запись того же числа с меньшим остатком. Поэтому остаток выбирают только от 0 до n − 1.
Как находить остаток от деления отрицательного числа?
Нужно записать число в виде nq + r так, чтобы частное q было целым, а остаток r удовлетворял условию 0 ≤ r < n. Например, −23 = 5 · (−5) + 2, поэтому при делении −23 на 5 остаток равен 2.
Почему классов остатков ровно n?
Возможны ровно n остатков: 0, 1, …, n − 1. Каждое целое число имеет единственный остаток при делении на n, поэтому оно принадлежит ровно одному из соответствующих классов.
Чем класс чисел по остатку отличается от одного конкретного остатка?
Остаток — это одно число от 0 до n − 1, которое получается при делении. Класс — это все целые числа, имеющие этот остаток; для остатка r они записываются как nk + r, где k — целое.
Можно ли по остаткам складывать и умножать числа?
Да. Чтобы узнать остаток суммы или произведения, достаточно сложить или перемножить остатки, а затем разделить результат на n и взять остаток. Например, при делении на 4 числа с остатками 2 и 3 имеют произведение с остатком 2, потому что 2 · 3 = 6, а остаток от деления 6 на 4 равен 2.
2.2.2. Классификация целых чисел по остаткам от деления
