Candale Silviu (silviu) 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 … \cdot p_{k}^{e_k} \), unde \( p_1 < p_2 < … < 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 … \cdot p_{k}^{e_k} \), numărul de divizori este: \( (e_1 + 1) \cdot (e_2 + 1) \cdot … \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 … \cdot p_{k}^{e_k} \), suma divizorilor este: \( { {p_1^{e_1+1} -1 } \over {p_1 – 1} } \cdot { {p_2^{e_2+1} -1 } \over {p_2 – 1} } \cdot … \cdot { {p_k^{e_k+1} -1 } \over {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 \( { {2^{2+1} -1 } \over {2 – 1} } \cdot { {3^{1+1} -1 } \over {3 – 1} } = { {2^3 -1 } \over {1} } \cdot { {3^{2} -1 } \over {2} } = { {8 -1 } \over {1} } \cdot { {9 -1 } \over {2} } = { {7 } \over {1} } \cdot { {8 } \over {2} } = {7 } \cdot {4} = 28 \).
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 \( \varphi(n) \) 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:
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) $$