До предела чисел. Эйлер. Математический анализ

где π(x) — число простых чисел, меньших х. Эта теорема была доказана независимо друг от друга математиками Шарлем Жаном де ла Валле Пуссеном (1866-1962) и Жаком Адамаром (1865-1963) в 1896 году. Бернхард Риман расширил идеи Эйлера до области комплексных чисел С, применив к ней дзета- функцию (мы говорили о ней в главе 2), которую сам Эйлер рассматривал только в области вещественных чисел R. Затем был совершен переход к так называемой аналитической теории чисел, а позже — к оставшейся недоказанной гипотезе Римана.

ФУНКЦИЯ φ

В арифметике существует понятие не только простого числа, но и взаимно простых чисел. Целые положительные числа р и q являются взаимно простыми, если у них нет общих делителей, кроме 1. Например, 14 и 15 — взаимно простые, поскольку, даже если ни одно из них не является простым само по себе, у них нет общего делителя, кроме 1:

14-2-7

15-3-5.

То же самое можно выразить более современным способом, используя понятие наибольшего общего делителя (НОД). Сказать, что p и q являются взаимно простыми, — равноценно тому, что их НОД - 1.Функция, которую Эйлер называл φ(n), определяется как количество взаимно простых чисел, меньших п и взаимно простых с ним. Возьмем для примера числа от 1 до 10:

φ(1) = 1

φ(2) = 1

φ(3) = 2

φ(4) = 2

φ(5) = 4

φ(6) = 2

φ(7) = 6

φ(8) = 4

φ(9) = 6

φ(10) = 4.

Функция φ(n) называется индикаторной функцией; это не просто довольно интересная арифметическая игрушка, а инструмент, который можно широко использовать; она встречается в одной из самых важных теорем теории чисел — так называемой малой теореме Ферма. Как ни странно, вопреки тому, что Эйлер обычно сам вводил математические обозначения в своих работах, знак функции <р принадлежит не ему. Он доказал, что если р ид взаимно простые, то

φ(pq) = φ(p)φ(q)·

К тому же, если р — простое число, то φ(р) = р-1. Эйлеру же принадлежит следующий результат (хотя к нему подошли и раньше): если p и q — взаимно простые числа, то верна так называемая малая теорема Ферма:

p^φ(q) ≡ 1 mod q,

где mod q — модуль q и означает, что pφ(q) и 1 имеют одинаковый остаток при делении на q. Эта теорема была доказана Эйлером в 1736 году, в Theorematum Quorundam ad Numéros Primos Spectantium Demonstratio ("Доказательство некоторых теорем о простых числах"), и в прошлом имела сжатую форму, которую придал ей сам Ферма. Если мы предположим, что q простое число, то φ(q) = q - 1. и мы получим оригинальную запись Ферма:

p^q-1 ≡ 1 mod q,

где q — простое число, а р и q — взаимно простые. Эйлер нашел еще по меньшей мере три доказательства этой теоремы, хотя можно почти с полной уверенностью утверждать, что он не знал, кто являлся автором оригинальной теоремы.

Эта теорема лежит в основе самого известного в мире криптографического современного алгоритма с открытым ключом RSA, о чем рассказывается в приложении 6.

МАРЕН МЕРСЕНН