Дискретно-непрерывная математика (стр. 16 )

Теорема 19. Для того чтобы числа а и b были равноостаточными при делении на т, необходимо и достаточно, чтобы (а - b)т.

Доказательство.

Необходимость. Пусть

(*)

(**)

Ввиду равноостаточности а и b должно быть r1 =r2. Значит,

т. е.

Достаточность. Пусть (а — b)т. Разделив а и b на т с остатком, мы получим (*) и (*). При этом

т. е.

По теореме 6 Но . Значит, по теореме r1 — r2 = 0 или r1 =r2, а это и требовалось.

Следствие. Если числа а и b равноостаточны при делении на т, и т d, то а и b равноостаточны при делении на d.

Теорема 20. Если при делении на т числа а1, a2, ..., ап соответственно равноостаточны числам b1, b2, ..., bп, то равноостаточными будут суммы а1+a2+ ...+ап и b1+ b2+ ...+bп, а также произведения а1а2 ... ап и b1b2 ...bп.

Доказательство.

Из условия на основании теоремы 16 мы имеем

(***)

Сложив почленно эти равенства, мы после про­стых преобразований получаем

что по теореме 19 и означает равноостаточность сумм. Для доказательства равноостаточности произведе­ний отметим следующее тождество:

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

Перемножив теперь почленно все равенства (***) и применив к правой части только что проведенные рассуждения, мы получаем

где t — некоторое целое число. Равноостаточность произведений, таким образом, доказана.

Следствие. Если при делении на m числа а и b равноостаточны, то такими же являются и сте­пени ап и bп при любом натуральном п.

Теорема 20 и ее следствие дают уже довольно бо­гатые возможности для нахождения остатков от де­ления.

Приведем несколько примеров.

Пример 1. Найти остаток от деления на 3 числа

А=1316-223∙515.

Очевидно, при делении на 3 число 13 равноостаточно с 1, 2 равноостаточно с —1, а 5 тоже с —1. Значит, на основании доказанного число А при делении на 3 равноостаточно с числом

116— (—1)25(—1)15==1—1==0;

т. е. искомый остаток равен нулю, а А делится на 3.

Пример 2. Найти остаток от деления того же числа А на 37.

Представим для этого А в следующем виде:

А = (132)8-(25)5-(53)5.

Так как 132= 169 при делении на 37 равноостаточно с —16, 25 = 32 равноостаточно с —5, а 53=125 — с +14, то все число А равноостаточно с

(-16)8-(-5)5(+14)5

или, что то же самое, с

(162)4 + 705.

Но 162, т. е. 256, равноостаточно с —3, а 70 — с —4. Значит, А равноостаточно с

(—3)4 + (—4)5

или, что то же самое, с

81 — (25)2,

а потому с

81- (-5)2= 81-25 = 56.

Наконец, 56 при делении на 37 равноостаточно с 19, которое неотрицательно и меньше 37 и потому яв­ляется искомым остатком.

4. Равноостаточные при делении на т числа а и b назы­ваются также сравнимыми по модулю т. Это обозначается так:

а = b (mod т),

а сама эта формула называется сравнением.

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

Отметим несколько свойств отношения сравнимости по мо­дулю.

1°. Рефлексивность: a ≡а (mod т).

Действительно, а — а =0т.

2°. Симметричность: если a≡b (mod т), то b≡a (mod m).

В самом деле, если (а — b) т, то (хотя бы по теореме 5) и (b — a) т

3°. Транзитивность: если a≡b (mod т) и b≡c (mod m), то

а≡c (mod m).

Для доказательства достаточно заметить, что из (а—b)т и (b— a)т

по теореме 6 следует, что (a — c) т.

Если некоторое отношение (обозначим его через ~) обладает свойствами рефлексивности, симметричности и транзитивно­сти, то оно называется отношением эквивалентности (или экви­валентным отношением). Простейшим примером отношения экви­валентности на множестве чисел является отношение равенства.

Так как отношение сравнимости по модулю m — отношение эквивалентности, оно также разбивает множество целых чисел на классы. Эти классы называют классами вычетов по модулю т.

4° Число классов вычетов по модулю m равно т.

В самом деле, два числа а и b принадлежат одному классу вычетов по модулю m тогда и только тогда, когда они при де­лении на m дают один и тот же остаток. Но остаток при деле­нии на m может принимать ровно m значений: 0, 1, 2, .... m— 1. Следовательно, и число классов равно m

Отметим одно обстоятельство, явля­ющееся уточнением следствия теоремы 19

Для того чтобы каждый класс вычетов по модулю m1 содержался в некотором классе вычетов по модулю m2, необхо­димо и достаточно, чтобы m1 m2.

Действительно, рассмотрим класс вычетов К1 по модулю m1, содержащий число 0. Очевидно, класс К1 состоит из всех чисел, дающих при делении на m1 в остатке 0, т е. делящихся на т1. В частности, он содержит число m1. Класс вычетов по модулю m2, содержащий K1, также содержит 0 и потому состоит из всех чисел, делящихся на m2. Так как в него входит число m1, долж­но быть m1 m2. Этим доказана необходимость, достаточность же очевидна.

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

Продолжим перечисление свойств сравнимости чисел. Из теоремы 20 немедленно следуют:

5°. Если a≡ b (mod т) и с≡ d(mod m), то

а +с ≡b+ d (mod т)

Следствие. Если а ≡ b (mod т), то

а + r ≡ b + r (mod m)

для любого целого r.

6°. Если а ≡ b (mod т) и с≡ d(mod m), то

ас ≡bd (mod m).

Свойства 5° и 6° показывают, что сравнения подобно равен­ствам можно почленно складывать и перемножать.

4.6. Признаки равноостаточности и признаки делимости

1. Весьма общий способ нахождения остатка от деления произвольного, но фиксированного натурального числа а на данное натуральное число m заклю­чается в следующем. Будем строить последователь­ность натуральных чисел

а = А0, А1, А2, ..., (1)

равноостаточных при делении на т. Способ построения этой последовательности выберем такой, чтобы после всякого ее члена, большего или равного т, следовал еще хотя бы один член. Тогда, очевидно, всякий член последовательности (1), меньший чем т (если, конечно, такой существует), будет равен остатку от деления а на т. Таким членом может быть, например, последний член последовательности (опять-таки, если такой имеется).

Одним из простейших примеров последовательно­сти (1) может служить последовательность (3) из п. 11 п. 4.3:

а, а — т, а — 2т, ...

В сущности, к построению последовательностей та­кого типа сводятся задачи нахождения остатков в примерах 1 и 2 из п. 4.6.

Всякий способ построения последовательности (1), обладающей последним членом, назовем признаком равноостаточности при делении на т.