Osztók listája.Értelemszerűen a szám n csak akkor prím, ha nem osztható egyenlően 2-vel és 1-től és önmagától eltérő egész számmal. A fenti képlet eltávolítja a felesleges lépéseket és időt takarít meg: például miután ellenőriztük, hogy egy szám osztható-e 3-mal, nem kell ellenőrizni, hogy osztható-e 9-cel.
Ismerje meg a moduláris aritmetikát. Az "x mod y" művelet (a mod a latin "modulo" szó rövidítése, jelentése "modul") azt jelenti, hogy "osztd el x-et y-val, és keresd meg a maradékot". Más szóval, a moduláris aritmetikában egy bizonyos érték elérésekor, amelyet ún modult, a számok "visszafordulnak" nullára. Például egy óra a 12-es modulusban méri az időt: 10, 11 és 12 órát mutat, majd visszatér 1-re.
Ismerje meg Fermat kis tételének buktatóit. Minden olyan szám, amelyre a vizsgálati feltételek nem teljesülnek, összetett, de a többi szám csak valószínűleg egyszerűnek tartják. Ha el akarja kerülni a helytelen eredményeket, keressen n a „Carmichael-számok” (összetett számok, amelyek megfelelnek ennek a tesztnek) és „pszeudoprím Fermat-számok” listájában (ezek a számok csak bizonyos értékek esetében felelnek meg a teszt feltételeinek a).
Ha kényelmes, használja a Miller-Rabin tesztet. Habár ez a módszer meglehetősen nehézkes a kézi számításokhoz, gyakran használják számítógépes programok. Elfogadható sebességet biztosít és kevesebb hibát ad, mint a Fermat-féle módszer. Az összetett szám nem tekinthető prímszámnak, ha a számításokat ¼-nél több értékre végezzük a. Ha véletlenszerűen választasz különféle jelentések aés mindegyiknél a teszt pozitív eredményt ad, elég nagy biztonsággal feltételezhetjük, hogy n egy prímszám.
Nagy számok esetén használjon moduláris aritmetikát. Ha nincs kéznél mod funkcióval rendelkező számológép, vagy a számológépet nem olyan műveletekre tervezték, nagy számok, használja a teljesítménytulajdonságokat és a moduláris aritmetikát a számítások megkönnyítése érdekében. Az alábbiakban egy példa található 3 50 (\displaystyle 3^(50)) 50. mód:
Meghatározás 1. prímszám 1-nél nagyobb természetes szám, amely csak önmagával és 1-gyel osztható.
Más szóval, egy szám prím, ha csak két különálló természetes osztója van.
Meghatározás 2. Minden olyan természetes számot hívunk, amelynek önmagán és egyen kívül más osztói is vannak összetett szám.
Más szavakkal egész számok, amelyek nem prímszámok, összetettnek nevezzük. Az 1. definíció azt jelenti, hogy egy összetett számnak kettőnél több természetes osztója van. Az 1-es szám nem prím és nem összetett. csak egy osztója 1 van, és ezen kívül sok prímszámra vonatkozó tétel nem érvényesül az egységre.
Az 1. és 2. definícióból következik, hogy minden 1-nél nagyobb pozitív egész prímszám vagy összetett szám.
Az alábbiakban egy program 5000-ig prímszámok megjelenítésére szolgál. Töltse ki a cellákat, kattintson a "Létrehozás" gombra, és várjon néhány másodpercet.
Nyilatkozat 1. Ha egy p egy prímszám és a tetszőleges egész szám, akkor bármelyik a osztva p, vagy pés a viszonylag prímszámok.
Igazán. Ha egy p prímszám, akkor csak önmagával és 1-gyel osztható, ha a-vel nem osztható p, akkor a legnagyobb közös osztó aés p egyenlő 1. Akkor pés a viszonylag prímszámok.
Nyilatkozat 2. Ha több szám szorzata a 1 , a 2 , a 3 , ... osztható egy prímszámmal p, akkor legalább az egyik szám a 1 , a 2 , a 3 , ... osztható vele p.
Igazán. Ha egyik szám sem osztható vele p, majd a számok a 1 , a 2 , a 3 , ... viszonylag prímszámok lennének a -hoz képest p. De a 3. () következményből az következik, hogy termékük a 1 , a 2 , a 3 , ... szintén koprím a tekintetben p, ami ellentmond az állítás feltételének. Ezért a számok közül legalább az egyik osztható vele p.
Tétel 1. Bármely összetett szám mindig ábrázolható, ráadásul egyedi módon, véges számú prímszám szorzataként.
Bizonyíték. Hadd kösszetett szám, és legyen a Az 1 az egyik osztója, amely különbözik 1-től és önmagától. Ha egy a 1 összetett, akkor az 1-en kívül van és a 1 és egy másik elválasztó a 2. Ha egy a A 2 összetett szám, akkor az 1-en kívül van és a 2 és egy másik elválasztó a 3. Ily módon érvelve és figyelembe véve, hogy a számok a 1 , a 2 , a 3 , ... csökken, és ez a sorozat véges számú tagot tartalmaz, elérünk valamilyen prímszámot p egy . Akkor k ként ábrázolható
Tegyük fel, hogy egy számnak két kiterjesztése van k:
Mert k=p 1 p 2 p 3 ... osztható prímszámmal q 1 , akkor például legalább az egyik tényező p 1 osztható vele q egy . De p 1 prím, és csak 1-gyel és önmagával osztható. Következésképpen p 1 =q 1 (mert q 1 ≠1)
Ekkor a (2)-ből kizárhatjuk p 1 és q 1:
Így biztosítjuk, hogy minden olyan prímszám, amely az első bővítést egy vagy többszöri tényezőként adja meg, legalább ugyanannyiszor lépjen be a második bővítménybe, és fordítva, minden olyan prímszám, amely a második bővítésbe egy vagy többszöri tényezőként lép be. alkalommal is legalább annyiszor belép az első bővítménybe. Ezért bármely prímszám ugyanannyiszor szerepel tényezőként mindkét bővítésben, és így ez a két bővítés azonos.
Összetett szám dekompozíciója k a következő formában írható fel
| (3) |
ahol p 1 , p 2 , ... különböző prímszámok, α, β, γ ... egész pozitív számok.
A dekompozíciót (3) nevezzük kanonikus dekompozíció számok.
prímszámok természetes számok sorozatában egyenetlenül fordulnak elő. A sorozat egyes részeiben több van belőlük, másokban kevesebb. Minél tovább haladunk a számsorok mentén, annál ritkábbak a prímszámok. A kérdés az, hogy van-e legnagyobb prímszám? Az ókori görög matematikus, Eukleidész bebizonyította, hogy végtelenül sok prímszám létezik. Az alábbiakban ezt a bizonyítékot mutatjuk be.
Tétel 2. A prímszámok száma végtelen.
Bizonyíték. Tegyük fel, hogy véges számú prím van, és legyen a legnagyobb prím p. Tekintsük az összes számot p. Az állítás feltételezése szerint ezeknek a számoknak összetettnek kell lenniük, és oszthatónak kell lenniük legalább egy prímszámmal. Válasszunk ki egy számot, amely az összes prímszám plusz 1 szorzata:
Szám z több p mert 2p már több p. p nem osztható ezen prímszámok egyikével sem, mivel mindegyikkel elosztva 1 maradékot ad. Így egy ellentmondáshoz jutunk. Ezért végtelen számú prímszám létezik.
Ez a tétel egy általánosabb tétel speciális esete:
Tétel 3. Legyen megadva egy aritmetikai progresszió
Ezután tetszőleges prímszám n, szintén szerepelnie kell m, tehát be n nem tartalmazhat más elsődleges tényezőket, amelyek nem szerepelnek benne més ráadásul ezek az elsődleges tényezők n nem jelenik meg többször, mint ben m.
Ennek a fordítottja is igaz. Ha egy szám minden prímtényezője n legalább ugyanannyiszor előfordul m, akkor m osztva n.
Nyilatkozat 3. Hadd a 1 ,a 2 ,a 3 ,... különböző prímszámok jelennek meg benne mígy
ahol én=0,1,...α , j=0,1,...,β , k=0,1,..., γ . vegye észre, az a i elfogadja α +1 értékek, β j elfogadja β +1 értékek, γ k veszi γ +1 értékek, ... .
A cikk a prímszámok és az összetett számok fogalmával foglalkozik. Az ilyen számok definícióit példákkal adjuk meg. Bizonyítjuk, hogy a prímek száma korlátlan, és Eratoszthenész módszerével beírjuk a prímszámok táblázatába. Bizonyítékot kapnak arra vonatkozóan, hogy egy szám prím-e vagy összetett.
Yandex.RTB R-A-339285-1
A prímszámokat és az összetett számokat pozitív egész számok közé soroljuk. Egynél nagyobbnak kell lenniük. Az osztókat egyszerű és összetett osztályokra is osztják. Az összetett számok fogalmának megértéséhez először az osztók és a többszörösek fogalmát kell tanulmányozni.
1. definíció
A prímszámok olyan egész számok, amelyek nagyobbak egynél, és két pozitív osztójuk van, azaz önmagukkal és 1-gyel.
2. definíció
Az összetett számok olyan egész számok, amelyek nagyobbak egynél, és legalább három pozitív osztójuk van.
Az egyes nem prímszám és nem is összetett szám. Csak egy pozitív osztója van, ezért különbözik az összes többi pozitív számtól. Minden pozitív egész számot természetesnek nevezünk, vagyis a számlálás során használjuk.
3. definíció
prímszámok természetes számok, amelyeknek csak két pozitív osztójuk van.
4. definíció
Összetett szám egy természetes szám, amelynek kettőnél több pozitív osztója van.
Minden 1-nél nagyobb szám prím vagy összetett. Az oszthatóságból azt kapjuk, hogy 1 és az a szám mindig osztója lesz bármely a számnak, azaz osztható lesz önmagával és 1-gyel. Megadjuk az egész számok definícióját.
5. definíció
Azokat a természetes számokat, amelyek nem prímszámok, összetett számoknak nevezzük.
Prímszámok: 2, 3, 11, 17, 131, 523. Csak önmagukkal és 1-gyel oszthatók. Összetett számok: 6, 63, 121, 6697. Vagyis a 6-os szám 2-re és 3-ra, a 63 pedig 1-re, 3-ra, 7-re, 9-re, 21-re, 63-ra, a 121-re bontható 11-re, 11-re, vagyis osztói 1, 11, 121 lesznek. A 6697-es szám 37-re és 181-re bomlik. Vegyük észre, hogy a prímszámok és a viszonylagos prímszámok fogalma különböző fogalmak.
A prímszámok használatának megkönnyítése érdekében egy táblázatot kell használnia:
Az összes létező természetes szám táblázata irreális, mivel végtelen sok van belőlük. Amikor a számok elérik az 10000-et vagy a 1000000000-et, akkor érdemes elgondolkodni az Eratosthenes szitán.
Tekintsünk egy tételt, amely megmagyarázza az utolsó állítást.
1. tétel
Az 1-től eltérő természetes szám legkisebb pozitív osztója prímszám.
1. bizonyíték
Tegyük fel, hogy a 1-nél nagyobb természetes szám, b pedig a legkisebb nem egy osztója. Ellentmondásos módszerrel kell bizonyítanunk, hogy b prímszám.
Tegyük fel, hogy b egy összetett szám. Innen azt kapjuk, hogy van b-nek egy osztója, amely különbözik 1-től és b-től. Az ilyen osztó jelölése b 1 . Szükséges az 1. feltétel< b 1 < b teljesítve lett.
Abból a feltételből látható, hogy a osztható b-vel, b osztható b 1-gyel, ami azt jelenti, hogy az oszthatóság fogalma így fejeződik ki: a = b qés b = b 1 q 1 , ahol a = b 1 (q 1 q) , ahol q és q 1 egész számok. Az egész számok szorzásának szabálya szerint az egész számok szorzata egy a = b 1 · (q 1 · q) alakú egyenlőséggel rendelkező egész szám. Látható, hogy b 1 az a osztója. Egyenlőtlenség 1< b 1 < b nem egyezik, mert azt kapjuk, hogy b a legkisebb pozitív nem 1 osztója.
2. tétel
Végtelen sok prímszám van.
2. bizonyítás
Tegyük fel, hogy veszünk egy véges számú n természetes számot, és jelöljük p 1 , p 2 , … , p n . Tekintsük a jelzettektől eltérő prímszám megtalálásának egy változatát.
Tekintsük a p számot, amely egyenlő p 1 , p 2 , … , p n + 1 . Nem egyenlő a p 1 , p 2 , … , p n alakú prímeknek megfelelő számokkal. A p szám prím. Ekkor a tételt bizonyítottnak tekintjük. Ha összetett, akkor a p n + 1 jelölést kell vennünk és mutasson osztó eltérést p 1 , p 2 , … , p n bármelyikével.
Ha ez nem így lenne, akkor a p 1 , p 2 , … , p n szorzat oszthatósági tulajdonsága alapján , azt kapjuk, hogy osztható lenne p n + 1 -gyel. Vegye figyelembe, hogy a p n + 1 kifejezés a p szám osztva egyenlő a p 1 , p 2 , … , p n + 1 összeggel. Azt kapjuk, hogy a p n + 1 kifejezés ennek az összegnek a második tagját, amely egyenlő 1-gyel, el kell osztani, de ez lehetetlen.
Látható, hogy tetszőleges számú prímszám között tetszőleges prímszám megtalálható. Ebből az következik, hogy végtelen sok prímszám van.
Mivel sok prímszám van, a táblázatok a 100, 1000, 10000 és így tovább számokra korlátozódnak.
A prímszámok táblázatának összeállításakor figyelembe kell venni azt a tényt, hogy egy ilyen feladat a számok szekvenciális ellenőrzését igényli, 2-től 100-ig. Ha nincs osztó, akkor a táblázatba kerül, ha összetett, akkor nem kerül be a táblázatba.
Nézzük lépésről lépésre.
Ha a 2-es számmal kezdi, akkor csak 2 osztója van: 2 és 1, ami azt jelenti, hogy beírható a táblázatba. A 3-as számmal is. A 4-es szám összetett, 2-re és 2-re kell bontani. Az 5-ös szám prímszám, ami azt jelenti, hogy rögzíthető a táblázatban. Tedd ezt a 100-as számig.
Ez a módszer kényelmetlen és hosszú. Készíthetsz asztalt, de költeni kell nagyszámú idő. Szükséges az oszthatósági kritériumok alkalmazása, ami felgyorsítja az osztók megtalálásának folyamatát.
Az Eratosthenes szitáját használó módszert tartják a legkényelmesebbnek. Vessünk egy pillantást az alábbi táblázatokra. Először a 2, 3, 4, ..., 50 számokat kell felírni.
Most át kell húznia az összes olyan számot, amely 2 többszöröse. Végezzen szekvenciális áthúzást. A következő táblázatot kapjuk:
Térjünk át az 5 többszörösei számok áthúzására. Kapunk:
Áthúzzuk azokat a számokat, amelyek 7, 11 többszörösei. Végül úgy néz ki az asztal
Térjünk át a tétel megfogalmazására.
3. tétel
Az a bázisszám legkisebb pozitív és nem 1 osztója nem haladja meg az a -t, ahol a az adott szám számtani gyöke.
3. bizonyítás
B-t egy a összetett szám legkisebb osztójaként kell jelölni. Van egy q egész szám, ahol a = b · q, és azt kapjuk, hogy b ≤ q . A forma egyenlőtlensége b > q mert a feltétel sérül. A b ≤ q egyenlőtlenség mindkét oldalát meg kell szorozni bármely b pozitív számmal, amely nem egyenlő 1-gyel. Azt kapjuk, hogy b b ≤ b q , ahol b 2 ≤ a és b ≤ a .
A bizonyított tételből látható, hogy a táblázatból a számok törlése oda vezet, hogy olyan számmal kell kezdeni, amely egyenlő b 2 -vel, és kielégíti a b 2 ≤ a egyenlőtlenséget. Vagyis ha kihúzod azokat a számokat, amelyek 2 többszörösei, akkor a folyamat 4-től kezdődik, a 3 többszörösei pedig 9-től, és így tovább 100-ig.
Egy ilyen táblázat összeállítása Eratoszthenész tételével azt mondja, hogy ha minden összetett számot áthúzunk, maradnak olyan prímszámok, amelyek nem haladják meg az n-t. Abban a példában, ahol n = 50, akkor n = 50. Innen azt kapjuk, hogy Eratoszthenész szitája kiszűr minden olyan összetett számot, amelynek értéke nem nagyobb az 50 gyökénél. A számok keresése áthúzással történik.
A megoldás előtt ki kell deríteni, hogy a szám prím vagy összetett. Gyakran használják az oszthatósági kritériumokat. Nézzük meg ezt az alábbi példában.
1. példa
Bizonyítsuk be, hogy a 898989898989898989 összetett szám.
Megoldás
Az adott szám számjegyeinek összege 9 8 + 9 9 = 9 17 . Tehát a 9 17 szám osztható 9-cel, a 9-cel való oszthatóság előjele alapján. Ebből következik, hogy összetett.
Az ilyen jelek nem képesek bizonyítani egy szám elsődlegességét. Ha ellenőrzésre van szükség, más lépéseket kell tenni. A legmegfelelőbb módszer a számok felsorolása. A folyamat során prím- és összetett számok találhatók. Azaz a számok értéke nem haladhatja meg a. Vagyis az a számot prímtényezőkre kell bontani. ha ez igaz, akkor az a szám prímnek tekinthető.
2. példa
Határozzuk meg az 11723 összetett vagy prímszámot.
Megoldás
Most meg kell találnia az 11723 szám összes osztóját. Értékelni kell a 11723-at.
Innen látjuk, hogy 11723< 200 , то 200 2 = 40 000 és 11 723< 40 000 . Получаем, что делители для 11 723 меньше числа 200 .
Az 11723 szám pontosabb becsléséhez a 108 2 = 11 664 kifejezést kell felírni, és 109 2 = 11 881 , akkor 108 2 < 11 723 < 109 2 . Ebből következik, hogy 11723< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.
Felbontáskor azt kapjuk, hogy 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 7, 7 , 7 , 7 A 83 , 89 , 97 , 101 , 103 , 107 mind prímszámok. Ez az egész folyamat egy oszlopos felosztásként ábrázolható. Vagyis osszuk el az 11723-at 19-cel. A 19-es szám az egyik tényezője, hiszen maradék nélkül kapunk osztást. Ábrázoljuk az osztást oszloppal:
Ebből következik, hogy az 11723 összetett szám, mert önmagán és 1-en kívül van még 19 osztója.
Válasz: Az 11723 egy összetett szám.
Ha hibát észlel a szövegben, jelölje ki, és nyomja meg a Ctrl+Enter billentyűkombinációt
A prímszám olyan természetes szám, amely csak önmagával és eggyel osztható.
A többi számot összetettnek nevezzük.
De nem minden természetes szám prímszám.
Egyszerű természetes számok csak azok, amelyek csak önmagukkal és eggyel oszthatók.
Példák prímszámokra:
2; 3; 5; 7; 11; 13;...
Ebből következik, hogy csak a természetes számok prímszámok.
Ez azt jelenti, hogy a prímszámok szükségszerűen természetesek.
De minden természetes szám is egész szám.
Így minden prímszám egész szám.
Példák prímszámokra:
2; 3; 5; 7; 11; 13; 17; 19; 23;...
Csak egy páros prímszám van, ez pedig kettő.
Az összes többi prímszám páratlan.
Miért nem lehet prímszám egy kettőnél nagyobb páros szám?
Hanem azért, mert minden kettőnél nagyobb páros szám önmagával osztható lesz, nem eggyel, hanem kettővel, vagyis egy ilyen számnak mindig három osztója lesz, és esetleg több is.
