Функція Ейлера

Функція Ейлера , де натуральне число, — це цілочисельна функція, яка показує кількість натуральних чисел, що не є більшими за і взаємно простих з ним.[1]

Перша тисяча значень

Функцію Ейлера можна подати у вигляді так званого добутку Ейлера:

де просте число.

Функція Ейлера широко застосовується в теорії чисел та криптографії. Зокрема відіграє значну роль у визначенні алгоритма шифрування RSA.

Деякі значення функції

+0+1+2+3+4+5+6+7+8+9
0+  112242646
10+ 41041268816618
20+ 812102282012181228
30+ 8301620162412361824
40+ 16401242202422461642
50+ 20322452184024362858
60+ 16603036324820663244
70+ 24702472364036602478
80+ 32544082246442564088
90+ 24724460467232964260

Властивості

  1. , якщо — просте число;[2]
  2. , якщо і взаємно прості. Тобто Функція Ейлера мультиплікативна;[3]
  3. , якщо і взаємно прості. Докладніше: Теорема Ейлера.[4]
  4. , , , якщо найменше спільне кратне, a найбільший спільний дільник.

Асимптотичні відношення

  1. де — деяка константа;

Комп'ютерна реалізація

C++

Pascal

Python

Примітки

  1. Ribenboim, 1996, с. 34(англ.).
  2. Сагалович, 2007, с. 35—36, Вычисление функции Эйлера(рос.).
  3. Burton, 2007, с. 133, Theorem 7.2(англ.).
  4. Чандрасекхаран. Введение в аналитическую теорию чисел, 1974 (рос.).

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.