Android-приложение для поиска дешевых авиабилетов: play.google.com
Главная -> Высшая арифметика

0 1 2 3 4 5 6 7 8 9 10 11 [12] 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

1] ПОНЯТИЕ СРАВНЕНИЯ 41

а + b = а + Р (mod ш), а - b = а - Р (mod ш), аЬ = о:;5 (mod ш). Первые два из этих утверждений получаются немедленно; например, {а+Ь) - {а+Р) кратно ш, так как а -а и Ь-Р кратны т. Третье сравнение лучше всего доказать в два шага. Во-первых, аЬ = аЬ потому что ab - ab= {а - a)b и а - а кратно т. Далее, по тем же соображениям аЬ = ар. Значит, аЬ = аР (mod ш).

Сравнение всегда можно умножить на целое число: если а = а (mod ш), то ка = ка (mod ш). Это - частный случай третьего из только что установленных результатов (если b и Р оба равны к). Однако сокрагцение сравнения на какой-либо множитель не всегда возможно. Например, 42 = 12 (mod 10), но нельзя сократить числа 42 и 12 на множитель 6; такое сокрагцение приводит к неверному сравнению 7 = 2 (mod 10). Причина очевидна: первое сравнение утверждает, что 42 - 12 кратно 10, но отсюда не вытекает, что (42 - 12) кратно 10. Сокрагцение на множитель допустимо, если этот множитель взаимно прост с модулем. В самом деле, пусть имеется сравнение ах = ау (mod ш) и пусть а - множитель, на который его нужно сократить; предположим, что а взаимно просто с т. Сравнение утверждает, что а{х - у) делится на ш, а из последнего предложения в (I, 5) тогда следует, что х - у делится на т.

Пример использования сравнений доставляется хорошо известными признаками делимости на 3, на 9 и на И. Обычное представление числа п цифрами в десятичной системе счисления есть просто представление п в виде

п = а +106+100с+...,

где а, 6, с, ... - цифры числа, прочитанные справа налево, так что а - число единиц, b - число десятков и так далее. Так как 10 = 1 (mod 9), то 10 = 1 (mod 9), 10 = 1 (mod 9) и так далее. Поэтому из только что написанного представления следует, что

п = а + 6 + с+ ... (mod 9).

Другими словами, любое число отличается от суммы своих цифр на кратное 9; в частности, п делится на 9 тогда и только тогда, когда сумма его цифр делится на 9. Это рассуждение проходит



также и при замене 9 на 3.

Признак делимости на 11 основан на том, что 10 = = -1 (mod 11), так что 10 = +1 (mod 11), 10 = -1 (mod 11) и так далее. Поэтому

п = а - Ь + с- ... (mod И).

Следовательно, п делится на 11 тогда и только тогда, когда а - - Ь + с-... делится на 11. Например, чтобы проверить, делится ли число 9581 на И, образуем сумму 1-8 + 5-9, равную -И. Так как эта сумма делится на И, то и 9581 делится на И.

2. Линейные сравнения. Ясно, что каждое целое число сравнимо по mod т точно с одним из следуюгцих чисел:

О, 1, 2, ...,ш-1, (1)

так как всякое целое число представимо в виде qm + г, где О г < ш, и, значит, сравнимо с г по mod т. Очевидно, что, помимо ряда (1), имеются и другие ряды чисел, обладаюгцие тем же свойством; так, например, любое целое число сравнимо по mod 5 точно с одним из чисел О, 1, -1, 2, -2. Любой такой ряд чисел называется полной системой вычетов по модулю т. Таким образом, полной системой вычетов по mod т называется любой ряд из т чисел, никакие два из которых не сравнимы друг с другом.

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

ах = Ь (mod ш). (2)

Важно отметить, что любое такое сравнение разрешимо относительно X при условии, что а взаимно просто с т. Простейший способ доказательства этого утверждения состоит в следуюгцем: если х пробегает полную систему вычетов, то со-ответствуюгцие значения ах также образуют полную систему вычетов. Действительно, таких чисел ровно т и никакие два из них не сравнимы между собой, так как из сравнения axi = = ах2 (mod т) следует сравнение Xi = Х2 (mod ш). (Здесь на множитель а можно сократить, так как а и ш взаимно просты.) Так как числа ах образуют полную систему вычетов, то среди них найдется (и притом в точности одно) число, сравнимое с



2] ЛИНЕЙНЫЕ СРАВНЕНИЯ 43

данным числом Ь.

Рассмотрим, например, сравнение

Зх = 5 (mod 11).

Если придавать х значения О, 1, 2, ..., 10 (полная система вычетов по модулю 11), то Зх будет принимать значения О, 3, 6, ..., 30. Они образуют другую полную систему вычетов по mod И; эти числа сравнимы соответственно с О, 3, 6, 9, 1, 4, 7, 10, 2, 5, 8. Число 5 встречается при х = 9 значит, х = 9 есть решение сравнения. Каждое число, сравнимое с 9 по модулю И, также, конечно, будет удовлетворять сравнению, но тем не менее мы говорим, что у этого сравнения есть только одно решение, имея в виду, что сугцествует лишь одно решение в каждой полной системе вычетов, т. е. все решения сравнимы между собой. То же самое применимо и к обгцему сравнению (2); такое сравнение (если а взаимно просто с ш) в точности эквивалентно сравнению X = Xq (mod ш), где Xq какое-нибудь частное решение сравнения.

Можно смотреть на линейное сравнение (2) по-другому. Это сравнение эквивалентно уравнению ах = ту+Ь или ах -ту = Ь. Мы доказали в (I, 8), что такое линейное диофантово уравнение разрешимо относительно х и у если а и ш взаимно просты; отсюда вытекает другое доказательство разрешимости линейного сравнения. Но приведенное выше доказательство прогце и показывает преимугцества, которые мы получаем, используя понятие сравнения.

Тот факт, что сравнение (2) имеет единственное решение (в объясненном ранее смысле), дает возможность использовать это решение для интерпретации дроби Ь/а по модулю т. Сделав это, мы получим арифметику по mod ш, в которой всегда выполнимы сложение, вычитание и умножение, а также возможно деление, если делитель взаимно прост с ш. В этой арифметике имеется только конечное число различных чисел (их ровно ш), ибо два числа, сравнимых друг с другом по mod ш, отождествляются. Возьмем модуль т равным И; примерами «арифметики по модулю 11» могут служить сравнения

5 + 7=1, 5-6 = 8, = 9 =-2.



0 1 2 3 4 5 6 7 8 9 10 11 [12] 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57



0.0108
Яндекс.Метрика