Descompunerea numerelor în prim-factori, matematică, algebră, geometrie

§ 90. Numerele simple și compuse. Orice număr, desigur, împărțit la unul și în sine. Există o mulțime de numere care sunt împărțite nu numai de unul și de la sine, dar sunt încă alte separatoare; de exemplu, numărul 30, și, în plus, unitatea 30 este încă divizoare 2, 3, 5, 6 și 15.

Orice număr, alta decât una care este divizibil doar de unul și în sine, este simplu (sau absolut simple sau original).

Un număr care este împărțit nu doar de unul și de la sine, ci și pe alte numere, se numește un compus (sau complex).

Numărul 1 nu ia în considerare nici simplă, nici un număr compozit, acesta ocupă o poziție specială.

Există 25 de numere prime mai mici de 100, și anume:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

La sfârșitul cărții este atașat un tabel în care sunt scrise toate numerele prime mai puțin de 6.000.

§ 91. Extinderea unui număr compozit în factori de prim. Orice număr de compus poate fi descompus în factori de prim r. E. prezenta ca un produs de numere prime. De exemplu, se descompun în factori de prim din 12 - înseamnă să prezinte acest număr, după cum urmează: 12 = 2 · 2 · 3.

Să presupunem că doriți să se răspândească factorii principali ai oricărui număr compozit, cum ar fi 420. În acest scop, vom găsi (pe motive de divizibilitatea), cel mai mic număr prim care separă 420; acest număr este 2. Divizare 420 de 2:

Acum, noi căutăm cel mai mic număr prim care împarte un număr compozit 210; acest număr este 2. Împărțiți 210 de 2:

Se înlocuiește în ecuația (1), numărul 210 este egal cu produsul dintre:

420 = 105 · 2 · 2 (2)

Cel mai mic număr prim care împarte numărul compus 105, 105 este 3. Împărțiți 3:

Se înlocuiește în ecuația (2) numărul 105 egal cu produsul dintre:

420 = 35 · 3 · 2 · 2 (3)

Cel mai mic număr prim care împarte un număr de 35 compozit, există 5; împărțirea 35 de 5, vom găsi 7; Adică 35 = 7 · 5 Prin înlocuirea în ecuația (3) numărul 35 egal cu produsul de 7 · 5, obținem:

420 = 7 · 5 · 3 · 2 · 2.

Acest lucru va fi extinderea necesară, pentru că acum toți factorii - numărul de ordinare.

Deoarece produsul nu este afectat de relocarea factorilor, este posibil să le scrie în orice ordine; de obicei, le scrie de la mic la mare, și anume după cum urmează:

420 = 2 · 2 · 1 · 5 · 7.

Prime factorizare este cel mai convenabil pentru a scrie acest lucru:

și anume a scrie acest număr compozit și să efectueze dreapta liniei verticale. Chiar de la bord a pus cel mai mic număr prim care împarte un compus dat, și este împărțit într-un număr dat. Numerele private semnează sub dividendului. Cu acest act particular în același mod ca și cu un număr dat. Acțiunea continuă atâta timp cât unitatea specială nu va funcționa. Apoi, toate numerele cu care se confruntă dreapta liniei, va fi factori de prim ale numărului.

În acest exemplu, de fiecare dată când am fost în căutarea pentru cel de prim împărțitor a primit numărul; Cel mai adesea este - cel mai convenabil mod de a extinde, deoarece este mai mic numărul,

cu atât mai ușor este să-l împărtășească; În plus, există semne simple de divizibilitate pentru cele mai multe separatoare mici. Cu toate acestea, această cale nu este obligatorie, și este adesea factorii principali se poate face mai ușor bt un alt ordin. Astfel, în exemplul nostru, vom vedea, de asemenea, că imediat 420 împărțit la 10 = 2 · 5. Prin urmare, prin expansiunea (în minte)

putem scrie

420 = 10 · 42 = 2 · 5 · 2 · 3 · 7 = 2 · 2 · 3 · 5 · 7

Dacă doriți, de exemplu, la factorul numărul 13 000, putem vedea imediat că 13 000 = 13 · 1000, iar din numărul prim-al 13-lea, apoi este descompusă în factori de prim ale numărului

1000 = 10 x 10 x 10 = 2 · 5 · 2 · 5 · 2 · 5

și obținem imediat:

13 000 = 2 x 2 x 2 x 5 x 5 x 5 x 13.

Să luăm un alt exemplu. Descompunem în factori de prim 8874:

Ajungând la 493 privat, considerăm că este dificil de a decide cu privire la ce număr este împărțit. În astfel de cazuri, accesul la masa de numere prime (la sfârșitul acestei cărți). În cazul în care întâlnește un număr, ne-a pus în dificultate, este divizibil doar de la sine. Numărul 493 nu este în tabelul de numere prime; Prin urmare, acesta este un număr compozit, așa că vom încerca să-l împartă în numere prime 7, 11, 13 și așa mai departe până când, până când vom ajunge la ns diviziune, fără rest ... Se pare că 493 este divizibil cu 17, și, în special, se transformă 29. Acum putem termina expansiunea.

Acest exemplu arată că, uneori, este foarte dificil de a efectua descompunerea compusului, deoarece extinderea ne putem întâlni cu un număr mare de care este dificil de a decide dacă este simplu sau compozit; și dacă este un compozit, nu este întotdeauna ușor să-l cel mai mic prim-împărțitor găsi.

§ 92. exponentiation. În cazul în care numerele de descompunere factoring, precum și în multe alte cazuri, am scrie de multe ori mai mulți factori identice consecutive, cum ar fi 2 × 2 × 2 × 2 sau 5 × 5 × 5. La fel ca și pentru adăugarea de condiții egale, am introdus un nume special (multiplicare) și o desemnare specială (2 x 4 în loc de 2 + 2 + 2 + 2), iar pentru multiplicarea factorilor egale este util să se introducă o denumire specială și denumire specială.

Produsul se numește gradul de factori identici. Astfel, 2 · 2 · 2 · 2 are 2 la puterea a patra. Este scris ca aceasta:

2 · 2 · 2 · 2 = 04 februarie

în timp ce numărul 2 este punctul de bază și numărul de 4 - exponent. Cea mai acțiune este numit construcția numărul 2 în al patrulea grad. În același mod,

Se poate citi: 5 în al treilea grad; aici 5 - de bază și 3 - exponent.

Al doilea grad abreviat ca pătratul bazei, și gradul al treilea - un cub-l. Deci, la 2 iulie citit „7 în caseta“, și din 5 martie - „5 într-un cub“ Prima putere a numărului numit de sine 3 1 = 3. Utilizând notația introdusă din descompunerea numerelor în factori de prime de multe ori pot fi înregistrate este mai scurt; astfel încât, în exemplele discutate în § 91, putem scrie:

420 = 2 3 x 2 x 5 x 7
13 000 = 2 3 „5 3 x 13.

Uneori, o astfel de reducere poate fi foarte vizibile; de exemplu, 1536 = 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 3 = 2 9 × 3.

§ 93. Un număr de compozit poate fi extins doar într-un număr de factori simpli. Este ușor de demonstrat că metoda descrisă în § 91 n. 6, orice număr de compozit poate fi descompus în factori de prim. Dar, folosind această metodă, nu putem lipi în mod necesar la comanda, care a fost specificată de noi, adică, putem începe descompunerea nu este cu cel mai mic prim număr, prin care să împartă compozitul și se produce o expandare într-o altă secvență (sau chiar se poate, după cum am văzut, pentru a răspândi un număr compozit în primul rând pe factorii de componente, atunci acești factori sunt defalcate în simplă) . Deci, se pune întrebarea: nu se poate ajunge acolo, uneori, pentru același compus din două (sau mai multe), un număr diferit de factori prime care diferă unul de altul sau de factori, sau numărul de repetiții ale acelorași factori? De exemplu, numărul 14000 are o extindere april 2 x 5 3 x 7; dacă acesta nu poate avea încă o descompunere, care a inclus ar fi oricare alt prim factor altul decât 2, 5 și 7, sau în care acești factori ar fi repetat alte ori decât în ​​extinderea 2 4 × 5, 3 x 7? Este dovedit faptul că acest lucru nu poate fi, t. E. că numărul compozit, ca și cum nu am descompus, dând doar un singur număr de factori prime (care, desigur, poate fi perestavlyaemy).

Dovada posibilităților și unicitatea descompunerea numerelor în factori de prim. Pentru a dovedi riguros că fiecare număr (cu excepția uneia) poate fi descompus într-una și doar o singură cale în factori de prim, stație de andocare> Cine mai întâi următoarele două teoreme.

Teorema 1. Orice număr diferit de unitatea are cel puțin un prim factor.

Dovada. Să o ≠ 1; în cazul în care un - un număr prim, atunci ea însăși este prim divizor ei, și dovada; dacă - numărul de compozit, are alte divizori decât o și de unitate; lasa b este cea mai mică dintre aceste separatoare; atunci b nu poate fi un număr compozit, ca și în cazul în care a fost împărțit la numărul de c, altele decât unitățile de sine, atunci este numărul de c-ar fi împărțit și numărul de o, și, prin urmare, b nu ar fi cel mai mic divizor al unui . Prin urmare, b - numărul de simplu, dar este un divizor al unei, teorema este demonstrată.

Teorema 2. Produsul de mai mulți factori a1 a2 a3. o este divizibil cu un prim p doar atunci când cel puțin unul dintre factorii este divizibil cu p.

Dovada. (. A2 a3 o): Având în vedere acest lucru ca produs a doi factori numai A1 și, putem argumenta după cum urmează: dacă A1 nu este divizibil cu un prim p, atunci înseamnă că A1 nu este p divizori comune, altele decât unitatea; în acest caz, dovedită într-un număr de 88 § Teorema (a2 a3. o) trebuie să fie divizibil cu p. De asemenea, vom vedea că, dacă a2 nu este divizibil cu p, atunci numărul (a3 a4. O) trebuie să fie divizibil cu p. Continuând acest argument în continuare, vom constata că, dacă nici unul dintre numerele: a1. a2. a3. ..., o-1 nu este divizibil cu p, atunci un divizibil cu p. Deci, unele dintre numerele: a1. a2. a3. ..., o este divizibil cu p.

Acum, pentru a demonstra posibilitatea de a extinde orice număr diferit de unul, pe prim factori, să facă acest lucru. Să o ≠ 1; în cazul în care un - un număr prim, atunci dovada; în cazul în care un - număr de compus, prin Teorema 1, are un simplu p1 compas; lasa

dacă a1 - un număr prim, atunci teorema este dovedită; în cazul în care este compozit, Teorema 1, are un factor de prim p2; lasa

dacă a2 - un număr prim, atunci teorema este dovedită; în cazul în care este compozit, vom continua să vorbim în acest fel. Din moment ce un> a1. .. A1> A2, etc că expansiunea noastră trebuie să se încheie mai devreme sau mai târziu; dar se poate termina doar atunci când unele număr va fi un ușor (dacă este compozit, atunci putem continua descompunerea); atât de descompunere

este descompunerea unei prime în factori, posibilitatea este astfel dovedită.

Pentru a demonstra unicitatea expansiunii va vorbi astfel:

Să presupunem că pentru unii avem doi factori de descompunere (identice sau diferite) prime:

Partea stângă a acestei ecuații este împărțit într-o; Prin urmare, partea dreapta trebuie să fie divizibil cu un. Dar - un număr prim, astfel încât b1 c1 A1 produs. numai apoi împărțit într-o, în cazul în care unul dintre factorii săi este divizată într-o (Teorema 2); dar un număr prim poate fi împărțită în diferite prim număr diferit de unitatea de numai atunci când PRIMES sunt aceleași. Deci, unul dintre numerele: a1 b1 c1. Este egal cu un. Să a1 = o. Împărțind ambele părți printr-o, obținem

Ca și anterior, vom vedea că unul dintre factorii b1. c1. este egal cu b. Să b1 = b; apoi CD-ul. = C1 d1. Continuând acest argument se poate vedea că toți factorii din primul rând sunt, de asemenea, incluse în al doilea rând. Împărțind de ambele părți A1 vedem că, în primul rând are un factor de multiplicare A1. Astfel, la fel ca cel precedent, constatăm că toți factorii din al doilea rând sunt în primul rând. Rezultă că aceste două serii pot fi diferite numai în ordinea factorilor, și nu de factori, cu alte cuvinte, că cele două serii sunt unul și același rând. Cu alte cuvinte, fiecare număr (cu excepția uneia) poate fi descompus în factori de prim pa și, în plus, doar o singură cale.

§ 94. Unele informații despre numere prime. Este ușor de observat că există un număr infinit de numere prime. Într-adevăr, să presupunem contrariul, adică. E. Acest amorsează este finit. În acest caz, cel mai mare număr prim trebuie să existe. Fie ca acest număr să fie o. Pentru a respinge presupunerea făcută, ne imaginăm noul număr N, compus în conformitate cu formula:

N = + 1 (2 · 3 · 5 · 7 a ...),

t. e. Îmi imaginez un număr N, care se obține prin multiplică toate numerele prime de la 2 la și inclusiv un produs și pentru a atașa o altă unitate. Deoarece N, evident, mai mult o, și, prin ipoteză, este cea mai mare dintre numerele prime, atunci N trebuie să fie un număr întreg. Dar numărul compozit este împărțit la un număr prim (§ 93, Teorema 1). Prin urmare, N este împărțit într-un număr de serie 2, 3, 5, 7, 11. a. Dar acest lucru nu poate fi, deoarece N este suma a doi termeni, primul dintre care (produsul 2 · 3 · 5 ... a) este împărțit în orice număr de serie 2, 3, 5 a, iar al doilea (1) nu este divizibil pe unul dintre aceste numere. Acest lucru înseamnă că cel mai mare număr prim nu există; dacă nu cel mai mare număr prim, numărul de numere prime este infinit.

Din cele mai vechi timpuri, numerele prime au făcut obiectul a numeroase studii. Apropo, oamenii de știință au încercat să găsească o redactare a legii de numere prime, care ar fi dat posibilitatea de a-și exprima toate numerele prime cu una sau mai multe formule, sau încearcă să găsească cel puțin următoarea formulă, care, deși nu și-a exprimat toate PRIMES, dar a permis să găsească prim arbitrar de mare număr. În acest sens, mai ales această încercare interesantă la celebrul matematician francez al secolului al XVII-lea. Farm (Fermat). El a descoperit că formula dă 2n + 1 amorse când n este 2 0 = 1 2 1 = 2, 2 2 = 4, 2 3 = 8. De fapt, atunci când aceste valori ale indicelui și obținut prin următoarele PRIMES:

Pe baza acestei observații (și unele considerații asupra proprietăților numerelor), Fermat a sugerat că formula 2 n + 1 trebuie să dea numerele prime pentru orice n, egal cu o putere de 2. Prezentul aviz este o lungă perioadă de timp nu a fost respinsă, deoarece nimeni (Euler) nu a reușit să se precizeze cel puțin un caz când n, egal cu o putere de 2, cu formula 2 n + 1 ar da un număr compozit. Prima ipoteză respinsă Farm cunoscută Euler (XVIII.), Demonstrând că atunci când n = 2 May = 32 formula 2 n + 1 oferă un număr divizibil cu 641. Această eroare este fermă exemplu instructiv, ca metodă de deducții matematică aplicabile la particular total (arătând metoda sau inducție).

(Atunci când n crește 2n expresie + 1 dă numărul crescând cu o rapiditate extremă, de exemplu, când n = 24, numărul 65537 este obținut atunci când n = 2 5 - numărul 4294967297. număr atât de mare a fost dificil de rezolvat (dacă XVII condiție știință și XVIII c.), dar ele sau compozit).

Pentru lipsa de formule care exprimă toate numerele prime, de a crea o nevoie de empiric (experimental) o serie de numere prime succesive de la 2 la orice număr specific de mare o. Cel mai simplu și totuși metoda cea mai veche de preparare a acestei serii apartine matematician alexandrin Eratostene (care a trăit în III. BC). Metoda Eratostene constă în faptul că un număr de numere întregi pozitive de la 2 la un (număr, care doresc să limiteze numărul) este oprit în primul rând este divizibil cu 2 (altele decât cele 2), atunci toate numerele care sunt divizibile cu 3 (cu excepția 3). apoi toate numerele divizibile cu 5, 7, 11 (cu excepția acestor numere), etc. Este foarte simplu: .. emiterea unei serii de numere întregi impare de la 3 la o cruce în acesta fiecare al treilea număr, după 3, fiecare a cincea număr după 5, 7 după fiecare a șaptea și t. d.

În prezent, există tabele de numere prime consecutive mai puțin de 9.000.000.

Dacă nu la îndemână scrisă dintr-un număr de numere prime, sau în cazul în care acest număr de N depășește cel mai mare număr scris dintr-un număr, atunci se pune întrebarea: cum știi dacă N este număr prim sau compozit? Cea mai simplă metodă pentru acest lucru este după cum urmează. Găsirea √N pre, scrie toate numerele prime mai mici decât această rădăcină. Să fie numărul de:

Dacă N nu este împărțit nici unul dintre aceste numere, se poate argumenta fără a se produce fisiuni în continuare că N - numărul de simplu. Într-adevăr, din moment ce N = √N · √N, este evident că, prin împărțirea N de către un număr mai mare √N, ar trebui să primească privat √N, mai mici; astfel încât în ​​cazul în care numărul N poate fi împărțit în orice număr mai mare decât √N, ar fi împărțit și numărul de √N mai mici. Când N este mare, atunci această metodă poate fi destul de obositoare; așa că, dacă N> 1 milion de care √N> 1000, și are 108 de numere prime mai puțin de 1000; Prin urmare, acest test număr ar fi necesar, ocazional, la 168 de diviziuni. În teoria numerelor indică metode prin care se poate reduce semnificativ numărul de diviziuni, necesitatea de a testa un anumit număr; dar în același timp, este încă problema de a stabili dacă un anumit număr este prim sau compozit, este, uneori, până în prezent dificultăți enorme.