Дискретка. Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений
 Скачать 1.99 Mb.
|
|
r, а через q — соответствующее значение k. По определению имеем r = a − qb > 0. Для доказательства единственности допустим, что a = bq 1 + r 1 , 0 6 r 1 < |b|, r 1 6= r. Пусть для определенности r 1 < r, так что 0 < r − r 1 < |b|; тогда r − r 1 = (q 1 − q)b и b | (r − r 1 ), что противоречит неравенствам 0 < r − r 1 < |b|. ¤ Пусть a, b — целые числа, не равные нулю. Целое число d > 0 называет- ся наибольшим общим делителем чисел a и b при выполнении следующих условий: 1) d | a и d | b; 2) если c | a и c | b, то c | d. Наибольший общий делитель чисел a и b обозначается через (a, b) или НОД(a, b). Единственность НОД следует из условия 2 и того, что он по- ложителен. Например, (12, 30) = (12, −30) = (−12, 30) = (−12, −30) = 6. Наибольший общий делитель двух ненулевых целых чисел всегда су- ществует. Теорема 3.5.2. Если целые числа a и b не равны нулю, то существуют целые числа x и y такие, что (a, b) = ax + by. Доказательство. Пусть d — наименьшее положительное целое чис- ло вида ax + by, например, d = ax 0 + by 0 (такое число существует в силу полной упорядоченности множества hω; 6i). Очевидно, что d > 0 и d удо- влетворяет условию 2 из определения НОД. От противного докажем, что d удовлетворяет также условию 1. Допустим, что условие 1 не выполняется, и предположим для определенности, что d не делит b. Тогда b = dq + r, 0 < r < d, следовательно, r = b − dq = b − (ax 0 + by 0 )q = a(−qx 0 ) + b(1 − qy 0 ), что противоречит минимальности d. ¤ Числа x и y, указанные в теореме, определяются неоднозначно. Напри- мер, 6 = (12, −30) = 12 · 3 + (−30) · 1 = 12 · (−2) + (−30) · (−1). 3.5. ДЕЛИМОСТЬ В КОЛЬЦЕ ЦЕЛЫХ ЧИСЕЛ 95 Пользуясь понятием НОД, можно охарактеризовать целые решения ли- нейных уравнений от двух переменных (ax + by = c), которые называются линейными диофантовыми уравнениями. Теорема 3.5.3. Пусть ax + by = c — линейное диофантово уравнение, a, b 6= 0, d = (a, b). Тогда 1) уравнение разрешимо относительно x и y тогда и только тогда, когда d | c; 2) если (x 0 , y 0 ) — частное решение, то общее решение имеет вид (x 0 − n(b/d), y 0 + n(a/d)), n ∈ Z. Доказательство. 1. Предположим, что x и y — целые числа, такие, что ax + by = c. Так как d | a и d | b, то d | c. Предположим теперь, что d | c, т. е. c = dk для некоторого целого k. По теореме 3.5.2 существуют целые числа s, t такие, что d = as + bt. Умножая это равенство на k, получаем c = dk = a(sk) + b(tk), откуда следует, что x = sk и y = tk удовлетворяют уравнению ax + by = c. Доказательство п. 2 оставляется читателю в качестве упражнения. ¤ Пример 3.5.1. Уравнение 12x − 30y = 84 разрешимо, поскольку (12, −30) = 6 | 84. Частным решением является пара (x, y) = (2, −2), а общее решение имеет вид x = 2 + 5n, y = −2 + 2n. ¤ Два целых числа a и b называются взаимно простыми, если (a, b) = 1. По теореме 3.5.3 это эквивалентно существованию целых чисел s и t таких, что as + bt = 1. Теорема 3.5.4. Пусть a, b — ненулевые целые числа, d = (a, b). Тогда числа a/d и b/d взаимно просты. ¤ Пусть a, b — целые числа, не равные нулю. Целое число m > 0 называ- ется наименьшим общим кратным чисел a и b при выполнении следующих условий: 1) a | m и b | m; 2) если a | c и b | c, то m | c. Наименьшее общее кратное чисел a и b обозначается через [a, b] или НОК(a, b). Единственность НОК следует из условия 2 и положи- тельности m. Теорема 3.5.5. Если a, b — ненулевые целые числа, то существует их НОК и справедливо равенство [a, b] = |ab|/(a, b). ¤ 96 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ Теперь изложим классический алгоритм Евклида вычисления НОД двух целых чисел. Ключевым в этом алгоритме является следующий факт: если a = bq+r и d делит a и b, то d | r = a−bq. Поскольку это верно для любого де- лителя, это справедливо и для d =НОД(a, b), а значит, НОД(a, b) =НОД(b, r). Кроме того, НОД(a, 0) = |a| для всякого a. Условимся также считать, что НОД(0, 0) = 0. Итак, если заданы целое число a и ненулевое целое число b, выполняем последовательность делений: пусть a 0 = a и a 1 = b, тогда a 0 = a 1 q 1 + a 2 (0 < a 2 < |a 1 |), a 1 = a 2 q 2 + a 3 (0 < a 3 < a 2 ), ... a k−2 = a k−1 q k−1 + a k (0 < a k < a k−1 ), a k−1 = a k q k + 0. Указанный процесс рано или поздно останавливается, так как остатки a i образуют строго убывающую последовательность неотрицательных целых чисел и a k = (a k , 0) = . . . = (a 1 , a 2 ) = (a 0 , a 1 ). Пример 3.5.2. Проиллюстрируем работу алгоритма Евклида для чисел a = 342 и b = 612. Имеем (342, 612) = (612, 342) = (342, 270) = (270, 72) = (72, 54) = = (54, 18) = (18, 0). Таким образом, НОД(a, b) = 18. ¤ § 3.6. Разложение целых чисел на множители Целое число a / ∈ {−1, 0, 1} называется неразложимым, если все его де- лители тривиальны, т. е. равны ±1 и ±a. Например, неразложимы числа 13 и −7. Целое число a / ∈ {−1, 0, 1} называется разложимым или cоставным, если у него имеются нетривиальные делители, т. е. оно может быть записано в виде a = bc, где b и c не равны ±1 и ±a. Например, 276 = 12·23 — составное число. Делители также называются сомножителями. Если сомножители b и c разложимы, то они также могут быть записаны как произведения нетри- виальных сомножителей и т. д. Этот процесс рано или поздно обрывается, поскольку не существует бесконечной строго убывающей последовательно- сти положительных целых чисел. 3.6. РАЗЛОЖЕНИЕ ЦЕЛЫХ ЧИСЕЛ НА МНОЖИТЕЛИ 97 Теорема 3.6.1 (существование неприводимого разложения). Любое це- лое число a / ∈ {−1, 0, 1} может быть записано как ± произведение конечно- го числа положительных неразложимых целых чисел, т. е. a = ±u 1 ·. . .·u r , где u i > 1, i = 1, . . . , r, — неразложимые числа. ¤ Пример 3.6.1. 1008 = 2 · 2 · 2 · 2 · 3 · 3 · 7. ¤ Целое число p > 1 называется простым, если для любых a, b из p | ab следует p | a или p | b. Предложение 3.6.2. Целое число 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 — натуральные числа. 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 называется остаток от деления числа |