De ce contează?
Ai un lacăt cu numărul n și o grămadă de chei numerotate de la 1 la n. O
cheie se potrivește doar dacă numărul ei nu împarte niciun factor comun cu n
(adică sunt prime între ele). Câte chei din toată grămada se potrivesc? Numărul
acela are un nume: indicatorul lui Euler, scris phi(n). Vestea bună: nu trebuie
să încerci toate cheile pe rând — phi(n) se citește direct din factorii primi ai
lui n.
Intuiția
phi(n) numără câți întregi k din intervalul 1..n sunt primi cu n (au
gcd(k, n) = 1). De exemplu pentru n = 12, cheile care se potrivesc sunt 1, 5, 7, 11 — exact 4 numere, deci phi(12) = 4. De ce tocmai astea? Pentru că 12 = 2^2 * 3: orice k care e divizibil cu 2 sau cu 3 „atinge” un factor al lui
12 și e eliminat. Rămân doar cele care evită ambele. Ideea-cheie e că ce contează
nu sunt toate numerele, ci doar factorii primi distincți ai lui n.
phi(n) depinde doar de factorii primi distincți ai lui n — nu de puterile
lor și nici de fiecare număr din 1..n. Pleci de la phi = n și, pentru fiecare
prim distinct p, aplici phi = phi / p * (p - 1). Atât: dacă 12 și 18 ar avea
aceiași primi distincți, fracția care „taie” ar fi aceeași. (12 = 2^2 * 3 și
18 = 2 * 3^2 au amândouă primii {2, 3}, deci aceeași formulă, doar pornind de la
n diferit.)