φ(n)
Factori primi
Proporția celor prime cu n
Divizori

          Afișează

          Mai multe despre indicatorul lui Euler

          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ă

          1. 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.
          2. 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.
          3. 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