- Numere prime, pe dreapta φ(p) = p − 1
- Alte numere
- n-ul tău
Calculator pentru indicatorul lui Euler
Dintre numerele de la 1 la 12, doar 1, 5, 7 și 11 nu au niciun divizor comun cu 12, deci φ(12) = 4. Indicatorul lui Euler numără aceste numere prime cu n pentru orice n. Introdu un număr până la 10^18 pentru a obține φ(n) cu factorii primi și formula produsului scrisă pe larg, a vedea numerele de la 1 la n cu cele prime cu n evidențiate, a verifica teorema lui Euler, a reprezenta grafic φ(k) pentru până la 100.000 de numere deodată sau a găsi fiecare n cu un φ(n) dat. Introdu un număr întreg n până la 10^18 sau alege un exemplu rezolvat. Casetele arată φ(n), factorii primi ai lui n, proporția numerelor de la 1 la n care sunt prime cu n și numărul de divizori, iar pașii scriu formula produsului cu numerele tale. Până la n = 500 sunt desenate numerele de la 1 la n: cele prime cu n sunt pline, celelalte au culoarea celui mai mic număr prim pe care îl au în comun cu n. Indică un număr pentru a vedea cmmdc-ul lui cu n și dă clic pe el pentru a-l folosi ca a în teorema lui Euler. Grafic arată φ(k) pentru fiecare k până la o limită; dă clic pe un punct pentru a deschide acel număr. Invers listează fiecare n cu φ(n) = m; dă clic pe unul pentru a-l deschide.
Cum funcționează
- Introdu un număr întreg n până la 10^18 sau alege un exemplu rezolvat, cum ar fi φ(60), un modul RSA sau numărul Carmichael 561.
- Citește φ(n), factorii primi și formula produsului cu numerele tale. Până la 500, indică numerele de la 1 la n pentru a le vedea cmmdc-ul cu n și dă clic pe unul pentru a verifica teorema lui Euler cu el.
- Treci la Grafic pentru a vedea φ(k) pentru fiecare k până la 100.000 sau la Invers pentru a lista fiecare n cu φ(n) = m.
Cum se calculează φ(n)
Descompune n în factori primi și înmulțește n cu (1 − 1/p) pentru fiecare număr prim p care îl divide. Pentru 60 = 2² × 3 × 5 se obține 60 × 1/2 × 2/3 × 4/5 = 16. Tăierea dă același număr: din cele 60 de numere, 30 sunt pare; din cele 30 impare, 10 sunt multipli de 3; din cele 20 rămase, 4 sunt multipli de 5, și rămân 16. Pentru o putere a unui număr prim, formula este φ(p^k) = p^(k−1)(p − 1), iar valorile se înmulțesc: φ(60) = 2 × 2 × 4. Partea grea este descompunerea. Calculatorul folosește împărțiri succesive, un test de primalitate Miller–Rabin și metoda rho a lui Pollard, așa că până și un produs de 18 cifre a două numere prime de 9 cifre durează o fracțiune de secundă.
Unde se folosește indicatorul
φ(n) numără fracțiile k/n dintre 0 și 1 care sunt deja ireductibile, pașii care duc un ac prin fiecare oră a unui ceas cu n ore (1, 5, 7 și 11 pe un ceas de 12 ore) și numerele care au un invers modulo n. Euler a demonstrat că a^φ(n) ≡ 1 (mod n) pentru orice a prim cu n, iar criptarea RSA se bazează pe asta: cu n = 3233 = 61 × 53, φ(n) = 60 × 52 = 3.120, iar exponentul public 17 are partenerul privat 2.753, pentru că 17 × 2.753 = 15 × 3.120 + 1.
Întrebări frecvente
Ce este indicatorul lui Euler?
φ(n) este numărul de întregi de la 1 la n care nu au niciun divizor comun cu n în afară de 1. φ(9) = 6, pentru că 1, 2, 4, 5, 7 și 8 sunt prime cu 9, în timp ce 3, 6 și 9 au în comun factorul 3. Prin convenție, φ(1) = 1. Euler a studiat funcția în anii 1760; Gauss i-a dat simbolul φ în 1801, iar James Joseph Sylvester numele englezesc totient în 1879.
Cât este φ pentru un număr prim?
p − 1, pentru că orice număr de la 1 la p − 1 este prim cu un număr prim p, deci φ(97) = 96. Pentru o putere a unui număr prim, φ(p^k) = p^k − p^(k−1), pentru că doar multiplii lui p au un divizor comun cu ea: φ(81) = 81 − 27 = 54.
Ce spune teorema lui Euler?
Dacă a și n sunt prime între ele, atunci a^φ(n) dă restul 1 la împărțirea cu n. Pentru n = 60 și a = 7: φ(60) = 16, iar 7^16 ≡ 1 (mod 60). Mica teoremă a lui Fermat este cazul în care n este prim. Adesea ajunge deja un exponent mai mic: 7^4 = 2.401 = 40 × 60 + 1. Cel mai mic exponent care funcționează pentru orice a prim cu n este funcția lui Carmichael λ(n), care pentru 60 este 4.
Pot două numere avea același indicator?
Da, și de obicei sunt mai multe: φ(n) = 24 pentru n = 35, 39, 45, 52, 56, 70, 72, 78, 84 și 90. Unele numere pare nu sunt niciodată o valoare a lui φ, cel mai mic este 14, și niciun număr impar mai mare decât 1 nu este, pentru că φ(n) este par de la n = 3 încolo. Robert Carmichael a afirmat în 1907 că nicio valoare nu este luată exact o dată. Nici acum nu este demonstrat, iar Kevin Ford a arătat în 1998 că o excepție ar trebui să fie mai mare decât 10^(10^10).
Cât de mare poate fi numărul introdus?
Orice întreg până la 10^18. Calculatorul îl descompune cu aritmetică întreagă exactă în browserul tău, așa că φ(10^18) = 4 × 10^17 și φ(999.999.866.000.004.473) = 999.999.864.000.004.608 ies exacte până la ultima cifră. Numerele de la 1 la n sunt desenate până la 500, graficul merge până la 100.000, iar inversul funcționează pentru valori până la 10^10.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Mergi la editor