Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
−(P − 1) 6 m 6 P − 1, то целое число m называется коротким. Осталь- ные целые числа называются длинными. Длинные числа m представляются в виде списка m = (m 0 , m 1 , . . . , m k ), k > 1, где m i — короткие целые числа (|m i | 6 P − 1), являющиеся коэффициентами в выражении m = k P i=0 m i · P i и имеющие тот же знак, что и число m. При хранении числа m в виде списка информацию о знаке будем записывать только в m k Пример 3.4.1. Предположим, что P = 10 3 , т. е. компьютерное сло- во может содержать только три десятичные цифры. Представление числа m = +23456789 в виде списка выглядит следующим образом: m = (789, 456, +23). ¤ Рациональные числа r = m n представляются списками r = (m, n), где m, n — списки, представляющие целые числа m и n. 3. Классические алгоритмы целочисленной арифметики Рассмотрим классические алгоритмы выполнения арифметических опе- раций с длинными целыми числами. Пусть m = k P i=0 m i · P i и n = l P i=0 n i · P i — длинные целые числа, m = (m 0 , m 1 , . . . , m k ) и n = (n 0 , n 1 , . . . , n l ) — соот- ветствующие списки. При сложении списков m и n последовательно скла- дываются (с использованием встроенной в компьютер операции сложения) короткие целые числа, находящиеся в соответствующих координатах спис- ков, и при сложении координат учитываются переносы от меньших разрядов к большим аналогично сложению десятичных чисел. Полученный список s 3.4. СПИСОЧНОЕ ПРЕДСТАВЛЕНИЕ ЧИСЕЛ 95 называется суммой списков m и n: m + n. Точно так же, используя школь- ные алгоритмы целочисленного умножения, поразрядным перемножением коротких целых чисел с переносом от меньших разрядов к большим опреде- ляется произведение списков m и n: m · n. Предложение 3.4.1. Алгебра hZ; +, ·i изоморфна алгебре hZ; +, ·i, где Z — множество списков, задающих целые числа. ¤ При делении m на n ищутся целые числа q и r, обладающие свойством делимости с остатком: m = nq + r, 0 6 r < n. Для определения операции деления со списками достаточно описать случай, когда n 6 m < P n. Общий случай сводится к этому случаю аналогично тому, как к нему сво- дится общий случай деления столбиком. Пример 3.4.2. При делении 1234 на 23 сначала делится 123 (начальное число m) на 23 (число n): 123 = 23 · 5 + 8, затем 84 (новое число m) делится на 23: 84 = 23 · 3 + 15. Таким образом, имеем 1234 = (23 · 5 + 8) · 10 + 4 = = 23 · 50 + 84 = 23 · 50 + 23 · 3 + 15 = 23 · 53 + 15. ¤ Наиболее очевидный подход к решению состоит в угадывании частно- го q по наиболее значимым цифрам чисел m и n. Полученное таким путем частное называется пробным частным и обозначается через q t . Согласно нашим предположениям, m = m 0 + . . . + m k · P k , n = n 0 + . . . + n k−1 · P k−1 , n 6 m < P n. Обозначим через [x] целую часть числа x, т. е. наибольшее целое число, не превосходящее числа x. Положим q t ( P − 1, если m k = n k−1 , h m k P +m k−1 n k−1 i , если m k < n k−1 . Пример 3.4.3. Обозначим истинное частное через q. Тогда при P = 10 имеем: • если m = 600, n = 69, то m 2 = n 1 , а следовательно, q t = 9, в этом случае q = 8; • если m = 480, n = 59, то q t = [48/5] = 9, в этом случае q = 8; • если m = 200, n = 29, то m 2 = n 1 , поэтому q t = 9, в этом случае q = 6. ¤ Отметим, что во всех случаях q t слишком велико, однако при n = 69 уга- данное значение не так плохо, как при n = 29. Величина такого отклонения объясняется следующей теоремой. 96 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ Теорема 3.4.2. Если целые числа q t и q являются пробным частным и частным соответственно при делении m на n, то q t > q. Более того, если n k−1 > P/2, то q t − 2 6 q 6 q t , т. е. q t равно либо q, либо q + 1, либо q + 2. Доказательство. Из qn 6 m, используя неравенство m 0 + . . . + +m k−2 P k−2 < P k−1 , получаем, что qn k−1 P k−1 < (1 + m k−1 + m k P )P k−1 , сле- довательно, qn k−1 < m k−1 + m k P , где q 6 P − 1. Тогда из определения q t , очевидно, следует, что q t > q. Предположим теперь, что n > P/2. В этом случае достаточно показать, что (q t − 2)n 6 m. Используя неравенство n 0 + . . . + n k−2 · P k−2 < P k−1 , получаем (q t − 2)n < (q t − 2)(n k−1 + 1)P k−1 = (q t n 1 + (q t − 2 − 2n k−1 ))P k−1 6 6 (m k P + m k−1 )P k−1 + (q t − 2 − 2n k−1 )P k−1 по определению q t . Поскольку n k−1 > P/2 и q t 6 P − 1, имеем q t − 2 − 2n k−1 < 0, (m k P + m k−1 )P k−1 + (q t − 2 − 2n k−1 )P k−1 6 (m k P + m k−1 )P k−1 6 6 (m k P + m k−1 )P k−1 + m k−2 P k−2 + . . . + m 0 = m, что и требовалось доказать. ¤ Чтобы добиться выполнения условия, что старшая цифра делителя боль- ше либо равна P/2, нужно домножить m и n на 2 e , где 2 e — наибольшая степень 2, для которой 2 e · n < P k+1 . Затем делим 2 e · m на 2 e · n. Пример 3.4.4. Рассмотрим P = 10, m = 200, n = 29. Вычислим наибольшее число e, для которого 2 e · 29 < 1000. Получаем e = 5 и 2 e · m = 32 · 200 = 6400, 2 e · n = 32 · 29 = 928. Имеем q t = [64/9] = 7, что отличается от истинного частного q = 6 на единицу. ¤ После нахождения пробного частного q t достаточно выбрать истинное частное среди чисел q t , q t − 1, q t − 2. § 3.5. Делимость в кольце целых чисел Будем говорить, что ненулевое целое число a делит целое число b или a является делителем b (записывается a | b), если существует такое целое чис- ло c, что b = a · c. Например, ±7 | 28, так как 28 = 7 · 4 и 28 = (−7) · (−4). Для любого ненулевого числа a имеем a | 0, ±1 | a и ±a | a. Понятие делителя будет очень важным в нашем изложении теории целых чисел. 3.5. ДЕЛИМОСТЬ В КОЛЬЦЕ ЦЕЛЫХ ЧИСЕЛ 97 Одно из основных свойств целых чисел — свойство делимости или ев- клидовости. Теорема 3.5.1 (свойство евклидовости). Для любого a и любого нену- левого b существуют единственные (целые) частное q и остаток r такие, что a = b · q + r, 0 6 r < |b|. Доказательство. Рассмотрим множество целых чисел вида a − kb, где k ∈ Z. Выберем в этом множестве наименьшее неотрицательное число (такое число существует, поскольку система hω; 6i является вполне упорядоченным множеством). Обозначим это число через 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). 98 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ Пользуясь понятием НОД, можно охарактеризовать целые решения ли- нейных уравнений от двух переменных (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). ¤ 3.6. РАЗЛОЖЕНИЕ ЦЕЛЫХ ЧИСЕЛ НА МНОЖИТЕЛИ 99 Теперь изложим классический алгоритм Евклида вычисления НОД двух целых чисел. Ключевым в этом алгоритме является следующий факт: если 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 разложимы, то они также могут быть записаны как произведения нетри- виальных сомножителей и т. д. Этот процесс рано или поздно обрывается, поскольку не существует бесконечной строго убывающей последовательно- сти положительных целых чисел. 100 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ Теорема 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. |