Funcția Euler

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 1 octombrie 2021; verificările necesită 3 modificări .

Funcția Euler este o funcție aritmetică multiplicativă a cărei valoare este egală cu numărul de numere naturale care sunt mai mici și coprime cu ea [1] . $\varphi (n)$ $n$

De exemplu, pentru numărul 36 există 12 numere mai mici și coprime (1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35), deci . $\varphi (36)=12$

Numit după Euler , care l-a folosit pentru prima dată în 1763 în lucrarea sa despre teoria numerelor pentru a demonstra mica teoremă a lui Fermat și apoi pentru a demonstra o afirmație mai generală - teorema lui Euler . Funcția a fost folosită mai târziu de Gauss în investigațiile sale aritmetice , publicate în 1801. Gauss a introdus notația acum standard [2] . $\varphi (n)$

Funcția Euler își găsește aplicație în chestiuni legate de teoria divizibilității și a reziduurilor (vezi comparația modulo ), teoria numerelor , criptografia . Funcția Euler joacă un rol cheie în algoritmul RSA [3] .

Calcul

Primele 99 de valori ale funcției Euler [4]

$\varphi (n)$	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
0+		unu	unu	2	2	patru	2	6	patru	6
10+	patru	zece	patru	12	6	opt	opt	16	6	optsprezece
20+	opt	12	zece	22	opt	douăzeci	12	optsprezece	12	28
30+	opt	treizeci	16	douăzeci	16	24	12	36	optsprezece	24
40+	16	40	12	42	douăzeci	24	22	46	16	42
50+	douăzeci	32	24	52	optsprezece	40	24	36	28	58
60+	16	60	treizeci	36	32	48	douăzeci	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

Informații generale

Funcția Euler arată câte numere naturale din intervalul c au un singur divizor comun - unu. Funcția Euler este definită pe mulțimea numerelor naturale , iar valorile sale se află în mulțimea numerelor naturale. $\varphi (n)$ $[1,\;n-1]$ $n$

După cum reiese din definiție, pentru a calcula , trebuie să parcurgeți toate numerele de la până la , și pentru fiecare verificați dacă are divizori comuni cu , apoi calculați câte numere s-au dovedit a fi coprime cu . Această procedură pentru numere mari necesită foarte mult timp, prin urmare, pentru calcul sunt utilizate alte metode , care se bazează pe proprietățile specifice ale funcției Euler. $\varphi (n)$ $unu$ $n-1$ $n$ $n$ $n$ $\varphi (n)$

Tabelul din dreapta arată primele 99 de valori ale funcției Euler. Analizând aceste date, puteți vedea că valoarea nu depășește , și este exact egală cu aceasta dacă - prim. Astfel, dacă o linie este trasată în coordonate , atunci valorile se vor afla fie pe această linie, fie sub ea. De asemenea, uitându-ne la graficul de la începutul articolului și la valorile din tabel, putem presupune că există o linie dreaptă care trece prin zero, care limitează valorile de jos. Cu toate acestea, se dovedește că o astfel de linie nu există. Adică, indiferent cât de superficială tragem o linie dreaptă, va exista întotdeauna un număr natural care se află sub această linie dreaptă. O altă caracteristică interesantă a graficului este prezența unor linii drepte de-a lungul cărora sunt concentrate valorile funcției Euler. Deci, de exemplu, pe lângă linia pe care se află valorile , unde este prim, se distinge o linie care corespunde aproximativ cu , pe care se încadrează valorile , unde este prim. $\varphi (n)$ $n-1$ $n$ $(n,\;y)$ $y=n-1$ $y=\varphi(n)$ $\varphi (n)$ $n$ $\varphi (n)$ $y=n-1$ $\varphi(n)=n-1$ $n$ $y=n/2$ $\varphi(2n)=\varphi(n)=n-1$ $n$

Comportamentul funcției Euler este discutat mai detaliat în secțiunea #Relații asimptotice .

Multiplicativitatea funcției Euler

Una dintre principalele proprietăți ale funcției Euler este multiplicativitatea acesteia . Această proprietate a fost stabilită de Euler și este formulată după cum urmează: pentru orice numere coprime și [5] $m$ $n$

\varphi(mn)=\varphi(m)\varphi(n).

Dovada multiplicativității

Pentru a demonstra multiplicativitatea funcției Euler, avem nevoie de următoarea teoremă auxiliară [6] .

Teorema 1. Fie și rulează prin sistemul complet de reziduuri modulo , în timp ce trece prin sistemul complet de reziduuri modulo . Apoi numerele formează un sistem complet de reziduuri modulo .

(m,\;m')=1

A

m

A'

m'

sunt + sunt

m

m'

Dovada. În cazul în care un

a_1'm+a_1m'\equiv a_2'm+a_2m'\pmod{mm'},

apoi

a_1m'\equiv a_2m'\pmod m,

de aceea

a_1\equiv a_2\pmod m;

de asemenea

a_1'\equiv a_2'\pmod{m'}.

Prin urmare, există numere modulo incomparabile care formează un sistem complet de resturi modulo .

mm'

mm'

Acum putem demonstra afirmația principală [7] .

Teorema 2. Funcția Euler este multiplicativă. Dovada. Dacă , atunci prin teorema 1 trece prin sistemul redus de reziduuri modulo , când și rulează prin sistemele reduse de reziduuri modulo și respectiv. De asemenea:

(m,\;m')=1

sunt + sunt

mm'

A

A'

m

m'

(a'm+am',\;mm')=1

\Leftrightarrow (a'm+am',\;m)=1,\;(a'm+am',\;m')=1

\Leftrightarrow (am',\;m)=1,\;(a'm,\;m')=1

\Leftrightarrow (a,\;m)=1,\;(a',\;m')=1.

Prin urmare, numerele care sunt mai mici decât un număr și coprime pentru acesta sunt cele mai mici reziduuri pozitive dintre valorile pentru care coprime la și coprime la . De aici rezultă că

\varphi(mm')

mm'

\varphi(m)\varphi(m')

sunt + sunt

A

m

A'

m'

\varphi(mm')=\varphi(m)\varphi(m').

Funcția Euler a unui număr prim

Pentru o valoare simplă a funcției Euler este dată de o formulă explicită [8] : $p$

\varphi(p)=p-1,

care rezultă din definiţie. Într-adevăr, dacă este un prim, atunci toate numerele mai mici decât sunt coprime pentru el și există exact unul dintre ele. $p$ $p$ $p-1$

Pentru a calcula funcția Euler a puterii unui număr prim, folosiți următoarea formulă [8] :

\varphi(p^n)=p^np^{n-1}.

Această egalitate este justificată după cum urmează. Să numărăm numărul de numere de la până la care nu sunt coprime până la . Toate, evident, sunt multiple , adică arată astfel: Total de astfel de numere . Prin urmare, numărul de numere coprime cu este egal cu . $unu$ $p^{n}$ $p^{n}$ $p$ $p,\;2p,\;3p,\;\ldots ,\;p^{n-1}p.$ $p^{n-1}$ $p^{n}$ $p^{n}-p^{n-1)$

Funcția Euler a unui număr natural

Calculul pentru o natură arbitrară se bazează pe multiplicativitatea funcției Euler, expresia pentru și, de asemenea, pe teorema fundamentală a aritmeticii . Pentru un număr natural arbitrar, valoarea este reprezentată ca [8] : $\varphi (n)$ $n$ $\varphi(p^{n})$ $\varphi (n)$

\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right),\;\;n>1,

unde este un număr prim și trece prin toate valorile implicate în descompunerea în factori primi. $p$ $n$

Dovada

După cum rezultă din teorema fundamentală a aritmeticii , orice număr natural este reprezentat în mod unic sub forma: $n>1$

n=p_1^{\alpha_1}\cdot\ldots\cdot p_k^{\alpha_k},

unde sunt numere prime și sunt numere naturale. $p_1<\ldots<p_k$ $\alpha_1,\;\ldots,\;\alpha_k$

Folosind multiplicativitatea funcției Euler și expresia pentru , obținem: $\varphi(p^{k})$ ${\begin{aliniat}\varphi (n)&=\varphi (p_{1}^{\alpha _{1)))\varphi (p_{2}^{\alpha _{2))} \cdot \ldots \cdot \varphi (p_{k}^{\alpha _{k)))=\\&=p_{1}^{\alpha _{1))\left(1-{\frac { 1}{p_{1}}}\right)p_{2}^{\alpha _{2}}\left(1-{\frac {1}{p_{2}}}\right)\cdot \ldots \cdot p_{k}^{\alpha _{k}}\left(1-{\frac {1}{p_{k}}}\right)=\\&=p_{1}^{\alpha _ {1}}p_{2}^{\alpha _{2}}\cdot \ldots \cdot p_{k}^{\alpha _{k}}\left(1-{\frac {1}{p_{ 1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdot \ldots \cdot \left(1-{\frac {1}{p_{k} }}\right)=\\&=n\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}} \right)\cdot \ldots \cdot \left(1-{\frac {1}{p_{k}}}\right).\end{aliniat}}$

Exemplu de aplicare: $\varphi (36)=\varphi (2^{2}\cdot 3^{2})=\varphi (2^{2})\varphi (3^{2})=(2^{2} }-2)(3^{2}-3)=2\cdot 6=12.$

Proprietăți

Multiplicativitate generalizată

Funcția Euler este o funcție aritmetică multiplicativă , adică

\varphi (mn)=\varphi (m)\varphi (n)\;\;\;\forall m,\,n\in \mathbb {N} \colon (m,\,n)=1 .

Este esențial aici ca cel mai mare divizor comun și să fie egal cu unu. Rezultă că există o generalizare a acestei formule în cazul în care și au divizori comuni alții decât unitatea. Și anume, pentru orice natură și [9] : $m$ $n$ $m$ $n$ $m$ $n$

\varphi(m \cdot n) = \varphi(m) \cdot \varphi(n)\cdot\frac{d}{\varphi(d)},

unde este cel mai mare divizor comun și Această proprietate este o generalizare naturală a multiplicativității. $d$ $m$ $n.$

Dovada multiplicativității generalizate

Fie atunci și în cazul general și Prin urmare, putem scrie: $(m,\,n)=d,$ $m = m'd, \; n = n'd,$ $(m',\,d)\neq 1$ $(n',\,d)\neq 1.$

d=d_{1}^{\delta _{1))\cdot \ldots \cdot d_{k}^{\delta _{k))\cdot d_{k+1}^{\delta _ {k+1}}\cdot \ldots \cdot d_{K}^{\delta _{K)),

m'=d_{1}^{\alpha _{1))\cdot \ldots \cdot d_{k}^{\alpha _{k))\cdot p_{1}^{\beta _{ 1))\cdot \ldots \cdot p_{r}^{\beta _{r)),

n'=d_{k+1}^{\gamma _{k+1}}\cdot \ldots \cdot d_{K}^{\gamma _{K}}\cdot q_{1}^{ \varepsilon _{1}}\cdot \ldots \cdot q_{s}^{\varepsilon _{s}}.

Aici primii divizori sunt și divizori, iar ultimii divizori sunt divizori Să scriem: $k$ $d$ $m',$ $Kk$ $d$ $n'.$

\varphi (mn)=\varphi (d^{2}\cdot m'n')=\varphi ((d_{1}^{\delta _{1))\cdot \ldots \cdot d_{ k}^{\delta _{k}}\cdot d_{k+1}^{\delta _{k+1}}\cdot \ldots \cdot d_{K}^{\delta _{K}}) ^{2}\cdot d_{1}^{\alpha _{1}}\cdot \ldots \cdot d_{k}^{\alpha _{k}}\cdot p_{1}^{\beta _{ 1}}\cdot \ldots \cdot p_{r}^{\beta _{r}}\cdot d_{k+1}^{\gamma _{k+1}}\cdot \ldots \cdot d_{K }^{\gamma _{K}}\cdot q_{1}^{\varepsilon _{1}}\cdot \ldots \cdot q_{s}^{\varepsilon _{s}}).

Datorită multiplicativității funcției Euler și luând în considerare și formula

\varphi(p^n) = p^n(1-\frac{1}{p}),

unde este primul, obținem: $p$

{\begin{aliniat}\varphi (mn)&=d_{1}^{\alpha _{1}+\delta _{1}}\left(1-{\frac {1}{d_{ 1}}}\right)\cdot \ldots \cdot d_{k}^{\alpha _{k}+\delta _{k}}\left(1-{\frac {1}{d_{k}} }\right)\cdot p_{1}^{\beta _{1}}\left(1-{\frac {1}{p_{1}}}\right)\cdot \ldots \cdot p_{r} ^{\beta _{r}}\left(1-{\frac {1}{p_{r}}}\right)\cdot d_{k+1}^{\delta _{k+1}}\ stânga(1-{\frac {1}{d_{k+1}}}\right)\cdot \ldots \cdot d_{K}^{\delta _{K}}\left(1-{\frac { 1}{d_{K))}\right)\times \\&\;\times \;d_{k+1}^{\gamma _{k+1}+\delta _{k+1}}\ stânga(1-{\frac {1}{d_{k+1}}}\right)\cdot \ldots \cdot d_{K}^{\gamma _{K}+\delta _{K}}\left (1-{\frac {1}{d_{K}}}\right)\cdot q_{1}^{\varepsilon _{1}}\left(1-{\frac {1}{q_{1} }}\right)\cdot \ldots \cdot q_{s}^{\varepsilon _{s}}\left(1-{\frac {1}{q_{s}}}\right)\cdot d_{1 }^{\delta _{1}}\left(1-{\frac {1}{d_{1}}}\right)\cdot \ldots \cdot d_{k+1}^{\delta _{k +1}}\left(1-{\frac {1}{d_{k+1}}}\right)\times \\&\;\times \;{\frac {1}{\left(1- {\frac {1}{d_{1}}}\right)\cdot \ldots \cdot \left(1-{\fr  ac {1}{d_{K}}}\right)}}.\end{aliniat}}

Prima linie este scrisă în a doua - iar a treia poate fi reprezentată astfel : $\varphi(m),$ $\varphi(n),$ $d/\varphi(d).$

\varphi(m \cdot n) = \varphi(m) \cdot \varphi(n) \cdot \frac{d}{\varphi(d)}.

Cateva cazuri speciale:

$\;\varphi\left(n^m\right) = n^{m-1}\varphi(n).$
$\varphi (2m)={\begin{cases}2\varphi (m),&m=2k,\;k\in \mathbb {N} ,\\\varphi (m),&m=2k-1 ,\;k\în \mathbb {N} .\end{cazuri}}$
$\varphi(M)\cdot\varphi(d) = \varphi(m)\cdot\varphi(n),$ unde este cel mai mic multiplu comun al și , și este cel mai mare divizor comun al acestora. $M$ $m$ $n$ $d$

Teorema lui Euler

Proprietatea stabilită de Euler este folosită cel mai des în practică :

a^{\varphi(m)}\equiv 1\pmod m,

dacă și sunt relativ prime . Această proprietate, care se numește teorema lui Euler , rezultă din Teorema lui Lagrange și din faptul că este egală cu ordinea grupului multiplicativ de elemente inversabile a inelului de reziduuri modulo . Ca o consecință a teoremei lui Euler, se poate obține mica teoremă a lui Fermat . Pentru a face acest lucru, trebuie să luați nu arbitrar , ci simplu. Apoi: $A$ $m$
$\varphi(m)$ $m$
$m,$

a^{m - 1}\equiv 1\pmod m.

Ultima formulă își găsește utilizare în diferite teste de primalitate .

Alte proprietăți

Pe baza reprezentabilității produsului Euler, este ușor să obțineți următoarea declarație utilă: $\varphi (n)$

a\mid b \Rightarrow \varphi(a)\mid\varphi(b).

Următoarea egalitate [10] [11] este o consecință a teoremei Zsigmondy :

\varphi (a^{n}+b^{n})\equiv 0{\pmod {n)),\;a>b\geqslant 1.

Orice număr natural poate fi reprezentat ca suma valorilor funcției Euler de la divizorii săi naturali [12] :

\sum_{d\mid n}\varphi(d)=n.

Suma tuturor numerelor mai mici decât un număr dat și relativ prime pentru acesta este exprimată în termenii funcției Euler:

\sum_{1\leqslant k\leqslant n\atop(k,\;n)=1}k=\frac{1}{2}n\varphi(n), \; n > 1.

Multe valori

Studiul structurii setului de valori al funcției Euler este o sarcină dificilă separată. Doar câteva dintre rezultatele obținute în acest domeniu sunt prezentate aici [13] .

Funcția Euler ia doar valori pare pentru În plus, dacă are divizori primi impari diferiți, atunci $\varphi (n)$ $n > 2.$ $n$ $r$ $2^{r} \mid \varphi(n).$

Dovada (funcția Euler ia doar valori pare pentru n > 2) Într-adevăr, dacă este un număr prim impar și atunci

p

\alpha > 1

p^{\alpha - 1}(p - 1)

- chiar. Din egalitate

\varphi(n)=\prod_{i=1}^{k}p_i^{\alpha_i - 1}(p_i - 1)

urmează afirmaţia.

În analiza reală, se pune adesea problema găsirii valorii unui argument având în vedere valoarea unei funcții sau, cu alte cuvinte, problema găsirii funcției inverse . O problemă similară poate fi pusă pentru funcția Euler. Cu toate acestea, trebuie reținute următoarele.

Valorile funcției Euler sunt repetate (de exemplu, ), astfel încât funcția inversă este multivalorică . $\varphi(1) = \varphi(2) = 1$
Funcția Euler ia doar valori pare, adică dacă impar și $n > 2$ $\varphi ^{-1}(m)=\varnothing ,$ $m$ $m\neq 1.$

În acest sens, sunt necesare metode speciale de analiză. Un instrument util pentru studierea preimaginei este următoarea teoremă [14] . $\varphi$

Să - chiar, să punem $m$ $A(m)=m\prod _{p-1\mid m}{\frac {p}{p-1)),$ unde este simplu. $p$

Dacă atunci

n \in \varphi^{-1}(m),

m<n\leqslant A(m).

Demonstrarea teoremei Evident, dacă atunci Pe de altă parte, dacă și atunci

\varphi(n) = m,

m < n.

\varphi(n) = m

n=p_{1}^{\alpha _{1}}\cdot \ldots \cdot p_{s}^{\alpha _{s)),

m = n \prod_{i=1}^s \frac{p_i-1}{p_i} \; \Sageata dreapta\; n = m \prod_{i=1}^s \frac{p_i}{p_i-1}.

Totuși, dacă atunci deci

p\mid n,

p-1\mid \varphi (n).

\forall p_{i}:\;p_{i}-1\mid m.

prin urmare

n\leqslant A(m).

Această teoremă arată că imaginea inversă a unui element este întotdeauna o mulțime finită. De asemenea, oferă următorul mod practic de a găsi preimaginea: $m\in \mathbb {N}$

1) calcula ;

A.m)

2) se calculează pentru toate din semi-interval ;

\varphi (n)

n

(m,\,A(m)]

3) toate numerele pentru care formează imaginea inversă a elementului .

n,

\varphi(n)=m,

m

Se poate dovedi că nu există un astfel de număr în intervalul indicat, astfel încât în acest caz preimaginea să fie setul gol . Este de remarcat faptul că pentru calcul trebuie să cunoașteți descompunerea în factori primi, ceea ce pentru cei mari este o sarcină dificilă din punct de vedere computațional . Apoi trebuie să calculați funcția Euler o dată, ceea ce este, de asemenea, foarte consumator de timp pentru numere mari. Prin urmare, găsirea preimaginei în ansamblu este o problemă dificilă din punct de vedere computațional. $n,$ $\varphi(n)=m;$
$A.m)$ $m$ $m$ $A(m)-m$

Exemplul 1 (calcul înainte de imagine)

Să găsim preimaginea lui 4. Divizorii lui 4 sunt numerele 1, 2 și 4. Adăugând câte unul la fiecare dintre ele, obținem 2, 3, 5 - numere prime. calculati

A(4) = 4 \cdot \frac{2}{1} \cdot \frac{3}{2} \cdot \frac{5}{4} = 15.

Pentru a găsi preimaginea lui 4, este suficient să luăm în considerare numerele de la 5 la 15. După ce am făcut calculele, obținem:

\varphi ^{-1}(4)=\{5,\;8,\;10,\;12\}.

Exemplul 2 (Nu toate numerele pare sunt valori ale funcției Euler)

Nu există, de exemplu, un astfel de număr care să fie: $m,$ $\varphi(m) = 14.$

\varphi ^{-1}(14)=\varnothing .

Într-adevăr, divizorii lui 14 sunt 1, 2, 7 și 14. Adăugând câte unul, obținem 2, 3, 8, 15. Dintre acestea, doar primele două numere sunt prime. De aceea

A(14) = 14 \cdot \frac{2}{1} \cdot \frac{3}{2} = 42.

După sortarea tuturor numerelor de la 15 la 42, este ușor de verificat

\varphi (n)\neq 14,\;n\in (15,\,42].

Relații asimptotice

Cele mai simple inegalități

Limita inferioară pentru valorile funcției Euler [15] [16] : $\varphi (n)\geqslant {\sqrt {n}),$

pentru toată lumea, cu excepția

n,

n=2

n = 6.

O limită superioară pentru compozit [15] [17] : $n$ $\varphi (n)\leqslant n-{\sqrt {n)),$

pentru orice compus

n.

Pentru toate valorile naturale , inegalitatea dublă este valabilă [15] : $n\geqslant 3$ $\frac{\log2}{2} \cdot \frac{n}{\log{n}} < \varphi(n) < n.$

Comparația lui φ( n ) cu n

Limita superioară a raportului se apropie de unitate cu creștere [18] : $\varphi(n)/n$ $n$ $\varlimsup \frac{\varphi(n)}{n} = 1.$
În același timp, raportul poate fi arbitrar mare [19] : $\varphi(n)/n^{1-\delta}$ $\forall \delta >0\colon {\frac {\varphi (n)}{n^{1-\delta ))}\rightarrow \infty .$

Raportul valorilor succesive

Următoarele egalități arată cât de imprevizibilă este funcția Euler [20] : $\lim \inf {\frac {\varphi (n+1)}{\varphi (n)))=0$ și $\lim \sup {\frac {\varphi (n+1)}{\varphi (n)))=\infty .$
Formulele de mai sus au fost obținute de Somayajulu în 1950. Și patru ani mai târziu, Schinzel și Sierpinski au demonstrat [20] că setul

{\displaystyle \left\{{\frac {\varphi (n+1)}{\varphi (n)))),\;\;n=1,\;2,\;\ldots \right\))

dens în mulţimea numerelor reale pozitive.

În același an au stabilit [20] că setul

\left\{{\frac {\varphi (n)}{n)),\;\;n=1,\;2,\;\ldots \right\)

strâns pe interval

(0,\;1).

Asimptotice pentru sume

Expresia exactă pentru suma valorilor succesive ale funcției Euler [21] este: $\sum_{n\leqslant x}\varphi(n)=\frac{3}{\pi^2}x^2+O(x\ln x).$

Aceasta implică faptul că ordinea medie a funcției Euler este egală cu . Acest rezultat este interesant prin faptul că permite obținerea probabilității evenimentului ca două numere naturale alese aleatoriu să fie coprime. Și anume, această probabilitate este egală cu [22] .

6n/\pi ^{2}

6/\pi ^{2}

Ținând cont de expresia de mai sus, putem obține următoarele estimări asimptotice: $\sum _{k=1}^{n}{\frac {k}{\varphi (k)))=O(n)$ ; $\sum _{k=1}^{n}{\frac {1}{\varphi (k)))=O(\ln n)$ .
Folosind multiplicativitatea funcției Euler și proprietățile sumei divizorilor , este ușor de stabilit că [23] $\sigma(n)$ ${\frac {6}{\pi ^{2})}}<{\frac {\varphi (n)\sigma (n)}{n^{2)}}<1,\;n>1$ .

Ordinea funcției Euler

În 1909, Landau a obținut egalitatea [24] [25] : $\lim\inf\frac{\varphi(n)}{n}\log\log n = e^{-\gamma},$

unde este constanta Euler-Mascheroni .

\gamma

Acest rezultat poate fi rafinat. În 1962, a fost obținută o estimare mai mică pentru funcția Euler [26] : $\varphi (n)\geqslant {\frac {n}{e^{\gamma}\log \log n+{\frac {2{,}5}{\log \log n)))}$

pentru toți , cu o singură excepție în acest caz ar trebui înlocuit cu Aceasta este una dintre cele mai precise limite inferioare pentru [27] .

n\geqslant 3

n=2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23;

2{,}5

2{,}50637.

\varphi (n)

Ca o estimare superioară, s-a stabilit următorul fapt [28] : există infinit de multe numere naturale astfel încât $n$ $\varphi(n) < e^{-\gamma} \frac {n} {\log \log n}.$

După cum remarcă Paulo Ribenboim cu privire la demonstrarea acestei inegalități [27] : „Metoda de demonstrare este interesantă prin faptul că inegalitatea este stabilită mai întâi prin ipoteza că ipoteza Riemann este adevărată, iar apoi sub ipoteza că nu este Adevărat."

Relația cu alte funcții

Funcția Möbius

Următoarea formulă poate fi utilizată pentru a calcula [29] : $\varphi (n)$ $\varphi(n)=\sum_{d\mid n} d\cdot\mu\left(\frac{n}{d}\right),$

unde este funcția Möbius .

\mămică)

Alte relații cu funcția Möbius: $\sum_{k=1}^n\varphi(k)=\frac{1}{2}\left(1+\sum_{k=1}^n \mu(k)\left\lfloor\frac{n }{k}\right\rfloor^2\right);$ $\sum_{k=1}^n\frac{\varphi(k)}{k}=\sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{ n}{k}\dreapta\retaj;$ $\sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)))={\frac {n}{\varphi (n))}$ [30] .

Seria Dirichlet

Seria Dirichlet cu coeficienți poate fi reprezentată în termenii funcției zeta Riemann [31] : $\varphi (n)$ $\sum_{n=1}^\infty\frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}, \; s > 2.$

Seria Lambert

Suma seriei Lambert cu coeficienți [32] : $\varphi (n)$ $\sum_{n=1}^\infty\frac{\varphi(n)q^n}{1-q^n}=\frac{q}{(1-q)^2}, \; |q|<1.$

Cel mai mare divizor comun

Funcția Euler este transformata Fourier discretă a celui mai mare divizor comun [33] : $\varphi (n)=\sum \limits _{k=1}^{n}\gcd(k,\,n)e^{{-2\pi i}{\tfrac {k}{n }}}.$

Partea reală:

\varphi (n)=\sum \limits _{k=1}^{n}\gcd(k,\,n)\cos {2\pi {\frac {k}{n)}}.

Spre deosebire de produsul Euler, calculele care folosesc aceste formule nu necesită cunoașterea divizorilor

n.

Legătura cu pătratele latine

Numărul de pătrate latine ciclice de ordin cu un prim rând fix este dat de funcția Euler . Această caracteristică poate fi utilizată atunci când se calculează valoarea funcției Euler prin numărarea numărului corespunzător de pătrate dintr-un ordin dat folosind un algoritm fără înmulțiri și diviziuni, cu toate acestea, acest lucru este asimptotic mai lent decât calculul bazat pe factorizarea argumentului . Pătratele latine diagonale ciclice sunt un subset de pătrate latine ciclice, astfel încât numărul de pătrate latine diagonale ciclice cu un prim rând fix (secvența A123565 în OEIS ) este o limită inferioară a valorii funcției Euler [34] . $N$ $\varphi (N)$ $N$ $N$ $\varphi (N)$

Aplicații și exemple

Funcția Euler în RSA

Pe baza algoritmului propus în 1978 de Ronald Rivest , Adi Shamir și Leonard Adleman , a fost construit primul sistem de criptare cu cheie publică, numit după primele litere ale numelor de familie ale autorilor - sistemul RSA . Puterea criptografică a acestui sistem este determinată de complexitatea factorizării unui număr întreg de biți. Rolul cheie în algoritmul RSA este jucat de funcția Euler, ale cărei proprietăți fac posibilă construirea unui sistem criptografic cu cheie publică [35] . $n$

În etapa creării unei perechi de chei secrete și publice,

\varphi(n) = \varphi(p \cdot q) = (p-1) \cdot (q-1),

unde și sunt simple. Apoi sunt alese numere aleatorii astfel încât $p$ $q$ $d,\e$

d \cdot e = 1 \;\bmod \;\varphi(n).

Mesajul este apoi criptat cu cheia publică a destinatarului:

c = m^e \;\bmod \;n.

După aceea, numai proprietarul cheii secrete poate decripta mesajul : $d$

m = c^d \;\bmod \;n.

Corectitudinea ultimei afirmații se bazează pe teorema lui Euler și pe teorema chineză a restului .

Dovada de decriptare

Datorită alegerii numerelor în etapa creării cheilor

e \cdot d = 1 + a \cdot \varphi(n).

Dacă , ținând cont de teorema lui Euler, $(m,\,n)=1,$

c^d = m^{ed} = m^{1}m^{a\varphi(n)} = m \cdot 1^{a} = m \;\bmod \;n.

În cazul general, și poate avea divizori comuni, dar decriptarea se dovedește totuși a fi corectă. Fie Conform teoremei chineze a restului: $m$ $n$ $m = 0 \;\bmod \;p.$

m = c^d \;\bmod \;n \;\Leftrightarrow \;\begin{cases} m = c^d \;\bmod \;p, \\ m = c^d \;\bmod \;q . \end{cazuri}

Înlocuind obținem identitatea $c = m^e,$

\begin{cases} m^{ed} = 0 = m \;\bmod \;p, \\ m^{ed} = m(m^{q-1})^{a(p-1)} = m \cdot 1^{a(p-1)} = m \;\bmod \;q. \end{cazuri}

Prin urmare,

m^{ed} = m \;\bmod \;pq.

Calculul elementului invers

Funcția Euler poate fi folosită pentru a calcula inversul unui element modulo , și anume [36] : $n$

a^{-1} \equiv a^{\varphi(n)-1} \pmod n,

dacă

(a,\,n)=1.

Această formulă rezultă din teorema lui Euler :

1 = (a \cdot a^{-1}) \cdot a^{\varphi(n)} \;\bmod \;n = a \cdot (a^{-1} \cdot a^{\varphi( n)}) \;\bmod \;n = a \cdot a^{\varphi(n) - 1} \;\bmod \;n.

Exemplu (calcul element invers)

Găsiți , adică un număr astfel încât $5^{-1} \;\bmod \;7$ $X$

5 \cdot x \equiv 1 \pmod 7.

Evident, și nu au divizori comuni cu excepția unu, , în timp ce numărul este prim și $5$ $7$ $(5,7)=1$ $7$

\varphi(7)=7-1=6,

Prin urmare, este convenabil să utilizați formula de mai sus:

5^{6-1} \;\bmod \;7 = 5^{5} \;\bmod \;7 = 25 \cdot 25 \cdot 5 \;\bmod \;7 = (-3) \cdot ( -3) \cdot 5 \;\bmod \;7 = 9 \cdot 5 \;\bmod \;7 = 2 \cdot 5 \;\bmod \;7 = 3.

Este ușor să verifici ce este cu adevărat

5 \cdot 3 \equiv 1 \pmod 7.

Observația 1 (Estimarea complexității de calcul)

În general, pentru calcularea reciprocelor , algoritmul euclidian este mai rapid decât utilizarea teoremei lui Euler [37] , deoarece complexitatea biților a calculului prin algoritmul euclidian este de ordinul , în timp ce calculul prin teorema lui Euler necesită o ordine a operațiilor pe biți, unde Totuși , în cazul în care este cunoscută factorizarea , complexitatea computațională poate fi redusă folosind algoritmi de exponențiere rapidă : algoritmul lui Montgomery sau algoritmul „pătrat și înmulțire” [38] . $O(k^2),$ $O(k^3)$ $k = \lceil \log_2{n} \rceil.$ $\varphi(n)-1$

Observația 2 (Fără soluție în cazul ( a , n ) ≠ 1)

Dacă atunci elementul invers nu există sau, cu alte cuvinte, ecuația $(a,\,n)\neq 1,$ $A$

a \cdot x \equiv 1 \pmod n

nu are soluție pe mulțimea numerelor naturale [39] .
Dovada. Într-adevăr, să presupunem

(a,\,n)=d>1,

iar solutia exista. Apoi, după definiția celui mai mare divizor comun

a=d\cdot a',\n=d\cdot n',

și

(a',\,n')=1;

ca sa poti scrie:

d \cdot a' \cdot x = d \cdot n' \cdot t + 1,

Unde

t\in \mathbb {N} _{0},x\in \mathbb {N} ;

sau, rearanjarea termenilor,

a' \cdot x - n' \cdot t = \frac{1}{d}.

În stânga este un număr întreg non-zero, ceea ce înseamnă că în dreapta trebuie să existe un număr întreg non-zero, prin urmare, cu necesitatea

d=1

ceea ce contrazice presupunerea.

Soluție de comparație liniară

Pentru rezolvarea comparației se poate folosi metoda de calcul a elementului invers

a \cdot x \equiv b \pmod n.

Soluția este dată de formula [37] :

x \equiv b \cdot a^{\varphi(n)-1} \pmod n,

dacă

(a,\,n)=1.

Exemplu (soluție de comparație liniară)

Luați în considerare comparația

7 \cdot x \equiv 3 \pmod 9.

Cum poți folosi această formulă: $(7,9)=1,$

x = 3 \cdot 7^{\varphi(3^{2})-1} \;\bmod \;9 = 3 \cdot 7^{3 \cdot (3-1) - 1} \;\bmod \ ;9 = 3 \cdot 7^{5} \;\bmod \;9 = 3 \cdot 49 \cdot 49 \cdot 7 \;\bmod \;9 = 3 \cdot 4 \cdot 4 \cdot 7 \;\ bmod \;9 = 3.

Prin înlocuire, ne asigurăm că

7 \cdot 3 \equiv 3 \pmod 9.

Observație (Neunicitatea unei soluții sau absența unei soluții în cazul ( a , n ) ≠ 1)

Dacă , comparația fie are o soluție neunică, fie nu are nicio soluție. Este ușor de verificat dacă comparația $(a,\,n)\neq 1$

2 \cdot x \equiv 3 \pmod 4

nu are soluție asupra mulțimii numerelor naturale. În același timp, comparație

4 \cdot x \equiv 6 \pmod {22}

are două soluții

x = 7, \; x=18.

Calculul restului unei diviziuni

Funcția Euler vă permite să calculați restul împărțirii numerelor mari [40] .

Exemplul 1 (Ultimele trei cifre din reprezentarea zecimală a unui număr)

Găsiți ultimele trei cifre în notația zecimală a unui număr Observând că $2^{100}.$

\varphi(125) = \varphi(5^3) = 5^3 - 5^2 = 100,

primim

2^{100} \;\bmod \;125 = 2^{125 - 25} \;\bmod \;125 = 2^{\varphi(125)} \;\bmod \;125 = 1 \;\bmod \;125.

Trecând acum din modul în modul avem: $125$ $1000$

2^{100} \equiv 1 \pmod{125} \equiv 376 \pmod{1000}.

Prin urmare, reprezentarea zecimală a unui număr se termină în $2^{100}$ $376.$

Exemplul 2 (Rămăsul împărțirii cu 1001)

Să găsim restul după împărțirea la Este ușor de văzut că $729^{720}$ $1001.$

(729,\;1001)=1.

Prin urmare, folosind multiplicativitatea funcției Euler și egalitatea

\varphi(p) = p - 1,

pentru orice simplu

p,

primim

\varphi(1001) = \varphi(7 \cdot 11 \cdot 13) = \varphi(7) \cdot \varphi(11) \cdot \varphi(13) = 6 \cdot 10 \cdot 12 = 720.

Conform teoremei lui Euler

729^{720} \equiv 1 \pmod{1001}.

Găsirea ordinii grupului multiplicativ al unui inel rezidual

Grupul multiplicativ al inelului de reziduuri modulo este format din clase de reziduuri [41] . Exemplu. Sistemul redus de reziduuri modulo 14 constă din clase de reziduuri: $m$ $\varphi(m)$
$\varphi(14) = 6$ $[1]_{14},\[3]_{14},\[5]_{14},\[9]_{14},\[11]_{14},\[13 ]_{paisprezece}.$

Aplicații în teoria grupurilor

Numărul de elemente generatoare dintr-un grup ciclic finit este . În special, dacă grupul multiplicativ al inelului de reziduuri modulo este un grup ciclic - ceea ce este posibil numai pentru , unde este un prim impar, este un număr natural [42] - atunci există generatori ai grupului ( rădăcini primitive modulo ) . Exemplu. Grupul considerat în exemplul de mai sus are un generator: și $G$ $\varphi(|G|)$ $m$ $m=2,\;4,\;p^{n},\;2p^{n)$ $p$ $n$ $\varphi(\varphi(m))$ $m$
$\mathbb {Z} _{14}^{\times },$ $\varphi(\varphi(14)) = \varphi(6) = 2$ $3$ $5.$

Probleme restante

Problema lui Lemaire

După cum știți, dacă este prim, atunci În 1932, Derrick Lemaire s- a întrebat dacă există un astfel de număr compus care este un divizor al lui . Lehmer a considerat ecuația: $p$ $\varphi(p) = p - 1.$ $n$ $\varphi (n)$ $n-1$

k\varphi(n) = n-1,

unde este un număr întreg. El a reușit să demonstreze că dacă este o soluție a unei ecuații, atunci fie este primă, fie este un produs de șapte sau mai multe numere prime diferite [43] . Alte afirmații puternice au fost dovedite ulterior. Așadar, în 1980, Cohen și Hagis au arătat că dacă este compus și împarte atunci și unde este numărul de divizori primi. În 1970, Lieuwens a stabilit că dacă atunci și Wall în 1980 au demonstrat că dacă atunci [44] . $k$ $n$ $n$ $n$ $\varphi (n)$ $n-1,$ $n > 10^{20}$ $\omega (n)\geqslant 14,$ $\omega(n)$ $3\mid n,$ $\omega (n)\geqslant 213$ $n>5{,}5\cdot 10^{570}.$ $30\mid n,$ $\omega (n)\geqslant 26$

Până în prezent, nu se știe dacă există soluții compozite la problema lui Lehmer. Dacă presupunem că nu există, atunci se obține următorul criteriu de simplitate: - prim dacă și numai dacă [43] . $n$ $\varphi (n)\mid n-1$

Ipoteza lui Carmichael

Chiar dacă te uiți la primele zece valori ale funcției Euler {1, 1, 2, 2, 4, 2, 6, 4, 6, 4}, este izbitor că există multe repetări printre ele. Conjectura lui Carmichael este că nu există o astfel de valoare pe care funcția Euler să ia o singură dată. $m$

În 1907, Carmichael a propus ca exercițiu să dovedească următoarea afirmație [45] :

Dacă este un număr natural, atunci există un număr natural astfel încât

n

m\neq n

\varphi(n)=\varphi(m).

În caz contrar, această afirmație poate fi formulată după cum urmează [46] : nu există un număr natural astfel încât $m$ $\dim(\varphi^{-1}(m)) = 1.$

Cu toate acestea, în 1922, Carmichael a descoperit că dovada sa conținea o eroare. În același an, el a arătat că, dacă mai târziu, această estimare a fost îmbunătățită în mod repetat, iar valoarea modernă a limitei inferioare, de la care merită să începem să căutăm un contraexemplu pentru conjectura lui Carmichael, este Această valoare a fost obținută de Schlafly și Wagon. în 1994 folosind metoda Klee [45] . $\dim(\varphi^{-1}(m)) = 1,$ $m>10^{37}.$ $m=10^{10^{7}}.$

Este de remarcat faptul că în 1999 Ford a demonstrat următoarea teoremă [47] :

\forall k\geqslant 2\;\există m\colon \dim(\varphi ^{-1}(m))=k.

Aceasta înseamnă că, având în vedere un anumit număr , se poate găsi în setul de valori ale funcției Euler o astfel de valoare încât să fie luată exact o dată. Cu toate acestea, nimeni nu a fost capabil să demonstreze că nu există o astfel de valoare pe care funcția Euler să o ia o singură dată [46] . $k\geqslant 2,$ $m,$ $k$

Vezi și

Lista obiectelor numite după Leonhard Euler

Note

↑ Funcția Euler // Enciclopedia matematică (în 5 volume). - M .: Enciclopedia Sovietică , 1985. - T. 5. - S. 934.
↑ Sandifer, 2007 , p. 203.
↑ Gabidulin, 2011 , RSA Systems.
↑ Secvența OEIS A000010 _
↑ Burton, 2007 , Teorema 7.2, p. 133.
↑ Hardy, 1975 , Teorema 59, p. 52.
↑ Hardy, 1975 , Teorema 60, p. 53.
↑ 1 2 3 Sagalovici, 2007 , Calculul funcției Euler, p. 35-36.
↑ Burton, 2007 , Euler's Phi-Function, p. 136.
↑ Weisstein, MathWorld, Totient Function
↑ Ruiz, S., A Congruence With the Euler Totient Function, 2004
↑ Vinogradov, 1952 , Funcția Euler.
↑ Informațiile din această secțiune se bazează pe articolul: Coleman, Some remarks on Euler's totient function
↑ Gupta H., 1981
↑ 1 2 3 Manual, 2005 , Inegalități elementare pentru φ.
↑ Kendall și Osborn 1965
↑ Sierpinski și Schinzel 1988
↑ Hardy, 1975 , Teorema 326, p. 267.
↑ Hardy, 1975 , Teorema 327, p. 267.
↑ 1 2 3 Ribenboim, 1996 , Valorile funcției lui Euler, p. 38.
↑ Hardy, 1975 , Teorema 330, p. 268.
↑ Hardy, 1975 , Teorema 332, p. 269.
↑ Hardy, 1975 , Teorema 329, p. 267.
↑ Manual, 2005 , Despre funcția n /φ( n ).
↑ Hardy, 1975 , Teorema 328, p. 267.
↑ Rosser, J. Barkley și Schoenfeld, Lowell. Formule aproximative pentru unele funcții ale numerelor prime // Illinois J. Math. : jurnal. - 1962. - Vol. 6 , nr. 1 . - P. 64-94 . (Teorema 15)
↑ 1 2 Ribenboim, 1996 , Distribuția valorilor funcției lui Euler, p. 320.
↑ Nicolae, 1983
↑ Vinogradov, 1952 , p. 29-31.
↑ Rosica Dineva, Totientul Euler, Möbius și funcțiile divizorului
↑ Hardy, 1975 , Teorema 288, p. 250.
↑ Hardy, 1975 , Teorema 309, p. 258.
↑ Schramm, 2008
↑ Vatutin E.I. Despre enumerarea pătratelor latine ciclice și calculul valorii funcției Euler folosindu-le // Sisteme și tehnologii de calcul de înaltă performanță. 2020. V. 4, Nr. 2. S. 40–48.
↑ Gabidulin, 2011 , Sistem de criptare RSA, p. 96.
↑ Alferov, 2002 , p. 462-463.
↑ 1 2 Schneier, 1995 , Funcția Euler Totient.
↑ Gabidulin, 2011 , Găsirea modulului invers multiplicativ, p. 233.
↑ Schneier, 1995 , Teoria numerelor.
↑ Sagalovici, 2007 , p. 36.
↑ Sagalovici, 2007 , Sistem redus de deduceri.
↑ Vinogradov, 1952 , p. 106.
↑ 1 2 Lehmer, 1932
↑ Ribenboim, 1996 , p. 36-37.
↑ 1 2 Ribenboim, 1996 , p. 39-40.
↑ 1 2 Coleman, Câteva remarci despre funcția toientă a lui Euler
↑ Ford, 1999

Literatură

Charles Sandifer. Matematica timpurie a lui Leonhard Euler. - MAA, 2007. - P. 391. - ISBN 0-88385-559-3 .
Jozsef Sandor, Dragoslav S. Mitrinovic, Borislav Crstici. Funcția φ a lui Euler // Handbook of Number Theory I. - Springer, 2005. - 622 p.
Vinogradov I.M. Fundamentele teoriei numerelor. - a 5-a ed. - M. - L .: Gostekhizdat, 1952. - 180 p. — 100.000 de exemplare.
GH Hardy, EM Wright. O introducere în teoria numerelor. - a patra editie. - Oxford: Oxford University Press, 1975. - 421 p.
Alferov A. P., Zubov A. Yu., Kuzmin A. S., Cheremushkin A. V. Elemente de algebră și teoria numerelor // Fundamentele criptografiei. — Ed. a II-a, corectată. si suplimentare - M. : Helios ARV, 2002. - 480 p. — ISBN 5-85438-025-0 .
Bruce Schneier. Criptografie aplicată: protocoale, algoritmi și cod sursă în C. - Australia: John Wiley & Sons, 1995. - ISBN 0-471-12845-7 .
Sagalovici Yu. L. Introducere în codurile algebrice - M. : MIPT , 2007. - 262 p. — ISBN 978-5-7417-0191-1
Paul Ribenboim. Noua carte a înregistrărilor numerelor prime. - New York: Springer, 1996. - ISBN 0-387-94457-5 .
Gabidulin E. M., Kshevetsky A. S., Kolybelnikov A. I. Securitatea informațiilor: un tutorial. - M. : MIPT, 2011. - 262 p. — ISBN 5-7417-0377-9 .
David M Burton. Teoria elementară a numerelor. — Ediția a șasea. - Universitatea din New Hampshire: McGraw-Hill, 2007. - 512 p. - ISBN 978-0-07-305188-8 .
Arnold V.I. Grupuri Euler și aritmetica progresiilor geometrice. - M. : MTSNMO, 2003. - 44 p. — ISBN 5-94057-141-7 .

Link -uri

Arnold V. I., Grupurile Euler și aritmetica progresiilor geometrice (2003)
Coleman R., Câteva remarci despre funcția toientă a lui Euler (2012)
Dineva R., Totientul Euler, Möbius și funcțiile divizorului (2005)
Ford K., Numărul de soluții ale lui φ(x) = m (1999)
József Sándor, Dragoslav S. Mitrinovic, Borislav Crstici, Handbook of Number Theory I (2005)
Gupta H., Funcția totală a lui Euler și inversul ei (1981)
Hardy, Wright O introducere în teoria numerelor (2008)
Lehmer D.H., Despre funcția de tot a lui Euler (1932)
Ruiz S., A Congruence With the Euler Totient Function (2004)
Schramm, Wolfgang, Transformarea Fourier a funcțiilor celui mai mare divizor comun (2008)
Weisstein, Eric W. „Funcția Totient”. De la MathWorld - O resursă web Wolfram. http://mathworld.wolfram.com/TotientFunction.html

Dicționare și enciclopedii	Britannica (online)