Алгоритмы - построение и анализ (1021735), страница 196
Текст из файла (страница 196)
— Прим. рсд. Глава 31. Теоретико-числовые алгоритмы 957 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71 В упражнении 31.1-1 предлагается доказать, что простых чисел бесконечно много. Целое число а ) 1, которое не является простым, называется составным (сошроз!!е). Например, число 39 — составное, поскольку 3 [ 39. Целое число 1 называют единицей (ип!!), и оно не является ни простым, ни составным. Аналогично, целое число 0 и все отрицательные целые числа тоже не являются ни простыми, ни составными. Теорема о делении, остатки и равенство по модулю Относительно заданного числа п, все целые числа можно разбить на те, которые являются кратными числу п, и те, которые не являются кратными числу и.
Ббльшая часть теории чисел основана на усовершенствовании этого деления, в котором последняя категория чисел классифицируется в соответствии с тем, чему равен остаток их деления на п. В основе этого усовершенствования лежит сформулированная ниже теорема (ее доказательство здесь не приводится, но его можно найти, например, в учебнике Найвена (%чеп) и Цукермана (Еис1сеппап) [23 1]).
Теорема 31.1 (Теорема о делении). Для любого целого а и любого положительного целого и существует единственная пара целых чисел 9 и т, таких что 0 < г < < п и а = дп+ т. О [а]„= (а + lгп: Й Е Е) Например, [3]т — — (..., — 11, -4, 3, 10, 17,...); другие обозначения этого множе- ства — [-4]т и [10]т. Используя обозначения из раздела 3.2, можно сказать, что запись а е [6]„— это то же самое, что и запись а = 6(шос!п). Множество всех таких классов эквивалентности имеет вид 2„= ([а]„: 0 < а < и — 1) (3 1. 1) Часто встречается определение Х„= (0,1,...,и — Ц, (31.2) Величина д = [а/п] называется частным (Чиойеп!) деления. Величина г = = а шог! п называется осюшкам (геш!пг!ег или гез1оие) деления.
Таким образом, и [ а тогда и только тогда, когда а пюг! и = О. В соответствии с тем, чему равны остатки чисел по модулю п, их можно разбить на п классов эквивалентности. Класс экеыеолентиости ло модулю п (ецшча!енсе с!ааа шайи!о п), в котором содержится целое число а, имеет вид Часть ЧП. Избранные темы 958 которое эквивалентно уравнению (31.1) с учетом того, что 0 представляет класс [0]„, 1 — класс [Ц„и т.д. Каждый класс в этом представлении определяется своим наименьшим неотрицательным элементом.
Однако при этом следует иметь в виду именно соответствующие классы эквивалентности. Например, -1 в качестве члена класса Е„обозначает «и — 1]„, поскольку -1 ке и — 1 (шоди). Если д — делитель числа а, а также делитель числа Ь, то г1 — общий делитель чисел а и Ь. Например, делители числа 30 — 1, 2, 3, 5, б, 10, 15 и 30, а общие делители чисел 24 и 30 — 1, 2, 3 и б. Заметим, что 1 — общий делитель двух любых целых чисел. Важное свойство общих делителей заключается в том, что (31.3) (31.4) иза [ЬиЬ[аследуета= ~6.
(31.5) Наибольший общий делитель (8геаГезГ сопппоп с11ч)зог) двух целых чисел а и Ь, отличных от нуля, — это самый большой из общих делителей чисел а и Ь; он обозначается как бсг1 (а, 6)~. Например, бсг1 (24, 30) = 6, бес) (5,7) = 1 и бед (0,9) = 9. Если числа а и Ь отличны от нуля, то значение бсг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 следует соотношение 8сд (аЬ, р) = 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), с) . Часть ЧП.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
