Ейлер продовжив досліджувати властивості чисел,
особливо - розподіл простих чисел.
Одна важлива функція, яку він визначив,
називається "функція Фі".
Вона вимірює перервність числа
Отже, маємо число, скажімо 'n',
воно дорівнює кількості цілих чисел, які є меншими за n ,або дорівнюють n
і не мають з ним ніяких спільних дільників (СД).
Наприклад, якщо ми хочемо знайти Фі від 8-ми,
ми переглядаємо усі величини від 1 до 8
і рахуємо, зі скількома цілими числами
8 не має більше 1-го спільного дільника.
Зверніть увагу, що 6 не рахується,
тому що 6 і 8 мають спільний дільник 2,
а 1, 3, 5 і 7 - рахуються,
тому що їхній СД з числом 8 - лише число 1.
Отже, Фі(8) = 4).
Цікаво, що
розрахунок функції Фі - складний, крім одного випадку.
Погляньте на графік.
Це - ділянка значень Фі за цілими числами від 1 до 1000.
Тепер, помічаєте якийсь передбачуваний шаблон?
Пряма лінія точок згори
відображає усі прості числа.
Так як прості числа не мають дільників, більших за 1,
фі будь-якого простого числа 'p' - це просто p - 1.
Щоб розрахувати фі простого числа 7,
ми рахуємо усі цілі числа крім числа 7,
оскільки жодне з них не має спільного дільника з 7.
Фі числа 7 = 6.
Отже, якщо вам треба знайти фі простого числа 21,337,
вам треба лише відняти 1, і ви матимете відповідь -
21,376.
Фі будь-якого простого числа легко порахувати.
Це приводить до цікавих результатів, заснованих на тому, що
функція фі також є "мультиплікативною".
Тобто, фі(A x B)=фі(A) x фі(B).
Якщо ми знаємо, що деяке число N
є добутком двох простих чисел, P1 і P2,
то фі(N) це просто добуток
значень фі для кожного простого числа,
або (P1 - 1) x (P2 - 1).
Переклад на українську: Роман Берла, рев’ювер Оксана Кузьменко, благодійний фонд “Magneticone.org”