Функція Ейлера , де — натуральне число, — це цілочисельна функція, яка показує кількість натуральних чисел, що не більші ніж і взаємно прості з ним. Функцію Ейлера можна подати у вигляді так званого добутку Ейлера:
де — просте число.
Функція Ейлера широко застосовується в теорії чисел та криптографії. Зокрема відіграє значну роль у визначенні алгоритму шифрування RSA.
Деякі значення функції +0 +1 +2 +3 +4 +5 +6 +7 +8 +9 0+ 1 1 2 2 4 2 6 4 610+ 4 10 4 12 6 8 8 16 6 1820+ 8 12 10 22 8 20 12 18 12 2830+ 8 30 16 20 16 24 12 36 18 2440+ 16 40 12 42 20 24 22 46 16 4250+ 20 32 24 52 18 40 24 36 28 5860+ 16 60 30 36 32 48 20 66 32 4470+ 24 70 24 72 36 40 36 60 24 7880+ 32 54 40 82 24 64 42 56 40 8890+ 24 72 44 60 46 72 32 96 42 60
Властивості , якщо — просте число; , якщо і взаємно прості. Тобто Функція Ейлера мультиплікативна; , якщо і взаємно прості. Докладніше: Теорема Ейлера.
, , , якщо — найменше спільне кратне, a — найбільший спільний дільник.
Асимптотичні відношення де — деяка константа;
Комп'ютерна реалізація C++
Pascal
Python
Ruby
Див. також Псі-функція Дедекінда Теорема Ейлера (теорія чисел) Функція Мебіуса
Примітки
Посилання Онлайн обчислювач функції Ейлера на JavaScript - до 20 цифр