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] .
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 .
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] .
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] .
+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 |
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.
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.
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.
Comportamentul funcției Euler este discutat mai detaliat în secțiunea #Relații asimptotice .
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]
Dovada multiplicativitățiiPentru 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 . Dovada. În cazul în care un apoi de aceea de asemenea Prin urmare, există numere modulo incomparabile care formează un sistem complet de resturi modulo .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: 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ăPentru o valoare simplă a funcției Euler este dată de o formulă explicită [8] :
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.
Pentru a calcula funcția Euler a puterii unui număr prim, folosiți următoarea formulă [8] :
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 .
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] :
unde este un număr prim și trece prin toate valorile implicate în descompunerea în factori primi.
DovadaDupă cum rezultă din teorema fundamentală a aritmeticii , orice număr natural este reprezentat în mod unic sub forma:
unde sunt numere prime și sunt numere naturale.
Folosind multiplicativitatea funcției Euler și expresia pentru , obținem:
Exemplu de aplicare:
Funcția Euler este o funcție aritmetică multiplicativă , adică
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] :
unde este cel mai mare divizor comun și Această proprietate este o generalizare naturală a multiplicativității.
Dovada multiplicativității generalizateFie atunci și în cazul general și Prin urmare, putem scrie:
Aici primii divizori sunt și divizori, iar ultimii divizori sunt divizori Să scriem:
Datorită multiplicativității funcției Euler și luând în considerare și formula
unde este primul, obținem:
Prima linie este scrisă în a doua - iar a treia poate fi reprezentată astfel :
Cateva cazuri speciale:
Proprietatea stabilită de Euler este folosită cel mai des în practică :
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:
Ultima formulă își găsește utilizare în diferite teste de primalitate .
Pe baza reprezentabilității produsului Euler, este ușor să obțineți următoarea declarație utilă:
Următoarea egalitate [10] [11] este o consecință a teoremei Zsigmondy :
Orice număr natural poate fi reprezentat ca suma valorilor funcției Euler de la divizorii săi naturali [12] :
Suma tuturor numerelor mai mici decât un număr dat și relativ prime pentru acesta este exprimată în termenii funcției Euler:
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] .
Î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.
În acest sens, sunt necesare metode speciale de analiză. Un instrument util pentru studierea preimaginei este următoarea teoremă [14] .
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:
1) calcula ; 2) se calculează pentru toate din semi-interval ; 3) toate numerele pentru care formează imaginea inversă a elementului .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.
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
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:
Exemplul 2 (Nu toate numerele pare sunt valori ale funcției Euler)Nu există, de exemplu, un astfel de număr care să fie:
Î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
După sortarea tuturor numerelor de la 15 la 42, este ușor de verificat
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 etapa creării unei perechi de chei secrete și publice,
unde și sunt simple. Apoi sunt alese numere aleatorii astfel încât
Mesajul este apoi criptat cu cheia publică a destinatarului:
După aceea, numai proprietarul cheii secrete poate decripta mesajul :
Corectitudinea ultimei afirmații se bazează pe teorema lui Euler și pe teorema chineză a restului .
Dovada de decriptareDatorită alegerii numerelor în etapa creării cheilor
Dacă , ținând cont de teorema lui Euler,
În cazul general, și poate avea divizori comuni, dar decriptarea se dovedește totuși a fi corectă. Fie Conform teoremei chineze a restului:
Înlocuind obținem identitatea
Prin urmare,
Funcția Euler poate fi folosită pentru a calcula inversul unui element modulo , și anume [36] :
dacăAceastă formulă rezultă din teorema lui Euler :
Exemplu (calcul element invers)Găsiți , adică un număr astfel încât
Evident, și nu au divizori comuni cu excepția unu, , în timp ce numărul este prim și
Prin urmare, este convenabil să utilizați formula de mai sus:
Este ușor să verifici ce este cu adevărat
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] .
Observația 2 (Fără soluție în cazul ( a , n ) ≠ 1)Dacă atunci elementul invers nu există sau, cu alte cuvinte, ecuația
nu are soluție pe mulțimea numerelor naturale [39] .
Dovada. Într-adevăr, să presupunem
iar solutia exista. Apoi, după definiția celui mai mare divizor comun
șica sa poti scrie:
Undesau, rearanjarea termenilor,
Î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
ceea ce contrazice presupunerea.
Pentru rezolvarea comparației se poate folosi metoda de calcul a elementului invers
Soluția este dată de formula [37] :
dacă Exemplu (soluție de comparație liniară)Luați în considerare comparația
Cum poți folosi această formulă:
Prin înlocuire, ne asigurăm că
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
nu are soluție asupra mulțimii numerelor naturale. În același timp, comparație
are două soluții
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ă
primim
Trecând acum din modul în modul avem:
Prin urmare, reprezentarea zecimală a unui număr se termină în
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ă
Prin urmare, folosind multiplicativitatea funcției Euler și egalitatea
pentru orice simpluprimim
Conform teoremei lui Euler
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:
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
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:
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] .
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] .
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ă.
Î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 caz contrar, această afirmație poate fi formulată după cum urmează [46] : nu există un număr natural astfel încât
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] .
Este de remarcat faptul că în 1999 Ford a demonstrat următoarea teoremă [47] :
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] .
![]() |
---|