Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 196
Текст из файла (страница 196)
Если числа а и Ь отличны от нуля, то значение бсг1 (а, 6) находится в интервале от 1 до ппп ([а[, ]6[). Величину ясд (О, 0) считаем равной нулю; это необходимо для универсальной применимости стандартных свойств функции бес( (пример одного из них выражается уравнением (31.9)).
Ниже перечислены элементарные свойства функции бсб: Сформулированная ниже теорема дает полезную альтернативную характеристику функции бсс1 (а, Ь). Общие делители и наибольшие общие делители из с) [ а и с( [ Ь следует с1 [ (а + Ь) и с( [ (а — Ь) . В более общем виде можно написать, что для всех целых х и у из с1 [ а и с1 [ Ь следует и' ] (ах + Ьу) . Кроме того, если а [ Ь, то либо [а[ < [Ь[, либо Ь = О, так что 8сг1(а,Ь) = боб(Ь,а), бес)(а, Ь) = бсг1(-а,Ь), бег) (а, Ь) = бсс1 ([а[, [Ь]), 8сг1(а, 0) = [а[, бсг1 (а, )са) = [а[ для всех )с б Е . В отечественной литературе применяется также обозначение НОд(а, Ь). — Прим. нер. (31.6) (3 1.7) (3 1.8) (3 1.9) (31.10) Глава 31.
Теоретико-числовые алгоритмы 959 Теорема 31.2. Если а и Ь вЂ” произвольные целые числа, отличные от нуля, то величина 8сс1(а,Ь) равна наименьшему положительному элементу множества (ах + Ьу: х, у е Е) линейных комбинаций чисел а и 6. Доказаогвльсосво. Обозначим через в наименьшую положительную из таких линейных комбинаций чисел а и Ь, и пусть в = ах + Ьу при некоторых х, у е в. Пусть также д = ~а/в). Тогда из равенства (3.8) следует а шос1 в = а — дв = а — с) (ах + Ьу) = а (1 — 9х) + Ь ( — ду), поэтому величина а аспас) в также является линейной комбинацией чисел а и Ь. Но поскольку О < а пюс1 в < в, выполняется соотношение а гпос1 в = О, так как в — наименьшая положительная из таких линейных комбинаций. Поэтому в ~ а; аналогично можно доказать, что в ~ 6.
Таким образом, в — общий делитель чисел а и 6, поэтому справедливо неравенство бес) (а, Ь) > в. Из уравнения (31.4) следует, что ясс1 (а, Ь) ~ в, поскольку величина бсс1(а, Ь) делит и а, и Ь, а в — линейная комбинация чисел а и Ь. Но из того, что ксс1(а, Ь) ) в, и в > О следует соотношение ясс) (а, Ь) < в. Совместное применение неравенств ясс1(а, Ь) > в и ясс1 (а, Ь) < в доказывает справедливость равенства ясс1 (а, 6) = в; следовательно, можно сделать вывод, что в — наибольший общий делитель чисел а и Ь. Следствие 31.3. Для любых целых чисел а и Ь из соотношений с1 ) а и с) ( Ь следует с1 ! ясс1 (а, Ь). Доказаогельсясво. Это следствие является результатом уравнения (31.4), поскольку, согласно теореме 31.2, величина ксс1(а, 6) является линейной комбинацией чисел а и 6.
1 Следствие 31.4. Для любых целых чисел а и Ь и произвольного неотрицательного целого числа и справедливо соотношение ясс1 (ап, Ьп) = и ксс1 (а, 6) Доказаосельсосво. Если п = О, то следствие доказывается тривиально. Если же п > О, то ясс1 (ап, Ьп) — наименьший положительный элемент множества (апх + + Ьпу), в п раз превышающий наименьший положительный элемент множества (ах+ Ьу). Следствие 31.5. Для всех положительных целых чисел п, а и Ь из условий п ! аЬ и ясс1 (а, п) = 1 следует соотношение п ~ Ь. Доказаосельсосво. Доказательство этого следствия читателю предлагается выполнить самостоятельно в упражнении 31.1-4.
Л Часть Ч11. Избранные темы 960 Взаимно простые целые числа Два числа а и Ь называются взаимно нроснзыми (ге!а11че1у ргппе), если единственный их общий делитель равен 1, т.е. если бсср (а, Ь) = 1. Например, числа 8 и 15 взаимно простые, поскольку делители числа 8 равны 1, 2, 4 и 8, а делители числа 15 — 1, 3, 5 и 15. В сформулированной ниже теореме утверждается, что если два целых числа взаимно простые с целым числом р, то их произведение тоже является взаимно простым с числом р. Теорема 31.6. Для любых целых чисел а, 6 и р из соотношений йсй (а, р) = 1 и бсср (Ь, р) = 1 следует соотношение йод (аЬ, р) = 1. Доказательство.
Из теоремы 31.2 следует, что существуют такие целые числа х, у, х' и у', для которых ах+ ру = 1, Ьх' + ру' = 1. Умножив эти уравнения друг на друга и перегруппировав слагаемые, получим: аЬ (хх') + р (уЬх' + у'ах + руу') = 1. Поскольку положительная линейная комбинация чисел аЬ и р равна 1, применение теоремы 31.2 завершает доказательство.
М Говорят, что целые числа пз, пз,..., пь иолврно взаимно простые (ра1пи1зе ге!апче1у рпше), если при 1 ф з' выполняется соотношение йсс1 (и;, и ) = 1. Единственность разложения на множители Элементарный, но важный факт„касающийся делимости на простые числа, сформулирован в приведенной ниже теореме. Теорема 31.7. Для любого простого числа р и всех целых чисел а и 6 из условия р ( аЬ следуют либо соотношение р ~ а, либо соотношение р ) Ь, либо они оба.
Доквзизиельсзиво. Проведем доказательство методом "от противного". Предположим, что р ) аЬ, но р 1' а и р 1 Ь. Таким образом, йсй(а,р) = 1 и бсср (Ь, р) = = 1, поскольку единственными делителями числа р являются 1 и р, и, согласно предположению, на р не делится ни а, ни Ь. Тогда из теоремы 31.6 следует, что йсг1 (аЬ, р) = 1, а это противоречит условию, что р ~ аЬ, поскольку из него следует, что 8сс( (аЬ, р) = р. Это противоречие и служит доказательством теоремы. а Из теоремы 31.8 следует, что любое целое число единственным образом представляется в виде произведения простых чисел. Глава 31.
Теоретико-числовые алгоритмы 961 Теорема 31.8 (Единственность разложения на множители). Целое составное число а можно единственным образом представить как произведение вида а = = р1'рз' р„", где р; — простые числа, р1 < рз « р„а е, — целые положительные числа. Доказательство. Доказательство этой теоремы в упражнении 31.1-10 читателю предлагается выполнить самостоятельно. и Например, число 6000 можно единственным образом разложить на множители 2с . 3, 5з Упражнения 31.1-1. Докажите, что простых чисел бесконечно много.
(Указание: покажите, что ни одно из простых чисел ры рз,..., рь не является делителем числа (Рзрз ' ' Рь) + 1 ) 31.1-2. Докажите, что если а ! Ь и Ь | с, то а ! с. 31.1-3. Докажите, что если р — простое число и 0 < lс < р, то йсс1 (Ь, р) = 1. 31.1-4. Докажите следствие 31.5. 31.1-5. Докажите, что если р — простое число и 0 < )с < р, то р ~ (~~). Сделайте отсюда вывод, что для всех целых чисел а и Ь и простых р выполняется соотношение (а+ 6)к = а" + Ьр (шос)р).
31.1-6. Докажите, что если а и Ь вЂ” положительные целые числа, такие что а ~ 6, то для всех х выполняется соотношение (х гпос1 6) шод а = х шос1 а. Докажите, что при тех же предположениях для всех целых чисел х и у из соотношения х ьч у(шос)6) следует соотношение х = у(шос)а).
31.1-7. Говорят, что для всех целых 1с > 0 целое число п — )с-я етенень (йс)з розсег), если существует целое число а, такое что ая = п. Число п > > 1 — нетривиальная степень (попП)ч)а! ротег), если оно является lс-й степенью для некоторого целого )с > 1. Покажите, как определить, является ли заданное Д-битовое целое число и нетривиальной степенью, за время, которое выражается полиномиальной функцией от )3. 31.1-8.
Докажите уравнения (31.6)-(31.10). 31.1-9. Покажите, что операция 8сд обладает свойством ассоциативности, т.е. докажите, что для всех целых а, Ь и с справедливо соотношение йод (а, йсс1 (6, с)) = йсс) (бсс1 (а, 6), с) . Часть ЧП. Избранные темы 962 31.2 Наибольший общий делитель В этом разделе описан алгоритм Евклида, предназначенный для эффективного вычисления наибольшего общего делителя двух целых чисел.
Анализ времени работы этого алгоритма выявляет удивительную связь с числами Фибоначчи, которые являются наихудшими входными данными для алгоритма Евклида. Ограничимся в этом разделе неотрицательными целыми числами. Это ограничение обосновывается уравнением (31.8), согласно которому боб (а, Ь) = бсс1Оа~, )ЬО. В принципе, величину бед (а, Ь) для положительных целых чисел а и Ь можно вычислить, пользуясь разложением чисел а и Ь на простые множители. В самом деле, если разложения чисел а и Ь имеют вид ь =р",ру'...ру, (31.11) (31.12) где нулевые показатели экспоненты используются для того, чтобы в обоих разложениях были представлены одинаковые множества простых чисел рырз,...,р„ то можно показать, что пнп(епй) ппп(е2,/з) т!п(е„,~у) В упражнении 31.2-1 предлагается показать, что это действительно так.
Однако в разделе 31.9 будет показано, что время работы самых эффективных на сегодняшний день алгоритмов разложения на множители не выражается полиномиальной функцией; оии работают менее производительно. Алгоритм Евклида, предназначенный для вычисления наибольшего общего делителя, основан на сформулированной ниже теореме. * 31.1-10.
Докажите теорему 31.8. 31.1-11. Разработайте эффективный алгоритм для операций деления )3-битового целого числа на более короткое целое число и вычисления остатка от деления )3-битового целого числа на более короткое целое число. Время работы алгоритма должно быть равно О (13з). 31.1-12. Разработайте эффективный алгоритм преобразования заданного )3-битового (двоичного) целого числа в десятичное. Докажите, что если умножение или деление целых чисел, длина которых не превышает )3, выполняется в течение времени М ()3), то преобразование из двоичной в десятичную систему счисления можно выполнить за время Е) (М (~3) )8)3).
(Указание: воспользуйтесь стратегией "разделяй и властвуй", при котором верхняя и нижняя половины результата получаются в результате отдельно выполненных рекурсивных процедур.) Глава 31. Теоретико-числовые алгоритмы 9б3 Теорема 31.9 (Рекурсивная теорема о НОД). Для любого неотрицательного целого числа а и любого положительного целого числа Ь справедливо соотношение ксс1(а,Ь) = ксс1(Ь,а пюс1 Ь).
Доказаосвльслсво. Покажем, что величины бсс1(а, Ь) и ксс1(Ь,а шос1 Ь) делятся друг на друга, поэтому они должны быть равны друг другу (поскольку оба они неотрицательны) согласно уравнению (31.5). Сначала покажем, что бсс1 (а, Ь) ! ксс1 (Ь, а пюс1 Ь). Если с1 = ксс1 (а, Ь), то с( ) а и с1 ! Ь. Согласно уравнению (3.8), (а тпос1 Ь) = а — 96, где д = '1а/Ь|. Поскольку величина (а шос1 Ь) представляет собой линейную комбинацию чисел а и Ь, то из уравнения (31.4) следует, что с( ! (а пюс1 Ь).
Таким образом, поскольку с( ( Ь и с1 ! (а шос1 Ь), согласно следствию 31.3, с1 ~ бсс1 (Ь, а пюс1 Ь) или, что то же самое, бсс1 (а, Ь) ! 8сс1 (Ь, а пюс1 Ь) . (31.14) Соотношение ксс1(Ь,а шос1 Ь) ~ ксс1 (а, Ь) доказывается почти так же. Если ввести обозначение с1 = йсс1 (Ь,а шос1 Ь), то с1 ! Ь и с1 ~ (а шос1 Ь). Поскольку а = 96+ (а шос1 Ь), где д = '1а/61, а представляет собой линейную комбинацию величин Ь и (а пюс1 6). Согласно уравнению (31.4), можно сделать вывод, что с1 ! а. Поскольку с( ! 6 и с1 ! а, то, согласно следствию 31.3, справедливо соотношение с1 ! ксс1 (а, Ь) или эквивалентное ему ксс1(Ь,а пюс1 Ь) ~ ксс1(а, Ь).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
