Suma și numărul divizorilor. Indicatorul lui Euler

Suma și numărul divizorilor. Indicatorul lui Euler

În acest articol voi prezenta câteva aplicații mai interesante la descompunerea unui număr întreg în factori primi: numărul divizorilor, suma divizorilor și indicatorul lui Euler. Ne vom axa pe demonstrarea formulelor pentru calculul acestor funcții, și implicit pe modul în care putem deduce aceste formule.

Funcția σx(n)\sigma_x(n)

Înainte de a începe, țin să menționez că, în literatura de specialitate, notația folosită pentru suma divizorilor lui nn ridicați la puterea xx este σx(n)\sigma_x(n)

σx(n)dndx\sigma_x(n) \triangleq \sum_{d \mid n} d^x

În particular, σ0(n)\sigma_0(n) reprezintă numărul divizorilor lui nn iar σ1(n)\sigma_1(n) reprezintă suma divizorilor lui nn De exemplu:

σ0(6)=10+20+30+60=4σ1(6)=11+21+31+61=12\begin{align*} \sigma_0(6) &= 1^0 + 2^0 + 3^0 + 6^0 = 4\\ \sigma_1(6) &= 1^1 + 2^1 + 3^1 + 6^1 = 12 \end{align*}

Vom păstra aceste notații și în continuare.

Numărul divizorilor unui întreg

După cum am zis, numărul divizorilor unui număr natural nenul nn se notează cu σ0(n)\sigma_0(n) Formula pentru numărul divizorilor este destul de cunoscută. Dacă descompunerea în factori primi a lui nn este p1e1p2e2pkekp_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} atunci:

σ0(n)=(e1+1)(e2+1)(ek+1)=i=1k(ei+1)\sigma_0(n) = (e_1 + 1)(e_2 + 1) \cdots (e_k + 1) = \prod_{i = 1}^{k} (e_i + 1)

Demonstrația este foarte simplă: Numărul nn este divizibil cu dd dacă și numai dacă dd poate fi scris sub forma p1e1p2e2pkekp_1^{e'_1} p_2^{e'_2} \cdots p_k^{e'_k} astfel încât fiecare exponent eie'_i să fie mai mic sau egal cu eie_i Ei bine, fiecare eie'_i poate lua ei+1e_i + 1 valori: 0,1,,ei0, 1, \ldots, e_i Conform regulii produsului, numerele ei+1e_i + 1 se înmulțesc, iar de aici obținem formula inițială.

Iată cum putem calcula eficient σ0(n)\sigma_0(n) în C++, modificând foarte puțin algoritmul clasic de descompunere în factori primi:

Numărul divizorilor
int num = 1;
for (int d = 2; d * d <= n; d++) {
int e = 1;
while (n % d == 0) {
e++;
n /= d;
}
num *= e;
}
if (n > 1)
num *= 2;
cout << num << '\n';

Puteți observa că, înainte de linia 8, nu a mai fost nevoie să testez dacă nn este divizibil cu dd Asta pentru că, dacă nu se intră în while, rezultatul va fi înmulțit cu 11 iar asta nu-l va afecta.

Suma divizorilor unui întreg

Suma divizorilor unui număr natural nenul nn se notează cu σ1(n)\sigma_1(n) Păstrând notația de mai sus pentru descompunerea lui nn în factori primi, suma divizorilor se calculează astfel:

σ1(n)=p1e1+11p11p2e2+11p21pkek+11pk1=i=1kpiei+11pi1\sigma_1(n) = \frac{p_1^{e_1 + 1} - 1}{p_1 - 1} \cdot \frac{p_2^{e_2 + 1} - 1}{p_2 - 1} \cdots \frac{p_k^{e_k + 1} - 1}{p_k - 1} = \prod_{i = 1}^k \frac{p_i^{e_i + 1} - 1}{p_i - 1}

Pentru a demonstra formula, vom porni de la un caz particular: n=pxn = p^x unde pp este un număr prim. În acest caz, singurii divizori ai lui nn sunt 1,p,p2,,px1, p, p^2, \ldots, p^x Aceștia se află într-o progresie geometrică de rație pp Prin urmare,

σ1(px)=px+11p1\sigma_1(p^x) = \frac{p^{x + 1} - 1}{p - 1}

La pasul următor, vom considera că n=pxqyn = p^x q^y unde pp și qq sunt numere prime distincte. Avem:

σ1(pxqy)=p0q0+p0q1+p0q2++p0qy+p1q0+p1q1+p1q2++p1qy+p2q0+p2q1+p2q2++p2qy  +pxq0+pxq1+pxq2++pxqy\begin{align*} \sigma_1(p^x q^y) &= p^0 q^0 + p^0 q^1 + p^0 q^2 + \cdots + p^0 q^y\\ &+ p^1 q^0 + p^1 q^1 + p^1 q^2 + \cdots + p^1 q^y\\ &+ p^2 q^0 + p^2 q^1 + p^2 q^2 + \cdots + p^2 q^y\\ &\text{ }\text{ }\vdots\\ &+ p^x q^0 + p^x q^1 + p^x q^2 + \cdots + p^x q^y \end{align*}

Dacă de pe fiecare linie ii îl dăm în factor pe pip^i iar mai apoi factorizăm q0+q1++qyq^0 + q^1 + \cdots + q^y obținem:

σ1(pxqy)=(p0+p1++px)(q0+q1++qy)=σ1(px)σ1(qy)\sigma_1(p^x q^y) = (p^0 + p^1 + \cdots + p^x) (q^0 + q^1 + \cdots + q^y) = \sigma_1(p^x) \sigma_1(q^y)

Generalizând, ajungem la formula inițială:

σ1(p1e1p2e2pkek)=σ1(p1e1)σ1(p2e2)σ1(pkek)=i=1kpiei+11pi1\sigma_1(p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}) = \sigma_1(p_1^{e_1}) \sigma_1(p_2^{e_2}) \cdots \sigma_1(p_k^{e_k}) = \prod_{i = 1}^k \frac{p_i^{e_i + 1} - 1}{p_i - 1}

Iată și o implementare în C++ a acestei formule:

Suma divizorilor
int sum = 1;
for (int d = 2; d * d <= n; d++) {
int pwr = d;
while (n % d == 0) {
pwr *= d;
n /= d;
}
sum *= (pwr - 1) / (d - 1);
}
if (n > 1)
sum *= (n * n - 1) / (n - 1);
cout << sum << '\n';

Indicatorul lui Euler

Indicatorul lui Euler se notează cu φ(n)\varphi(n) și reprezintă numărul de numere naturale nenule mai mici sau egale cu nn care sunt prime cu nn De exemplu, φ(1)=1\varphi(1) = 1 φ(6)=2\varphi(6) = 2 φ(11)=10\varphi(11) = 10 De remarcat că acel sau egale cu este pus doar pentru a asigura faptul că φ(1)=1\varphi(1) = 1 orice x>1x \gt 1 nefiind prim cu el însuși. Formula pentru calculul indicatorului este:

φ(n)=i=1kpiei1(pi1)=ni=1k(11pi)\varphi(n) = \prod_{i = 1}^k p_i^{e_i - 1}(p_i - 1) = n \prod_{i = 1}^k \left( 1 - \frac{1}{p_i} \right)

Chiar dacă a doua variantă a formulei este mai elegantă, deoarece nu folosește exponenții eie_i noi o vom folosi pe prima, pentru a evita lucrul cu double. Iată deci calcularea lui φ(n)\varphi(n) în C++:

Indicatorul lui Euler
int phi = 1;
for (int d = 2; d * d <= n; d++)
if (n % d == 0) {
phi *= d - 1;
n /= d;
while (n % d == 0) {
phi *= d;
n /= d;
}
}
if (n > 1)
phi *= n - 1;
cout << phi << '\n';

Demonstrația formulei

În cele ce urmează, pasionații de matematică pot urmări demonstrația formulei de mai sus. Avantajul ei este că nu necesită folosirea Teoremei Chineze a Resturilor, spre deosebire de majoritatea demonstrațiilor găsite de mine pe net. Mai întâi, va trebui să introducem conceptul de funcție multiplicativă:

Funcții multiplicative

În teoria numerelor, o funcție ff definită pe N\mathbb{N}^* se numește multiplicativă dacă are proprietatea că f(1)=1f(1) = 1 și că f(ab)=f(a)f(b)f(ab) = f(a)f(b) oricare ar fi aa și bb două numere naturale nenule prime între ele. Atât numărul cât și suma divizorilor sunt funcții multiplicative, acest fapt bazându-se pe formulele deja demonstrate. În cazul indicatorului lui Euler, va fi mai ușor să deducem formula dacă mai întâi demonstrăm multiplicitatea funcției.

Așadar, trebuie să demonstrăm că φ(mn)=φ(m)φ(n),m,nN,(m,n)=1\varphi(mn) = \varphi(m) \varphi(n), \forall m, n \in \mathbb{N}^*, (m, n) = 1 Vom aranja numerele de la 11 la mnmn sub forma unei matrice cu mm linii și nn coloane. Să luăm drept exemplu m=5m = 5 și n=3n = 3

123456789101112131415\begin{matrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9\\ 10 & 11 & 12\\ 13 & 14 & 15 \end{matrix}

Partea cu φ(n)\varphi(n)

Pentru ca un număr să fie prim cu mnmn el trebuie să fie prim atât cu mm cât și cu nn În acest sens, haideți să vedem mai întâi ce numere din matrice sunt prime cu nn Elementul de pe poziția (i,j)(i, j) are forma (i1)n+j(i - 1)n + j Este evident că ((i1)n+j,n)=(j,n)((i - 1)n + j, n) = (j, n) Deci, (aij,n)=1(a_{ij}, n) = 1 dacă și numai dacă (j,n)=1(j, n) = 1 Așadar, elementele prime cu nn sunt cele de pe coloanele jj pentru care (j,n)=1(j, n) = 1 Numărul acestor coloane este φ(n)\varphi(n)

Partea cu φ(m)\varphi(m)

Acum, de pe aceste coloane ne interesează doar numerele prime cu mm Să vedem ce resturi obținem dacă împărțim toate elementele matricei din exemplu la mm

123401234012340\begin{matrix} 1 & 2 & 3\\ 4 & 0 & 1\\ 2 & 3 & 4\\ 0 & 1 & 2\\ 3 & 4 & 0 \end{matrix}

Aparent, pe fiecare coloană obținem toate resturile posibile modulo mm Dacă asta este adevărat întotdeauna, înseamnă că pe fiecare coloană jj cu (j,n)=1(j, n) = 1 avem φ(m)\varphi(m) numere prime cu mm de unde φ(mn)=φ(m)φ(n)\varphi(mn) = \varphi(m) \varphi(n)

Deci, mai rămâne să demonstrăm că pe nicio coloană kk nu putem găsi două resturi egale. Vom presupune prin reducere la absurd că putem. Cum elementele de pe coloana kk sunt de forma xn+kxn + k cu 0x<m0 \le x \lt m ar trebui să existe două elemente pn+kpn + k și qn+kqn + k cu pqp \neq q congruente modulo mm Asta ar însemna că diferența lor, (pq)n(p - q)n ar fi divizibilă cu mm Cum nn este prim cu mm rămâne ca pqp - q să fie divizibil cu mm Însă, din cauza faptului că 0p,q<m0 \le p, q \lt m singura posibilitate este p=qp = q Contradicție cu pqp \neq q Deci, presupunerea făcută este falsă, ceea ce înseamnă că formula φ(mn)=φ(m)φ(n)\varphi(mn) = \varphi(m) \varphi(n) este într-adevăr corectă.

Formula pentru φ(px)\varphi(p^x)

Pentru n=pxn = p^x singurele valori pe care le poate lua CMMDC-ul dintre nn și un număr mai mic sau egal cu el sunt 1,p,,pk1, p, \ldots, p^k Prin urmare, numerele care nu sunt prime cu nn sunt multiplii lui pp și anume p,2p,,px1pp, 2p, \ldots, p^{x - 1} p numărul lor fiind px1p^{x - 1} Asta înseamnă că

φ(n)=pxpx1=px1(p1)\varphi(n) = p^x - p^{x - 1} = p^{x - 1} (p - 1)

Generalizarea

Acum putem generaliza foarte ușor formula, folosindu-ne de multiplicitatea indicatorului:

φ(n)=i=1kφ(piei)=i=1kpiei1(pi1)\varphi(n) = \prod_{i = 1}^k \varphi(p_i^{e_i}) = \prod_{i = 1}^k p_i^{e_i - 1}(p_i - 1)

Probleme recomandate

Problema Fracții am explicat-o aici. De asemenea, un exercițiu bun este să adaptați Ciurul lui Eratostene din problema Fracții pentru a calcula eficient suma și numărul divizorilor tuturor numerelor naturale de la 11 la nn În plus, o aplicație importantă a indicatorului lui Euler este Teorema lui Euler, care e foarte utilă în calculul inversului modular, despre care voi scrie într-un articol viitor.

Dacă aveți vreo întrebare despre cele trei aplicații la descompunerea în factori primi, nu ezitați să o adresați mai jos, într-un comentariu Iar dacă vi s-a părut un articol interesant, nu uitați să-i dați un share pe FaceBook!

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii