Расин, Алгебра

(9) снизу вверх начиная с предпоследнего равенства. Перемещаясь по равенствам, мы всякий раз будем находится в одной и той же ситуации: rk делит каждое из слагаемых в правой части данного равенства, а потому делит его левую часть. Тем самым мы получим, что rk поочередно делит rk−2, rk−3,. . . , r2, r1, n, m.

Пусть теперь c – некоторый общий делитель чисел m, n. Начнем перемещаться по равенствам (9) сверху вниз. Последовательно получаем, что c |r1, c |r2,. . . ,c |rk−1, c |rk. Тем самым доказано, что rk = (m, n).

В качестве примера применим алгоритм Евклида для отыскания наибольшего общего делителя чисел 5967 и 689. Имеем

5967 = 8 · 689 + 455,

689 = 1 · 455 + 234,

455 = 1 · 234 + 221,

234 = 1 · 221 + 13,

221 = 17 · 13.

Следовательно, наибольший общий делитель чисел 5967 и 689 равен 13.

3.7.Простые числа. Теорема Евклида

Вэтом разделе мы вернемся к изучению свойств натуральных чисел. Здесь мы сформулируем несколько важных свойств простых чисел и докажем знаменитую теорему Евклида о бесконечности множества всех простых чисел.

О п р е д е л е н и е. Натуральное число p > 1 называется простым, если для любого натурального числа n из соотношения n |p следует, что n = 1 или n = p.

Таким образом, простое число p имеет в точности два натуральных делителя – 1 и p.

Предложение 3.4. Пусть p – простое число. Тогда для любого n Z либо p делит n, либо p и n взаимно просты.

Д о к а з а т е л ь с т в о. Пусть d = (p, n). Тогда d | p и потому d = p или d = 1. Если d = p, то p |n, если же d = 1, то (p, n) = 1.

50

Предложение 3.5. Любое натуральное число n > 1 имеет простой делитель.

Д о к а з а т е л ь с т в о. Пусть D = {q | q > 1 и q | n}. Ясно, что D – непустое множество натуральных чисел. В силу теоремы 2.1 множество D имеет наименьший элемент p. Проверим, что p – простое число. Пусть s | p и s > 1. Так как p D, имеем p | n. Стало быть, s | n, откуда следует включение s D. Поскольку s 6 p и p – наименьший элемент D, получаем равенство s = p.

Обозначим через P множество всех простых чисел. Свойства множества P интересовали еще математиков Древней Греции. Одним из первых утверждений о свойствах этого множества является следующая теорема, называемая теоремой Евклида.

Теорема 3.4. Множество P бесконечно.

Д о к а з а т е л ь с т в о. Проверим, что для любого натурального числа n > 1 существует простое число p, большее чем n. Пусть m = n! + 1 (через n!, как обычно, обозначено произведение всех натуральных чисел от 1 до n включительно). Ясно, что m > 1; поэтому найдется простое число p, делящее m. Предположим, что p 6 n. Тогда, очевидно, p | n!. Стало быть, p является общим делителем чисел n! и m = n! + 1. Мы получили противоречие с тем, что эти числа взаимно просты.

Замечание. На самом деле мы доказали, что множество всех простых чисел не является ограниченным сверху. Представляется правдоподобным, что неограниченное сверху множество натуральных чисел бесконечно. Правда, у внимательного читателя может возникнуть вопрос: а что такое бесконечное множество ? Ответ на этот вопрос не так прост, как может показаться; к его обсуждению мы еще вернемся.

3.8. Теорема о каноническом представлении

Предложение 3.6. Любое натуральное число n > 1 можно представить в виде произведения простых чисел; такое представление единственно с точностью до перестановки сомножителей.

51

Д о к а з а т е л ь с т в о. Заметим сразу, что предложение очевидным образом выполнено для простых чисел: каждое простое число представляется в виде произведения, состоящего из единственного сомножителя – себя самого.

Для доказательства предложения применим метод математической индукции. При n = 2 данное утверждение, разумеется, выполнено, поскольку 2 – простое число.

Пусть n = k > 2 и для всех натуральных чисел, меньших k, утверждение выполняется. В силу сделанного выше замечания можно считать, что k – составное число. Пусть p1 – простой делитель числа k. Тогда k = p1k1, причем 1 < k1 < k. Применяя предположение индукции, получаем, что

k1 = p2p3 . . . ps,

где p2, p3, . . . , ps – некоторые простые числа. Отсюда следует, что

k = p1p2p3 . . . ps.

Таким образом, установлена возможность разложения числа k на простые множители.

Убедимся теперь, что такое разложение числа k единственно с точностью до перестановки сомножителей. Пусть

k = p1p2 . . . ps и k = q1q2 . . . qt,

где p1, p2, . . . ps, q1, q2, . . . , qt – некоторые простые числа. Поскольку k – составное число, в каждом из двух разложений этого числа содержится не менее двух сомножителей, т. е. s, t > 2. Убедимся, что s = t и два указанных выше разложения числа k состоят из одних и тех же сомножителей (возможно, различающихся порядком этих сомножителей). Из равенства

следует, что простое число p1 делит произведение q1q2 . . . qt. Отсюда вытекает, что p1 не является взаимно простым с одним из сомножителей q1, q2, . . . , qt. Без ограничения общности можно считать, что p1 не является взаимно простым с q1. Тогда p1 делит

52

простое число q1 и, следовательно, p1 = q1 Поделив обе части равенства (10) на p1, получим

p2 . . . ps = q2 . . . qt = m.

Так как 1 < m < k, к числу m применимо предположение индукции. В частности, это означает, что разложение числа m на простые множители единственно с точностью до перестановки сомножителей. Следовательно, s − 1 = t − 1, откуда s = t. Кроме того, k = p1m = q1m, и потому единственность разложения k на простые множители доказана.

В полученном нами разложении натурального числа на простые множители некоторые из множителей могут совпадать. Ясно, произведения совпадающих множителей можно заменить степенями. Таким образом, из предложения 3.6 вытекает утверждение, называемое теоремой о каноническом представлении.

Теорема 3.5. Пусть n – произвольное натуральное число, большее чем 1. Тогда n можно представить в виде произведения натуральных степеней различных простых чисел; такое представление единственно с точностью до перестановки сомножителей.

3.9. Сравнения

Продолжим изучение свойств целых чисел. Пусть n – натуральное число и n > 1.

О п р е д е л е н и е. Целые числа a, b сравнимы по модулю n, если n |a − b.

Сравнимость чисел a, b по модулю n будет обозначаться одним из двух способов: a ≡ b (mod n) или a ≡n b; каждая из этих записей называется сравнением по модулю n.

Таким образом, для каждого натурального n > 1 на множестве Z определено отношение сравнимости по модулю n.

Свойства сравнений.

(С1) a ≡ a (mod n);

(C2) a ≡ b (mod n) b ≡ a (mod n);

53

(C3) a ≡ b (mod n) и b ≡ c (mod n) a ≡ c (mod n);

(C4) a ≡ b (mod n) и c ≡ d (mod n) a + c ≡ b + d (mod n); (C5) a ≡ b (mod n) и c ≡ d (mod n) ac ≡ bd (mod n); (C6) a ≡ b (mod n) am ≡ bm (mod nm), m Z, m 6= 0; (C7) если (m, n) = 1, то ma ≡ mb (mod n) a ≡ b (mod n).

Эти свойства легко получаются из определения сравнимости по модулю n.

Непосредственно проверяется и следующее утверждение.

Предложение 3.7. Целые числа a, b сравнимы по модулю n тогда и только тогда, когда остатки от деления чисел a, b на

nсовпадают.

Оп р е д е л е н и е. Пусть A – n-элементное множество. Будем говорить, что A – полная система вычетов по модулю n, если элементы из A попарно несравнимы по модулю n.

Важным примером полной системы вычетов является множество Zn = {0, 1, 2, . . . , n − 1}.

Теорема 3.6. Пусть A = {a1, a2, . . . , an} – полная система вычетов по модулю n, m – целое число, взаимно простое с n, d

– произвольное целое число. Тогда множество

M = {ma + d | a A}

также является полной системой вычетов по модулю n.

Д о к а з а т е л ь с т в о. Достаточно проверить, что числа из M попарно несравнимы по модулю n. Предположим, что при 1 6 6 i < j 6 n выполнено соотношение mai + d ≡ maj + d (mod n). Отсюда следует, что n |m(ai −aj ). Так как m и n взаимно просты, имеем n | ai − aj , т. е. ai ≡ aj (mod n). Полученное соотношение противоречит определению полной системы вычетов.

3.10. Кольцо вычетов по модулю n

В предыдущем разделе было введено множество

Zn = {0, 1, 2, . . . , n − 1}.

54

Определим на этом множестве операции сложения и умножения. Временно обозначим через [a]n остаток от деления a на n.

Пусть a, b – произвольные числа из Zn. Положим a b = = [a + b]n и a b = [a · b]n.

Прежде чем изучать свойства этих операций при произвольном n, рассмотрим конкретный пример. А именно, построим таблицы сложения и умножения для случая n = 6.

Обратим внимание читателя на таблицу умножения. Из нее видно, что в Z6 есть отличные от нуля числа, произведение которых равно нулю (например, 3 4 = 0). Такие числа называются

делителями нуля.

Чтобы получить свойства операции сложения и операции умножения , докажем следующее вспомогательное утверждение.

Лемма 1. Пусть a, b Z. Тогда [a + b]n = [a + [b]n]n и [a ·b]n =

=[a · [b]n]n

До к а з а т е л ь с т в о. Разность (a + b) − (a + [b]n) равна b − [b]n и потому делится на n. Из предложения 3.7 следует, что остат-

ки [a + b]n и [a + [b]n]n совпадают. Второе равенство проверяется аналогично.

Теорема 3.7. Множество Zn относительно операций и является коммутативным кольцом с единицей.

Д о к а з а т е л ь с т в о. Проверим, что относительно операции сложения множество Zn является абелевой группой. Коммутативность сложения сразу вытекает из коммутативности сложения на множестве Z. Проверим ассоциативность сложения, т. е. докажем, что

a (b c) = (a b) c.

55

Используя лемму 1, имеем

a (b c) = [a + [b + c]n]n = [a + (b + c)]n,

(a b) c = [c + [a + b]n]n = [c + (a + b)]n.

Таким образом, ассоциативность операции вытекает из ассоциативности и коммутативности сложения на множестве Z.

Далее, нетрудно понять, что нейтральным элементом для операции является число 0.

Осталось проверить, что каждый элемент a Zn имеет противоположный a. Если a = 0, то a = 0. Пусть a 6= 0. Тогда

a = n − a.

Ассоциативность и коммутативность умножения, а также то, что 1 является нейтральным элементом относительно умножения, проверяется аналогично.

Проверку закона дистрибутивности мы также оставляем читателю.

Продолжим изучение операции умножения в кольце Zn. Из рассмотренного выше примера (кольцо Z6) видно, что множество ненулевых элементов такого кольца может быть не замкнуто относительно умножения. Выделим в Zn подмножество Zn, состоящее из ненулевых элементов и замкнутое относительно умножения.

Пусть Zn = {k | k Zn и (k, n) = 1}. Иными словами, Zn состоит из всех элементов кольца Zn, взаимно простых с n.

Теорема 3.8. Множество Zn относительно операции является абелевой группой.

При доказательстве этой теоремы удобно воспользоваться следующим утверждением.

Предложение 3.8. Для любого a Zn множество

M == {a k | k Zn}

совпадает с Zn

Д о к а з а т е л ь с т в о. Пусть k – произвольный элемент из Zn. Поскольку a, k взаимно просты с n, их произведение ak также

56

взаимно просто с n. Заметим теперь, что n | ak − [ak]n. Отсюда немедленно вытекает, что a k = [ak]n также взаимно просто с n и потому принадлежит Zn. Это рассуждение показывает, что

M Zn.

Пусть теперь k1, k2 – различные элементы из Zn. Проверим, что элементы a k1 и a k2 также различны. Предположим, что a k1 = a k2; отсюда следует, что n |a(k1 − k2). Поскольку n и a взаимно просты, имеем n |k1 − k2. Последнее соотношение выполняться не может, так как 0 < |k1 − k2| < n. Тем самым доказано, что множества M и Zn имеют одно и то же число элементов. Но

MZn, поэтому M = Zn.

До к а з а т е л ь с т в о теоремы 3.8. Из предложения 3.8 следует

замкнутость множества Zn относительно умножения , а из теоремы 3.7 вытекает его ассоциативность и коммутативность. Легко понять, что 1 Zn. Осталось проверить, что для любого a Zn найдется такой b Zn, что a b = 1. Применяя предложение 3.8, мы видим, что умножая элемент a поочередно на элементы из Zn, можно получить все элементы этого множества. Так как 1 Zn, то для некоторого b Zn получим a b = 1.

Начиная с этого места сложение и умножение в кольце вычетов мы будем обозначать обычными символами “+” и “·”. Из контекста всегда будет понятно, идет речь об операциях в кольце Z или в кольце Zn.

Пусть p – простое число. Поскольку все числа 1, 2, . . . , p − 1 в этом случае взаимно просты с p, множество Zp = {1, 2, . . . , p − 1} относительно умножения является абелевой группой.

Кольцо с единицей, в котором множество ненулевых элементов относительно операции умножения образует абелеву группу, называется полем.

Таким образом, при простом p кольцо Zp является полем. Это утверждение имеет многочисленные следствия. Остановися лишь на одном из них.

Теорема 3.9. Число p > 1 является простым тогда и только тогда, когда p |(p − 1)! + 1

57

Д о к а з а т е л ь с т в о. Пусть p – простое число. Докажем, что

Если p = 2 или p = 3, то выполнение соотношения (11) очевидно. Поэтому можно считать, что p > 5. Поскольку Zp – поле, для каждого числа x Zp существует такое y Zp, что в Zp выполнено равенство xy = 1. В кольце Z этому равенству отвечает сравнение

Может оказаться, что для некоторых x, 0 6 x 6 p − 1, выполнено равенство y = x. Найдем все такие x. Если x2 ≡ 1 (mod p), то p | x2 − 1, откуда p | (x − 1)(x + 1). Так как p – простое число, имеем p |(x − 1) или p |(x + 1). В первом случае имеем равенство x = 1, во втором – равенство x = p − 1. Из доказанного следует, что множество {2, 3, . . . , p − 2} разбивается на такие пары, что произведение чисел, входящих в каждую пару, сравнимо с 1 по модулю p. Поэтому

Из равенства (13) немедленно вытекает, что

(p − 1)! = 1 · (p − 1) · 2 · 3 · . . . · (p − 2) ≡p p − 1 ≡p −1.

Стало быть, p |(p − 1)! + 1.

Проверим обратное утверждение. Пусть p > 1 и p удовлетворяет соотношению (11). Рассуждая “от противного”, допустим, что p – составное число. Тогда существует такое q, что 1 < q 6 p − 1 и q | p. Ясно, что q | (p − 1)! и q | (p − 1)! + 1. Но тогда q | 1, что невозможно. Полученное противоречие доказывает простоту числа p.

Теорему 3.9 часто называют теоремой Вильсона.

3.11. Малая теорема Ферма. Теорема Эйлера

Теорема 3.10. Если p – простое число и натуральное число a взаимно просто с p, то ap−1 ≡ 1 (mod p).

58

Д о к а з а т е л ь с т в о. Пусть r1, r2, . . . , rp−1 – остатки от деления чисел 1 · a, 2 · a, . . . ,(p − 1) · a на p. Ясно, что эти остатки попарно различны, и каждый из них отличен от нуля. Поэтому

В силу равенства (14) имеем (p − 1)! = r1r2 . . . rp−1. Заметим теперь, что числа (p−1)! и p взаимно просты. Поэтому сокращая обе части сравнения (15) на число (p−1)!, взаимно простое с модулем, получим ap−1 ≡ 1 (mod p).

Это утверждение называется малой теоремой Ферма1. Обобщением этой теоремы является теорема Эйлера2. В формулировке теоремы Эйлера используется функция натурального аргумента, называемая функцией Эйлера.

Для натурального числа n > 1 обозначим через ϕ(n) количество натуральных чисел, меньших чем n и взаимно простых с n. Если n = 1, то положим ϕ(1) = 1. Вспоминая определение множества Zn, мы видим, что при n > 1 число элементов в Zn равно

ϕ(n).

Таким образом, функция ϕ определена на множестве всех натуральных чисел; эта функция и называется функцией Эйлера.

Теорема 3.11. Если a и n – натуральные числа, причем n взаимно просто с a и n > 1, то aϕ(n) ≡ 1 (mod n).

Д о к а з а т е л ь с т в о. Пусть k = ϕ(n). Рассмотрим множество Zn = {z1, z2, . . . , zk}. Пусть u1, u2, . . . , uk – остатки от деления на n чисел az1, az2, . . . , azk. Числа u1, u2, . . . , uk попарно различны, и

каждое из них взаимно просто с n. Поэтому Zn = {u1, u2, . . . , uk}.

1П.Ферма (1601–1665) – выдающийся французский математик, один из основоположников математического анализа и теории вероятностей.

2Л.Эйлер (1707–1783) – выдающийся российский математик, один из крупнейших математиков восемнадцатого столетия. Известен своими работами по алгебре, теории чисел, математическому анализу, теоретической механике.

59