φ(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. и мы получим оригинальную запись Ферма:
pq-1 ≡ 1 mod q,
где q — простое число, а р и q — взаимно простые. Эйлер нашел еще по меньшей мере три доказательства этой теоремы, хотя можно почти с полной уверенностью утверждать, что он не знал, кто являлся автором оригинальной теоремы.
Эта теорема лежит в основе самого известного в мире криптографического современного алгоритма с открытым ключом RSA, о чем рассказывается в приложении 6.
МАРЕН МЕРСЕНН
Марен Мерсенн (1588-1648) был священником, музыкантом, математиком, философом и теологом, хотя его настоящим призванием была музыка, которой он посвятил большую часть своих сил. Не случайно во многих источниках его называют отцом акустики. Мерсенн установил основные законы вибрации струн, занимался вопросами гармонии и инструментальной музыки. Существует мнение, что во второй сюите Отторино Респиги "Старинные танцы и арии для лютни· есть фрагмент, написанный Мерсенном. Он также серьезно изучал телескопы и зеркала, став авторитетом в этой области. Мерсенн вел обширнейшую переписку и был в центре научных новостей в эпоху, когда они еще очень редко публиковались для широкой публики. Благодаря своим разносторонним интересам он познакомился со многими интеллектуалами своего времени, с которыми поддерживал отношения и завел дружбу, в частности с Декартом. Обладая рассудительным и рациональным умом, Мерсенн активно боролся с иррациональными верованиями — каббалой и магией. Он увлекался математикой и опубликовал различные работы древнегреческих авторов, таких как Архимед и Евклид, а также занимался числами. По мнению ученых, именно в этой области он сделал свой основной вклад, поэтому числа, которые он изучал, вида
МР ≡ 2Р - 1,
были названы числами Мерсенна. Сегодня существует генератор псевдослучайных чисел, связанных с простыми числами Мерсенна, который носит имя ученого, — вихрь Мерсенна.
ЧИСЛА МЕРСЕННА
Эйлер хотел найти простые числа больших размеров. Многие математики до него ошибочно предполагали, что все числа Мр вида Мр = 2р - 1, где Р — простое число, простые. Пьетро Катальди (1548-1626) в 1588 году доказал, что M17 и М19 простые, при помощи немного устаревшего, но стандартного для того времени метода, состоявшего в том, чтобы попытаться разделить их на простые числа, меньшие их квадратного корня. Впоследствии Марен Мерсенн, в честь которого эти числа обозначаются буквой М, составил целый список предполагавмых простых чисел, оказавшийся неточным, так как М67 и М257 повторялись два раза, а M61, M89 и M107 в нем не было. Сегодня самым большим числом является M43112609, в котором 12978189 цифр, в полном виде оно займет 50 таких книг, как эта.
В 1772 году Эйлер доказал, что число M31 простое. Любопытно, что прошло более 100 лет, прежде чем было найдено следующее простое число — M127. Сделал это французский математик Эдуард Люка (1842-1891) в 1876 году. Также простыми являются M61 и M89, но они были открыты позже. Таким образом, на протяжении 104 лет Эйлеру принадлежал рекорд по открытию самого большого простого числа.
КВАДРАТИЧНЫЙ ЗАКОН ВЗАИМНОСТИ
Квадратичный закон взаимности, превосходно сформулированный Гауссом в его Disquisitiones arithmeticae ("Арифметические исследования"), появился у Лежандра и Эйлера, который рассказал о нем Гольдбаху в письме 1742 года. Для начала определим, что такое символы Лежандра (p/q).
Предположим, что p и q — разные простые нечетные числа и
(p/q) =
0, если р ≡ 0 (mod q)
1, если х2 ≡ р (mod q) разрешимое уравнение
-1, если х2 ≡ p (mod q) неразрешимое уравнение.
Таким образом, Гауссу, а не Эйлеру, удалось доказать, что
(p/q) =
(q/p), если q ≡ 1 (mod 4)
(-q/p), если q ≡ 3 (mod 4)
Это можно выразить, хотя это и непросто, в одной формуле. Гаусс сделал это открытие в 19 лет и так гордился им, что назвал его aurum theorema — "золотой теоремой".
ДРУЖЕСТВЕННЫЕ И СОВЕРШЕННЫЕ ЧИСЛА
Делитель d произвольного числа n называется собственным делителем n, если 1 ≤ d < n. Число n — несобственный делитель n. Первое серьезное исследование Эйлера в области дружественных чисел относится к 1747 году. Два числа считаются дружественными, если сумма собственных делителей одного равна другому и наоборот. Это арифметическое понятие "дружбы" можно проиллюстрировать следующим примером. Возьмем числа 220 и 284. Собственными делителями 220 будут 1, 2, 4, 10,11,20,22,44,55 и 110; а 284 -1,2,4,71 и 142. Получаем, что
220 =1 + 2 + 4 + 10+11+20 + 22 + 44 + 55 + 110 = 284
284 = 1 +2 + 4 + 71 + 142 = 220.
АДРИЕН МАРИ ЛЕЖАНДР
Научная жизнь Лежандра (1752- 1833) началась под счастливой звездой. Он обладал выдающимися интеллектуальными способностями и достаточным состоянием, чтобы посвятить себя работе, ни на что не отвлекаясь. Успехов в математике Лежандр добился не сразу. Вместе с Лапласом он сделал важные разработки в области астрономии, открыв многочлены, позже названные многочленами Лежандра, зашел на малоизвестную территорию эллиптических функций и теории чисел, в рамках которой ему удалось, как он считал, решить старую задачу о квадратичном законе взаимности. Но в его исследовании были ошибки, как впоследствии установил Карл Фридрих Гаусс. За свои астрономические работы Лежандр был принят в члены Лондонского королевского общества. Он также участвовал в работе комиссии по созданию десятичной метрической системы, входившей в программу всеобщей рационализации, начатой после Французской революции. Хотя Лежандр и разделял многие революционные идеи, в эпоху Террора он был вынужден скрываться и потерял свое состояние. После этого он переписал и издал "Начала" Евклида с точки зрения того времени и современным языком, получив оглушительный и долгий успех у читателей. Придя к власти, Наполеон сразу же взял Лежандра под свою протекцию. Ученый, бывший к тому времени уже известным академиком, занялся изучением движения комет, разработал метод наименьших квадратов для вычисления траекторий, опередив на сей раз Гаусса. К этому же периоду относятся его исследования по распределению простых чисел, которое, как он предположил, подчинялось асимптотическому закону:
Это значение, очень близкое к современному, впоследствии совпало с фундаментальной теоремой о распределении простых чисел. Гаусс здесь оказался первым, но он так и не опубликовал свои результаты.
Приложение
1. ЛОГАРИФМЫ И НЕПЕР
Джон Непер (1550-1617) может по праву считаться изобретателем логарифмов. Он нарисовал две прямые линии следующим образом: на первой отложил отрезок с концами А и В, а параллельно ему провел прямую из точки А'. Затем он предположил, что есть некое тело, которое скользит по бесконечной прямой с постоянной скоростью. В каждой точке X' на прямой он отмечал соответствующую точку на отрезке АВ, но не случайным образом: X двигался со скоростью, равной расстоянию ХВ. Взяв х = ВХ и у = А'Х', Непер создал свой логарифм:
у - logx.
Непер взял AB - 107, что привело его к довольно сложным алгебраическим равенствам. Если N — число, a L — логарифм, то Непер вычислил N = 107 (1-10-7)L. Мы получаем
Здесь уже появляется постоянная е, так как
(1 - 10-7)107 ≈ 1/e.
Во многих старинных трактатах говорится о логарифмах Непера, или натуральных. Здесь мы имеем дело с путаницей, потому что натуральные логарифмы — это логарифмы по основанию е, в то время как все (почти) логарифмы Непера имеют основание 1/е. Это почти одно и то же, они различаются лишь знаком, а не абсолютным значением:
