Пока алгебра не разлучит нас

Прежде чем приступить к изучению диофантовых уравнений, проясним некоторые понятия. Так как в моих заметках упоминаются различные классы чисел, скажем о них несколько слов. С одной стороны, существуют натуральные числа, которые используются при счете: 1, 2, 3... (к ним также иногда относят ноль). Для двух любых натуральных чисел определена операция сложения, однако она не может быть групповой: чтобы существовали обратные элементы, необходимо также рассмотреть отрицательные числа. Добавив отрицательные числа к натуральным, получим абелеву группу целых чисел: 0, 1,-1, 2,-2, 3,-3. В действительности на этой структуре определена не одна, а сразу две операции: мы можем не только складывать целые числа, но и перемножать их. Операция умножения ненулевых целых чисел также не является групповой. Так, чтобы, к примеру, элемент 2 имел обратный, необходимо рассмотреть число 1/2. Чтобы устранить этот недостаток, необходимо рассмотреть все дроби вида а/b (где а и b целые числа, b отлично от нуля), которые образуют множество рациональных чисел. Каждому из них мы можем поставить в соответствие периодическую десятичную дробь: к примеру, для 1/3 такой дробью будет 0,3333..., для 2/11 — 0,181818... Если мы будем рассматривать только периодические дроби, то такие простые уравнения, как х² = 2, не будут иметь решения, поскольку десятичная запись квадратного корня из 2 — непериодическая дробь.

88

Такие числа называются иррациональными. Чтобы получить еще больше решений, мы можем рассмотреть все десятичные дроби, в записи которых отсутствуют какиелибо закономерности. Такие числа называются вещественными.

Но вернемся к натуральным числам, которые Кронекер называл божьим творением. Для двух натуральных чисел m и n, m называется делителем n, если результат деления n на m — натуральное число. К примеру, 2 — делитель 10, так как 10 при делении на 2 дает 5 — натуральное число; 2 не является делителем 15, так как 15 при делении на 2 дает 7,5 — «некруглое» число. Если n делится на m, то существует натуральное число k такое, что n будет произведением m и k: n = m · k. Обратите внимание, что делители числа всегда меньше либо равны ему, и любое число делится на единицу и само себя. В некоторых случаях число делится только на единицу и само себя — такие числа называются простыми. Так, 5 — простое число, так как ни 2, ни 3, ни 4 не являются его делителями, а 6 не является простым, так как делится на 2 и на 3. Первые простые числа — 2, 3, 5, 7, 11, 13, 17, 19, 23... Можно доказать, что простых чисел бесконечно много.

Простые числа составляют основу всей арифметики: через них определяются все остальные числа. В самом деле, если 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 · 5. Общие делители этих чисел — 2 и 5. В первом случае они возведены в степени 3 и 1, во втором — в степени 1 и 2.