До предела чисел. Эйлер. Математический анализ - [30]
то есть аналог гармонического ряда
также расходится. Кроме того, несмотря на то что гармонический ряд расходится приблизительно как логарифм л, ряд обратных простых чисел расходится еще медленнее, как логарифм логарифма n.
Идеи Эйлера, считающегося изобретателем методов анализа в теории чисел, были развиты вначале Лежандром, а затем Гауссом, отцами теоремы о распределении простых чисел, которая гласит:
π(x = x/Inx
где π(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.
Марен Мерсенн (1588-1648) был священником, музыкантом, математиком, философом и теологом, хотя его настоящим призванием была музыка, которой он посвятил большую часть своих сил. Не случайно во многих источниках его называют отцом акустики. Мерсенн установил основные законы вибрации струн, занимался вопросами гармонии и инструментальной музыки. Существует мнение, что во второй сюите Отторино Респиги "Старинные танцы и арии для лютни· есть фрагмент, написанный Мерсенном. Он также серьезно изучал телескопы и зеркала, став авторитетом в этой области. Мерсенн вел обширнейшую переписку и был в центре научных новостей в эпоху, когда они еще очень редко публиковались для широкой публики. Благодаря своим разносторонним интересам он познакомился со многими интеллектуалами своего времени, с которыми поддерживал отношения и завел дружбу, в частности с Декартом. Обладая рассудительным и рациональным умом, Мерсенн активно боролся с иррациональными верованиями — каббалой и магией. Он увлекался математикой и опубликовал различные работы древнегреческих авторов, таких как Архимед и Евклид, а также занимался числами. По мнению ученых, именно в этой области он сделал свой основной вклад, поэтому числа, которые он изучал, вида
М>Р ≡ 2>Р - 1,
были названы числами Мерсенна. Сегодня существует генератор псевдослучайных чисел, связанных с простыми числами Мерсенна, который носит имя ученого, — вихрь Мерсенна.
Эйлер хотел найти простые числа больших размеров. Многие математики до него ошибочно предполагали, что все числа М>р вида М>р = 2>р - 1, где Р — простое число, простые. Пьетро Катальди (1548-1626) в 1588 году доказал, что M>17 и М>19 простые, при помощи немного устаревшего, но стандартного для того времени метода, состоявшего в том, чтобы попытаться разделить их на простые числа, меньшие их квадратного корня. Впоследствии Марен Мерсенн, в честь которого эти числа обозначаются буквой М, составил целый список предполагавмых простых чисел, оказавшийся неточным, так как М
