Numere prime. Numerele compuse. Ce înseamnă „număr prim”?

numere prime reprezintă unul dintre cele mai interesante fenomene matematice, care a atras atenția oamenilor de știință și a cetățenilor de rând de mai bine de două mii de ani. În ciuda faptului că acum trăim în era computerelor și a celor mai moderne programe de informare, multe ghicitori ale numerelor prime nu au fost încă rezolvate; există chiar unele pe care oamenii de știință nu știu cum să le abordeze.

Numerele prime sunt, după cum se știe din cursul aritmeticii elementare, acelea care sunt divizibile fără rest doar cu unul și cu el însuși. Apropo, dacă un număr natural este divizibil, pe lângă cele enumerate mai sus, cu orice alt număr, atunci se numește compus. Una dintre cele mai faimoase teoreme afirmă că orice număr compus poate fi reprezentat ca un produs posibil unic al numerelor prime.

Câteva fapte interesante. În primul rând, unitatea este unică în sensul că, de fapt, nu aparține nici numerelor prime, nici numerelor compuse. În același timp, în comunitatea științifică este încă obișnuit să-l clasifice în mod specific ca aparținând primului grup, deoarece formal își satisface pe deplin cerințele.

În al doilea rând, singurul număr par strâns în grupul „numerelor prime” este, desigur, doi. Orice alt număr par pur și simplu nu poate ajunge aici, deoarece prin definiție, pe lângă el însuși și unul, este și divizibil cu doi.

Numerele prime, a căror listă, după cum am menționat mai sus, poate începe cu unul, reprezintă o serie infinită, la fel de infinită ca și seria numerelor naturale. Pe baza teoremei fundamentale a aritmeticii, putem ajunge la concluzia că numerele prime nu sunt niciodată întrerupte și nu se termină niciodată, deoarece altfel seria numerelor naturale ar fi inevitabil întreruptă.

Numerele prime nu apar aleatoriu în seria naturală, așa cum ar putea părea la prima vedere. După ce le-ați analizat cu atenție, puteți observa imediat mai multe caracteristici, dintre care cele mai interesante sunt asociate cu așa-numitele numere „gemene”. Se numesc așa pentru că într-un fel de neînțeles au ajuns unul lângă altul, despărțiți doar de un delimitator par (cinci și șapte, șaptesprezece și nouăsprezece).

Dacă te uiți cu atenție la ele, vei observa că suma acestor numere este întotdeauna un multiplu de trei. Mai mult, la împărțirea celui din stânga la trei, restul rămâne întotdeauna doi, iar cel din dreapta rămâne întotdeauna unul. În plus, însăși distribuția acestor numere de-a lungul seriei naturale poate fi prezisă dacă ne imaginăm această serie întreagă sub formă de sinusoide oscilatorii, ale căror puncte principale se formează atunci când numerele sunt împărțite la trei și doi.

Numerele prime nu sunt doar obiectul unei atenții atente de către matematicienii din întreaga lume, dar au fost de multă vreme folosite cu succes în compilarea diferitelor serii de numere, care stă la baza, printre altele, pentru criptografie. În același timp, trebuie recunoscut că o cantitate mare Misterele asociate cu aceste elemente minunate încă așteaptă să fie rezolvate; multe întrebări au o semnificație nu numai filozofică, ci și practică.

număr prim este un număr natural (întreg pozitiv) care este divizibil fără rest cu doar două numere naturale: prin el însuși. Cu alte cuvinte, un număr prim are exact doi divizori naturali: și numărul însuși.

Prin definiție, mulțimea tuturor divizorilor unui număr prim este de două elemente, adică. reprezintă un set.

Mulțimea tuturor numerelor prime se notează prin simbol. Astfel, datorita definirii multimii numerelor prime, putem scrie: .

Secvența numerelor prime arată astfel:

Teorema fundamentală a aritmeticii

Teorema fundamentală a aritmeticii afirmă că fiecare număr natural mai mare decât unu poate fi reprezentat ca produs de numere prime, și într-un mod unic, până la ordinea factorilor. Astfel, numerele prime sunt „blocurile” elementare ale mulțimii numerelor naturale.

Expansiunea numerelor naturale title="Redată de QuickLaTeX.com" height="13" width="42" style="vertical-align: -1px;"> в произведение простых чисел называют !} canonic:

unde este un număr prim și . De exemplu, extinderea canonică a unui număr natural arată astfel: .

Reprezentarea unui număr natural ca produs de numere prime se mai numește factorizarea unui număr.

Proprietățile numerelor prime

Sita lui Eratosthenes

Unul dintre cei mai faimoși algoritmi pentru căutarea și recunoașterea numerelor prime este sita lui Eratosthenes. Deci, acest algoritm a fost numit după matematicianul grec Eratosthenes din Cirene, care este considerat autorul algoritmului.

Pentru a găsi toate numerele prime mai mici decât un anumit număr, urmând metoda lui Eratostene, urmați acești pași:

Pasul 1. Notați toate numerele naturale de la doi la , adică. .
Pasul 2. Atribuiți variabilei valoarea , adică valoarea egală cu cel mai mic număr prim.
Pasul 3. Taiați în listă toate numerele de la până la care sunt multipli de , adică numerele: .
Pasul 4. Găsiți primul număr neîncrucișat din listă mai mare decât și atribuiți valoarea acestui număr unei variabile.
Pasul 5. Repetați pașii 3 și 4 până când se ajunge la numărul.

Procesul de aplicare a algoritmului va arăta astfel:

Toate numerele rămase neîncrucișate din listă la sfârșitul procesului de aplicare a algoritmului vor fi setul de numere prime de la până la .

Conjectura Goldbach

Coperta cărții „Unchiul Petros și ipoteza Goldbach”

În ciuda faptului că numerele prime au fost studiate de matematicieni destul de mult timp, multe probleme conexe rămân nerezolvate astăzi. Una dintre cele mai cunoscute probleme nerezolvate este Ipoteza lui Goldbach, care se formulează după cum urmează:

• Este adevărat că orice număr par mai mare de doi poate fi reprezentat ca suma a două numere prime (ipoteza binară a lui Goldbach)?
• Este adevărat că orice număr impar mai mare de 5 poate fi reprezentat ca o sumă? trei simple numere (ipoteza Goldbach ternară)?

Trebuie spus că ipoteza Goldbach ternară este un caz special al ipotezei Goldbach binare sau, după cum spun matematicienii, ipoteza Goldbach ternară este mai slabă decât ipoteza Goldbach binară.

Conjectura lui Goldbach a devenit cunoscută pe scară largă în afara comunității matematice în 2000, datorită unei cascadorii de marketing promoționale de către companiile de editură Bloomsbury SUA (SUA) și Faber și Faber (Marea Britanie). Aceste edituri, după ce au lansat cartea „Unchiul Petros și Conjectura lui Goldbach”, au promis să plătească un premiu de 1 milion de dolari SUA oricărei persoane care demonstrează ipoteza lui Goldbach în termen de 2 ani de la data publicării cărții. Uneori, premiul menționat de la edituri este confundat cu premiile pentru rezolvarea problemelor premiului Mileniului. Nu vă înșelați, ipoteza lui Goldbach nu este clasificată de Institutul Clay drept o „provocare milenială”, deși este strâns legată de Ipoteza Riemann- una dintre „provocările mileniului”.

Cartea „Numere prime. Drum lung spre infinit"

Coperta cărții „Lumea matematicii. Numere prime. Drum lung catre infinit"

În plus, vă recomand să citiți o carte de popularizare fascinantă, a cărei adnotare spune: „Căutarea numerelor prime este una dintre cele mai paradoxale probleme din matematică. Oamenii de știință încearcă să o rezolve de câteva milenii, dar, crescând cu noi versiuni și ipoteze, acest mister rămâne încă nerezolvat. Apariția numerelor prime nu este supusă niciunui sistem: ele apar spontan în seria numerelor naturale, ignorând toate încercările matematicienilor de a identifica modele în succesiunea lor. Această carte va permite cititorului să urmărească evoluția conceptelor științifice din cele mai vechi timpuri până în zilele noastre și să introducă cele mai interesante teorii ale căutării numerelor prime.”

În plus, voi cita începutul celui de-al doilea capitol al acestei cărți: „Numerele prime sunt unul dintre subiecte importante, care ne duc înapoi chiar la începuturile matematicii, iar apoi, pe o cale din ce în ce mai complexă, ne conduc în prim-plan. stiinta moderna. Astfel, ar fi foarte util să urmărim istoria fascinantă și complexă a teoriei numerelor prime: exact cum s-a dezvoltat, exact cum au fost adunate faptele și adevărurile care sunt acum general acceptate. În acest capitol vom vedea cum generații de matematicieni au studiat cu atenție numerele naturale în căutarea unei reguli care să prezică apariția numerelor prime - o regulă care a devenit din ce în ce mai evazivă pe măsură ce căutarea progresa. De asemenea, vom analiza în detaliu contextul istoric: în ce condiții au lucrat matematicienii și în ce măsură munca lor a implicat practici mistice și semi-religioase, care nu sunt deloc asemănătoare cu metode științifice, folosit în zilele noastre. Cu toate acestea, încet și cu greu, terenul a fost pregătit pentru noi vederi care i-au inspirat pe Fermat și Euler în secolele al XVII-lea și al XVIII-lea.”

• Traducere

Proprietățile numerelor prime au fost studiate pentru prima dată de matematicieni Grecia antică. Matematicienii școlii pitagoreice (500 - 300 î.Hr.) au fost interesați în primul rând de proprietățile mistice și numerologice ale numerelor prime. Au fost primii care au venit cu idei despre numere perfecte și prietenoase.

Un număr perfect are o sumă a propriilor divizori egală cu el însuși. De exemplu, divizorii proprii ai numărului 6 sunt 1, 2 și 3. 1 + 2 + 3 = 6. Împărțitorii numărului 28 sunt 1, 2, 4, 7 și 14. Mai mult, 1 + 2 + 4 + 7 + 14 = 28.

Numerele sunt numite prietenoase dacă suma divizorilor proprii ai unui număr este egală cu altul și invers - de exemplu, 220 și 284. Putem spune că un număr perfect este prietenos cu el însuși.

Pe vremea Elementelor lui Euclid în 300 î.Hr. mai multe au fost deja dovedite fapte importante referitor la numere prime. În Cartea a IX-a a Elementelor, Euclid a demonstrat că există un număr infinit de numere prime. Acesta, apropo, este unul dintre primele exemple de utilizare a demonstrației prin contradicție. El demonstrează, de asemenea, Teorema fundamentală a aritmeticii - fiecare număr întreg poate fi reprezentat în mod unic ca un produs al numerelor prime.

El a mai arătat că dacă numărul 2n-1 este prim, atunci numărul 2n-1 * (2n-1) va fi perfect. Un alt matematician, Euler, a reușit să arate în 1747 că toate numerele par perfecte pot fi scrise în această formă. Până în prezent nu se știe dacă există numere perfecte impare.

În anul 200 î.Hr. Greacul Eratosthenes a venit cu un algoritm pentru găsirea numerelor prime numit Sita lui Eratosthenes.

Și apoi a avut loc o mare pauză în istoria studiului numerelor prime, asociată cu Evul Mediu.

Următoarele descoperiri au fost făcute deja la începutul secolului al XVII-lea de către matematicianul Fermat. El a demonstrat conjectura lui Albert Girard că orice număr prim de forma 4n+1 poate fi scris unic ca sumă a două pătrate și a formulat, de asemenea, teorema că orice număr poate fi scris ca sumă a patru pătrate.

A dezvoltat noua metoda factorizarea numere mari, și a demonstrat-o pe numărul 2027651281 = 44021 × 46061. El a demonstrat și Teorema Mică a lui Fermat: dacă p este un număr prim, atunci pentru orice număr întreg a va fi adevărat că a p = a modulo p.

Această afirmație dovedește jumătate din ceea ce era cunoscut sub numele de „conjectura chineză” și datează de 2000 de ani: un număr întreg n este prim dacă și numai dacă 2 n -2 este divizibil cu n. A doua parte a ipotezei s-a dovedit a fi falsă - de exemplu, 2.341 - 2 este divizibil cu 341, deși numărul 341 este compus: 341 = 31 × 11.

Mica Teoremă a lui Fermat a servit drept bază pentru multe alte rezultate în teoria numerelor și metode pentru a testa dacă numerele sunt numere prime - dintre care multe sunt încă folosite astăzi.

Fermat a corespuns foarte mult cu contemporanii săi, mai ales cu un călugăr pe nume Maren Mersenne. Într-una dintre scrisorile sale, el a emis ipoteza că numerele de forma 2 n +1 vor fi întotdeauna prime dacă n este o putere a doi. El a testat acest lucru pentru n = 1, 2, 4, 8 și 16 și a fost încrezător că, în cazul în care n nu este o putere a doi, numărul nu este neapărat prim. Aceste numere se numesc numerele lui Fermat și numai 100 de ani mai târziu Euler a arătat că următorul număr, 2 32 + 1 = 4294967297, este divizibil cu 641 și, prin urmare, nu este prim.

Numerele de forma 2 n - 1 au făcut, de asemenea, obiectul cercetării, deoarece este ușor de arătat că dacă n este compus, atunci numărul în sine este și compus. Aceste numere sunt numite numere Mersenne pentru că le-a studiat pe larg.

Dar nu toate numerele de forma 2 n - 1, unde n este prim, sunt prime. De exemplu, 2 11 - 1 = 2047 = 23 * 89. Acesta a fost descoperit pentru prima dată în 1536.

Timp de mulți ani, numerele de acest fel au oferit matematicienilor cele mai mari numere prime cunoscute. Că M 19 a fost dovedit de Cataldi în 1588 și timp de 200 de ani a fost cel mai mare număr prim cunoscut, până când Euler a demonstrat că M 31 a fost și prim. Acest record a durat încă o sută de ani, apoi Lucas a arătat că M 127 este prim (și acesta este deja un număr de 39 de cifre), iar după aceea cercetările au continuat odată cu apariția computerelor.

În 1952 a fost dovedită primitatea numerelor M 521, M 607, M 1279, M 2203 și M 2281.

Până în 2005, au fost găsite 42 de numere prime Mersenne. Cel mai mare dintre ele, M 25964951, este format din 7816230 de cifre.

Lucrarea lui Euler a avut un impact imens asupra teoriei numerelor, inclusiv asupra numerelor prime. El a extins Teorema Mică a lui Fermat și a introdus funcția φ. S-a factorizat al 5-lea număr Fermat 2 32 +1, a găsit 60 de perechi de numere prietenoase și a formulat (dar nu a putut dovedi) legea reciprocității pătratice.

El a fost primul care a introdus metode de analiză matematică și a dezvoltat teoria analitică a numerelor. El a demonstrat că nu numai seria armonică ∑ (1/n), ci și o serie de formă

1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…

Diverge și rezultatul obținut prin suma reciprocelor numerelor prime. Suma n termeni ai seriei armonice crește aproximativ ca log(n), iar a doua serie diverge mai lent ca log[ log(n) ]. Aceasta înseamnă că, de exemplu, suma reciprocelor tuturor numerelor prime găsite până în prezent va da doar 4, deși seria încă diverge.

La prima vedere, se pare că numerele prime sunt distribuite destul de aleatoriu între numere întregi. De exemplu, printre cele 100 de numere imediat înainte de 10000000 există 9 numere prime, iar dintre cele 100 de numere imediat după această valoare sunt doar 2. Dar pe segmente mari numerele prime sunt distribuite destul de uniform. Legendre și Gauss s-au ocupat de problemele distribuției lor. Gauss i-a spus odată unui prieten că în orice 15 minute libere el numără întotdeauna numărul de numere prime din următoarele 1000 de numere. Până la sfârșitul vieții, numărase toate numerele prime până la 3 milioane. Legendre și Gauss au calculat în mod egal că pentru n mare densitatea primului este 1/log(n). Legendre a estimat numărul de numere prime în intervalul de la 1 la n ca

π(n) = n/(log(n) - 1,08366)

Și Gauss este ca o integrală logaritmică

π(n) = ∫ 1/log(t) dt

Cu un interval de integrare de la 2 la n.

Afirmația despre densitatea primelor 1/log(n) este cunoscută sub numele de Teorema distribuției prime. Ei au încercat să demonstreze acest lucru de-a lungul secolului al XIX-lea, iar progresul a fost realizat de Cebyshev și Riemann. Au legat-o cu ipoteza Riemann, o ipoteză încă nedovedită despre distribuția zerourilor funcției zeta Riemann. Densitatea numerelor prime a fost demonstrată simultan de Hadamard și Vallée-Poussin în 1896.

Există încă multe întrebări nerezolvate în teoria numerelor prime, unele dintre ele vechi de sute de ani:

• Ipoteza prime gemene este despre un număr infinit de perechi de numere prime care diferă între ele cu 2
• Conjectura lui Goldbach: orice număr par, începând cu 4, poate fi reprezentat ca suma a două numere prime
• Există un număr infinit de numere prime de forma n 2 + 1?
• Este întotdeauna posibil să găsim un număr prim între n 2 și (n + 1) 2? (faptul că există întotdeauna un număr prim între n și 2n a fost demonstrat de Cebyshev)
• Numărul primelor Fermat este infinit? Există numere prime Fermat după 4?
• există oare progresie aritmetică de numere prime consecutive pentru orice lungime dată? de exemplu, pentru lungimea 4: 251, 257, 263, 269. Lungimea maximă găsită este 26.
• Există un număr infinit de mulțimi de trei numere prime consecutive într-o progresie aritmetică?
• n 2 - n + 41 este un număr prim pentru 0 ≤ n ≤ 40. Există un număr infinit de astfel de numere prime? Aceeași întrebare pentru formula n 2 - 79 n + 1601. Aceste numere sunt prime pentru 0 ≤ n ≤ 79.
• Există un număr infinit de numere prime de forma n# + 1? (n# este rezultatul înmulțirii tuturor numerelor prime mai mici decât n)
• Există un număr infinit de numere prime de forma n# -1?
• Există un număr infinit de numere prime de forma n? + 1?
• Există un număr infinit de numere prime de forma n? - 1?
• dacă p este prim, 2 p -1 nu conține întotdeauna pătrate prime printre factorii săi?
• secvența Fibonacci conține un număr infinit de numere prime?

Cele mai mari numere prime gemene sunt 2003663613 × 2 195000 ± 1. Sunt formate din 58711 cifre și au fost descoperite în 2007.

Cel mai mare număr prim factorial (de tipul n! ± 1) este 147855! - 1. Este format din 142891 de cifre și a fost găsit în 2002.

Cel mai mare număr prim primar (un număr de forma n# ± 1) este 1098133# + 1.

Articolul discută conceptele de numere prime și compuse. Definițiile unor astfel de numere sunt date cu exemple. Oferim o dovadă că numărul numerelor prime este nelimitat și îl vom înregistra în tabelul numerelor prime folosind metoda lui Eratosthenes. Vor fi date dovezi pentru a determina dacă un număr este prim sau compus.

Yandex.RTB R-A-339285-1

Numere prime și compuse - Definiții și exemple

Numerele prime și compuse sunt clasificate ca numere întregi pozitive. Ele trebuie să fie mai mari decât unul. Divizorii sunt, de asemenea, împărțiți în simpli și compoziți. Pentru a înțelege conceptul de numere compuse, trebuie mai întâi să studiați conceptele de divizori și multipli.

Definiția 1

Numerele prime sunt numere întregi mai mari decât unu și au doi divizori pozitivi, adică ele însele și 1.

Definiția 2

Numerele compuse sunt numere întregi mai mari decât unu și au cel puțin trei divizori pozitivi.

Unul nu este nici prim, nici numar compus. Are un singur divizor pozitiv, deci este diferit de toate celelalte numere pozitive. Toate numerele întregi pozitive se numesc numere naturale, adică sunt folosite în numărare.

Definiția 3

numere prime sunt numere naturale care au doar doi divizori pozitivi.

Definiția 4

Numar compus este un număr natural care are mai mult de doi divizori pozitivi.

Orice număr care este mai mare decât 1 este prim sau compus. Din proprietatea divizibilității avem că 1 și numărul a va fi întotdeauna divizori pentru orice număr a, adică va fi divizibil cu el însuși și cu 1. Să dăm o definiție a numerelor întregi.

Definiția 5

Numerele naturale care nu sunt prime se numesc numere compuse.

Numerele prime: 2, 3, 11, 17, 131, 523. Ele sunt divizibile numai prin ele însele și 1. Numere compuse: 6, 63, 121, 6697. Adică, numărul 6 poate fi descompus în 2 și 3, iar 63 în 1, 3, 7, 9, 21, 63 și 121 în 11, 11, adică divizorii săi vor fi 1, 11, 121. Numărul 6697 este descompus în 37 și 181. Rețineți că conceptele de numere prime și numere coprime sunt concepte diferite.

Pentru a ușura utilizarea numerelor prime, trebuie să utilizați un tabel:

Un tabel pentru toate numerele naturale existente este nerealist, deoarece există un număr infinit de ele. Când numerele ajung la dimensiuni de 10000 sau 1000000000, atunci ar trebui să vă gândiți să utilizați Sita lui Eratosthenes.

Să luăm în considerare teorema care explică ultima afirmație.

Teorema 1

Cel mai mic divizor pozitiv, altul decât 1, al unui număr natural mai mare decât unu este un număr prim.

Dovada 1

Să presupunem că a este un număr natural care este mai mare decât 1, b este cel mai mic divizor non-unic al lui a. Este necesar să se demonstreze că b este un număr prim folosind metoda contradicției.

Să presupunem că b este un număr compus. De aici avem că există un divizor pentru b, care este diferit de 1, precum și de b. Un astfel de divizor este notat cu b 1. Este necesară această condiție 1< b 1 < b a fost completat.

Din condiție este clar că a este împărțit cu b, b este împărțit cu b 1, ceea ce înseamnă că conceptul de divizibilitate este exprimat astfel: a = b qși b = b 1 · q 1 , de unde a = b 1 · (q 1 · q) , unde q și q 1 sunt numere întregi. Conform regulii înmulțirii numerelor întregi, avem că produsul numerelor întregi este un număr întreg cu o egalitate de forma a = b 1 · (q 1 · q) . Se poate observa că b 1 este divizorul pentru numărul a. Inegalitatea 1< b 1 < b Nu corespunde, deoarece constatăm că b este cel mai mic divizor pozitiv și non-1 al lui a.

Teorema 2

Există un număr infinit de numere prime.

Dovada 2

Se presupune că luăm un număr finit de numere naturale n și le notăm ca p 1, p 2, …, p n. Să luăm în considerare opțiunea de a găsi un număr prim diferit de cele indicate.

Să luăm în considerare numărul p, care este egal cu p 1, p 2, ..., p n + 1. Nu este egal cu fiecare dintre numerele corespunzătoare numerelor prime de forma p 1, p 2, ..., p n. Numărul p este prim. Atunci teorema este considerată a fi demonstrată. Dacă este compus, atunci trebuie să luați notația p n + 1 și arătați că divizorul nu coincide cu niciunul dintre p 1, p 2, ..., p n.

Dacă nu ar fi așa, atunci, pe baza proprietății de divizibilitate a produsului p 1, p 2, ..., p n , constatăm că ar fi divizibil cu pn + 1. Rețineți că expresia p n + 1 împărțirea numărului p este egală cu suma p 1, p 2, ..., p n + 1. Obținem că expresia p n + 1 Al doilea termen al acestei sume, care este egal cu 1, trebuie împărțit, dar acest lucru este imposibil.

Se poate observa că orice număr prim poate fi găsit între orice număr de numere prime date. Rezultă că există infinit de numere prime.

Deoarece există o mulțime de numere prime, tabelele sunt limitate la numerele 100, 1000, 10000 și așa mai departe.

Atunci când compilați un tabel cu numere prime, ar trebui să țineți cont de faptul că o astfel de sarcină necesită verificarea succesivă a numerelor, începând de la 2 la 100. Dacă nu există divizor, acesta este înregistrat în tabel; dacă este compus, atunci nu este introdus în tabel.

Să ne uităm la asta pas cu pas.

Dacă începeți cu numărul 2, atunci are doar 2 divizori: 2 și 1, ceea ce înseamnă că poate fi introdus în tabel. La fel și cu numărul 3. Numărul 4 este compus; trebuie descompus în 2 și 2. Numărul 5 este prim, ceea ce înseamnă că poate fi înregistrat în tabel. Faceți asta până la numărul 100.

Această metodă este incomodă și necesită timp. Puteți crea o masă, dar va trebui să cheltuiți un numar mare de timp. Este necesar să se utilizeze criterii de divizibilitate, care vor grăbi procesul de găsire a divizorilor.

Metoda care utilizează sita lui Eratosthenes este considerată cea mai convenabilă. Să ne uităm la tabelele de mai jos ca exemplu. Pentru început, se notează numerele 2, 3, 4, ..., 50.

Acum trebuie să tăiați toate numerele care sunt multipli ai lui 2. Efectuați barajuri secvențiale. Obținem un tabel ca:

Trecem la tăierea numerelor care sunt multipli de 5. Primim:

Taiați numerele care sunt multiple ai lui 7, 11. În cele din urmă, masa arată ca

Să trecem la formularea teoremei.

Teorema 3

Cel mai mic divizor pozitiv și non-1 al numărului de bază a nu depășește a, unde a este rădăcina aritmetică a numărului dat.

Dovada 3

Este necesar să notăm b cel mai mic divizor al unui număr compus a. Există un număr întreg q, unde a = b · q, și avem că b ≤ q. Inegalitățile de formă sunt inacceptabile b > q, deoarece condiția este încălcată. Ambele părți ale inegalității b ≤ q ar trebui înmulțite cu orice număr pozitiv b care nu este egal cu 1. Obținem că b · b ≤ b · q, unde b 2 ≤ a și b ≤ a.

Din teorema dovedită este clar că tăierea numerelor din tabel duce la faptul că este necesar să începem cu un număr care este egal cu b 2 și satisface inegalitatea b 2 ≤ a. Adică, dacă tăiați numerele care sunt multipli de 2, atunci procesul începe cu 4, iar multiplii de 3 cu 9 și așa mai departe până la 100.

Compilarea unui astfel de tabel folosind teorema lui Eratostene sugerează că atunci când toate numerele compuse sunt tăiate, vor rămâne numere prime care nu depășesc n. În exemplul în care n = 50, avem că n = 50. De aici rezultă că sita lui Eratostene cerne toate numerele compuse care nu au valoare. valoare mai mare rădăcină de 50. Căutarea numerelor se face prin tăiere.

Înainte de a rezolva, trebuie să aflați dacă numărul este prim sau compus. Criteriile de divizibilitate sunt adesea folosite. Să ne uităm la asta în exemplul de mai jos.

Exemplul 1

Demonstrați că numărul 898989898989898989 este compus.

Soluţie

Suma cifrelor unui număr dat este 9 8 + 9 9 = 9 17. Aceasta înseamnă că numărul 9 · 17 este divizibil cu 9, pe baza testului de divizibilitate cu 9. Rezultă că este compus.

Astfel de semne nu sunt capabile să demonstreze primitatea unui număr. Dacă este necesară verificarea, ar trebui luate alte măsuri. Cel mai mod potrivit- este o grămadă de numere. În timpul procesului, pot fi găsite numere prime și compuse. Adică, numerele nu trebuie să depășească o valoare. Adică, numărul a trebuie descompus în factori primi. dacă acest lucru este satisfăcut, atunci numărul a poate fi considerat prim.

Exemplul 2

Determinați numărul compus sau prim 11723.

Soluţie

Acum trebuie să găsiți toți divizorii numărului 11723. Trebuie evaluat 11723 .

De aici vedem că 11723< 200 , то 200 2 = 40 000 , și 11 723< 40 000 . Получаем, что делители для 11 723 număr mai mic 200 .

Pentru mai mult evaluare precisa numărul 11723, trebuie să scrieți expresia 108 2 = 11 664 și 109 2 = 11 881 , Acea 108 2 < 11 723 < 109 2 . Rezultă că 11723< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.

La extindere, constatăm că 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 , 101 , 103 , 107 sunt toate numere prime. Toate acest proces poate fi descris ca o împărțire după o coloană. Adică, împărțiți 11723 la 19. Numărul 19 este unul dintre factorii săi, deoarece obținem împărțirea fără rest. Să reprezentăm împărțirea ca o coloană:

Rezultă că 11723 este un număr compus, deoarece în plus față de el și 1 are un divizor de 19.

Răspuns: 11723 este un număr compus.

Dacă observați o eroare în text, vă rugăm să o evidențiați și să apăsați Ctrl+Enter

Toate celelalte numere naturale se numesc compuse. Numărul natural 1 nu este nici prim, nici compus.

Exemplu

Exercițiu. Care dintre numerele naturale scrise mai jos sunt prime:

Răspuns.

Factorizarea unui număr

Reprezentarea unui număr natural ca produs al numerelor naturale se numește factorizarea. Dacă în descompunerea unui număr natural toți factorii sunt numere prime, atunci se numește o astfel de descompunere factorizare primara.

Teorema

(Teorema fundamentală a aritmeticii)

Fiecare număr natural, altul decât 1, poate fi descompus în factori primi și într-un mod unic (dacă identificăm descompunerea în factori și , unde și sunt numere prime).

Combinând factori primi identici în descompunerea unui număr, obținem așa-numita descompunere canonică a unui număr:

unde , sunt diverse numere prime și sunt numere naturale.

Exemplu

Exercițiu. Găsiți expansiunea canonică a numerelor:

Soluţie. Pentru a găsi descompunerea canonică a numerelor, trebuie mai întâi să le descompuneți în factori primi, apoi să combinați aceiași factori și să scrieți produsul lor ca putere cu un exponent natural:

Răspuns.

Referință istorică

Cum se determină ce număr este prim și care nu? Cea mai comună metodă de găsire a tuturor numerelor prime din orice interval de numere a fost propusă în secolul al III-lea. î.Hr e. Eratosthenes (metoda se numește „sita lui Eratosthenes”). Să presupunem că trebuie să determinăm care numere sunt prime. Să le scriem pe rând și să tăiem fiecare al doilea număr dintre cele care urmează numărului 2 - toate sunt compuse, deoarece sunt multipli ai numărului 2. Primul dintre numerele rămase netașate - 3 - este prim. Să tăiem fiecare al treilea număr din cei care urmează numărului 3; următorul dintre numerele neîncrucișate - 5 - va fi și el prim. Folosind același principiu, vom tăia fiecare al cincilea număr din cei care urmează numărului 5 și, în general, fiecare dintre cei care urmează numărului . Toate numerele rămase neîncrucișate vor fi numere prime.

Pe măsură ce numerele prime cresc, ele devin treptat din ce în ce mai puțin comune. Cu toate acestea, vechii erau deja conștienți de faptul că există o infinitate de ei. Dovada lui este dată în Elementele lui Euclid.