Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf

98
Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ
Имея такие разложения, легко находить НОД и НОК целых чисел: если
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. ¤

3.7. ЦЕЛЫЕ ЧИСЛА ПО МОДУЛЮ m
99
Приведенный алгоритм достаточно трудоемок и может использоваться для нахождения сравнительно небольшого числа простых чисел. Более эф- фективные методы можно найти в специальной литературе, например в кни- ге А. Акритаса [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.

100
Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ
В получающейся таким образом алгебре 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 называется остаток от деления числа

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
. ¤