-
Эйлер продолжил исследование числовых свойств.
-
В особенности распределение простых чисел.
-
Одной из важнейших функций, которую он определил,
-
является функция Фи.
-
Она измеряет "раскладываемость" числа.
-
То есть для числа, скажем N,
-
значение функции Фи -- это количество целых чисел меньших или равных N,
-
которые не имеют ни одного общего делителя с N.
-
Например, если нужно найти Фи от 8,
-
то надо посмотреть на все числа от 1 до 8
-
и посчитать с какими из них
-
у 8 нет ни одного общего делителя большего единицы.
-
Заметим, что 6 не считается,
-
так как делится на 2,
-
но 1, 3, 5 и 7 считаются,
-
потому что у них нет общего делителя (кроме 1).
-
Таким образом Фи(8) = 4.
-
Что интересно -- вычисление функции Фи
-
довольно сложное занятие, за исключением одного случая.
-
Взгляните на график!
-
На нем отмечены значения функции Фи для целых чисел от 1 до 1000.
-
Заметим предсказуемый шаблон.
-
Прямая линия точек вверху
-
показывает все простые числа.
-
Так как простые числа не имеют делителей больше 1,
-
значение Фи от любого простого P -- это просто P - 1.
-
Для вычисления Фи(7) -- простого числа, -- нужно
-
посчитать все целые числа от 1 до 7, исключая 7,
-
так как ни одно из них не имеет общего делителя с семеркой.
-
Фи(7) = 6.
-
Если нужно найти Фи от 21 377 (простое число),
-
для решения всего лишь нужно вычесть единицу и получить
-
21 376.
-
Фи от любого простого числа вычисляется очень просто.
-
У этого есть интересное следствие, основанное на том факте,
-
что функция Фи мультипликативна.
-
Это значит, что Фи(AxB) = Фи(A) x Фи(B).
-
Если нам известно, что некоторое число N -- это
-
произведение простых чисел P1 и P2,
-
то Фи(N) -- это просто произведение значений Фи
-
от каждого из них,
-
то есть (P1 - 1)x(P2 - 1).
