Дискретка. Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений
 Скачать 1.99 Mb.
|
|
a · b на m. Теорема 3.7.2. Тогда и только тогда элемент a кольца Z m имеет обратный (т. е. элемент a −1 такой, что a · a −1 = 1), когда (a, m) = 1. Доказательство. По теореме 3.5.3 уравнение ax + my = 1 разрешимо тогда и только тогда, когда (a, m) = 1, а это равносильно существованию элемента x, для которого остаток от деления числа ax на m равняется еди- нице. Этот элемент x является представителем класса, который при умно- жении на класс, соответствующий остатку a, дает единицу, т. е. является обратным. ¤ Теорема 3.7.3. Кольцо вычетов hZ m ; +, ·i тогда и только тогда явля- ется полем, когда m — простое число. Доказательство. По теореме 3.7.2 если m — простое число, то в Z m все ненулевые элементы обратимы, следовательно, hZ m ; +, ·i является полем. С другой стороны, если число m не является простым, то hZ m ; +, ·i не поле. Действительно, если m = a·b, 1 < a < m, 1 < b < m, то уравнение ax+my = 1 неразрешимо, поскольку (a, m) = a - 1. ¤ Пример 3.7.2. Кольцо Z 5 является полем. Все его ненулевые элемен- ты 1, 2, 3, 4 обратимы (обратные элементы — это 1, 3, 2 и 4 соответственно). Кольцо Z 8 полем не является, поскольку не существует 2 −1 . ¤ 3.7. ЦЕЛЫЕ ЧИСЛА ПО МОДУЛЮ m 101 По теореме 3.7.3 для любого простого числа p алгебра hZ p ; +, ·i образу- ет конечное поле. В отличие от полей Q, R, C в этом поле сложением еди- ницы p раз получается нуль: 1 + 1 + . . . + 1 = 0. Наименьшее количество таких слагаемых называется характеристикой поля и обозначается через char. Поле, в котором сумма любого количества единиц не равна нулю, на- зывается полем характеристики нуль. Таким образом, char(Q) = char(R) = = char(C) = 0, char(Z p ) = p. Опишем два алгоритма нахождения обратных элементов в поле hZ m ; +, ·i. 1. Использование алгоритма Евклида Пусть a ∈ Z m — ненулевой элемент. Так как (a, m) = 1, по алгоритму Евклида выполняются следующие соотношения: m = aq 1 + r 1 , 0 < r 1 < |a|, a = r 1 q 1 + r 2 , 0 < r 2 < r 1 , r 1 = r 2 q 2 + r 3 , 0 < r 3 < r 2 , . . . r k−2 = r k−1 q q−1 + r k , 0 < r k < r k−1 , r k−1 = r k q k + 1. С помощью последней формулы выражаем число 1 через r k и r k−1 : 1 = r k−1 − r k q k . Затем с помощью полученного выражения и предпоследней формулы алгоритма Евклида выражаем число 1 через r k−1 и r k−2 : 1 = r k−1 − r k q k = r k−1 − (r k−2 − r k−1 q k−1 )q k = = r k−1 (1 + q k−1 q k ) + r k−2 (−q k ). Продолжая процесс, на последнем шаге получим выражение числа 1 через a и m: 1 = ax + my. Искомый класс a −1 есть класс, содержащий число x, поскольку ax ≡ 1 (mod m). Пример 3.7.3. Найдем число a −1 при a = 9, m = 23. По алгоритму Евклида имеем 23 = 9 · 2 + 5, 9 = 5 · 1 + 4, 5 = 4 · 1 + 1. Тогда 1 = 5 · 1 − 4 · 1 = = 5−(9−5·1) = 5·2−9·1 = (23−9·2)·2−9·1 = (−5)·9+23·2. Следовательно, класс a −1 содержит число −5. При рассмотрении симметричной системы остатков это число берется в качестве числа 9 −1 . Если же рассматривается неотрицательная система остатков, в качестве числа 9 −1 нужно взять −5 + m = −5 + 23 = 18. Таким образом, 9 −1 ≡ 18 (mod 23). ¤ 102 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ 2. Использование малой теоремы Ферма Следующий способ нахождения обратного числа основан на малой тео- реме Ферма. Теорема 3.7.4 (малая теорема Ферма). Если m — простое число и a — произвольное целое число, не делящееся на m, то a m−1 ≡ 1 (mod m). ¤ Из соотношения a · a m−2 = a m−1 ≡ 1 (mod m) получаем Следствие 3.7.5. Если m — простое число, то в кольце Z m выполня- ется равенство a −1 = a m−2 . ¤ Пример 3.7.4. Если a = 2, m = 5, то 2 −1 ≡ 2 5−2 (mod 5) ≡ 8 (mod 5) ≡ 3 (mod 5). Тогда 2 −1 = 3. ¤ Следующий метод, называемым бинарным, позволяет более эффективно использовать малую теорему Ферма, поскольку с его помощью ускоряется процесс возведения данного числа в степень. Этот метод работает следу- ющим образом. Предположим, требуется вычислить число a k . Запишем k в двоичной системе счисления, опустив нули перед первой значащей циф- рой: k = n−1 P i=0 k i 2 i . Заменим каждую цифру 1 на пару букв SM a и каждую цифру 0 на букву S; после этого вычеркнем пару букв SM a слева. Получив- шаяся последовательность букв представляет собой правило для вычисле- ния a k , если интерпретировать S как “возвести в квадрат и взять остаток по модулю m”, а M a как “умножить на a и взять остаток по модулю m”. Пример 3.7.5. В Z 11 для нахождения 4 −1 (mod 11) нужно вычислить 4 9 , причем двоичное представление 9 равно 1001. Образуем последовательность SM 4 SSSM 4 и, вычеркнув левые SM 4 , получим последовательность SSSM 4 , которая означает “возвести в квадрат, возвести в квадрат, возвести в квадрат и умножить на 4”, выполняя все эти операции по модулю 11: 4 9 = ((4 2 ) 2 ) 2 · 4. Проводя последовательно вычисления в Z 11 , получим 4 2 = 5, 4 4 = 5 2 = 3, 4 9 = (4 4 ) 2 · 4 = (3 2 ) · 4 = 9 · 4 = 3. Следовательно, 4 −1 ≡ 3 (mod 11), т. е. 4 −1 = 3 в Z 11 . ¤ 3.8. ЛИНЕЙНЫЕ УРАВНЕНИЯ ПО МОДУЛЮ m 103 § 3.8. Линейные уравнения по модулю m. Китайская теорема об остатках Теорема 3.8.1. Уравнение ax ≡ b (mod m) тогда и только тогда име- ет решение, когда (a, m) | b. Если решение существует, то оно единственно по модулю m/d, где d = (a, m), и уравнение имеет d решений по модулю m. Доказательство. Целое число x удовлетворяет уравнению ax ≡ b (mod m) тогда и только тогда, когда существует целое число y такое, что ax + my = b. По теореме 3.5.3 уравнение ax + my = b разрешимо тогда и только тогда, когда (a, m) | b. Для доказательства второй части теоремы предположим, что x удовлетворяет условию ax ≡ b (mod m), и пусть z срав- нимо с x по модулю m/d. Тогда z = x + w(m/d) для некоторого w ∈ Z, az = ax + aw(m/d) = ax + mw(a/d) ≡ ax ≡ b (mod m). Таким образом, az ≡ b (mod m). Напротив, если ax ≡ az ≡ b (mod m), то ax − az ≡ b − b ≡ 0 (mod m), и значит, m | a(x − z). Тогда m/d делит x − z, и следовательно, x ≡ z (mod m/d). ¤ Пример 3.8.1. Найдем решение уравнения 270x ≡ 36 (mod 342). По ал- горитму Евклида получим (−5) · 270 + 4 · 342 = 18 = (270, 342) и 18 | 36. По теореме 3.8.1 существует единственное решение данного уравнения по мо- дулю 19 = 342/18. Для нахождения этого решения умножим равенство (−5) · 270 + 4 · 342 = 18 на 2 = 36/18 и получим (−10) · 270 + 8 · 342 = 36, откуда следует, что (−10) — одно из решений уравнения по модулю 342. Так как 9 ≡ −10 (mod 19), то 9 — единственное решение по модулю 19. Общее решение уравнения представляется в виде x = 9 + 19k. ¤ Частным случаем теоремы 3.8.1 является Следствие 3.8.2. Уравнение ax ≡ 1 (mod m) тогда и только тогда имеет решение, когда (a, m) = 1. Решение a −1 (mod m) единственно по мо- дулю m и является обратным к a элементом по модулю m. ¤ Пример 3.8.2. Уравнение 2x ≡ 1 (mod 26) не имеет решений, поскольку (2, 26) = 2. ¤ Рассмотрим теперь задачу решения системы линейных уравнений по мо- дулю некоторого числа m. При этом возникает изоморфизм кольца Z M и декартова произведения колец Z m 1 , Z m 2 , . . ., Z m k , где M = m 1 m 2 . . . m k , (m i , m j ) = 1, i 6= j. Прежде чем формулировать изоморфизм в общем случае, рассмотрим следующий 104 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ Пример 3.8.3. Кольцо Z 6 изоморфно декартову произведению колец Z 2 и Z 3 : Z 6 ∼ = Z 2 × Z 3 , M = 6, m 1 = 2, m 2 = 3. Шести элементам кольца Z 6 со- ответствуют пары (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2). Арифметическим опе- рациям в Z 6 соответствуют операции над парами, выполняемые покоорди- натно: (x 1 , x 2 ) + (y 1 , y 2 ) = (x 1 + y 1 , x 2 + y 2 ), (x 1 , x 2 ) · (y 1 , y 2 ) = (x 1 · y 1 , x 2 · y 2 ). Например, (0, 2)·(1, 2) = (0, 1), где умножение 0·1 выполняется по модулю 2, а умножение 2 · 2 — по модулю 3. ¤ Теорема 3.8.3 (китайская теорема об остатках). Пусть m 1 , m 2 , . . . , m k — попарно взаимно простые целые числа больше 1, M = m 1 m 2 . . . m k ; a 1 , a 2 , . . . , a k — целые числа, 0 6 a i < m i , i ∈ {1, 2, . . . , k}. Тогда существует единственное неотрицательное решение по модулю M следующей системы уравнений: x ≡ a 1 (mod m 1 ), x ≡ a 2 (mod m 2 ), . . . , x ≡ a k (mod m k ). Отображение, которое каждому целому числу x (0 6 x 6 M − 1) ставит в соответствие строку (a 1 , a 2 , . . . , a k ), где x ≡ a i (mod m i ) (i = 1, 2, . . . , k), является изоморфизмом кольца Z M на кольцо Z m 1 × Z m 2 × . . . × Z m k . Доказательство. Нужно найти число x (0 6 x 6 M − 1), удовле- творяющее всем сравнениям x ≡ a i (mod m i ), i = 1, 2, . . . , k. Будем решать уравнения по два одновременно. Рассмотрим сначала первые два сравне- ния. Первое сравнение x ≡ a 1 (mod m 1 ) справедливо для всякого x вида x = a 1 + m 1 q, q ∈ Z. Для нахождения q подставим значение x во второе сравнение x ≡ a 2 (mod m 2 ). Имеем x = a 1 + m 1 q ≡ a 2 (mod m 2 ), откуда q ≡ (m 1 ) −1 (a 2 − a 1 ) (mod m 2 ). Таким образом, q = (m 1 ) −1 (a 2 − a 1 ) + rm 2 для некоторого r. Подставив значение q в выражение x = a 1 + m 1 q, получим, что решение x первых двух уравнений представляется в виде x = a 12 + r(m 1 m 2 ) для некоторого r. Теперь первые два сравнения можно заменить на од- но сравнение x ≡ a 12 (mod m 1 m 2 ). Применим описанную выше процедуру к сравнению x ≡ a 12 (mod m 1 m 2 ) и сравнению, которое первоначально было третьим, и будем повторять этот процесс, пока не найдем число x, удовле- творяющее всем сравнениям. Для доказательства единственности предположим, что существует x 0 (0 6 x 0 6 M − 1) такой, что x 0 ≡ a i (mod m i ) для любого i. Тогда x − x 0 ≡ 0 (mod m i ) для всех i, откуда следует, что m i | (x − x 0 ) для любого i. Тогда M | (x − x 0 ) и, поскольку |x − x 0 | < M , x = x 0 . ¤ 3.8. ЛИНЕЙНЫЕ УРАВНЕНИЯ ПО МОДУЛЮ m 105 Пример 3.8.4. Решим систему уравнений x ≡ 1 (mod 2), x ≡ 2 (mod 5), x ≡ 5 (mod 7). Из первого уравнения следует, что x = 1+2q. Чтобы вычислить q, подста- вим x во второе уравнение: 1 + 2q ≡ 2 (mod 5) или 2q ≡ (2 − 1) (mod 5). Так как 2 −1 ≡ 3 (mod 5), то q ≡ 2 −1 (2 − 1) (mod 5) ≡ 3 (mod 5) или q = 3 + 5r для некоторого r. Следовательно, решением первых двух уравнений явля- ется x = 1 + 2(3 + 5r) = 7 + 2 · 5r, т. е. x ≡ 7 (mod 2 · 5). Осталось решить систему уравнений x ≡ 7 (mod 2 · 5) и x ≡ 5 (mod 7). Имеем x = 7 + 2 · 5q ≡ 5 (mod 7) или 2 · 5q ≡ (5 − 7) ≡ −2 ≡ 5 (mod 7). Так как 10 −1 ≡ 3 −1 ≡ 5 (mod 7), то q ≡ 5 · 5 (mod 7) ≡ 4 (mod 7) или q = 4 + 7r для некоторого r. Следовательно, решением трех уравнений является число x = 7 + 2 · 5(4 + 7r) или x ≡ 47 (mod 2 · 5 · 7). Отметим, что 47 = 1 + 3 · (2) + 4 · (2 · 5), где коэффициенты 3 и 4 являются значениями q. Заметим также, что при изоморфизме Z 2·5·7 ∼ = Z 2 × Z 5 × Z 7 число 47 соответствует данной тройке (1, 2, 5). ¤ В общем случае решение системы k уравнений x ≡ a 1 (mod m 1 ), x ≡ a 2 (mod m 2 ), . . . , x ≡ a k (mod m k ) представляется в виде x = q 1 + q 2 · m 1 + q 3 · (m 1 · m 2 ) + . . . + q k · (m 1 · m 2 · . . . · m k−1 ), где 0 6 q i < |m i |, q 1 — остаток от деления a 1 на m 1 Опишем применение китайского алгоритма к задаче о безопасном хране- нии ключа. Пусть K ∈ Z — ключ, который необходимо сохранить. При этом требуется, чтобы любые L человек из тех k (k > L), которые получили ин- формацию о ключе, могли бы вместе восстановить ключ, но ни одна группа из L − 1 человек или менее не могла этого сделать. Для решения этой задачи выберем такое множество целых чисел {p, d 1 , d 2 , . . . , d k }, что: 1) p > K; 2) d 1 < d 2 < . . . < d k ; 3) числа p, d 1 , d 2 , . . . , d k попарно взаимно просты; 4) d 1 · d 2 · . . . · d k > p · d k−L+2 · d k−L+3 · . . . · d k Пункт 4 означает, что произведение L наименьших чисел d i больше, чем произведение p и L − 1 наибольших чисел d i . Положим D d 1 · d 2 · . . . · d |