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) был священником, музыкантом, математиком, философом и теологом, хотя его настоящим призванием была музыка, которой он посвятил большую часть своих сил. Не случайно во многих источниках его называют отцом акустики. Мерсенн установил основные законы вибрации струн, занимался вопросами гармонии и инструментальной музыки. Существует мнение, что во второй сюите Отторино Респиги "Старинные танцы и арии для лютни· есть фрагмент, написанный Мерсенном. Он также серьезно изучал телескопы и зеркала, став авторитетом в этой области. Мерсенн вел обширнейшую переписку и был в центре научных новостей в эпоху, когда они еще очень редко публиковались для широкой публики. Благодаря своим разносторонним интересам он познакомился со многими интеллектуалами своего времени, с которыми поддерживал отношения и завел дружбу, в частности с Декартом. Обладая рассудительным и рациональным умом, Мерсенн активно боролся с иррациональными верованиями — каббалой и магией. Он увлекался математикой и опубликовал различные работы древнегреческих авторов, таких как Архимед и Евклид, а также занимался числами. По мнению ученых, именно в этой области он сделал свой основной вклад, поэтому числа, которые он изучал, вида