Teorema fundamentală a aritmeticii

Teorema fundamentală a aritmeticii afirmă că [1] [2]

fiecare număr natural poate fi factorizat ( extins) sub forma $n>1$ $n=p_{1}\cdot \ldots \cdot p_{k)$ $p_{1},\ldots,p_{k)$

Dacă suntem de acord în mod formal că produsul gol al unei mulțimi goale de numere este egal cu 1, atunci condiția din formulare poate fi omisă - atunci pentru unitate, este implicată factorizarea printr-o mulțime goală de numere prime: [3] [ 4] . $n>1$ $1=1$

În consecință, fiecare număr natural poate fi reprezentat ca $n$

n=p_{1}^{d_{1}}\cdot p_{2}^{d_{2}}\cdot \ldots \cdot p_{k}^{d_{k)),

unde sunt numere prime și unele numere naturale,

p_{1}<p_{2}<\ldots <p_{k)

d_{1},\ldots,d_{k)

și într-un mod unic . Această reprezentare a unui număr se numește factorizarea sa canonică . $n$

Dovada

Conform metodei de inducție

Existenta : vom demonstra existenta unei factorizari a unui numar in factori primi, daca presupunem ca acelasi lucru a fost deja demonstrat pentru orice alt numar mai mic decat . Dacă este prim, atunci existența este dovedită. Dacă este compus, atunci poate fi reprezentat ca un produs de două numere și , fiecare dintre acestea fiind mai mare decât 1, dar mai mic decât . Numerele și sunt fie prime, fie pot fi descompuse într-un produs de numere primi (demonstrat deja mai devreme). Înlocuind descompunerea lor în , obținem descompunerea numărului inițial în numere prime. Existența este dovedită [5] . $n$ $n$ $n$ $n$ $A$ $b$ $n$ $A$ $b$ $n=a\cdot b$ $n$

Unicitatea : Pentru un număr prim, unicitatea este evidentă.

Pentru un număr compus, ideea pentru demonstrație este de a folosi metoda „prin contradicție” , și anume, se presupune că numărul are două expansiuni diferite. Luăm în considerare numerele prime și , care sunt cele mai mici în prima și, respectiv, a doua dintre aceste expansiuni și demonstrăm următoarea lemă: $p_{0}$ $q_{0}$

dacă descompunerea unui număr în factori primi este unică, atunci fiecare divizor prim trebuie inclus în această descompunere. $m$ $m$

În continuare, luăm în considerare numărul , care, la rândul său, este un număr natural și care este mai mic decât . Din ipoteza inductivă și lema de mai sus rezultă că este un divizor al numărului dat, după care se concluzionează în mod similar că prima factorizare este divizibilă cu . Niciun număr prim nu poate apărea în ambele descompunere simultan, deoarece altfel ar fi posibil să-l reducă și să se obțină diferite descompunere în factori primi ai unui număr mai mic de . $n-p_{0}\cdot q_{0)$ $n$ $p_{0}\cdot q_{0}$ $q_{0}$ $n$ $n$

Folosind algoritmul Euclid

Se poate demonstra teorema fundamentală a aritmeticii folosind corolarul din algoritmul lui Euclid [7] :

cel mai mare divizor comun este cel mai mare divizor comun al și înmulțit cu . $n\cdot a$ $n\cdot b$ $A$ $b$ $n$

Din acest corolar, se poate demonstra lema lui Euclid , necesară și pentru demonstrarea teoremei:

dacă este un număr prim și produsul a două numere este divizibil cu , atunci cel puțin unul dintre cei doi factori este divizibil cu . $p$ $p$ $p$

Existență: Ideea din spatele dovezii existenței este de a demonstra lema:

luați în considerare un număr prim și un produs . Dacă este divizibil cu , dar nu este divizibil cu , atunci este divizibil cu . $p$ $n\cdot a$ $n\cdot a$ $p$ $A$ $p$ $n$ $p$

În plus, folosind lema de mai sus, numărul este descompus secvenţial în factori primi, presupunând că toţi divizorii primi ai acestui număr sunt cunoscuţi.

Unicitate: numărul n are două descompuneri diferite în numere prime:

n=p_{1}\cdot p_{2}\cdot p_{3}\cdot \ldots =p'_{1}\cdot p'_{2}\cdot p'_{3}\cdot \ldots

Deoarece este divizibil cu , atunci fie , fie este divizibil cu . Dacă este divizibil cu , atunci , deoarece ambele numere sunt prime. Dacă este divizibil cu , atunci continuăm raționamentul anterior. În cele din urmă, se va dovedi că unul dintre numere este egal cu numărul și, prin urmare, ambele expansiuni ale numărului coincid de fapt. Astfel, este dovedită unicitatea descompunerii. $p'_{1}\cdot p'_{2}\cdot p'_{3}\cdot \ldots$ $p_{1}$ $p'_{1}$ $p'_{2}\cdot p'_{3}\cdot \ldots$ $p_{1}$ $p'_{1}$ $p_{1}$ $p'_{1}=p_{1}$ $p'_{2}\cdot p'_{3}\cdot \ldots$ $p_{1}$ $p'_{1},p'_{2},p'_{3},\ldots$ $p_{1}$

Istorie

Premisele teoremei fundamentale a aritmeticii își au originea în Grecia Antică . În ciuda faptului că în matematica greacă veche teorema de bază a aritmeticii în formularea modernă nu apare, în „ Principii ” ( alte grecești Στοιχεῖα ) Euclid are propoziții echivalente. În urma lui Euclid, mulți matematicieni de-a lungul secolelor au contribuit la demonstrarea teoremei fundamentale a aritmeticii, citând enunțuri apropiate ca înțeles în lucrările lor, printre acești oameni de știință se numără Kamal ad-Din al-Farisi , J. Preste , L Euler , A. Legendre [8] . Prima formulare exactă a teoremei fundamentale a aritmeticii și demonstrarea acesteia sunt date de K. Gauss în cartea „ Investigații aritmetice ” ( lat. Disquisitiones Arithmeticae ), publicată în 1801 [9] . De atunci, au apărut multe noi dovezi diferite ale teoremei, concurând între ele în frumusețe și originalitate [8] .

Euclid (sec. III î.Hr.)

Euclid a stabilit în Elementele fundamente importante pentru teoria numerelor, inclusiv teorema fundamentală a aritmeticii. Trei propoziții foarte apropiate ca înțeles de Teorema fundamentală a aritmeticii pot fi găsite în Cărțile VII și IX, și anume Propoziția 30 din Cartea VII, cunoscută cel mai bine sub numele de Lema lui Euclid , Propunerea 31 din Cartea a VII-a și Propunerea 14 din Cartea IX. Mai jos sunt versiunile lor în traducerea lui Morduchai-Boltovsky :

VII.30:

Dacă două numere, înmulțindu-se între ele, produc ceva, iar ceea ce rezultă din ele este măsurat cu un prim număr, atunci (cel din urmă) va măsura și unul dintre originalul [10]

VII.31:

Fiecare număr compus este măsurat de un prim număr [11]

IX.14:

Dacă numărul este cel mai mic măsurabil (dat) de primele numere, atunci nu poate fi măsurat de niciun alt număr prim, cu excepția celor care l-au măsurat inițial [12]

In prezent[ ce? ] timp, demonstrația teoremei fundamentale a aritmeticii este derivată din Propozițiile VII.30 și VII.31, dar Euclid nu a prezentat această demonstrație în scrierile sale. Propunerea IX.14, la rândul său, este destul de asemănătoare cu afirmația despre unicitatea factorizării în factori primi, dar s-a dovedit că această afirmație nu acoperă toate cazurile posibile - de exemplu, când apare cel puțin un pătrat al unui număr prim. în descompunerea în factori primi [ 13] [14] .

Al-Farisi (sec. XIV)

Celebrul om de știință persan Kamal ad-Din al-Farisi a făcut un pas semnificativ înainte în studiul teoremei fundamentale a aritmeticii. În lucrarea sa Memorandum for friends on the proof of amistability , el a dovedit existența unei factorizări în factori primi și a furnizat informațiile necesare pentru a demonstra unicitatea acestei descompunere. Cu toate acestea, Kamal al-Farisi a fost cel mai interesat să-și construiască propria demonstrație pentru teorema lui Sabit ibn Kurra privind căutarea numerelor prietenoase - și al-Farisi nu a căutat să demonstreze teorema fundamentală a aritmeticii, ci a căutat toți divizorii unui număr compus [15] . Examinând cu scrupulozitate factorizarea numerelor, a formulat și a dovedit o afirmație, care, de fapt, s-a dovedit a fi o dovadă a existenței unei factorizări a unui număr natural în factori primi.

Tradusă, declarația lui sună cam așa:

Fiecare număr compus poate fi descompus într-un număr finit de factori primi din care este un produs.

În afirmația 9, al-Farisi a formulat un principiu pentru determinarea tuturor divizorilor unui număr compus: exact de asta avea nevoie pentru a demonstra teorema lui Ibn Qurra. Traducerea sună astfel:

Dacă un număr compus este descompus în factori primi ca , atunci nu are niciun divizor cu excepția și și produsele fiecăruia dintre ei cu fiecare, produsele tripleților etc., până la produsul tuturor elementelor fără niciunul. $A$ $a=b\cdot c\cdot d\cdot h\cdot \ldots \cdot k\cdot l$ $A$ $unu$ $b,c,d,...,k,l$

Deja din formularea afirmației, se poate concluziona că al-Farisi știa despre unicitatea descompunerii în factori primi. În plus, toate afirmațiile și faptele date de om de știință pentru a demonstra această afirmație sunt un set necesar pentru demonstrarea unicității în teorema principală a aritmeticii.

Jean Preste (secolul al XVII-lea)

Rezultatele publicate de Jean Preste în cartea Elements de Mathématiques (1675) confirmă că descompunerea în factori primi a fost considerată în acele vremuri nu ca ceva de interes în sine, ci ca o aplicație utilă - un mijloc de a găsi divizori ai unui număr dat. . Preste nu a formulat nici existența, nici unicitatea descompunerii și a acordat cea mai mare atenție însăși căutării divizorilor unui număr [16] . În ciuda acestui fapt, Preste, ca și al-Farisi, a furnizat toate informațiile necesare pentru a dovedi unicitatea factorizării prin Corolarul IX al său, care în sine poate fi considerat echivalent cu unicitatea factorizării.

Corolarul IX:

Dacă numerele și sunt prime, atunci fiecare divizor al unui număr este fie , fie , fie , fie unul dintre produsele acestor trei numere cu . Acesta este unul din șase: . $A$ $b$ $a\cdot a\cdot b$ $A$ $a^2$ $unu$ $b$ $1,a,a\cdot a,1\cdot b,a\cdot b,a\cdot a\cdot b$

Euler și Legendre (secolul al XVIII-lea)

În The Complete Guide to Algebra ( germană: Vollstandige Einleitung zur Algebra ), Leonhard Euler a publicat rezultate similare cu cele ale predecesorilor săi. El a formulat existența factorizării unui număr în factori primi și, omițând unele detalii, a oferit o dovadă parțială în acest sens în paragraful 41 al capitolului IV din prima parte a primei secțiuni a cărții.

Traducerea lui este următoarea:

Toate numerele compuse care pot fi factorizate sunt reprezentate prin produsul numerelor prime; adică toți factorii lor sunt numere prime. Căci dacă se găsește un factor care nu este un număr prim, acesta poate fi întotdeauna factorizat și reprezentat prin două sau mai multe numere prime.

Euler nu a formulat teoreme cu privire la unicitatea descompunerii, dar a propus o afirmație similară, pe care a lăsat-o fără dovezi, în secțiunea 65 a capitolului IV din prima secțiune a primei părți. Acolo, Euler explică implicit că factorizarea unui număr în factori primi este unică, spunând că toți divizorii unui număr pot fi găsiți prin cunoașterea factorilor primi din factorizarea numărului dat [17] . Astfel, acest item poate fi considerat echivalent cu unicitatea factorizării.

Această afirmație este tradusă după cum urmează:

Când factorăm un număr în factori primi, devine foarte ușor să găsim toți divizorii lui. Căci trebuie mai întâi să înmulțim factorii primi între ei, apoi să-i înmulțim în perechi, trei cu trei, patru cu patru și așa mai departe, până ajungem la numărul însuși.

„Experiența în teoria numerelor” ( franceză Essai sur la théorie des nombres , 1798) Legendre conține o dovadă a existenței descompunerii în factori primi și o presupunere particulară despre unicitatea acestei descompunere prin enumerarea tuturor divizorilor primi ai unui număr dat. .

Afirmația lui Legendre despre existența unei descompunere este [18] :

Orice număr care nu este prim poate fi reprezentat ca un produs al mai multor numere prime etc., fiecare dintre ele ridicat la o anumită putere, astfel, se poate presupune întotdeauna etc. $N$ $\alpha ,\beta ,\gamma$ $N=\alpha ^{m}\beta ^{n}\gamma ^{p)$

Afirmația legată de unicitatea factorizării este dată în paragraful 10 al introducerii, unde Legendre intenționa să găsească numărul tuturor divizorilor unui număr și, în același timp, suma acestora. Unicitatea este ușor de demonstrat din această afirmație.

Carl Gauss (secolul al XIX-lea)

Prima formulare exactă a teoremei și demonstrația ei sunt date în Investigațiile aritmetice ale lui Gauss (1801). Enunțul teoremei poate fi găsit în paragraful 16, iar traducerea ei este după cum urmează:

Un număr compus poate fi factorizat în factori primi într-un mod unic.

Aplicație

Cel mai mare divizor comun și cel mai mic multiplu comun

Teorema fundamentală a aritmeticii oferă expresii elegante pentru GCD și LCM .

Notați prin toate numerele prime diferite în care numerele au fost descompuse și gradele cu care apar în aceste descompunere, ca și respectiv. Este clar că pot lua doar valori naturale sau zero. ${p_{i}}$ $A$ $b$ ${d_{i)}$ ${d'_{i)}$ ${d_{i}},{d'_{i}}$

Apoi:

{\text{gcd}}(a,b)=p_{1}^{\min\{\,d_{1},d_{1}'\,\}}\cdot p_{2}^ {\min\{\,d_{2},d_{2}'\,\}}\cdot p_{3}^{\min\{\,d_{3},d_{3}'\,\} }\cdot p_{4}^{\min\{\,d_{4},d_{4}'\,\))\cdot \ldots =\prod p_{i}^{\min\{\,d_ {i},d_{i}'\,\}};

{\text{LCD)}(a,b)=p_{1}^{\max\{\,d_{1},d_{1}'\,\))\cdot p_{2}^ {\max\{\,d_{2},d_{2}'\,\}}\cdot p_{3}^{\max\{\,d_{3},d_{3}'\,\} }\cdot p_{4}^{\max\{\,d_{4},d_{4}'\,\))\cdot \ldots =\prod p_{i}^{\max\{\,d_ {i},d_{i}'\,\}}.

Divizori ai unui număr natural

Cunoscând factorizarea unui număr natural, puteți indica imediat toți divizorii acestuia .

Folosim descompunerea canonică a numărului indicat la începutul articolului. Numerele naturale nu sunt altceva decât numărul de numere prime corespondente care apar în descompunerea numărului original. Astfel, pentru a găsi toți divizorii, este suficient să scrieți produse cu toate combinațiile posibile de numere prime, variind numărul fiecăruia din produs de la la $n=p_{1}^{d_{1}}\cdot p_{2}^{d_{2}}\cdot \ldots \cdot p_{k}^{d_{k)),$ $d_{1},\cdots, d_{k)$ $p_{1},...,p_{k}$ $p_{i}$ $0$ $d_{i}$

Exemplu: $N=1164=2\cdot 2\cdot 3\cdot 97=2^{2}\cdot 3^{1}\cdot 97^{1}.$

Deoarece numărul 2 apare în expansiune de 2 ori, poate lua valori întregi de la 0 la 2. În mod similar , ele iau valori de la 0 la 1. Astfel, mulțimea tuturor divizorilor este formată din numere $d_{1}$ $d_{2}$ $d_{3}$

${\begin{alignedat}{2}1,\\2,\\3,\\97,\\2\cdot 2,\\2\cdot 3,\\2\cdot 97,\\3 \cdot 97,\\2\cdot 2\cdot 3,\\2\cdot 2\cdot 97,\\2\cdot 3\cdot 97,\\2\cdot 2\cdot 3\cdot 97.\end{ aliniat}}$ .

Pentru a calcula numărul total de divizori, trebuie să înmulțiți numărul tuturor valorilor posibile pentru diferite . $d_{k}$

În acest exemplu, numărul total de divizori este $2\cdot 2\cdot 3=12.$

Funcții aritmetice

Unele funcții aritmetice pot fi calculate folosind factorizarea prime canonice.

De exemplu, pentru funcția Euler a unui număr natural, formula este valabilă: unde este un număr prim și trece prin toate valorile implicate în expansiunea în factori primi ( dovada ). $\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right),\;\;n>1,$ $p$ $n$

Factorizarea produsului numerelor naturale

Produsul a două numere poate fi calculat după cum urmează:

a\cdot b=p_{1}^{d_{1}+d_{1}'}\,p_{2}^{d_{2}+d_{2}'}\,p_{3} ^{d_{3}+d_{3}'}\,p_{4}^{d_{4}+d_{4}'}\ldots =\prod p_{i}^{d_{i}+d_{ i}'},

unde este puterea cu care apare numărul prim în expansiunea numărului . Exemplu: ${d'_{i)}$ ${p_{i}}$ $b$ $68\cdot 36=(2\cdot 2\cdot 17)\cdot (2\cdot 2\cdot 3\cdot 3)=2^{4}\cdot 3^{2}\cdot 17$

Teorema fundamentală a aritmeticii în inele

Considerăm teorema fundamentală a aritmeticii într-un caz mai general: în inele de normă și în inele euclidiene .

Un inel care are un algoritm de împărțire cu un rest se numește inel euclidian. Pentru orice inel euclidian, demonstrarea teoremei fundamentale a aritmeticii poate fi efectuată exact în același mod ca și pentru numerele naturale.

Teorema fundamentală a aritmeticii în inelul numerelor întregi gaussiene

Teorema principală a aritmeticii cu o ușoară corecție (și anume, se clarifică faptul că factorii sunt luați nu numai până la ordinea succesiunii, ci și până la asociere - proprietățile numerelor gaussiene se obțin unele de la altele prin înmulțirea cu divizorul de unitate : 1, i , −1 sau − i ) are loc în inelul numerelor întregi gaussiene . Ideea demonstrației este de a găsi un algoritm de împărțire cu un rest într-un inel de numere dat [19] .

Neunicitatea descompunerii într-un inel

Totuși, această teoremă nu se aplică tuturor inelelor [19] .

Luați în considerare, de exemplu, numere complexe de forma , unde , sunt numere întregi. Suma și produsul unor astfel de numere vor fi numere de același fel. Apoi primim un inel cu normă . $a=m+in{\sqrt {5}}$ $m$ $n$ $N(a)=m^{2}+5n^{2}=|a|^{2)$

Există două descompuneri diferite pentru numărul 6 din acest inel: . Rămâne de demonstrat că numerele sunt prime. Să demonstrăm că numărul 2 este prim. Fie ca numărul să fie descompus în factori primi ca . Apoi . Și pentru ca numerele și să rămână prime, singura opțiune este ca ele să fie exact 2. $6=2\cdot 3=(1-i{\sqrt {5)})(1+i{\sqrt {5)))$ $2,3,1\pm i{\sqrt {5}}$ $2$ $(m_{1}+in_{1}{\sqrt {5)))(m_{2}+in_{2}{\sqrt {5)))$ $4=|m_{1}+in_{1}{\sqrt {5}}|^{2}|m_{2}+in_{2}{\sqrt {5}}|^{2}= (m_{1}^{2}+5n_{1}^{2})(m_{2}^{2}+5n_{2}^{2})$ $m_{1}+in_{1}{\sqrt {5))$ $m_{2}+in_{2}{\sqrt {5))$ ${\displaystyle m_{1}^{2}+5n_{1}^{2))$ ${\displaystyle m_{2}^{2}+5n_{2}^{2))$

Dar în inelul luat în considerare nu există numere cu norma 2, deci o astfel de descompunere este imposibilă, deci numărul 2 este prim. Numerele sunt tratate în mod similar . $3,1\pm i{\sqrt {5}}$

Inelele în care teorema principală a aritmeticii încă este valabilă se numesc factoriale .

Vezi și

Note

↑ Davenport, 1965 .
↑ Jikov, 2000 , p. 112.
↑ Kaluzhnin, 1969 , p. 6-7.
↑ Weisstein, 2010 , pp. 1126.
↑ Davenport, 1965 , p. 15-16.
↑ Davenport, 1965 , p. 17-18.
↑ Davenport, 1965 , p. 26-27.
↑ 1 2 A. Göksel Ağargün și E. Mehmet Özkan, 2001 , p. 207.
↑ Davenport, 1965 , p. 17.
↑ Începuturile lui Euclid. Cărțile VII - X, 1949 , p. 33.
↑ Începuturile lui Euclid. Cărțile VII - X, 1949 , p. 34.
↑ Începuturile lui Euclid. Cărțile VII - X, 1949 , p. 83.
↑ Hendy, 1975 .
↑ Mullin, 1965 .
↑ A. Göksel Ağargün și E. Mehmet Özkan, 2001 , p. 209.
↑ A. Göksel Ağargün și E. Mehmet Özkan, 2001 , p. 211.
↑ A. Göksel Ağargün și E. Mehmet Özkan, 2001 , p. 212.
↑ A.M. Le Gendre, Essai sur la théorie des nombres , Paris, VI (1798), p. 6.
↑ 1 2 Jikov, 2000 , p. 116.

Literatură

Vinogradov I.M. Fundamentele teoriei numerelor . - Editura de stat de literatură tehnică și teoretică, 1952. - 180 p. — 10.000 de exemplare.
Davenport G. Aritmetică superioară / ed. Yu. V. Linnik , trad. B. Z. Moroz - M . : Nauka , 1965. - S. 15-38. — 176 p.
Jikov V.V. Teorema fundamentală a aritmeticii // Soros Educational Journal . - 2000. - T. 6 , nr 3 . - S. 112-117 .
Kaluzhnin L. A. Teorema fundamentală a aritmeticii . — Prelegeri populare de matematică . — M .: Nauka, 1969. — 32 p.
Courant R., Robbins G. Supliment la capitolul I, § 4.2 // Ce este matematica? - MTSNMO , 2000. - 568 p.
Weisstein E. W. CRC Concise Encyclopedia of Mathematics (engleză) - Ediția a doua - Chapman and Hall London , CRC Press , 2010. - 3242 p. — ISBN 978-1-4200-3522-3
A. Göksel Ağargün și E. Mehmet Özkan. Un studiu istoric al teoremei fundamentale a aritmeticii // Historia Mathematica. - 2001. - Vol. 28. - P. 207-214. - doi : 10.1006/hmat.2001.2318 .
D.D. Mordukhai-Boltovskoy, I.N. Veselovski. Începutul lui Euclid. Cărțile VII-X. - Editura de stat de literatură tehnică și teoretică, 1949. - 510 p.
MD Hendy. Euclid și teorema fundamentală a aritmeticii . - Historia Mathematica 05/1975, 1975.
A. A. Mullin. Observații matematico-filosofice asupra noilor teoreme anaioge teoremei fundamentale a aritmeticii. — Notre Dame Journal of Formal Logic, 1965.

Dicționare și enciclopedii	Britannica (online)

Numerele după caracteristicile de divizibilitate
Informatii generale	Factorizarea numerelor întregi Divizibilitate divizor unitar Funcția divizor număr prim Teorema fundamentală a aritmeticii Număr aritmetic
Forme de factorizare	număr prim Numar compus Semiprim număr dreptunghiular Numărul sfenic Număr fără pătrat Multiplu complet Gradul perfect numărul lui Ahile număr neted Număr obișnuit număr grosier număr neobișnuit
Cu divizori limitați	număr perfect Cifre ușor insuficiente Numere ușor redundante Număr multiperfect Numerele hemiperfecte număr hiperperfect număr super perfect prim unitar număr semiperfect număr pararitmic numărul Erdős-Nicolas
Numerele cu mulți divizori	Numere în exces Numerele în exces primitive Numere extrem de redundante Numere super redundante Numere extrem de redundante număr supercompus Un număr foarte supercompus număr ciudat
Legat de secvențele alicote	număr sacru numere amicale numere publice Numere aproape prietenoase
Alte	Nu sunt suficiente numere numere de prieteni numere sublimate Numerele de minereu număr umil Cifre egale număr extravagant