Теорема 33.8 (Существование и единственность разложения) Всякое составное число а единственным образом представляется в виде

ei еоег

а = Plp22 -р/,

где pi < р2 < < рг - простые числа, а ег- - положительные целые числа.

Доказательство оставляется читателю (упр. 33.1-10).

Упражнения.

33.1-1

Докажите, что существует бесконечно много простых чисел. (Указание: ни одно из простых чисел pi,P2, ,Pk не делит число

(PiP2 • • -Рк) + 1-) 33.1-2

Докажите, что если а \ Ь и Ь с, то а \ с. 33.1-3

Пусть число р - простое, а 0 < к < р. Докажите, что НОД(к,р) = 1. 33.1-4

Докажите следствие 33.5. 33.1-5

Пусть число р - простое, а 0 < к < р. Докажите, что р Ср. Выведите отсюда, что для любых целых а, Ь и простого р выполняется сравнение

(а + Ь)р = ар + Ьр (modp).

33.1-6

Пусть а и Ь - целые числа, причём а \ Ь и Ь > 0. Докажите, что (ж mod Ъ) mod а = ж mod а при любом целом ж. Докажите, что (при тех же допущениях) из ж = у (mod Ъ) следует, что ж = у (mod а) при любых целых хну.

33.1-7

Фиксируем целое положительное к. Будем называть целое число п (точной) к-й степенью (Arth power), если п равно ак при некотором целом а. Целое число п > 1 назовём нетривиальной степенью (nontrivial power), если оно является к-ъ степенью при некотором целом к > 1. Предложите полиномиальный алгоритм, определяющий, является ли данное число п нетривиальной степенью.

33.1-8

Докажите свойства (33.8)-(33.12). 33.1-9

Докажите, что функция gcd ассоциативна, то есть для gcd(a, gcd(6, с)) = gcd (gcd (a, b), с) для любых целых a,b,c. 33.1-10*

Докажите теорему 33.8. 33.1-11

Предложите алгоритмы, вычисляющие за время 0(/32) частное и остаток от деления /3-битового целого числа на более короткое (временем считаем число битовых операций).

33.1-12

Постройте эффективный алгоритм, переводящий /3-битовое целое число из двоичной системы в десятичную. Покажите, что если умножение и деление двух целых чисел длины не более /3 (имеется в виду длина двоичной записи) требует времени М(/3), то перевод /3-битового целого числа из двоичной системы в десятичную может быть выполнен за время 0(М(/3) lg/3).

(Указание. Используйте метод «разделяй и властвуй», получая отдельно левую и правую части результата.)

33.2. Наибольший общий делитель

В этом разделе мы предполагаем, что все рассматриваемые целые числа положительны (для наибольшего общего делителя знак роли не играет).

Можно вычислять НОД(а,Ь), разлагая а и Ь на множители и отбирая общие множители: если

a = fyf-(33.13)

и

Ъ = р{1р{2 ... -р1/,(33.14)

то

gcd(a, b) = pm-(eb/0pmin(e2J2) pmin(er,/r)(33

Но разложение на множители, как мы увидим в разделе 33.9, является трудной задачей, так что его лучше избегать.

Алгоритм Евклида для нахождения наибольшего общего делителя основан на следующей теореме.

Теорема 33.9 (Рекуррентная формула для gcd)

Пусть а - целое неотрицательное, а Ь - целое положительное число. Тогда gcd (a, Ъ) = gcd (b, a mod b).

Доказательство.

Пара (a, b) имеет те же делители, что и пара (b, a mod b) (a mod b является целочисленной линейной комбинацией а и b и наоборот). Поэтому и наибольший общий делитель у этих пар одинаковый.

Алгоритм Евклида.

Приводимый ниже алгоритм вычисления наибольшего общего делителя описан в книге Евклида «Начала» (около 300 г. до Р.Х.), хотя, возможно, был известен и ранее. Мы запишем его в виде рекурсивной процедуры; её входом являются неотрицательные целые числа а и Ь.

Euclid (a,b)

1if b=0

2then return a

3else return Euclid (b, a mod b)

Например, при вычислении Euclid(30, 21) = Euclid(21.9) = Euclid(9, 3) = Euclid(3, 0) = 3 процедура вызывает себя трижды.

Правильность процедуры Euclid вытекает из соотношения (33.11) и из теоремы 33.9. Процедура не может работать бесконечно, поскольку рекурсивный вызов происходит с меньшим значением второго аргумента.

Время работы алгоритма Евклида.

Оценим время работы алгоритма Евклида, считая, что размера входа случай а > ft 0 (при ft > а 0 процедура Euclid (а, ft) первым делом вызывает себя, переставив аргументы местами, а при а = Ь > 0 работа процедуры завершается после единственного рекурсивного вызова, поскольку a mod а = 0). Заметим, что во всех рекурсивных вызовах первый аргумент будет строго больше второго (остаток меньше делителя).

Время работы процедуры Euclid пропорционально глубине рекурсии. Для её оценки нам пригодятся числа Фибоначчи Fk, определённые рекуррентным соотношением (2.13).

Лемма 33.10

Пусть а > Ь 0. Если процедура EucLm(a,ft) во время работы вызывает себя к раз (к 1), то a Fk+2 и ft ) Fk+\. Доказательство

проведём индукцией по к. Базисом индукции служит значение к = 1. Если происходит хоть один рекурсивный вызов, то Ь 1 = F2; по условию теоремы а > Ь, так что а 2 = F3.

Пусть лемма выполнена для случая к - 1 вызовов; докажем её для к вызовов. На первом шаге процедура Euclid (а, ft) выполняет вызов Euclid (b, a mod Ъ), внутри которого происходит к - 1 рекурсивных вызовов, так что по предположению индукции Ь -Ffc+i и (a mod Ъ) Fk- Из неравенства а > Ь > 0 следует, что [a/b\ 1 и Ь + (a mod Ъ) = Ь + (а - [a/b\b) а, так что а Ь + (a mod Ъ) Fk+1+Fk = Fk+2.

Из леммы 33.10 вытекает следующая теорема.

Теорема 33.11 (Теорема Ламе)

Пусть к - целое положительное число. Если й > ft 0 и ft < Fk+i, то процедура Euclid (a, ft) выполняет менее к рекурсивных вызовов.

Покажем, что оценка теоремы 33.11 неулучшаема, рассмотрев вычисление наибольшего общего делителя соседних чисел Фибоначчи. Процедура Euclid(F3, F2) выполняет один рекурсивный вызов. Поскольку Fk+i mod Fk = Fk-i, вычисление будет идти так: gcd(Ffc+i,Ffc) = gcd(Ffc, (Ffc+i mod Fk)) = ЯОД(,-1), поэтому