Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
Целое число p > 1 тогда и только тогда являет- ся простым, когда оно неразложимо. ¤ Следующая теорема называется основной теоремой арифметики. Теорема 3.6.3 (единственность неприводимого разложения). Всякое це- лое число a 6= 0, ±1 может быть записано как ± произведение простых чисел единственным способом с точностью до порядка сомножителей. Доказательство. Предположим, что положительное целое число a имеет два неприводимых разложения: a = u 1 · . . . · u r = v 1 · . . . · v s , где u i , v j — простые числа. Имеем u 1 | v 1 · . . . · v s и, так как u 1 просто, u 1 | v j 1 для некоторого j 1 . Поскольку v j 1 не имеет нетривиальных делителей, u 1 = v j 1 Продолжая процесс, получаем, что u 2 делит произведение оставшихся со- множителей v j и, следовательно, u 2 = v j 2 для некоторого j 2 и т. д. В конце концов получим, что r = s и после некоторого переупорядочивания u i = v i для всех i. ¤ Пример 3.6.2. Покажем, что существует коммутативное кольцо, для которого не выполняется теорема о единственности неприводимого разложения. Рассмотрим множество всех положительных четных чисел 2Z + {2k | k ∈ Z и k > 0} с обычными операциями сложения и умножения: h2Z + ; +, ·i. В этой алгебре число 8 является разложимым, поскольку 8 = 2·4, а число 14 — неразложимым, поскольку оно не является произведением двух или более чисел из 2Z + . Число 60 имеет два неприводимых разложения: 60 = 2 · 30 = 6 · 10. ¤ Из основной теоремы арифметики следует однозначность (с точностью до порядка сомножителей) разложения произвольного целого числа a / ∈ {−1, 0, 1} в произведение степеней простых чисел: a = ±p e 1 1 p e 2 2 · . . . · p e k k , где p i — различные простые числа, e i — натуральные числа. 3.6. РАЗЛОЖЕНИЕ ЦЕЛЫХ ЧИСЕЛ НА МНОЖИТЕЛИ 101 Имея такие разложения, легко находить НОД и НОК целых чисел: если a = ±p e 1 1 p e 2 2 · . . . · p e k k и b = p f 1 1 p f 2 2 · . . . · p f k k , e i , f i > 0, то НОД(a, b) = p min{e 1 ,f 1 } 1 p min{e 2 ,f 2 } 2 · . . . · p min{e k ,f k } k , НОК(a, b) = p max{e 1 ,f 1 } 1 p max{e 2 ,f 2 } 2 · . . . · p max{e k ,f k } k . Теорема 3.6.4. Множество простых чисел бесконечно. Доказательство. Предположим противное. Пусть существует лишь конечное число простых чисел p 1 , p 2 , . . . , p m . Рассмотрим число n = p 1 ·p 2 ·. . .·p m +1, которое либо является простым, и тогда оно будет новым простым числом, либо имеет простой сомножитель p. Если p является одним из перечисленных простых чисел p i , то p делит произведение p 1 · p 2 · . . . · p m и, поскольку p делит n = p 1 · p 2 · . . . · p m + 1, оно делит также и разность этих чисел, т. е. единицу, что невозможно. Следовательно, p является новым про- стым числом, т. е. имеет место противоречие с предположением конечности множества простых чисел. ¤ Опишем алгоритм нахождения всех простых чисел, не превосходящих заданного целого числа, с помощью решета Эратосфена. Запишем по по- рядку все целые числа от 2 до n. Затем вычеркнем все четные числа, кроме 2, поскольку они делятся на 2 и потому не являются простыми. После этого вычеркнем все числа, кратные 3, и т. д. После i-го прохода будут вычеркну- ты все числа, которые делятся на первые i простых чисел p 1 , . . . , p i . Первое число x > p i , которое останется невычеркнутым, будет (i + 1)-м простым числом. Затем будут вычеркнуты все числа, кратные p i . Процесс вычерки- вания заканчивается при p i > √ n, так как у любого составного числа 6 n есть простой делитель 6 √ n. Пример 3.6.3. Найдем все простые числа 6 60. В исходный список включим нечетные числа больше 2: 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59. Числа, кратные 3, > 3 2 , подчеркнуты одной чертой, кратные 5, > 5 2 , — двумя, кратные 7, > 7 2 , — тремя. Для следующего простого числа 11 выпол- няется неравенство 11 2 > 60, поэтому все неподчеркнутые числа являются простыми 6 60. ¤ 102 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ Приведенный алгоритм достаточно трудоемок и может использоваться для нахождения сравнительно небольшого числа простых чисел. Более эф- фективные методы можно найти в специальной литературе, например в кни- ге А. Акритаса [1]. Из этой книги заимствован дальнейший материал насто- ящей главы. § 3.7. Целые числа по модулю m Рассмотрим кольцо целых чисел hZ; +, ·i. Зафиксируем целое число m > 1 и зададим отношение эквивалентности ≡ m на множестве Z по следу- ющему правилу: b ≡ m a ⇔ b − a = m · q для некоторого q ∈ Z. Класс эквивалентности элемента a — это множество {a + m · q | q ∈ Z} = = {. . . , −3m + a, −2m + a, −m + a, a, m + a, 2m + a, 3m + a, . . .}, которое обо- значается через a + mZ или просто a. Пример 3.7.1. Если m = 5, то 0 = {. . ., −10, −5, 0, 5, 10, . . .}, 1 = {. . ., −9, −4, 1, 6, 11, . . .} и т. д. Таким образом, множество Z разби- вается на непересекающиеся подмножества 0, 1, 2, 3, 4, и фактор-множество есть Z/ ≡ 5 = {0, 1, 2, 3, 4}. Заметим, что, хотя каждый класс эквивалентности содержит бесконечно много элементов, множество классов эквивалентности содержит всего пять элементов. ¤ В общем случае множество Z/ ≡ m = {0, 1, . . . , m − 1} содержит m элемен- тов. Вместо записи b ≡ m a будем также использовать запись b ≡ a (mod m), которая читается “b равно a по модулю m” или “b сравнимо с a по модулю m”. Множество Z/ ≡ m обозначается также через Z m и называется множеством вычетов или множеством целых чисел по модулю m. Доказательство следующего утверждения оставляется читателю в каче- стве упражнения. Лемма 3.7.1. Отношение ≡ m является конгруэнцией на алгебре hZ; +, ·i. ¤ Из этой леммы следует, что на множестве Z m можно корректно опреде- лить операции сложения и умножения по правилам: a+b a + b, a·b a · b. 3.7. ЦЕЛЫЕ ЧИСЛА ПО МОДУЛЮ m 103 В получающейся таким образом алгебре hZ m ; +, ·i выполняются все аксиомы коммутативного кольца с единицей. Например, нулевым элементом является класс 0, единицей — 1, противоположным по отношению к a элементом — элемент −a m − a. Кольцо hZ m ; +, ·i называется кольцом вычетов по мо- дулю m. Арифметика целых чисел по модулю m может рассматриваться как ариф- метика остатков или модулярная арифметика. Полная система остатков по модулю m состоит из m целых чисел, по одному представителю из каж- дого класса эквивалентности. Чаще всего используются следующие две си- стемы: система неотрицательных остатков по модулю m, состоящая из чи- сел 0, 1, 2, . . . , m − 1, и система наименьших по абсолютной величине остат- ков, или симметричная система остатков, состоящая из чисел 0, ±1, ±2, . . . , ±(m − 1)/2 для нечетного m. В дальнейшем мы будем часто отождеств- лять классы с соответствующими остатками, а арифметические операции + и · выполнять по следующим правилам: суммой a + b остатков a и b назы- вается остаток от деления числа a + b на m, произведением a · b остатков a и b называется остаток от деления числа 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 . ¤ 104 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ По теореме 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). ¤ 3.7. ЦЕЛЫЕ ЧИСЛА ПО МОДУЛЮ m 105 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 . ¤ 106 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ § 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). Таким образом, |