М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 181
Текст из файла (страница 181)
Говорят, что целое число д делшп и (обозначение: 0~и), если существует такое целое я, что и = ап. В таком случае также можно сказать, что и делится на д или что д является делителем числа и. Заметим, что 1 и и всегда являются делителями числа и. Если 4 не делит и (не является делителем числа и), пишут д,~ и, например: 3~6, 3)18, но 3,~5, 3,~ 7. 'Упражнение П4.1 (транзитнвность). Покажите, что если а~6 и 6|с, то а~с. упражнение П4.2.
Покажите, что если 4~а и Ы~Ь, то д также делит линейную комбинацию чисел а и 6 (ах + Ьу, где х и д — целые числа). т'пражиенне П4.3. Пусть а и 6 — положительные целые числа. Докажите, что если а)6, то а < Ь. Получите следствие этого факта: а = Ь, если а~6 и Ь|а. Прость«м называют целое число т, большее единицы, которое имеет только два делителя: 1 и т. Перечислим несколько первых простых чисел: 2, 3, 5, 7, 11, 13, 17,... Оказывается, любое положительное целое число можно однозначно представить в виде произведения простых множителей. Это утверждение известно как основная теорема арифметики.
Теорема П4.1 (основная теорема арифметики). Пусть а — положительное целое число, большее единицы. Тогда а можно представить в виде произведения простых множителей: (П4.1) где рь..., р„— различные простые числа, а ам..., а„— положительные целые числа. Более того, это разложение единственно (с точностью до порядка сомножителей) . П4.2.
Арифметика остатков и алгоритм Евклида 759 Дояаза»пааво«пво. Читателю, не знакомому с доказательством основной теоремы арифметики, настоятельно рекомендуется попытаться доказать ее самостоятельно. В случае неудачи доказательство можно найти в любом элементарном учебнике по теории чисел; см. ссылки «История и дополнительная литература» в конце приложения. Легко найти разложение на простые множители небольших чисел методом проб и ошибок, например: 20 = 2э 51. Для больших чисел эффективный алгоритм разложения на простые множители с помощью классического компьютера не найден, хотя на его поиски затрачены неимоверные усилия. «Гпражнение П4.4.
Найдите разложение на простые множители чисел 697 и 36 300. П4.2 Арифметика остатков и алгоритм Евклида Приемы обычной арифметики хорошо знакомы каждому. Другим типом арифметики является арифметика остатков. Мы считаем, что читатель хорошо знаком с элементарными идеями арифметики остатков, поэтому лишь кратко напомним основные идеи и обозначения, прежде чем перейти к более сложным областям этой дисциплины.
Из самого названия ясно, что арифметика остатков имеет дело с осп»атка««и. Если мы делим 18 на 7, то получаем неполное частное 2 и 4 в остатке. Говоря строго, для любых положительных чисел х и и существует (единственное) представление х в виде х = Йи+г, (П4.2) где Й вЂ” неотрицательное целое число (неполное частное, результат деления х на и), а остап«он г лежит между 0 и (и — 1) (включительно).
Арифметика остатков является обычной арифметикой, в которой мы обращаем внимание только на остатки. Будем использовать обозначение «(шоб и)», чтобы показать, что мы имеем дело с арифметикой остатков. Например, можно написать 2 = 5 = 8 = и (щи 3), поскольку 2,5,8 и 11 дают одинаковый остаток (2) при делении на 3. Обозначение «(шест и)» напоминает нам, что мы имеем дело с остатками по модулю и. Операции сложения, умножения и вычитания для арифметики остатков могут быть определены очевидным образом, но не столь очевидно, как деление. Чтобы понять, как это сделать, введем еще один ключевой термин теории чисел — наибольший общий девин»а«ь двух целых чисел.
Наибольший общий делитель чисел а и Ь (НОД(а, Ь)) — это наибольшее целое число, которое одновременно делит и число а, и число Ь. Например, наибольший общий делитель чисел 12 и 18 равен 6. Проще всего в этом убедиться, выписав все положительные делители числа 18 (1,2,3,6,9,18) и числа 12 (1,2,3,4,6,12), после чего выбрать максимальное число, принадлежащее обоим множествам.
Однако этот способ неэффективен, и его нельзя использовать для больших чисел. Суще- 760 Приложение 4. Теория чисел ствует более эффективный способ нахождения наибольшего общего делителя, называемый алгории»мол«Евклида, который будет описан ниже. Теорема П4.2 (теорема представления для КОД). Наибольший общий делитель чисел а и 6 равен наименьшему положительному целому числу, которое можно представить в виде ах + 6у, где х и у — целые числа. Доказав»ельси»во.
Пусть з = ах + Ьу — наименьшее положительное целое число, которое может быть представлено в виде линейной комбинации а и 6. Поскольку НОД(а,Ь) делит а и 6, он также делит ю Отсюда следует, что НОД(а, 6) < ю Чтобы завершить доказательство, покажем, что з < НОД(а, 6) (доказав, что з является делителем чисел а и 6). Будем доказывать «от противного». Предположим, что з не делит а. Тогда а = Йз + т, где остаток т удовлетворяет условию 1 < т < (з — 1).
После переноса слагаемого Йз в другую часть получим (учитывая, что з = ах+Ьу), что а(1 — Йх)+6( — Йу) = т — положительное целое число меныпее з, которое можно представить в виде линейной комбинации чисел а и 6. Это противоречит нашему определению з как наименьшего целого числа, которое можно записать в виде линейной комбинации а и 6. Следовательно, наше предположение неверно, и з делит а. Аналогично доказывается и тот факт, что з делит 6. Следствие П4.3 Предположим, что с делит а и 6. Тогда с делит НОД(а, Ь).
Доказательство. Согласно теореме П4.2, НОД(а, 6) = ах + Ьу, где х и у— целые числа. Поскольку число с делит а и 6, оно должно также делить ах+ 6у. Зададимся вопросом: в каком случае у числа а есть обратное в арифметике остатков? Иными словами, для каких а и и существует такое 6, что аЬ = 1 (пюб и)? Заметим, например, что 2 3 = 1 (шоб 5), следовательно, число 3 является обратным для числа 2 в арифметике остатков по модулю 5.
В то же время методом проб и ошибок можно убедиться, что у числа 2 нет обратного в арифметике остатков по модулю 4. Оказывается, наличие обратных чисел в арифметике остатков связано с понятием взаил«кой проси»оты (числа а и 6 называют взаил«ио-проси»ььии, если их наибольший общий делитель равен едишще). Например, 14 и 9 — взаимно-простые числа, поскольку для числа 14 положительными делителями являются 1, 2, 7 и 14, а для числа 9 — числа 1, 3 и 9. Приводимое ниже следствие связывает существование обратных элементов в арифметике остатков со свойством взаимной простоты.
Следствие П4.4 Пусть и — целое число, большее единицы. Для целого числа а существует обратное по модулю и тогда и только тогда, когда НОД(а, и) = 1, т. е. когда а и и — взаимно-простые. Доказан»ельси»во. Пусть существует число, обратное а (по модулю и), которое мы обозначим как а 1. Тогда аа ' = 1 + Йи для некоторого целого Й, следовательно, аа» + ( — Й)и = 1. Из теоремы П4.2 следует, что НОД(а, и) = 1.
И наоборот, если НОД(а, и) = 1, то должны существовать такие целые числа 1 и 6, что а1 + Ьи = 1, т. е. а1 = 1 (пюд и). Следовательно, 1 является обратным для числа а, т. е. 1 = а 1. Упри»кненяе П4.5. Пусть р — простое число. Докажите, что для каждого П4.2. Арифметика остатков и алгоритм Евклида 781 числа ог 1 до (р — 1) включительно существует обратное (по модулю р).
Для каких чисел в диапазоне от 1 до (рз — 1) включительно не существует обратного по модулю рз? упражнение П4.6. Найдите число, обратное 17 по модулю 24. МпРвжнение П4.7. Найдите, число, обратное (и+ 1) по модулю пз, если п— целое число, большее единицы. з првжнение П4.8 (единственность обратного). Пусть Ь и Ь'- числа, обратные а (по модулю и). Докажите, что 6 = 6' (шоб и). Следующая ниже теорема чрезвычайно важна для построения алгоритма Евклида нахождения наибольшего общего делителя двух положительных целых чисел. Теорема П4.5.
Пусть а и 6 — целые числа, т — остаток от деления а на Ь. Тогда если г ф О, то (П4.3) НОД(а,6) = НОД(Ь,т). Доказапьельсгпво. Чтобы доказать равенство (П4.3), покажем, что каждая из его частей делит другую. Сначала докажем, что левая часть делит правую. Заметим, что т . (а — 66) для некоторого целого й. Поскольку НОД(а, 6) делит а, Ь и любые их линейные комбинации, НОД(а, 6) также делит г.
С учетом следствия П4.3 сделаем вывод, что НОД(а,6) делит НОД(6,г). Чтобы доказать, что правая часть делит левую, заметим, что НОД(Ь,г) делит Ь, а поскольку а = т+ 66 — линейная комбинация чисел Ь и г, получим, что НОД(6, г) также делит а. С учетом следствия П4.3 можно заключить, что НОД(6, г) делит НОД(а, 6). Ъ'пражнение П4.9. Покажите, как найти НОД(а,Ь), если известны разложения чисел а и 6 на простые множители. Разложите на простые множители числа 8825 и 1430 и вычислите с помощью этих разложений НОД(6825, 1430). Алгоритм Евклида для нахождения наибольшего общего делителя двух положительных целых чисел а и Ь работает следующим образом.
(Без ограничения общности можно считать, что а > 6.) Разделим а на 6 с остатком, пусть неполное частное равно Ьм а остаток равен г~. а = 6~6+ гь Из теоремы П4.5 следует, что НОД(а, 6) = НОД(Ь, г~). Затем разделим с остатком Ь на г~'. Ь = Ьзг~ + гю С учетом теоремы П4.5 заключаем, что НОД(а, 6) = НОД(Ь,г~) = НОД(гм гз). На следующем шаге разделим с остатком г~ на гьс г~ = кзгз + гз. Согласно теореме П4.5, НОД(а, 6) = НОД(6, г~) = НОД(гм гз) = НОД(гю гз).
Продолжим эту процедуру, каждый рзз производя деление с остатком последнего полученного остатка на остаток, полученный на предпоследнем шаге, получая новые остаток и неполное частное. Выполнение алгоритма завершается, когда на очередном шаге мы получим нулевой остаток, т. е. г = Й,„.~~г ~.~ для некоторого т. При этом НОД(а, 6) = НОД(г, г .~~) = г ем следовательно, результатом работы алгоритма является число г еь 762 Приложение 4. Теория чисел Следовательно, НОД(6825, 1430) = 65. С помощью модификации алгоритма Евклида несложно найти такие целые числа х и р, что ах+ Ьу = НОД(а, 5).
Начнем с последовательного выполнения операций деления с остатком (см. два предыдущих абзаца). Затем подставим последнее из полученных в алгоритме Евклида равенств ((П4.8) в нашем примере) в предпоследнее. Переформулированное таким образом предпоследнее равенство подставим в стоящее перед ним и т. д. вплоть до первого. Тогда имеем следующий результат: Итак, мы получили интересующее нас представление числа НОД(6825, 1430) = 65, а именно: 65 = 6825 ° ( — 9) + 1430 ° 37. Какие ресурсы используются в алгоритме Евклида? Пусть каждое из чисел а и 5 представляется строкой битов длиной не более Ь.
Очевидно, что тогда все неполные частные й, и остатки г; также могут быть записаны строками из Ь бит, так что можно считать, что все вычисления выполняются в Ь-битовой арифметике. Ключевым моментом для оценки используемых ресурсов является то обстоятельство, что гь!.з < г;/2. Для доказательства этого факта рассмотрим два случая: ° гц.1 ~ т,/2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
