Хавьер Фресан - Мир математики - m. 35 Пока алгебра не разлучит нас. Теория групп и ее применение.

Простые числа составляют основу всей арифметики: через них определяются все остальные числа. В самом деле, если n не является простым, то на интервале от 1 до n найдется натуральное число, которое будет его делителем. Таким образом, n можно представить в виде n = а · b. К примеру, если исходное число равно 30, имеем 30 = 2 · 15. Мы получили два числа а и b, для которых можем повторить описанные действия еще раз. Если оба этих числа простые, процесс заканчивается.

Если же какое-то из этих чисел не является простым, мы вновь запишем его в виде произведения двух множителей. В нашем примере 2 является простым, а 15 можно представить как произведение 3 и 5. Имеем 30 = 2 · 3 * 5. Так как 2, 3 и 5 — простые числа, процесс завершен. В общем случае на каждом шаге мы либо находим простой сомножитель, либо представляем число как произведение двух меньших чисел, поэтому описанный нами процесс рано или поздно обязательно завершится.

Основная теорема арифметики: любое натуральное число можно представить в виде произведения простых множителей.

Хотя доказать основную теорему арифметики нетрудно, задача о разложении числа на простые множители на практике может оказаться неразрешимой.

89

К примеру, если n представляет собой произведение двух простых чисел р и q приблизительно из 400 знаков каждое, то для разложения n на простые множители даже самым мощным компьютерам потребуется время, сравнимое с возрастом Вселенной. Как вы увидите далее, это один из основных принципов криптографического алгоритма RSA, обеспечивающего безопасность всех наших компьютерных транзакций.

Введем новое понятие: для двух натуральных чисел m и n будем называть наибольшим общим делителем наибольшее натуральное число, на которое делятся одновременно m и n. Обозначим его НОД (m, n). Если нам известны разложения m и n на простые множители, найти НОД очень просто: нужно взять простые числа, которые содержатся в обоих разложениях, возведенные в наименьшую степень. Допустим, что мы хотим найти НОД 50 = 2 · 5² и 120 = 2 3· 3 · 5. Общие делители этих чисел — 2 и 5. В первом случае они возведены в степени 3 и 1, во втором — в степени 1 и 2.

Таким образом, НОД будет равен 2 1· 5 1= 10. Задача о разложении числа на простые множители на практике оказывается неразрешимой, поэтому для очень больших m и n описанный метод неприменим. К счастью, существует еще один метод расчета наибольшего общего делителя, который называется алгоритмом Евклида. Допустим, что m больше n. На первом шаге разделим m на n. Возможны два случая: если остаток от деления равен 0, то n — делитель m, следовательно, n — искомый НОД. В противном случае повторим деление, заменив m на n, а n — на остаток от деления r. Можно доказать, что наибольший общий делитель m и n совпадает с наибольшим общим делителем n и r [8] 1 Докажем это! Пусть d = НОД (m, n). Допустим, что результат деления m на n равен f, остаток равен r, то есть m = л/ + r. Заметим, что r делится на d. В самом деле, по определению существуют числа р и q такие, что m = dp и n = dq. Подставив эти выражения в первое равенство, получим: r = m — nt = dp — dqt = d (p — qt), следовательно, r делится на d. Чтобы показать, что НОД (n, r) = d, достаточно доказать, что эти два числа не могут иметь общий делитель, больший d. Это вновь следует из формулы m = nt + r: если бы такой делитель существовал, он также был бы делителем m, следовательно, был бы общим делителем m и n, большим d, но d — наибольший общий делитель по определению. .

Вернемся к нашему примеру: остаток от деления 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. Это соотношение называется соотношением Безу.