Všetky ostatné prirodzené čísla sa nazývajú zložené. Prirodzené číslo 1 nie je ani prvočíslo, ani zložené.
Príklad
Cvičenie. Ktoré z prirodzených čísel napísaných nižšie sú prvočísla:
Odpoveď.
Faktorizácia čísla
Reprezentácia prirodzeného čísla ako súčinu prirodzených čísel sa nazýva faktorizácia. Ak sú pri rozklade prirodzeného čísla všetky faktory prvočísla, potom sa takýto rozklad nazýva prvočíselná faktorizácia.
Veta
(Základná veta aritmetiky)
Každý prirodzené číslo, odlišné od 1, možno rozdeliť na prvočísla a to jedinečným spôsobom (ak identifikujeme rozklady a , kde a sú prvočísla).
Kombináciou identických prvočiniteľov pri rozklade čísla získame takzvaný kanonický rozklad čísla:
kde , sú rôzne prvočísla a sú prirodzené čísla.
Príklad
Cvičenie. Nájdite kanonický rozvoj čísel:
Riešenie. Ak chcete nájsť kanonický rozklad čísel, musíte ich najskôr rozdeliť na prvočísla a potom skombinovať rovnaké faktory a zapísať ich súčin ako mocninu s prirodzeným exponentom:
Odpoveď.
Historický odkaz
Ako určiť, ktoré číslo je prvočíslo a ktoré nie? Najbežnejšia metóda na nájdenie všetkých prvočísel v ľubovoľnom číselnom rozsahu bola navrhnutá v 3. storočí. BC e. Eratosthenes (metóda sa nazýva „Eratosthenovo sito“). Predpokladajme, že musíme určiť, ktoré čísla sú prvočísla. Vypíšeme ich za sebou a vyškrtneme každé druhé číslo z nasledujúcich po čísle 2 - všetky sú zložené, keďže sú násobkami čísla 2. Prvé zo zvyšných neprečiarknutých čísel - 3 - je prvočíslo. Vyškrtnime každé tretie číslo z tých, ktoré nasledujú po čísle 3; ďalšie z neprečiarknutých čísel - 5 - bude tiež prvočíslo. Rovnakým princípom prečiarkneme každé piate číslo od čísel za číslom 5 a vo všeobecnosti každé jedno od čísel za číslom . Všetky zostávajúce neprečiarknuté čísla budú prvočísla.
S pribúdajúcimi prvočíslami sa postupne stávajú čoraz menej bežnými. Už starovekí ľudia si však dobre uvedomovali, že ich je nekonečne veľa. Jeho dôkaz je uvedený v Euklidových prvkoch.
Ilyova odpoveď je správna, ale nie veľmi podrobná. V 18. storočí sa mimochodom ešte jedna považovala za prvočíslo. Napríklad takí veľkí matematici ako Euler a Goldbach. Goldbach je autorom jedného zo siedmich problémov tisícročia – Goldbachovej hypotézy. Pôvodná formulácia hovorí, že každé párne číslo môže byť vyjadrené ako súčet dvoch základné čísla. Navyše, pôvodne sa 1 brala do úvahy ako prvočíslo a vidíme toto: 2 = 1+1. Toto najmenší príklad, čím sa splnila pôvodná formulácia hypotézy. Neskôr to bolo opravené a znenie sa stalo moderný vzhľad: „každé párne číslo počnúc 4 môže byť vyjadrené ako súčet dvoch prvočísel.“
Pripomeňme si definíciu. Prvočíslo je prirodzené číslo p, ktoré má iba 2 odlišné prirodzený deliteľ: samotné p a 1. Dôsledok z definície: prvočíslo p má len jedného prvočísla - samotné p.
Teraz predpokladajme, že 1 je prvočíslo. Prvočíslo má podľa definície iba jedného prvočísla – samo seba. Potom sa ukáže, že každé prvočíslo väčšie ako 1 je deliteľné prvočíslom, ktoré sa od neho líši (1). Ale dve rôzne prvočísla nemožno navzájom deliť, pretože inak to nie sú prvočísla, ale zložené čísla, a to je v rozpore s definíciou. S týmto prístupom sa ukazuje, že existuje len 1 prvočíslo - samotná jednotka. Ale toto je absurdné. Preto 1 nie je prvočíslo.
1, rovnako ako 0, tvoria ďalšiu triedu čísel - triedu neutrálnych prvkov vzhľadom na n-árne operácie v niektorej podmnožine algebraického poľa. Okrem toho, čo sa týka operácie sčítania, 1 je tiež generujúcim prvkom kruhu celých čísel.
S touto úvahou nie je ťažké objaviť analógy prvočísel v iných algebraických štruktúrach. Predpokladajme, že máme multiplikatívnu skupinu vytvorenú z mocniny 2, začínajúcu od 1: 2, 4, 8, 16, ... atď. 2 tu pôsobí ako formujúci prvok. Prvočíslo v tejto skupine je číslo väčšie ako najmenší prvok a deliteľné iba sebou samým a ním najmenší prvok. V našej skupine majú takéto vlastnosti iba 4. V našej skupine už nie sú žiadne prvočísla.
Ak by aj 2 bola v našej skupine prvočíslo, tak pozri prvý odsek – opäť by sa ukázalo, že len 2 je prvočíslo.
V tomto článku budeme skúmať prvočísla a zložené čísla. Najprv uvedieme definície prvočísel a zložených čísel a tiež uvedieme príklady. Potom dokážeme, že prvočísel je nekonečne veľa. Ďalej si napíšeme tabuľku prvočísel a zvážime metódy na zostavenie tabuľky prvočísel, pričom osobitnú pozornosť budeme venovať metóde nazývanej Eratosthenovo sito. Na záver poukážeme na hlavné body, ktoré je potrebné vziať do úvahy pri dokazovaní, že dané číslo je prvočíslo alebo zložené.
Navigácia na stránke.
Prvočísla a zložené čísla – definície a príklady
Koncepty prvočísel a zložených čísel sa vzťahujú na čísla, ktoré sú väčšie ako jedna. Takéto celé čísla sa v závislosti od počtu ich kladných deliteľov delia na prvočísla a zložené čísla. Takže pre pochopenie definície prvočísel a zložených čísel, musíte dobre rozumieť tomu, čo sú deliteľ a násobky.
Definícia.
základné čísla sú celé čísla, veľké jednotky, ktoré majú iba dvoch kladných deliteľov, konkrétne seba a 1.
Definícia.
Zložené čísla sú celé čísla, veľké, ktoré majú aspoň troch kladných deliteľov.
Samostatne si všimneme, že číslo 1 sa nevzťahuje na prvočísla ani na zložené čísla. Jednotka má iba jedného kladného deliteľa, ktorým je samotné číslo 1. Toto odlišuje číslo 1 od všetkých ostatných kladných celých čísel, ktoré majú aspoň dvoch kladných deliteľov.
Vzhľadom na to, že kladné celé čísla sú , a že jedno má iba jedného kladného deliteľa, môžeme uviesť iné formulácie uvedených definícií prvočísel a zložených čísel.
Definícia.
základné čísla sú prirodzené čísla, ktoré majú iba dvoch kladných deliteľov.
Definícia.
Zložené čísla sú prirodzené čísla, ktoré majú viac ako dvoch kladných deliteľov.
Všimnite si, že každé kladné celé číslo väčšie ako jedna je buď prvočíslo, alebo zložené číslo. Inými slovami, neexistuje jediné celé číslo, ktoré by nebolo ani prvočíslo, ani zložené. Vyplýva to z vlastnosti deliteľnosti, ktorá hovorí, že čísla 1 a a sú vždy deliteľmi ľubovoľného celého čísla a.
Na základe informácií v predchádzajúcom odseku môžeme uviesť nasledujúcu definíciu zložených čísel.
Definícia.
Voláme prirodzené čísla, ktoré nie sú prvočísla zložený.
Dajme si príklady prvočísel a zložených čísel.
Príklady zložených čísel zahŕňajú 6, 63, 121 a 6 697. Toto vyhlásenie si tiež vyžaduje objasnenie. Číslo 6 má okrem kladných deliteľov 1 a 6 aj deliteľov 2 a 3, keďže 6 = 2 3, preto je 6 skutočne zložené číslo. Pozitívne faktory 63 sú čísla 1, 3, 7, 9, 21 a 63. Číslo 121 sa rovná súčinu 11·11, takže jeho kladnými deliteľmi sú 1, 11 a 121. A číslo 6 697 je zložené, keďže jeho kladnými deliteľmi sú okrem 1 a 6 697 aj čísla 37 a 181.
Na záver tohto bodu by som chcel ešte upozorniť na fakt, že prvočísla a druhočísla nie sú ani zďaleka to isté.
Tabuľka prvočísel
Prvočísla sú pre pohodlie ich ďalšieho použitia zaznamenané v tabuľke nazývanej tabuľka prvočísel. Nižšie je tabuľka prvočísel do 1000.
Vynára sa logická otázka: „Prečo sme naplnili tabuľku prvočísel len do 1000, nie je možné vytvoriť tabuľku všetkých existujúcich prvočísel“?
Najprv odpovedzme na prvú časť tejto otázky. Pre väčšinu problémov, ktoré vyžadujú použitie prvočísel, budú postačovať prvočísla do tisícky. V iných prípadoch sa s najväčšou pravdepodobnosťou budete musieť uchýliť k niektorým špeciálnym riešeniam. Aj keď, samozrejme, môžeme zostaviť tabuľku prvočísel až do ľubovoľne veľkého konečného čísla kladné číslo, či už je to 10 000 alebo 1 000 000 000, v ďalšom odseku si povieme o metódach zostavovania tabuliek prvočísel, konkrétne si rozoberieme metódu tzv.
Teraz sa pozrime na možnosť (alebo skôr nemožnosť) zostaviť tabuľku všetkých existujúcich prvočísel. Nemôžeme vytvoriť tabuľku všetkých prvočísel, pretože prvočísel je nekonečne veľa. Posledné tvrdenie je veta, ktorú dokážeme po nasledujúcej pomocnej vete.
Veta.
Najmenší kladný deliteľ prirodzeného čísla väčšieho ako jedna okrem 1 je prvočíslo.
Dôkaz.
Nechaj a je prirodzené číslo väčšie ako jedna a b je najmenší kladný deliteľ iného ako jedna. Dokážme, že b je prvočíslo kontradikciou.
Predpokladajme, že b je zložené číslo. Potom existuje deliteľ čísla b (označme ho b 1), ktorý je odlišný od 1 aj b. Ak vezmeme do úvahy aj to, že absolútna hodnota deliteľa nepresahuje absolútnu hodnotu dividendy (vieme to z vlastností deliteľnosti), potom musí byť splnená podmienka 1
Keďže číslo a je deliteľné b podľa podmienky a povedali sme, že b je deliteľné b 1, pojem deliteľnosti nám umožňuje hovoriť o existencii celých čísel q a q 1 takých, že a=b q a b=b 1 q 1 , odkiaľ a= b 1 · (q 1 · q) . Z toho vyplýva, že súčin dvoch celých čísel je celé číslo, potom rovnosť a=b 1 ·(q 1 ·q) udáva, že b 1 je deliteľ čísla a. Berúc do úvahy vyššie uvedené nerovnosti 1
Teraz môžeme dokázať, že prvočísel je nekonečne veľa.
Veta.
Existuje nekonečné množstvo prvočísel.
Dôkaz.
Predpokladajme, že to tak nie je. To znamená, že predpokladajme, že existuje iba n prvočísel a tieto prvočísla sú p 1, p 2, ..., p n. Ukážme, že vždy môžeme nájsť iné prvočíslo, ako je uvedené.
Uvažujme číslo p rovné p 1 ·p 2 ·...·p n +1. Je jasné, že toto číslo sa líši od každého z prvočísel p 1, p 2, ..., p n. Ak je číslo p prvočíslo, potom je veta dokázaná. Ak je toto číslo zložené, potom na základe predchádzajúcej vety existuje prvočíselník tohto čísla (označíme ho p n+1). Ukážme, že tento deliteľ sa nezhoduje so žiadnym z čísel p 1, p 2, ..., p n.
Ak by to tak nebolo, potom by sa podľa vlastností deliteľnosti súčin p 1 ·p 2 ·…·p n delil p n+1. Ale číslo p je tiež deliteľné p n+1, ktoré sa rovná súčtu p 1 ·p 2 ·...·p n +1. Z toho vyplýva, že p n+1 musí deliť druhý člen tohto súčtu, ktorý sa rovná jednej, ale to nie je možné.
Je teda dokázané, že vždy sa dá nájsť nové prvočíslo, ktoré nie je zahrnuté v žiadnom počte vopred určených prvočísel. Preto existuje nekonečne veľa prvočísel.
Takže vzhľadom na to, že prvočísel je nekonečne veľa, pri zostavovaní tabuliek prvočísel sa vždy zhora obmedzíte na nejaké číslo, zvyčajne 100, 1000, 10000 atď.
Eratosthenove sito
Teraz budeme diskutovať o spôsoboch vytvárania tabuliek prvočísel. Predpokladajme, že potrebujeme vytvoriť tabuľku prvočísel do 100.
Najzrejmejšou metódou riešenia tohto problému je postupná kontrola kladných celých čísel, počínajúc 2 a končiacimi 100, na prítomnosť kladného deliteľa, ktorý je väčší ako 1 a menší ako testované číslo (z vlastností deliteľnosti vieme že absolútna hodnota deliteľa nepresahuje absolútnu hodnotu dividendy, nenulovú). Ak sa takýto deliteľ nenájde, potom je testované číslo prvočíslo a zapíše sa do tabuľky prvočísel. Ak sa takýto deliteľ nájde, potom je testované číslo zložené, NIE JE zapísané v tabuľke prvočísel. Potom nasleduje prechod na ďalšie číslo, ktoré sa podobne kontroluje na prítomnosť deliteľa.
Poďme si popísať prvých pár krokov.
Začíname číslom 2. Číslo 2 nemá žiadneho kladného deliteľa okrem 1 a 2. Preto je to jednoduché, preto to zapíšeme do tabuľky prvočísel. Tu treba povedať, že 2 je najmenšie prvočíslo. Prejdime k číslu 3. Jeho možný kladný deliteľ iný ako 1 a 3 je číslo 2. Ale 3 nie je deliteľné 2, preto je 3 prvočíslo a tiež je potrebné ho zahrnúť do tabuľky prvočísel. Prejdime k číslu 4. Jeho kladnými deliteľmi okrem 1 a 4 môžu byť čísla 2 a 3, skontrolujme ich. Číslo 4 je deliteľné 2, preto je 4 zložené číslo a nie je potrebné ho uvádzať v tabuľke prvočísel. Upozorňujeme, že 4 je najmenšie zložené číslo. Prejdime k číslu 5. Skontrolujeme, či aspoň jedno z čísel 2, 3, 4 je jeho deliteľ. Keďže 5 nie je deliteľné 2, 3 alebo 4, potom je prvočíslo a treba ho zapísať do tabuľky prvočísel. Potom nasleduje prechod na čísla 6, 7 a tak ďalej až do 100.
Tento prístup k zostaveniu tabuľky prvočísel nie je ani zďaleka ideálny. Tak či onak má právo na existenciu. Všimnite si, že pri tejto metóde konštrukcie tabuľky celých čísel môžete použiť kritériá deliteľnosti, ktoré mierne urýchlia proces hľadania deliteľov.
Existuje pohodlnejší spôsob vytvorenia tabuľky prvočísel, tzv. Slovo „sito“ prítomné v názve nie je náhodné, pretože akcie tejto metódy pomáhajú takpovediac „preosiať“ celé čísla a veľké jednotky cez Eratosthenovo sito, aby sa oddelili jednoduché od zložených.
Ukážme si Eratosthenovo sito v akcii pri zostavovaní tabuľky prvočísel do 50.
Najprv si zapíšte čísla 2, 3, 4, ..., 50 v poradí.
Prvé napísané číslo, 2, je prvočíslo. Teraz sa od čísla 2 posúvame postupne o dve čísla doprava a tieto čísla škrtáme, kým sa nedostaneme na koniec zostavovanej tabuľky čísel. Tým sa prečiarknu všetky čísla, ktoré sú násobkom dvoch.
Prvé číslo po 2, ktoré nie je prečiarknuté, je 3. Toto číslo je prvočíslo. Teraz sa od čísla 3 postupne posunieme doprava o tri čísla (berúc do úvahy už prečiarknuté čísla) a prečiarkneme ich. Tým sa prečiarknu všetky čísla, ktoré sú násobkom troch.
Prvé číslo po 3, ktoré nie je prečiarknuté, je 5. Toto číslo je prvočíslo. Teraz sa od čísla 5 dôsledne posunieme doprava o 5 čísel (berieme do úvahy aj skôr prečiarknuté čísla) a prečiarkneme ich. Tým sa prečiarknu všetky čísla, ktoré sú násobkami piatich.
Ďalej prečiarkneme čísla, ktoré sú násobkami 7, potom násobkami 11 atď. Proces končí, keď už nie sú žiadne čísla na odčiarknutie. Nižšie je vyplnená tabuľka prvočísel do 50 získaných pomocou Eratosthenovho sita. Všetky neprečiarknuté čísla sú prvočísla a všetky prečiarknuté čísla sú zložené.
Sformulujme a dokážme aj vetu, ktorá urýchli proces zostavovania tabuľky prvočísel pomocou Eratosthenovho sita.
Veta.
Najmenší kladný deliteľ zloženého čísla a, ktorý sa líši od jednotky, nepresahuje , kde je od a .
Dôkaz.
Označme písmenom b najmenšieho deliteľa zloženého čísla a, ktoré je odlišné od jednotky (číslo b je prvočíslo, ako vyplýva z vety dokázanej na samom začiatku predchádzajúceho odseku). Potom existuje celé číslo q také, že a=b·q (tu q je kladné celé číslo, čo vyplýva z pravidiel násobenia celých čísel) a (pre b>q je porušená podmienka, že b je najmenším deliteľom a , keďže q je tiež deliteľ čísla a kvôli rovnosti a=q·b ). Vynásobením oboch strán nerovnosti kladným celým číslom b väčším ako jedna (môžeme to urobiť), dostaneme , z ktorého a .
Čo nám dáva osvedčená veta o Eratosthenovom sitku?
Po prvé, prečiarknutie zložených čísel, ktoré sú násobkami prvočísla b, by malo začínať číslom rovným (to vyplýva z nerovnosti). Napríklad prečiarknutie čísel, ktoré sú násobkom dvoch, by malo začínať číslom 4, násobky troch číslom 9, násobky piatich číslom 25 atď.
Po druhé, zostavenie tabuľky prvočísel až po číslo n pomocou Eratosthenovho sita možno považovať za úplné, ak všetky zložené čísla, ktoré sú násobkami prvočísel, nepresahujú . V našom príklade n=50 (keďže robíme tabuľku prvočísel do 50), a preto by Eratosthenovo sito malo eliminovať všetky zložené čísla, ktoré sú násobkami prvočísel 2, 3, 5 a 7, ktoré nepresiahne aritmetickú druhú odmocninu 50. To znamená, že už nemusíme hľadať a preškrtávať čísla, ktoré sú násobkami prvočísel 11, 13, 17, 19, 23 a tak ďalej až do 47, keďže už budú prečiarknuté ako násobky menších prvočísel 2. 3, 5 a 7.
Je toto číslo prvočíslo alebo zložené?
Niektoré úlohy vyžadujú zistenie, či je dané číslo prvočíslo alebo zložené. Vo všeobecnosti táto úloha nie je ani zďaleka jednoduchá, najmä pri číslach, ktorých písanie pozostáva z veľkého počtu znakov. Vo väčšine prípadov musíte hľadať nejaký konkrétny spôsob, ako to vyriešiť. My sa však pokúsime nasmerovať myšlienkový pochod pre jednoduché prípady.
Samozrejme, môžete skúsiť použiť testy deliteľnosti, aby ste dokázali, že dané číslo je zložené. Ak napríklad nejaký test deliteľnosti ukáže, že dané číslo je deliteľné nejakým kladným celým číslom väčším ako jedna, potom je pôvodné číslo zložené.
Príklad.
Dokážte, že 898,989,898,989,898,989 je zložené číslo.
Riešenie.
Súčet číslic tohto čísla je 9·8+9·9=9·17. Keďže číslo rovnajúce sa 9·17 je deliteľné 9, potom pomocou deliteľnosti 9 môžeme povedať, že pôvodné číslo je deliteľné aj 9. Preto je zložený.
Významnou nevýhodou tohto prístupu je, že kritériá deliteľnosti neumožňujú dokázať prvoradosť čísla. Preto pri testovaní čísla, aby ste zistili, či je prvočíslo alebo zložené, musíte robiť veci inak.
Najlogickejší prístup je vyskúšať všetky možné delitele daného čísla. Ak žiadny z možných deliteľov nie je skutočným deliteľom daného čísla, potom toto číslo bude prvočíslo, inak bude zložené. Z teorém dokázaných v predchádzajúcom odseku vyplýva, že deliče daného čísla a treba hľadať medzi prvočíslami nepresahujúcimi . Dané číslo a možno teda postupne deliť prvočíslami (ktoré sa dajú pohodlne prevziať z tabuľky prvočísel), pričom sa snažíme nájsť deliteľa čísla a. Ak sa nájde deliteľ, potom číslo a je zložené. Ak medzi prvočíslami nepresahujúcimi , nie je deliteľ čísla a, potom číslo a je prvočíslo.
Príklad.
číslo 11 723 jednoduché alebo zložené?
Riešenie.
Poďme zistiť, do akého prvočísla môžu byť deliče čísla 11 723. Aby sme to urobili, poďme hodnotiť.
To je celkom zrejmé 
, od roku 200 2 = 40 000 a 11 723<40 000
(при необходимости смотрите статью porovnanie čísel). Možné hlavné faktory 11 723 sú teda menšie ako 200. Už to nám značne uľahčuje úlohu. Ak by sme to nevedeli, museli by sme prejsť všetkými prvočíslami nie do 200, ale do čísla 11 723.
V prípade potreby môžete presnejšie vyhodnotiť. Pretože 108 2 = 11 664 a 109 2 = 11 881, potom 108 2<11 723<109 2
, следовательно, 
. Akékoľvek z prvočísel menších ako 109 je teda potenciálne prvočíslo daného čísla 11 723.
Teraz postupne rozdelíme číslo 11 723 na prvočísla 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. Ak je číslo 11 723 delené jedným zo zapísaných prvočísel, bude zložené. Ak nie je deliteľné žiadnym zo zapísaných prvočísel, tak pôvodné číslo je prvočíslo.
Nebudeme popisovať celý tento monotónny a monotónny proces delenia. Povedzme hneď, že 11 723
- Preklad
Vlastnosti prvočísel prvýkrát študovali matematici starovekého Grécka. Matematici pytagorejskej školy (500 - 300 pred Kristom) sa zaujímali predovšetkým o mystické a numerologické vlastnosti prvočísel. Ako prví prišli s nápadmi o dokonalých a priateľských číslach.
Dokonalé číslo má súčet svojich vlastných deliteľov rovný sebe samému. Napríklad správnymi deliteľmi čísla 6 sú 1, 2 a 3. 1 + 2 + 3 = 6. Deliteľmi čísla 28 sú 1, 2, 4, 7 a 14. Navyše 1 + 2 + 4 + 7 + 14 = 28.
Čísla sa nazývajú priateľské, ak sa súčet vlastných deliteľov jedného čísla rovná druhému a naopak - napríklad 220 a 284. Môžeme povedať, že dokonalé číslo je priateľské samo k sebe.
V čase Euklidových prvkov v roku 300 p.n.l. Niekoľko dôležitých faktov o prvočíslach už bolo dokázaných. V knihe IX prvkov Euklides dokázal, že existuje nekonečný počet prvočísel. Toto je mimochodom jeden z prvých príkladov použitia dôkazu protirečením. Dokazuje tiež základnú vetu aritmetiky - každé celé číslo môže byť reprezentované jednoznačne ako súčin prvočísel.
Ukázal tiež, že ak je číslo 2n-1 prvočíslo, potom číslo 2n-1 * (2n-1) bude dokonalé. Iný matematik Euler dokázal v roku 1747 ukázať, že všetky párne dokonalé čísla sa dajú zapísať v tejto forme. Dodnes nie je známe, či existujú nepárne dokonalé čísla.
V roku 200 pred Kr. Grék Eratosthenes prišiel s algoritmom na hľadanie prvočísel, ktorý sa nazýva Eratosthenovo sito.
A potom nastal veľký zlom v dejinách štúdia prvočísel, spojený so stredovekom.
Nasledujúce objavy urobil už začiatkom 17. storočia matematik Fermat. Dokázal domnienku Alberta Girarda, že každé prvočíslo v tvare 4n+1 možno zapísať jednoznačne ako súčet dvoch štvorcov, a tiež sformuloval vetu, že každé číslo možno zapísať ako súčet štyroch štvorcov.
Vyvinul novú metódu faktorizácie veľkých čísel a demonštroval ju na čísle 2027651281 = 44021 × 46061. Dokázal tiež Fermatovu Malú vetu: ak je p prvočíslo, potom pre akékoľvek celé číslo a bude platiť, že a p = modulo p.
Toto tvrdenie dokazuje polovicu toho, čo bolo známe ako "čínska domnienka" a pochádza z obdobia pred 2000 rokmi: celé číslo n je prvočíslo práve vtedy, ak je 2 n -2 deliteľné číslom n. Druhá časť hypotézy sa ukázala ako nepravdivá – napríklad 2 341 – 2 je deliteľné 341, hoci číslo 341 je zložené: 341 = 31 × 11.
Fermatova malá veta slúžila ako základ pre mnohé ďalšie výsledky v teórii čísel a metódy na testovanie, či čísla sú prvočísla – mnohé z nich sa používajú dodnes.
Fermat si veľa dopisoval so svojimi súčasníkmi, najmä s mníchom menom Maren Mersenne. V jednom zo svojich listov vyslovil hypotézu, že čísla v tvare 2 n + 1 budú vždy prvočísla, ak n je mocninou dvoch. Testoval to pre n = 1, 2, 4, 8 a 16 a bol si istý, že v prípade, keď n nie je mocninou dvoch, číslo nemusí byť nevyhnutne prvočíslo. Tieto čísla sa nazývajú Fermatove čísla a len o 100 rokov neskôr Euler ukázal, že nasledujúce číslo, 2 32 + 1 = 4294967297, je deliteľné 641, a preto nie je prvočíslo.
Čísla v tvare 2 n - 1 boli tiež predmetom výskumu, pretože je ľahké ukázať, že ak je n zložené, potom je zložené aj samotné číslo. Tieto čísla sa nazývajú Mersennove čísla, pretože ich intenzívne študoval.
Ale nie všetky čísla v tvare 2 n - 1, kde n je prvočíslo, sú prvočísla. Napríklad 2 11 - 1 = 2047 = 23 * 89. Prvýkrát to bolo objavené v roku 1536.
Po mnoho rokov poskytovali čísla tohto druhu matematikom najväčšie známe prvočísla. Že M 19 dokázal Cataldi v roku 1588 a 200 rokov bolo najväčším známym prvočíslom, kým Euler nedokázal, že M 31 bolo tiež prvočíslo. Tento záznam trval ďalších sto rokov a potom Lucas ukázal, že M 127 je prvočíslo (a toto je už číslo 39 číslic), a potom výskum pokračoval s príchodom počítačov.
V roku 1952 bola dokázaná prvotriednosť čísel M 521, M 607, M 1279, M 2203 a M 2281.
Do roku 2005 sa našlo 42 Mersennových prvočísel. Najväčší z nich, M 25964951, pozostáva zo 7816230 číslic.
Eulerova práca mala obrovský vplyv na teóriu čísel, vrátane prvočísel. Rozšíril Fermatovu Malú vetu a zaviedol φ-funkciu. Faktorizoval 5. Fermatovo číslo 2 32 +1, našiel 60 párov priateľských čísel a sformuloval (ale nedokázal dokázať) zákon kvadratickej reciprocity.
Bol prvým, kto zaviedol metódy matematickej analýzy a vyvinul analytickú teóriu čísel. Dokázal, že nielen harmonický rad ∑ (1/n), ale aj rad tvaru
1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…
Výsledok získaný súčtom prevrátených hodnôt prvočísel sa tiež rozchádza. Súčet n členov harmonického radu rastie približne ako log(n) a druhý rad diverguje pomalšie ako log[ log(n) ]. To znamená, že napríklad súčet prevrátených hodnôt všetkých doteraz nájdených prvočísel dá iba 4, hoci séria sa stále líši.
Na prvý pohľad sa zdá, že prvočísla sú medzi celými číslami rozdelené celkom náhodne. Napríklad medzi 100 číslami bezprostredne pred 10000000 je 9 prvočísiel a medzi 100 číslami bezprostredne za touto hodnotou sú len 2. Ale vo veľkých segmentoch sú prvočísla rozdelené celkom rovnomerne. Legendre a Gauss sa zaoberali otázkami ich distribúcie. Gauss raz povedal priateľovi, že za každých voľných 15 minút vždy spočíta počet prvočísel v nasledujúcich 1000 číslach. Do konca života narátal všetky prvočísla do 3 miliónov. Legendre a Gauss rovnako vypočítali, že pre veľké n je prvotná hustota 1/log(n). Legendre odhadol počet prvočísel v rozsahu od 1 do n ako
π(n) = n/(log(n) – 1,08366)
A Gauss je ako logaritmický integrál
π(n) = ∫ 1/log(t) dt
S integračným intervalom od 2 do n.
Výrok o hustote prvočísel 1/log(n) je známy ako teorém o primárnom rozdelení. Snažili sa to dokázať počas celého 19. storočia a pokrok dosiahli Čebyšev a Riemann. Spojili to s Riemannovou hypotézou, zatiaľ neoverenou hypotézou o rozdelení núl Riemannovej zeta funkcie. Hustotu prvočísel súčasne dokázali Hadamard a Vallée-Poussin v roku 1896.
V teórii prvočísel je stále veľa nevyriešených otázok, z ktorých niektoré sú staré stovky rokov:
- Hypotéza dvojčiat je o nekonečnom počte dvojíc prvočísel, ktoré sa od seba líšia o 2.
- Goldbachova domnienka: každé párne číslo, počnúc 4, môže byť reprezentované ako súčet dvoch prvočísel
- Existuje nekonečný počet prvočísel v tvare n 2 + 1?
- Je vždy možné nájsť prvočíslo medzi n 2 a (n + 1) 2? (to, že medzi n a 2n je vždy prvočíslo, dokázal Čebyšev)
- Je počet Fermatových prvočísel nekonečný? Existujú nejaké Fermatove prvočísla po 4?
- existuje aritmetický postup po sebe idúcich prvočísiel pre akúkoľvek danú dĺžku? napríklad pre dĺžku 4: 251, 257, 263, 269. Maximálna zistená dĺžka je 26.
- Existuje nekonečný počet množín troch po sebe idúcich prvočísel v aritmetickej postupnosti?
- n 2 - n + 41 je prvočíslo pre 0 ≤ n ≤ 40. Existuje nekonečný počet takýchto prvočísel? Rovnaká otázka pre vzorec n 2 - 79 n + 1601. Tieto čísla sú prvočísla pre 0 ≤ n ≤ 79.
- Existuje nekonečný počet prvočísel v tvare n# + 1? (n# je výsledkom vynásobenia všetkých prvočísel menších ako n)
- Existuje nekonečný počet prvočísel v tvare n# -1 ?
- Existuje nekonečný počet prvočísel tvaru n? + 1?
- Existuje nekonečný počet prvočísel tvaru n? - 1?
- ak p je prvočíslo, neobsahuje 2 p -1 vždy medzi svojimi faktormi druhé mocniny?
- obsahuje Fibonacciho postupnosť nekonečný počet prvočísel?
Najväčšie dvojčísla sú 2003663613 × 2 195000 ± 1. Pozostávajú z 58711 číslic a boli objavené v roku 2007.
Najväčšie faktoriál prvočíslo (typu n! ± 1) je 147855! - 1. Skladá sa z 142891 číslic a bol nájdený v roku 2002.
Najväčšie prvotné prvočíslo (číslo v tvare n# ± 1) je 1098133# + 1.
Štítky: Pridajte štítky
prvočíslo
prirodzené číslo väčšie ako jedna a nemajúce iných deliteľov okrem seba a jedného: 2, 3, 5, 7, 11, 13... Počet prvočísel je nekonečný.
prvočíslo
kladné celé číslo väčšie ako jedna, ktoré nemá iných deliteľov okrem seba a jedného: 2, 3, 5, 7, 11, 13,... Pojem čísla je základom pri štúdiu deliteľnosti prirodzených (kladných celých čísel ) čísla; Hlavný teorém teórie deliteľnosti totiž stanovuje, že každé kladné celé číslo, okrem 1, je jednoznačne rozložené na súčin niekoľkých čísel (poradie faktorov sa neberie do úvahy). Existuje nekonečne veľa prvočísel (tento návrh poznali starogrécki matematici; jeho dôkaz je dostupný v 9. knihe Euklidových prvkov). Pri skúmaní grúp sú dôležité otázky deliteľnosti prirodzených čísel, a teda otázky súvisiace s prvočíslami; najmä štruktúra skupiny s konečným počtom prvkov úzko súvisí so spôsobom, akým sa tento počet prvkov (poradie skupiny) rozkladá na prvočiniteľa. Teória algebraických čísel sa zaoberá problematikou deliteľnosti algebraických celých čísel; Koncept parciálneho čísla sa ukázal ako nedostatočný na zostavenie teórie deliteľnosti, čo viedlo k vytvoreniu konceptu ideálu. P. G. L. Dirichlet v roku 1837 zistil, že aritmetická postupnosť a + bx pre x = 1, 2,... so spoločnými celými číslami a a b obsahuje nekonečne veľa prvočísel Určiť rozdelenie prvočísel v prirodzenom rade čísel je veľmi ťažké problém v teórii čísel. Je formulovaná ako štúdium asymptotického správania funkcie p(x), ktorá označuje počet čiastkových čísel nepresahujúcich kladné číslo x. Prvé výsledky v tomto smere patria P.L. Čebyševovi, ktorý v roku 1850 dokázal, že existujú dve konštanty a a A, že ═< p(x) < ═при любых x ³ 2 [т. е., что p(х) растет, как функция ]. Хронологически следующим значительным результатом, уточняющим теорему Чебышева, является т. н. асимптотический закон распределения П. ч. (Ж. Адамар, 1896, Ш. Ла Валле Пуссен, 1896), заключающийся в том, что предел отношения p(х) к ═равен
Následne sa značné úsilie matematikov zameralo na objasnenie asymptotického zákona rozdelenia frekvenčného faktora Otázky rozdelenia frekvenčného faktora sú študované tak elementárnymi metódami, ako aj metódami matematickej analýzy. Obzvlášť plodná je metóda založená na použití identity
(súčin sa vzťahuje na všetky P. h. p = 2, 3,...), ako prvý uviedol L. Euler; táto identita platí pre všetky komplexy s reálnou časťou väčšou ako jednota. Na základe tejto identity vedú otázky rozdelenia P. čísel k štúdiu špeciálnej funkcie ≈ zeta funkcia x(s), určenej pre Res > 1 radom
Túto funkciu použil v otázkach distribúcie prvočísel pre reálne s Čebyšev; B. Riemann poukázal na dôležitosť štúdia x(s) pre komplexné hodnoty s. Riemann predpokladal, že všetky korene rovnice x(s) = 0 ležiace v pravej polrovine majú reálnu časť rovnajúcu sa 1/
Táto hypotéza nebola dodnes (1975) dokázaná; jeho dôkaz by urobil veľa pri riešení problému rozdelenia prvočísel Otázky rozdelenia prvočísel úzko súvisia s Goldbachovým problémom, stále nevyriešeným problémom „dvojičiek“ a ďalšími problémami analytickej teórie čísel. Problémom „dvojičiek“ je zistiť, či počet P. čísel líšiacich sa o 2 (ako napr. 11 a 13) je konečný alebo nekonečný. Tabuľky P. čísel ležiacich v rámci prvých 11 miliónov prirodzených čísel ukazujú prítomnosť veľmi veľkých „dvojičiek“ (napríklad 10006427 a 10006429), ale to nie je dôkazom nekonečnosti ich počtu. Mimo zostavených tabuliek sú známe jednotlivé čiastkové čísla, ktoré pripúšťajú jednoduchý aritmetický výraz [napríklad (1965) sa zistilo, že 211213 ≈1 je regulárne číslo; má 3376 číslic].
Lit.: Vinogradov I.M., Základy teórie čísel, 8. vydanie, M., 1972; Hasse G., Prednášky z teórie čísel, prel. z nemčiny, M., 1953; Ingham A. E., Distribúcia prvočísel, prekl. z angličtiny, M. ≈ L., 1936; Prahar K., Rozdelenie prvočísel, prekl. z nemčiny, M., 1967; Trost E., Prvočísla, preklad, z nemčiny, M., 1959.
Wikipedia
prvočíslo
prvočíslo- prirodzené číslo, ktoré má práve dvoch odlišných prirodzených deliteľov - a samo seba. Inými slovami, číslo X je prvočíslo, ak je väčšie ako 1 a je deliteľné bezo zvyšku iba 1 a X. Napríklad 5 je prvočíslo a 6 je zložené číslo, keďže okrem 1 a 6 je deliteľné aj 2 a 3.
Prirodzené čísla, ktoré sú väčšie ako jedna a nie sú prvočíslami, sa nazývajú zložené čísla. Všetky prirodzené čísla sú teda rozdelené do troch tried: jedna. Teória čísel študuje vlastnosti prvočísel. V teórii prstencov prvočísla zodpovedajú neredukovateľným prvkom.
Postupnosť prvočísel začína takto:
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 , 109 , 113 , 127 , 131 , 137 , 139 , 149 , 151 , 157 , 163 , 167 , 173 , 179 , 181 , 191 , 193 , 197 , 199 …