Indicatorul lui Euler explicat
Scrie numerele de la 1 la 10 și taie-l pe fiecare care are un divizor comun cu 10. Rămân patru: 1, 3, 7 și 9. Acest număr, φ(10) = 4, este indicatorul lui Euler, una dintre cele mai folosite funcții din teoria numerelor, de la fracții și ceasuri până la criptarea care protejează plățile online.
Numărarea numerelor prime cu n
Două numere sunt prime între ele când cel mai mare divizor comun al lor este 1. φ(n) numără acei k de la 1 la n cu cmmdc(k, n) = 1: φ(9) = 6, φ(10) = 4, φ(12) = 4 și φ(1) = 1. Același număr apare în multe locuri. Este numărul fracțiilor k/n dintre 0 și 1 care sunt deja ireductibile, numărul pașilor care duc un ac prin fiecare oră a unui ceas cu n ore și numărul acelor k care au un invers modulo n, astfel încât k × x ≡ 1 (mod n) să aibă soluție.
Formula produsului
Dacă numerele prime care îl divid pe n sunt p₁, p₂ …, atunci φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × …. Motivul este un ciur. Jumătate din toate numerele sunt pare, așa că eliminarea multiplilor lui 2 lasă fracția 1 − 1/2; dintre numerele rămase, unul din trei este multiplu de 3, și așa mai departe. Conform teoremei chinezești a resturilor, condițiile pentru numere prime diferite sunt independente, deci fracțiile pur și simplu se înmulțesc. Pentru 100 = 2² × 5² se obține 100 × 1/2 × 4/5 = 40. Două proprietăți dau același rezultat sub altă formă: φ(p^k) = p^(k−1)(p − 1) și φ(mn) = φ(m) φ(n) când m și n sunt prime între ele, deci φ(100) = φ(4) × φ(25) = 2 × 20 = 40.
Teorema lui Euler
Fermat a observat în 1640 că a^(p−1) ≡ 1 (mod p) pentru un număr prim p și orice a nedivizibil cu p. Euler a demonstrat versiunea generală, publicată în 1763: a^φ(n) ≡ 1 (mod n) ori de câte ori cmmdc(a, n) = 1. Demonstrația este scurtă. Înmulțește cu a cele φ(n) numere prime cu n; produsele sunt din nou prime cu n și toate diferite modulo n, deci sunt aceleași numere în altă ordine, iar comparând cele două produse rămâne a^φ(n) ≡ 1. Cel mai mic exponent care funcționează pentru un a dat este ordinul lui, care îl divide mereu pe φ(n); cel mai mic care funcționează pentru toți a deodată este funcția lui Carmichael λ(n). Pentru 561 = 3 × 11 × 17, λ(561) = 80 îl divide pe 560, deci a^560 ≡ 1 (mod 561) pentru orice a prim cu 561, deși 561 nu este prim. Este cel mai mic număr Carmichael și motivul pentru care testul lui Fermat singur nu poate demonstra că un număr este prim.
Suma pe divizori a lui Gauss și media
Adună φ(d) pe divizorii d ai lui n și obții mereu din nou n: pentru 12, φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12. Gauss a demonstrat asta în Disquisitiones Arithmeticae din 1801; se vede simplificând fracțiile 1/12, 2/12 … 12/12 și ordonându-le după numitor. În medie, φ(k) este aproximativ 0,61 k: media lui φ(k)/k tinde spre 6/π² ≈ 0,6079, care este și probabilitatea ca două numere întregi alese la întâmplare să fie prime între ele, iar φ(1) + … + φ(N) este aproape de 3N²/π². Pentru N = 1.000 suma este 304.192, față de 3N²/π² ≈ 303.964.
Valori care nu apar niciodată
φ(n) este par pentru orice n începând cu 3, pentru că numerele prime cu n vin în perechi k și n − k. Nici orice număr par nu este o valoare: 14, 26, 34, 38 și 50 sunt primele care nu apar niciodată, în timp ce 24 este valoarea pentru zece numere diferite, de la 35 la 90. Găsirea lor este o căutare finită, pentru că pentru fiecare număr prim p care îl divide pe n, p − 1 trebuie să-l dividă pe φ(n). În 1907, Robert Carmichael a afirmat că nicio valoare nu este luată exact o dată. Demonstrația lui era greșită, afirmația este încă deschisă, iar orice excepție ar trebui să fie mai mare decât 10^(10^10). D. H. Lehmer a întrebat în 1932 dacă φ(n) poate să-l dividă pe n − 1 pentru un n compus; nu se cunoaște niciun exemplu.
Indicatorul în RSA
RSA alege două numere prime mari p și q și publică n = pq și un exponent e. Deoarece φ(n) = (p − 1)(q − 1), oricine poate descompune n poate calcula φ(n) și, de aici, exponentul privat d cu e × d ≡ 1 (mod φ(n)); teorema lui Euler garantează apoi că (m^e)^d ≡ m (mod n). În exemplul clasic n = 3233 = 61 × 53, φ(n) = 3.120, e = 17 și d = 2.753. Multe implementări folosesc în schimb λ(n) = cmmmc(p − 1, q − 1), aici 780, ceea ce dă un d mai mic, 413. Calcularea lui φ(n) pentru un modul RSA de 600 de cifre este la fel de grea ca descompunerea lui: din n și φ(n), cele două numere prime rezultă cu o singură rădăcină pătrată.
Explorează
Deschide calculatorul și introdu orice n până la 10^18 pentru a vedea φ(n) cu factorii primi și formula. Până la 500 sunt desenate numerele de la 1 la n, cele prime cu n pline și celelalte colorate după cel mai mic număr prim pe care îl au în comun cu n, astfel încât formula produsului devine un ciur pe care îl poți număra. Alege un număr a pentru a verifica teorema lui Euler, treci la Grafic pentru a vedea φ(k) până la 100.000 cu numerele prime pe dreapta φ(p) = p − 1 sau la Invers pentru a găsi fiecare n cu φ(n) = m.
Întrebări frecvente
De ce φ(1) = 1?
Pentru că cmmdc(1, 1) = 1: singurul număr de la 1 la 1 este prim cu 1. Convenția păstrează și formulele valabile, de exemplu suma lui Gauss pe divizorii lui n, care pentru n = 1 este pur și simplu φ(1) = 1.
Este φ același lucru cu funcția de numărare a numerelor prime?
Nu. π(n) numără numerele prime până la n, φ(n) numerele până la n care sunt prime cu n. φ(10) = 4 numără 1, 3, 7 și 9, în timp ce π(10) = 4 numără 2, 3, 5 și 7. Aici coincid din întâmplare: φ(12) = 4, dar π(12) = 5.
Cât de repede se poate calcula φ(n)?
Atât de repede cât poate fi descompus n. Cu factorii primi cunoscuți sunt câteva înmulțiri; fără ei nu se cunoaște nicio metodă rapidă, și pe asta se bazează RSA. Pentru numere până la 10^18 descompunerea durează milisecunde într-un browser, pentru numere cu sute de cifre poate dura ani.
Ce numere au cel mai mic φ(n) în raport cu n?
Numerele cu mulți factori primi mici. φ(n)/n = (1 − 1/p₁)(1 − 1/p₂)… depinde doar de numerele prime care îl divid pe n, nu de puterile lor: pentru orice putere a lui 2 este exact 1/2, iar pentru 30 = 2 × 3 × 5 este 8/30, aproximativ 27 %. Produsul primelor 15 numere prime, 614.889.782.588.491.410, are φ(n)/n ≈ 14 %, cea mai mică valoare dintre toate numerele până la 10^18.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Deschide calculatorul