Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.12.2023
Просмотров: 437
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
3.4. СПИСОЧНОЕ ПРЕДСТАВЛЕНИЕ ЧИСЕЛ
91 2.
Списочное представление целых и рациональных чисел
Как уже отмечалось, компьютерное представление целых чисел ограни- чено длиной машинного слова. Для расширения возможностей такого пред- ставления и выполнения точных арифметических действий можно исполь- зовать задание целых чисел в виде списков. При этом, однако, необходи- мо разработать специальное программное обеспечение, позволяющее выпол- нять арифметические операции над списками.
Пусть P — такое основание счисления, что P − 1 — наибольшее значение,
хранимое в компьютерном слове. Рассмотрим два типа целых чисел. Если
−(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
92
Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ
называется суммой списков 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. Величина такого отклонения объясняется следующей теоремой.
3.5. ДЕЛИМОСТЬ В КОЛЬЦЕ ЦЕЛЫХ ЧИСЕЛ
93
Теорема 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. Понятие делителя будет очень важным в нашем изложении теории целых чисел.
94
Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ
Одно из основных свойств целых чисел — свойство делимости или ев-
клидовости.
Теорема 3.5.1 (свойство евклидовости). Для любого a и любого нену-
левого b существуют единственные (целые) частное q и остаток r такие,
что a = b · q + r, 0 6 r < |b|.
Доказательство. Рассмотрим множество целых чисел вида a − kb, где
k ∈ Z. Выберем в этом множестве наименьшее неотрицательное число (такое число существует, поскольку система hω; 6i является вполне упорядоченным множеством). Обозначим это число через
1 ... 7 8 9 10 11 12 13 14 ... 29
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
— натуральные числа.