Aplicații ale descompunerii în factori primi

Cuprins

Teoreme fundamentală a aritmeticii:

Orice număr natural $n$ mai mare decât $1$ se poate scrie în mod unic sub forma $n = p_{1}^{e_{1}} \cdot p_{2}^{e_{2}} \cdot \dots \cdot p_{k}^{e_{k}}$ , unde $p_{1} < p_{2} < \dots < p_{k}$ sunt numere prime, iar $e_{i} > 0, i = 1. . k$

V-ați întrebat de ce numărul $1$ nu este prim? Dacă ar fi, teorema de mai sus ar fi falsă! Pentru numărul $12$ , ar fi valabile descompunerile:

$12 = 2^{2} \cdot 3$
$12 = 1 \cdot 2^{2} \cdot 3$
$12 = 1^{7} \cdot 2^{2} \cdot 3$
ș.a.m.d.

Iată trei aplicații interesante ale descompunerii în factori primi. Lăsăm demonstrarea lor în sarcina cititorului!

Numărul de divizori

Numărul de divizori ai lui $n$ poate fi determinat prin numărarea acestora: parcurgerea intervalului de divizori posibili și numărarea valorilor care sunt divizori ai lui $n$ .

O altă soluție este folosirea următoarei proprietăți.

Proprietate: Pentru un număr natural care are descompunerea în factori primi: $n = p_{1}^{e_{1}} \cdot p_{2}^{e_{2}} \cdot \dots \cdot p_{k}^{e_{k}}$ , numărul de divizori este: $(e_{1} + 1) \cdot (e_{2} + 1) \cdot \dots \cdot (e_{k} + 1)$ .

Exemplu: Fie $n = 12$ . Divizorii sunt $1, 2, 3, 4, 6, 12$ – 6 divizori.
Descompunerea în factori este: $n = 12 = 2^{2} \cdot 3^{1}$ .
Aplicând formula de mai sus obținem $(2 + 1) \cdot (1 + 1) = 3 \cdot 2 = 6$ .

Suma divizorilor

Proprietate: Pentru un număr natural care are descompunerea în factori primi: $n = p_{1}^{e_{1}} \cdot p_{2}^{e_{2}} \cdot \dots \cdot p_{k}^{e_{k}}$ , suma divizorilor este: $\frac{p_{1}^{e_{1} + 1} - 1}{p_{1} - 1} \cdot \frac{p_{2}^{e_{2} + 1} - 1}{p_{2} - 1} \cdot \dots \cdot \frac{p_{k}^{e_{k} + 1} - 1}{p_{k} - 1}$ .

Exemplu: Fie $n = 12$ . Suma divizorilor este $1 + 2 + 3 + 4 + 6 + 12 = 28$ .
Descompunerea în factori este: $n = 12 = 2^{2} \cdot 3^{1}$ .
Aplicând formula de mai sus obținem $\frac{2^{2 + 1} - 1}{2 - 1} \cdot \frac{3^{1 + 1} - 1}{3 - 1} = \frac{2^{3} - 1}{1} \cdot \frac{3^{2} - 1}{2} = \frac{8 - 1}{1} \cdot \frac{9 - 1}{2} = \frac{7}{1} \cdot \frac{8}{2} = 7 \cdot 4 = 28$ .

Indicatorul lui Euler

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

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

Proprietate: Pentru un număr natural $n$ care are descompunerea în factori primi: $n = p_{1}^{e_{1}} \cdot p_{2}^{e_{2}} \cdot \dots \cdot p_{k}^{e_{k}}$ , are loc relația: $φ (n) = (p_{1} - 1) p_{1}^{e_{1} - 1} \cdot (p_{2} - 1) p_{2}^{e_{2} - 1} \cdot \dots \cdot (p_{k} - 1) p_{k}^{e_{k} - 1}$ .
O scriere echivalentă este: $φ (n) = n (1 - \frac{1}{p_{1}}) \cdot (1 - \frac{1}{p_{2}}) \cdot \dots \cdot (1 - \frac{1}{p_{k}})$

Exemplu: Pentru $n = 12$ , numerele mai mici decât $n$ , prime cu acesta sunt: $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 $φ (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 $φ (n) = n - 1$ .

Teorema lui Euler:

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