www.wikidata.uk-ua.nina.az

Функція Ейлера φ n displaystyle varphi n де n displaystyle n натуральне число це цілочисельна функція яка показує кількі

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

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

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

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

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

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

Деякі значення функції Редагувати

+0 +1 +2 +3 +4 +5 +6 +7 +8 +9
0+   1 1 2 2 4 2 6 4 6
10+ 4 10 4 12 6 8 8 16 6 18
20+ 8 12 10 22 8 20 12 18 12 28
30+ 8 30 16 20 16 24 12 36 18 24
40+ 16 40 12 42 20 24 22 46 16 42
50+ 20 32 24 52 18 40 24 36 28 58
60+ 16 60 30 36 32 48 20 66 32 44
70+ 24 70 24 72 36 40 36 60 24 78
80+ 32 54 40 82 24 64 42 56 40 88
90+ 24 72 44 60 46 72 32 96 42 60

Властивості Редагувати

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

Асимптотичні відношення Редагувати

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

Комп'ютерна реалізація Редагувати

C++ Редагувати

Pascal Редагувати

Python Редагувати

Ruby Редагувати

Див. також Редагувати

Примітки Редагувати

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

Посилання Редагувати

Це незавершена стаття з математики.
Ви можете допомогти проєкту, виправивши або дописавши її.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Funkciya Ejlera f n displaystyle varphi n de n displaystyle n naturalne chislo ce cilochiselna funkciya yaka pokazuye kilkist naturalnih chisel sho ne ye bilshimi za n displaystyle n i vzayemno prostih z nim 1 Persha tisyacha znachen f n displaystyle varphi n Funkciyu Ejlera mozhna podati u viglyadi tak zvanogo dobutku Ejlera f n n p n 1 1 p displaystyle varphi n n prod p mid n left 1 frac 1 p right de p displaystyle p proste chislo Funkciya Ejlera shiroko zastosovuyetsya v teoriyi chisel ta kriptografiyi Zokrema vidigraye znachnu rol u viznachenni algoritma shifruvannya RSA Zmist 1 Deyaki znachennya funkciyi 2 Vlastivosti 3 Asimptotichni vidnoshennya 4 Komp yuterna realizaciya 4 1 C 4 2 Pascal 4 3 Python 4 4 Ruby 5 Div takozh 6 Primitki 7 PosilannyaDeyaki znachennya funkciyi Redaguvatif n displaystyle varphi n nbsp 0 1 2 3 4 5 6 7 8 90 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 60Vlastivosti Redaguvatif p n p 1 p n 1 displaystyle varphi p n p 1 p n 1 nbsp yaksho p displaystyle p nbsp proste chislo 2 f m n f m f n displaystyle varphi mn varphi m varphi n nbsp yaksho m displaystyle m nbsp i n displaystyle n nbsp vzayemno prosti Tobto Funkciya Ejlera multiplikativna 3 a f m 1 mod m displaystyle a varphi m equiv 1 pmod m nbsp yaksho a displaystyle a nbsp i m displaystyle m nbsp vzayemno prosti Dokladnishe Teorema Ejlera 4 f m k m k 1 f m displaystyle varphi m k m k 1 varphi m nbsp m n m n m n displaystyle mn m n m n nbsp f m f n f m n f m n displaystyle varphi m varphi n varphi m n varphi m n nbsp f m n f m n f m f n m n displaystyle varphi mn varphi m n varphi m varphi n m n nbsp yaksho m n displaystyle m n nbsp najmenshe spilne kratne a m n displaystyle m n nbsp najbilshij spilnij dilnik Asimptotichni vidnoshennya RedaguvatiC n ln ln n f n n displaystyle frac Cn ln ln n leqslant varphi n leqslant n nbsp de C displaystyle C nbsp deyaka konstanta n x f n 3 p 2 x 2 O x ln x displaystyle sum n leqslant x varphi n frac 3 pi 2 x 2 O x ln x nbsp k 1 n k f k O n displaystyle sum k 1 n frac k varphi k O n nbsp k 1 n 1 f k O ln n displaystyle sum k 1 n frac 1 varphi k O ln n nbsp Komp yuterna realizaciya RedaguvatiC Redaguvati Kod na movi C int phi int n int ret 1 for int i 2 i i lt n i int p 1 while n i 0 p i n i if p i gt 1 ret p i 1 return n n ret ret Pascal Redaguvati Kod na movi Pascal function gcd A B longint longint begin while A lt gt B do begin if A gt B then Dec A B else Dec B A end gcd A end var N longint I A longint begin WriteLn Input N ReadLn N A 0 for I 1 to N 1 do if gcd I N 1 then Inc A WriteLn The Euler Function of N is A ReadLn end Python Redaguvati Kod na movi Python def euler function n ret 1 for i in range 2 math floor n 0 5 p 1 while not n i p i n i p i if p gt 1 ret ret p i 1 n 1 return n ret if n else ret Kod vishe pri n 6 9 vidaye nepravilnij rezultat Perevireno dlya Python 3 11 u Visual Studio CodeNastupnij kod pracyuye korektno def euler function n ret 1 i 2 while i i lt n p 1 while not n i p i n i p i if p gt 1 ret ret p i 1 i 1 n 1 return n ret if n else ret Ruby Redaguvati Kod na movi Ruby def euler function n ret 1 for i in range 2 math floor n 0 5 p 1 while not n i p i n i p i if p gt 1 ret ret p i 1 n 1 return n ret if n else retDiv takozh RedaguvatiPsi funkciya Dedekinda Teorema Ejlera teoriya chisel Funkciya MebiusaPrimitki Redaguvati Ribenboim 1996 s 34 angl Sagalovich 2007 s 35 36 Vychislenie funkcii Ejlera ros Burton 2007 s 133 Theorem 7 2 angl Chandrasekharan Vvedenie v analiticheskuyu teoriyu chisel 1974 ros Posilannya RedaguvatiOnlajn obchislyuvach funkciyi Ejlera na JavaScript do 20 cifr angl nbsp Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Otrimano z https uk wikipedia org w index php title Funkciya Ejlera amp oldid 39032217