Основная теорема арифметики: любое натуральное число можно представить в виде произведения простых множителей.
Хотя доказать основную теорему арифметики нетрудно, задача о разложении числа на простые множители на практике может оказаться неразрешимой.
89
К примеру, если n представляет собой произведение двух простых чисел р и q приблизительно из 400 знаков каждое, то для разложения n на простые множители даже самым мощным компьютерам потребуется время, сравнимое с возрастом Вселенной. Как вы увидите далее, это один из основных принципов криптографического алгоритма RSA, обеспечивающего безопасность всех наших компьютерных транзакций.
Введем новое понятие: для двух натуральных чисел m и n будем называть наибольшим общим делителем наибольшее натуральное число, на которое делятся одновременно m и n. Обозначим его НОД (m, n). Если нам известны разложения m и n на простые множители, найти НОД очень просто: нужно взять простые числа, которые содержатся в обоих разложениях, возведенные в наименьшую степень. Допустим, что мы хотим найти НОД 50 = 2 · 5² и 120 = 23 · 3 · 5. Общие делители этих чисел — 2 и 5. В первом случае они возведены в степени 3 и 1, во втором — в степени 1 и 2.
Таким образом, НОД будет равен 21 · 51 = 10. Задача о разложении числа на простые множители на практике оказывается неразрешимой, поэтому для очень больших m и n описанный метод неприменим. К счастью, существует еще один метод расчета наибольшего общего делителя, который называется алгоритмом Евклида. Допустим, что m больше n. На первом шаге разделим m на n. Возможны два случая: если остаток от деления равен 0, то n — делитель m, следовательно, n — искомый НОД. В противном случае повторим деление, заменив m на n, а n — на остаток от деления r. Можно доказать, что наибольший общий делитель m и n совпадает с наибольшим общим делителем n и r[8].
Вернемся к нашему примеру: остаток от деления 120 на 50 равен 20, следовательно, на следующем шаге алгоритм нужно повторить для 50 и 20. Остаток от деления 50 на 20 равен 10, поэтому на следующем шаге рассмотрим 20 и 10. На этот раз первое число делится на второе без остатка, таким образом, НОД равен 10. Более того, алгоритм Евклида позволяет получить некоторую дополнительную информацию: если мы рассмотрим последний ненулевой остаток от деления, то сможем записать 10 = 50 — 2·20. Сделаем еще один шаг назад и получим, что 20 = 120 — 2 · 50. Если теперь мы подставим это выражение в первое равенство, то получим отношение с целыми коэффициентами, связывающее
10 = 50-2-(120-2·50) = 5·50-2·120.
90
В общем случае алгоритм Евклида позволяет не только эффективно вычислить наибольший общий делитель чисел, но также показать следующее:
Предложение. Пусть m и n — два натуральных числа. Обозначим их наибольший общий делитель через d. Тогда существуют два целых числа u и v такие, что d = mu + nv.
Особенно интересен случай, когда m и n не имеют общих делителей. Тогда их наибольший общий делитель равен 1, а m и n называются взаимно простыми. Согласно приведенному выше предложению, существуют два целых числа u и v такие, что mu + nv = 1. Это соотношение называется соотношением Безу.
Еще одно фундаментальное свойство делимости чисел звучит так: если число а — делитель произведения bс, и нам известно, что а и b — взаимно простые, то а обязательно будет делителем с. В самом деле, в противном случае один из простых делителей а также будет делителем b, и эти числа не будут взаимно простыми.
С другой стороны, если d — наибольший общий делитель а и b, то существуют два целых числа р и q такие, что а = dp, b = dq. Это утверждение выполняется для любых общих делителей, но так как d — НОД, можно утверждать, что р и q взаимно простые — в противном случае а и b имели бы общий делитель, больший d.
Теперь мы знаем все, что нужно для решения диофантовых уравнений вида ах + by = с,
где а, b и c — произвольные целые числа. Чтобы решить это уравнение, нужно найти все пары целых чисел (х, у), которые удовлетворяют соотношению ах + by = с.
Посмотрим, как это сделать. Обозначим через d наибольший общий делитель а и b. По определению а и b делятся на d, следовательно, выражение ах + by также будет делиться на d. Так как согласно исходному уравнению ах + by = с, число d также должно быть делителем с. Следовательно, если с не делится на d, то уравнение не имеет решений. Так, решений не имеет уравнение 50х + 120у = 7. Мы уже показали, что наибольший общий делитель 50 и 120 равен 10, а 7 не делится на 10.
Далее будем предполагать, что с делится на d.
Тогда мы можем записать а = dp, b = dq и с = dr, где р и q — взаимно простые.
Сначала рассмотрим случай с = 0, то есть однородное уравнение ах + by = 0.
91
Разделив на d первый член уравнения, получим следующее: достаточно решить уравнение рх + qy = 0, или, что аналогично, рх = —qy. Будем рассуждать следующим образом: так как рх равно — qy, qy должно делиться на р. Однако р и q взаимно простые, следовательно, остается единственный вариант: у делится на р, то есть существует целое число Λ такое, что у = Λр. Аналогично доказывается, что х делится на q, поэтому существует другое целое число μ такое, что х = μq. Подставив значения х и у в уравнение, получим: μpq = —Λpq, то есть μ = —Λ, так как pq отлично от нуля. Следовательно, решениями уравнения ах + by = 0 будет пара чисел (q, —р) и всех кратных им чисел (Λq, —Λр).
Теперь предположим, что с отлично от нуля. Если известно два решения (x0, у0) и (х1 y1) уравнения ах + by = с, то:
а(х0 - х1) + b(у0 - у1) = (ах0 + by1-(ax1+by1) = с-с = О,
откуда следует, что (x0 — x1, у0 — y1) — решение однородного уравнения ах + by = 0.
Так как все решения этого уравнения имеют вид (Λq, —Λр), найдется целое число Λ такое, что x0 — x1 = Λq и у0 — у1 = —Λр, или, что аналогично, х = x0 — Λq и y1 = y0 +Λр. Иными словами, уравнение имеет бесконечно много решений, но все они выводятся из частного решения (x0, у0). Напомню, что р и q — результат деления а и b на наибольший общий делитель. Следовательно, мы доказали, что все решения выглядят так:
где (x0, у0) — частное решение, Λ — любое целое число. Теперь всего лишь осталось найти метод, позволяющий получить (x0, у0). Найти эти решения нетрудно, если р и q — взаимно простые, так как по соотношению Безу существуют два целых числа u и v такие, что рu + qv— 1. Умножив u и v на r, получим два числа x0 = ur и у0 = vr такие, что ax0 + by0 = с.
Рассмотрим пример. Допустим, мы хотим решить диофантово уравнение 50х + 120у = 20.
Мы уже знаем, что наибольший общий делитель 50 и 120 равен 10.
Так как 20 делится на 10, уравнение имеет решение.
92
В этом случае в упрощенном виде уравнение выглядит так: 5х + 12у = 2. Найдем числа, которые мы обозначили через u и v. Так как 1 = 5 — 2 ·2 и 2 = 12 — 2·5, имеем
1 = 5 - 2 · (12 - 2 · 5) = 5 · 5 - 2 · 12,
то есть u = 5, v = —2. Умножив эти значения на 2, получим частное решение (10, —4), на основе которого можно найти общее решение:
Краткий экскурс в криптографию
Посмотрим, как диофантовы уравнения используются в системе шифрования с открытым ключом. Напомним, что для данного натурального числа n группа целых чисел со сложением по модулю n состоит из элементов [0], [1], [2]...[n — 1], а сложение выполняется следующим образом: сначала мы складываем элементы группы как обычные числа, затем вычитаем n из полученного результата до тех пор, пока не получим число, заключенное на интервале от 0 до n — 1. Аналогично можно определить операцию умножения. Допустим, n = 7 и нам нужно вычислить произведение 4*5. Сначала умножим эти два числа так же, как и целые числа. Получим 20.
Теперь нужно вычесть из этого результата 7 нужное число раз: после первого вычитания получим 13, после второго — 6, что меньше 7. Следовательно, произведение 4 и 5 по модулю 7 равно 6.
Теперь перейдем к криптографии.
Допустим, что Боб хочет отправить Алисе секретное сообщение. Так как любую информацию можно представить с помощью чисел, достаточно решить задачу о защищенной передаче числа m. Боб знает открытый ключ Алисы (он доступен всем).
У Алисы также есть закрытый ключ, известный только ей. Следует различать три этапа передачи сообщения: генерация ключей, шифрование сообщения и расшифровка.
Сначала покажем, как генерируются ключи. Выберем два простых числа р и q.
В принципе, достаточно, чтобы произведение р и q (обозначим его через n), было больше числа m, которое нужно передать. Но наш метод шифрования будет обеспечивать достаточный уровень защиты только тогда, когда р и q будут достаточно большими и никакой компьютер не будет способен разложить n на простые множители за разумное время. Выберем два простых числа р и р, состоящие из 300—400 знаков.
