Programare Competitivă

Indicatorul lui Euler (funcția φ)

Indicatorul lui Euler, notat φ(n) (phi de n), este o funcție care numără câte numere din 1, 2, ..., n sunt coprime cu n (adică au CMMDC(k, n) = 1).

E una dintre cele mai elegante funcții din teoria numerelor și apare în aritmetica modulară, criptografie (RSA) și multe probleme de olimpiadă.

Definiție

φ(n) = numărul de k ∈ {1, 2, ..., n} pentru care CMMDC(k, n) = 1.

Exemple

  • φ(1) = 1 — prin convenție (1 e coprim cu sine).
  • φ(6) = 2 — doar 1 și 5 sunt coprime cu 6 (2, 3, 4, 6 au factori comuni cu 6).
  • φ(9) = 6 — coprime cu 9: 1, 2, 4, 5, 7, 8 (lipsesc 3, 6, 9).
  • φ(12) = 4 — coprime cu 12: 1, 5, 7, 11.

Tabel primele valori

n     1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
φ(n)  1  1  2  2  4  2  6  4  6  4 10  4 12  6  8

Formula cu factorizare

Dacă n = p₁^a₁ · p₂^a₂ · ... · pₖ^aₖ (descompunere în factori primi — vezi 106.html), atunci:

φ(n) = n · Π (1 - 1/pᵢ)

Iterăm peste toți factorii primi distincți pᵢ și înmulțim cu (1 - 1/pᵢ).

Demonstrație scurtă

Dintre cele n numere 1, ..., n, eliminăm pe cele divizibile cu p₁ (sunt n/p₁), apoi aplicăm incluziunea-excluziunea pentru intersecții. Rezultă formula de produs.

Exemple aplicate

φ(12): 12 = 2² · 3

φ(12) = 12 · (1 - 1/2) · (1 - 1/3)
      = 12 · 1/2 · 2/3
      = 4 ✓

φ(100): 100 = 2² · 5²

φ(100) = 100 · 1/2 · 4/5 = 40

φ(p) pentru p prim: φ(p) = p - 1. (Toate 1, 2, ..., p-1 sunt coprime cu p.)

φ(p^k) pentru p prim: φ(p^k) = p^k - p^(k-1) = p^(k-1)·(p-1).

Proprietăți importante

1. Multiplicativitate

Dacă CMMDC(a, b) = 1:

φ(a · b) = φ(a) · φ(b)

Exemplu: φ(15) = φ(3) · φ(5) = 2 · 4 = 8 ✓.

Atenție: doar pentru numere coprime. φ(4) ≠ φ(2) · φ(2).

2. Teorema lui Euler

Dacă CMMDC(a, n) = 1:

a^φ(n) ≡ 1 (mod n)

Generalizarea Micii teoreme a lui Fermat (a^(p-1) ≡ 1 mod p). Are aplicații directe:

  • Calcul al inversului modular: a^(-1) ≡ a^(φ(n)-1) (mod n).
  • Reducerea exponenților mari: a^k (mod n) = a^(k mod φ(n)) (mod n) când CMMDC(a, n) = 1.

3. Sumă peste divizori

Pentru orice n ≥ 1:

Σ_{d | n} φ(d) = n

Suma lui φ peste toți divizorii lui n dă chiar n. Elegant.

Exemplu: divizorii lui 12 sunt 1, 2, 3, 4, 6, 12.
φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12 ✓.

Cod: calcul φ(n) în O(√n)

Folosim factorizarea directă:

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

long long phi(long long n) {
    long long rez = n;
    for (long long d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            while (n % d == 0) n /= d;
            rez -= rez / d;  // echivalent cu rez *= (1 - 1/d)
        }
    }
    if (n > 1) rez -= rez / n;
    return rez;
}

int main() {
    long long n;
    fin >> n;
    fout << phi(n);
    return 0;
}

Complexitate: O(√n) per apel.

De ce rez -= rez / d în loc de rez *= (1 - 1/d)?

Pentru a evita aritmetica cu fracții. Dacă n / d divide exact rez (știm că e așa pentru că d | n), atunci:

rez · (1 - 1/d) = rez - rez/d

Rămâne în long long, fără pierderi de precizie.

Cod: φ pentru toți 1..N (ciur)

Dacă vrem φ(i) pentru toți i ≤ N, folosim un ciur modificat care aplică formula în timp ce marchează numerele prime:

const int NMAX = 1e6 + 5;
long long phi[NMAX];

void precalcPhi(int n) {
    for (int i = 0; i <= n; i++) phi[i] = i;
    for (int i = 2; i <= n; i++) {
        if (phi[i] == i) {
            // i e prim
            for (int j = i; j <= n; j += i)
                phi[j] -= phi[j] / i;
        }
    }
}

Complexitate: O(N log log N) — aceeași ca ciurul Eratostene (vezi 27.html).

După precalcul, phi[i] dă φ(i) în O(1).

Pas cu pas: ciurul pentru N = 10

Inițial:  phi = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

i = 2 (prim, phi[2] == 2):
  j=2:  phi[2] -= 2/2 = 1 → phi[2] = 1
  j=4:  phi[4] -= 4/2 = 2 → phi[4] = 2
  j=6:  phi[6] -= 6/2 = 3 → phi[6] = 3
  j=8:  phi[8] -= 8/2 = 4 → phi[8] = 4
  j=10: phi[10] -= 10/2 = 5 → phi[10] = 5

i = 3 (phi[3] == 3, prim):
  j=3:  phi[3] -= 3/3 = 1 → phi[3] = 2
  j=6:  phi[6] -= 3/3 = 1 → phi[6] = 2
  j=9:  phi[9] -= 9/3 = 3 → phi[9] = 6

i = 4: phi[4] == 2 ≠ 4, nu e prim, sărim.
i = 5 (prim):
  j=5:  phi[5] = 4
  j=10: phi[10] -= 5/5 = 1 → phi[10] = 4

i = 6: phi[6] == 2 ≠ 6, sărim.
i = 7 (prim): phi[7] = 6.
i ≥ 8: nu mai schimbă nimic.

Rezultat: phi = [_, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4] ✓

Aplicații în probleme

1. Inversul modular (când MOD nu e prim)

Pentru a calcula a^(-1) (mod m) când m nu e prim, folosim Euler:

long long invers(long long a, long long m) {
    return putere(a, phi(m) - 1, m);
}

Cu putere(a, b, m) exponențiere rapidă modulară (vezi 83.html).

2. Reducerea exponenților foarte mari

Dacă trebuie să calculezi a^(b) mod n unde b = 10^1000000, poți reduce:

a^b (mod n) = a^(b mod φ(n)) (mod n)   dacă CMMDC(a, n) = 1

3. Numărarea fracțiilor ireductibile

Câte fracții ireductibile k / n cu 1 ≤ k ≤ n există?

Răspuns: exact φ(n). Pentru că fracția k/n e ireductibilă ⇔ CMMDC(k, n) = 1.

4. Fracții Farey

Suma φ(1) + φ(2) + ... + φ(n) e aproximativ 3n²/π² — densitatea fracțiilor ireductibile în [0, 1].

5. Cicluri în x → g·x (mod p)

În teoria grupurilor, ordinul unui element g într-un grup de n elemente divide φ(n).

6. Sume specializate

Probleme de tipul:

Calculează Σ_{k=1}^{n} CMMDC(k, n)

Soluție: Σ_{d | n} d · φ(n/d). Foarte elegant, derivat din proprietățile lui φ.

Tabel proprietăți utile

Proprietate Condiție
φ(1) = 1 convenție
φ(p) = p - 1 p prim
φ(p^k) = p^(k-1) · (p - 1) p prim, k ≥ 1
φ(a · b) = φ(a) · φ(b) CMMDC(a, b) = 1
φ(n) = n · Π (1 - 1/p) pentru orice n ≥ 1
Σ_{d|n} φ(d) = n suma peste divizori
a^φ(n) ≡ 1 (mod n) CMMDC(a, n) = 1
φ(2n) = 2φ(n) dacă n par
φ(2n) = φ(n) dacă n impar

Greșeli frecvente

1. rez / d înainte de while

// GREȘIT
if (n % d == 0) {
    rez -= rez / d;        // mai întâi reducem rez
    while (n % d == 0) n /= d;
}

Ordinea corectă: mai întâi scoatem factorul d complet din n, apoi reducem rez. Dar în practică, linia rez -= rez / d se face o singură dată per factor, deci ambele variante funcționează dacă d e factor prim. Totuși, convenția e ca while să vină prima (e mai clar).

2. Ignorarea factorului rămas n > 1

Dacă după bucla d * d <= n rămâne n > 1, atunci n e un factor prim rămas (> √n_inițial). Trebuie aplicat:

if (n > 1) rez -= rez / n;

Altfel φ iese greșit pentru numere care au un factor prim mare (ex. n = 2 · 97).

3. Confuzia cu numărul de divizori

  • φ(n) = numărul de k ≤ n coprime cu n.
  • τ(n) (sau d(n)) = numărul de divizori ai lui n.

Sunt funcții diferite. φ(12) = 4, τ(12) = 6.

4. Overflow la ciurul precalculat

Pentru N = 10⁶, phi[i] poate fi până la i ≤ 10⁶ — încape în int, dar dacă însumezi Σ φ(i), folosește long long.

5. Aplicarea teoremei lui Euler fără coprimalitate

a^φ(n) ≡ 1 (mod n) cere CMMDC(a, n) = 1. Fără această condiție, nu e garantat. Pentru cazul general, vezi teorema lui Euler generalizată (cu lifting-the-exponent).

Ce să reții

  • φ(n) = numărul de întregi din 1..n coprime cu n.
  • Formula: φ(n) = n · Π (1 - 1/p) pentru factorii primi p ai lui n.
  • Calcul O(√n) per apel cu factorizare directă.
  • Calcul O(N log log N) cu ciurul pentru toți i ≤ N.
  • φ(p) = p - 1 pentru p prim.
  • Multiplicativă: φ(a · b) = φ(a) · φ(b) dacă CMMDC(a, b) = 1.
  • Teorema lui Euler: a^φ(n) ≡ 1 (mod n) dacă CMMDC(a, n) = 1.
  • Suma peste divizori: Σ_{d|n} φ(d) = n.
  • Aplicații: inversul modular non-prim, reducerea exponenților, fracții ireductibile, RSA.

Probleme

pbinfoFractii Ired→

pbinfoMaxprimeintreele→

pbinfoBiprime→

Cuprins Inapoi Inainte