Indicatorul lui Euler

Indicatorul lui Euler sau funcția lui Euler, sau totient se notează cu \( \varphi(n) \) (unde \(n\) este un număr natural nenul ) și reprezintă numărul de numere mai mici sau egale cu \(n\) și prime cu acesta.

Valoarea lui \( \varphi(n) \) poate fi determinată prin numărarea valorilor prime cu \(n\), sau putem aplica următoarea proprietate:

Formula bazată pe descompunerea în factori

Proprietate: Pentru un număr natural \(n\) care are descompunerea în factori primi: \( n = p_{1}^{e_1} \cdot p_{2}^{e_2} \cdot … \cdot p_{k}^{e_k} \), are loc relația: \( \varphi(n)=(p_{1}-1)p_{1}^{e_{1}-1} \cdot(p_{2}-1)p_{2}^{e_{2}-1} \cdot \cdots \cdot (p_{k}-1)p_{k}^{e_{k}-1} \).
O scriere echivalentă este: \(\varphi(n)=n \left(1-\frac{1}{p_{1}}\right) \cdot \left(1-\frac{1}{p_{2}}\right) \cdot \cdots \cdot \left(1-\frac{1}{p_{k}}\right) \)

Exemplu: Pentru \( n = 12\), numerele mai mici decât \( n \), prime cu acesta sunt: \( \text 1, 5, 7, 11\), adică \( 4 \) numere.
Descompunerea în factori este: \( n = 12 = 2^2 \cdot 3^1 \).
Aplicând formula de mai sus obținem \( \varphi(12) = (2-1) \cdot 2^{2-1} \cdot (3-1) \cdot 3^{1-1} = 1 \cdot 2^1 \cdot 2 \cdot 3^0 = 2 \cdot 2 = 4 \).

Observaţie: Dacă \( n \) este număr prim, atunci \( \varphi(n) = n – 1 \).

Teorema lui Euler:

Dacă \(a, n\) sunt două numere naturale prime între ele, atunci:
$$ a^{ \varphi (n) } \equiv 1 \left(\mod n \right) $$

Secvență C++

Următoarea funcție C++ determină valoarea indicatorului lui Euler pentru o valoare n transmisă ca parametru:

int phi(int n)
{
    int r = n , d = 2;
    while(n > 1)
    {
        if(n % d == 0)
        {
            r = r / d * (d - 1);
            while(n % d == 0)
                n /= d;
        }
        d ++;
        if(d * d > n)
            d = n;
    }
    return r;
}

Complexitatea ei este \(O \left( \sqrt{n} \right) \).

Determinarea indicatorului lui Euler pe toate numerele mai mici sau egale cu n

Uneori – vezi problema #Tramvaie – trebuie să determinăm indicatorul lui Euler pentru multe numere, acestea fiind relativ mici (de exemplu, mai mici decât 1.000.000). În această situație se poate utiliza un algoritm similar cu Ciurul lui Etatostene, bazat tot pe formula de mai sus: \( \varphi(n)=n \left(1-\frac{1}{p_{1}}\right) \cdot \left(1-\frac{1}{p_{2}}\right) \cdot \cdots \cdot \left(1-\frac{1}{p_{k}}\right) \). În plus, dacă \( p \) este număr prim, atunci \( \varphi(p) = p -1 \).

Algoritmul este următorul, pentru a determina valoarea indicatorului lui Euler pentru toate numerele mai mici sau egale cu DIM:

• declarăm un tabloul F[] cu DIM + 1 elemente; la final, F[x] va reprezenta indicatorul lui Euler pentru x
• inițializăm fiecare element F[i] = i; scopul acestei inițializari este dublu:
  • pe de o parte în formula pentru indicatorul lui Euler al lui n produsul începe cu n;
  • pe de altă parte, dacă pe parcurs F[p] este egal cu p, deducem că p este număr prim și va influența indicatorul lui Euler pentru toți multipli săi.
• parcurgem cu p numerele de la 2 la DIM:
• dacă F[p] este egal cu p, înseamnă că p este număr prim:
  • decrementăm F[p], aducându-l la valoarea corectă a indicatorului pentru numere prime; (A)
  • parcurgem toți multipli k ai lui p mai mari decât acesta și actualizăm valoarea lui \( F[k] = F[k] * (1 – \frac{1}{p})\). (B)

OBS: Pașii (A) și (B) pot fi integrați într-un singur pas de tip (B). Cum?

Secvență C++

int F[DIM + 1];

for(int i =1 ; i <= DIM ; i ++)
    F[i] = i;
for(int i = 2;  i <= DIM ; i ++)
    if(F[i] == i)
    {
        F[i] --;
        for(int j =2 ; j * i <= DIM ; j ++)
            F[j * i]= F[j * i] / i * (i - 1);
    }