Hogyan állapítható meg, hogy a számok másodprímek? Második prímszámok

A $p$-t prímszámnak nevezzük, ha csak $2$ osztói vannak: $1$ és önmaga.

osztó természetes szám Az $a$ egy természetes szám, amellyel az eredeti $a$ szám maradék nélkül osztható.

1. példa

Keresse meg a $6$ szám osztóit.

Megoldás: Meg kell találnunk mindazon számokat, amelyekkel az adott $6$ szám maradék nélkül osztható. Ezek számok lesznek: $1,2,3,6$. Tehát a $6$ szám osztója az $1,2,3,6.$ számok lesznek

Válasz: $1,2,3,6$.

Tehát egy szám osztóinak megtalálásához meg kell találni az összes természetes számot, amelyekkel az adott maradék nélkül osztható. Könnyen belátható, hogy az $1$ szám bármely természetes szám osztója lesz.

2. definíció

Összetett A számot olyan számnak nevezzük, amelynek az egyen és önmagán kívül más osztói is vannak.

Példa a prímszámra 13 USD, összetett számra pedig 14 USD.

Megjegyzés 1

A $1$ számnak csak egy osztója van – ez maga a szám, tehát nem osztályozható sem prímnek, sem összetettnek.

Második prímszámok

3. definíció

Második prímszámok Azokat, akiknek a GCD értéke $1$, hívjuk, tehát ahhoz, hogy megtudjuk, hogy a számok másodlagosak-e, meg kell találni a GCD-jüket, és össze kell hasonlítani a $1$-tal.

Páronkénti koprím

4. definíció

Ha egy számhalmazban bármelyik kettő koprím, akkor az ilyen számokat hívjuk páronkénti koprím. Két szám esetében a "coprime" és a "pairwise coprime" fogalma megegyezik.

2. példa

8 $, 15 $ - nem prím, hanem koprím.

6, 8, 9 dollár – kölcsönösen prímszámok, de nem páronkénti koprím.

8, 15, 49 dollár páronkénti koprím.

Amint látjuk, annak meghatározásához, hogy a számok koprímek-e, először fel kell bontani őket prímtényezőkre. Figyeljünk arra, hogyan kell ezt helyesen csinálni.

Prímfaktorizálás

Például faktorizáljuk a $180$ számot:

180 USD=2\cdot 2\cdot 3\cdot 3\cdot 5$

Használjuk a fokok tulajdonságát, akkor azt kapjuk,

180 USD=2^2\cdot 3^2\cdot 5$

A prímtényezőkre való bontás ilyen ábrázolását kanonikusnak, azaz kanonikusnak nevezzük. egy szám kanonikus formában történő faktorizálásához szükséges a hatványtulajdonság használata, és a számot különböző bázisú hatványok szorzataként kell ábrázolni.

Természetes szám kanonikus felbontása általános formában

Természetes szám kanonikus felbontása in Általános nézetúgy néz ki, mint a:

$m=p^(n1)_1\cdot p^(n2)_2\cdot \pontok \pontok ..\cdot p^(nk)_k$

ahol $p_1,p_2\pontok \pontok .p_k$ prímszámok és kitevők fokok - természetes számok.

Ha egy számot egyszerű halmazokra kanonikus bontásként ábrázolunk, akkor könnyebben megtalálhatjuk a számok legnagyobb közös osztóját, és ez a másodprímszámok bizonyításának vagy meghatározásának következménye.

3. példa

Keresse meg a $180$ és a 240$ legnagyobb közös osztóját.

Megoldás: Bontsa fel a számokat egyszerű halmazokra a kanonikus bontás segítségével

$180=2\cdot 2\cdot 3\cdot 3\cdot 5$, majd $180=2^2\cdot 3^2\cdot 5$

240 USD=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 5$, majd 240 USD=2^4\cdot 3\cdot 5$

Most keressük meg ezeknek a számoknak a GCD-jét, ehhez válasszunk azonos bázisú és legkisebb kitevőjű fokokat, majd

$gcd \ (180;240)= 2^2\cdot 3\cdot 5=60$

Komponáljunk algoritmus a gcd megtalálására, figyelembe véve a kanonikus felosztást prímtényezőkre.

Két szám legnagyobb közös osztójának megtalálásához a kanonikus kiterjesztéssel a következőket kell tennie:

faktorizálja a számokat prímtényezőkké kanonikus formában
válasszon fokokat azonos bázissal és a számok felosztásában szereplő számok legkisebb kitevőjével
Keresse meg a 2. lépésben talált számok szorzatát. Az eredményül kapott szám lesz a kívánt legnagyobb közös osztó.

4. példa

Határozza meg, hogy a $195$ és a $336$ számok prím-, másodprímszámok-e.

195 USD=3\cdot 5\cdot 13 USD

336 $=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 7=2^4\cdot 3\cdot 5$

$gcd \ (195;336) =3\cdot 5=15$

Látjuk, hogy ezeknek a számoknak a gcd-je eltér a $1$-tól, ami azt jelenti, hogy a számok nem másodlagos prímek. Azt is látjuk, hogy a számok mindegyike tartalmaz faktorokat az $1$-on és magán a számon kívül, ami azt jelenti, hogy a számok sem prímszámok, hanem összetettek lesznek.

5. példa

Határozza meg, hogy a $39$ és a $112$ számok prím-, másodprímszámok-e.

Megoldás: A faktorizáláshoz a kanonikus faktorizációt használjuk:

112 $=2\cdot 2\cdot 2\cdot 2\cdot 7=2^4\cdot 7$

$gcd \ (39;112)=1$

Látjuk, hogy ezeknek a számoknak a gcd értéke $1$, ami azt jelenti, hogy a számok másodprímek. Azt is látjuk, hogy a számok mindegyike tartalmaz faktorokat az $1$-on és magán a számon kívül, ami azt jelenti, hogy a számok sem prímszámok, hanem összetettek lesznek.

6. példa

Határozza meg, hogy a $883$ és a $997$ számok prímszámok-e.

Megoldás: A faktorizáláshoz a kanonikus faktorizációt használjuk:

$883=1\cdot 883$

997 USD=1\cdot 997 USD

$gcd \ (883;997)=1$

Látjuk, hogy ezeknek a számoknak a gcd értéke $1$, ami azt jelenti, hogy a számok másodprímek. Azt is látjuk, hogy mindegyik szám csak $1$-nak megfelelő tényezőket és magát a számot tartalmazza, ami azt jelenti, hogy a számok prímek lesznek.

Kivéve ±1.

14 és 25 másodlagos szám, mivel nincs közös osztójuk;
15 és 25 nem viszonylag prím, mert közös osztójuk 5;

Vizuális ábrázolás: ha egy síkon „erdőt” építünk úgy, hogy nulla vastagságú „fákat” állítunk be egész koordinátájú pontokra, akkor az origóból csak azok a fák láthatók, amelyek koordinátái másodlagosak, példaként lásd a jobb oldali ábrát. egy „fa” láthatósága koordinátákkal (9 , 4).

Jelölés

A számok kölcsönös egyszerűségének jelzésére m (\displaystyle m)És n (\displaystyle n) jelölést használnak:

m ⊥ n . (\displaystyle m\perp n.)

Azonban nem minden matematikus ismeri fel és használja ezt a jelölést. A leggyakrabban használt megfogalmazás vagy azzal egyenértékű jelölés gcd (a , b) = 1 (\displaystyle \gcd(a,b)=1), ami azt jelenti: "a számok legnagyobb közös osztója aÉs b egyenlő 1"

Kapcsolódó definíciók

Ha egy számhalmazban Bármi két szám koprím, akkor az ilyen számokat nevezzük páronkénti koprím. Két szám esetében a "coprime" és a "pairwise coprime" fogalma megegyezik.

Példák

8, 15 - nem prím, hanem másodprím.
A 6, 8, 9 másodprím (együttesen) számok, de nem páronkénti koprímszámok.
A 8, 15, 49 páronkénti koprím.

Tulajdonságok

Számok a (\displaystyle a)És b (\displaystyle b) coprime akkor és csak akkor, ha az egyenértékű feltételek valamelyike teljesül:
Bármely két (különböző) prímszám viszonylag prím.
Ha a (\displaystyle a)- termékosztó bc (\displaystyle bc), És a (\displaystyle a) kölcsönösen egyszerű b (\displaystyle b), azután a (\displaystyle a)- osztó c (\displaystyle c).
Ha számok a 1 , … , a n (\displaystyle a_(1),\ldots ,a_(n)) akkor páronkénti koprímszámok NEM C(a 1 , … , a n) = | a 1 ⋅ … ⋅ a n | (\displaystyle (a_(1),\ldots ,a_(n))=|a_(1)\cdot \ldots \cdot a_(n)|). Például a NOC (9, 11) = 9 ⋅ 11 = 99 (\displaystyle (9,11)=9\cdot 11=99).
Annak a valószínűsége, hogy bármelyik k (\displaystyle k) A véletlenszerűen kiválasztott pozitív egész számok relatív prímszámok lesznek, egyenlők -vel, abban az értelemben, hogy mikor N → ∞ (\displaystyle N\to \infty ) annak a valószínűsége k (\displaystyle k) pozitív egész számok kisebbek, mint N (\displaystyle (\textstyle (N)))(és véletlenszerűen választott) másodlagos lesz, hajlamos arra 1 ζ (k) (\displaystyle (\dfrac (1)(\zeta (k)))). Itt ζ (k) (\displaystyle \zeta (k))- ezt

A $p$-t prímszámnak nevezzük, ha csak $2$ osztói vannak: $1$ és önmaga.

Az $a$ természetes szám osztója olyan természetes szám, amellyel az eredeti $a$ szám osztható maradék nélkül.

1. példa

Keresse meg a $6$ szám osztóit.

Válasz: $1,2,3,6$.

2. definíció

Összetett A számot olyan számnak nevezzük, amelynek az egyen és önmagán kívül más osztói is vannak.

Példa a prímszámra 13 USD, összetett számra pedig 14 USD.

Megjegyzés 1

A $1$ számnak csak egy osztója van – ez maga a szám, tehát nem osztályozható sem prímnek, sem összetettnek.

Második prímszámok

3. definíció

Páronkénti koprím

4. definíció

Ha egy számhalmazban bármelyik kettő koprím, akkor az ilyen számokat hívjuk páronkénti koprím. Két szám esetében a "coprime" és a "pairwise coprime" fogalma megegyezik.

2. példa

8 $, 15 $ - nem prím, hanem koprím.

A 6, 8, 9 dollár másodpímszámok, de nem páronkénti másodpímszámok.

8, 15, 49 dollár páronkénti koprím.

Amint látjuk, annak meghatározásához, hogy a számok koprímek-e, először fel kell bontani őket prímtényezőkre. Figyeljünk arra, hogyan kell ezt helyesen csinálni.

Prímfaktorizálás

Például faktorizáljuk a $180$ számot:

180 USD=2\cdot 2\cdot 3\cdot 3\cdot 5$

Használjuk a fokok tulajdonságát, akkor azt kapjuk,

180 USD=2^2\cdot 3^2\cdot 5$

Természetes szám kanonikus felbontása általános formában

A természetes szám kanonikus kiterjesztésének általában a következő formája van:

$m=p^(n1)_1\cdot p^(n2)_2\cdot \pontok \pontok ..\cdot p^(nk)_k$

ahol $p_1,p_2\pontok \pontok .p_k$ prímszámok, a kitevők pedig természetes számok.

3. példa

Keresse meg a $180$ és a 240$ legnagyobb közös osztóját.

Megoldás: Bontsa fel a számokat egyszerű halmazokra a kanonikus bontás segítségével

$180=2\cdot 2\cdot 3\cdot 3\cdot 5$, majd $180=2^2\cdot 3^2\cdot 5$

240 USD=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 5$, majd 240 USD=2^4\cdot 3\cdot 5$

Most keressük meg ezeknek a számoknak a GCD-jét, ehhez válasszunk azonos bázisú és legkisebb kitevőjű fokokat, majd

$gcd \ (180;240)= 2^2\cdot 3\cdot 5=60$

Komponáljunk algoritmus a gcd megtalálására, figyelembe véve a kanonikus felosztást prímtényezőkre.

Két szám legnagyobb közös osztójának megtalálásához a kanonikus kiterjesztéssel a következőket kell tennie:

faktorizálja a számokat prímtényezőkké kanonikus formában
válasszon fokokat azonos bázissal és a számok felosztásában szereplő számok legkisebb kitevőjével
Keresse meg a 2. lépésben talált számok szorzatát. Az eredményül kapott szám lesz a kívánt legnagyobb közös osztó.

4. példa

Határozza meg, hogy a $195$ és a $336$ számok prím-, másodprímszámok-e.

195 USD=3\cdot 5\cdot 13 USD

336 $=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 7=2^4\cdot 3\cdot 5$

$gcd \ (195;336) =3\cdot 5=15$

5. példa

Határozza meg, hogy a $39$ és a $112$ számok prím-, másodprímszámok-e.

Megoldás: A faktorizáláshoz a kanonikus faktorizációt használjuk:

112 $=2\cdot 2\cdot 2\cdot 2\cdot 7=2^4\cdot 7$

$gcd \ (39;112)=1$

6. példa

Határozza meg, hogy a $883$ és a $997$ számok prímszámok-e.

Megoldás: A faktorizáláshoz a kanonikus faktorizációt használjuk:

$883=1\cdot 883$

997 USD=1\cdot 997 USD

$gcd \ (883;997)=1$

Meghatározás1. Egész számok a 1 ,a 2 ,…,a k koprímnek nevezzük, ha (a 1 ,a 2 ,…,a k) =1

2. definíció. Az а 1 ,а 2 ,…,ak egész számokat páronkénti koprímnek nevezzük, ha i,s (i, s = 1, 2, .. , k, is, (а i , а s) =1) .

Ha a számok megfelelnek a 2. definíciónak, akkor ezek is megfelelnek az 1. definíciónak. Ennek fordítottja nem igaz általános esetben, például: (15, 21, 19)= 1, de (15, 21) = 3

Tétel (kölcsönös elsődlegességi kritérium)

(a, b) = 1<=> x, y Z: ax + by = 1

Bizonyíték:

Bizonyítsuk be a szükségességet. Legyen (а, b) = 1. Fentebb megmutattuk, hogy ha d=(a, b), akkor  x, y  Z: d = ax + by.

Mivel ebben az esetben d =1, akkor lesz  x, y Z (az Euklidész algoritmusból meghatározva): 1 = ax + bу.

Megfelelőség. Legyen (*) ax + = 1, bebizonyítjuk, hogy (a, b)=1. Tegyük fel, hogy (a, b) = d, akkor a (*) egyenlőség bal oldalán

(a / d ) & ( b/d ) => (ax + by) /d => (1/d) => (d=l) => (a, b) = 1.

4. §. Az egész számok Nok és tulajdonságai.

1. definíció. Az a 1 ,a 2 ,…,a k véges halmazának a nullától eltérő közös többszöröse egy m egész szám, amely osztható minden a i számmal (i=l, 2,…, k)

2. definíció. Egy egész számot (m) az а 1 ,а 2 ,…,a k nullától eltérő számok legkisebb közös többszörösének nevezünk, ha:

1 m - közös többszörösük;

2 (m) osztja e számok bármely más közös többszörösét.

Jelölés: m = LCM (a 1, a 2,…, a k) vagy m = [a 1, a 2,…, a k]

Példa. Adott számok: 2, 3, 4, 6, 12.

A 12, 24. 48. 96 számok 2, 3, 4, 6, 12 közös többszörösei. A legkisebb közös többszörös a 12. azaz.

Az LCM egyedileg meghatározott a tényezők sorrendjéig. Valóban, ha feltételezzük, hogy m 1 \u003d [a, b] &m 2 \u003d  (m 1 / m 2) & (m 2 / m 1) => [(m 1 = m 2) v (m 1 = - m 2)]. Két egész szám legkisebb közös többszöröse és legnagyobb közös osztója között kapcsolat van, amelyet a következő képlettel fejezünk ki: [a, b] = ab / (a, b) (következtesse ki saját maga)

Ez a kapcsolat lehetővé teszi számunkra, hogy kijelentsük, hogy minden nullától eltérő egész számpárnak van a legkisebb közös többszöröse. Valójában (a, b) mindig egyértelműen származtatható az euklidészi algoritmusból, és definíció szerint (a, b)  0, akkor az ab/(a, b)  0 tört egyedileg lesz meghatározva.

A két egész szám legegyszerűbb LCM-jét akkor számítjuk ki, ha (a, b) = 1, akkor [a, b] = ab/1 = a b

Például = 215/1 = 105, mert (21, 5) = 1.

§öt. Prímszámok és tulajdonságaik.

1. definíció. Egy természetes számot (p) prímnek nevezünk, ha p > 1, és nincs pozituma. 1-től és p-től eltérő osztók.

2. definíció. Az a > 1 természetes számot, amelynek 1-en és önmagán kívül más pozitív osztói is vannak, összetettnek nevezzük.

Ezekből a meghatározásokból az következik, hogy a természetes számok halmaza három osztályba osztható:

a) összetett számok;

b) prímszámok;

c) egység.

Ha a összetett, akkor a = nq, ahol 1

1. feladat. Bizonyítsuk be, hogy ha aZ és p prímszám, akkor (a, p) = 1 v (a / p)

Bizonyíték.

Legyen d = (a, p) => (a / d) & (p / d), mert p prímszám, akkor két osztója van: 1 és p. Ha (a, p) = 1, akkor a és p relatív prímek, ha (a, p) = p, akkor (a/p).

2. feladat. Ha több tényező szorzata osztható p-vel, akkor legalább az egyik tényező osztható p-vel.

Megoldás.

Hagyja, hogy a termék (a 1, a 2, ..., és k)/p, ha minden a i nem osztható p-vel, akkor a szorzat koprím lesz p-vel, ezért valamilyen tényező osztható p-vel.

3. feladat. Bizonyítsuk be, hogy egy a > 1 egész szám 1-től eltérő legkisebb osztója prímszám.

Bizonyíték.

Legyen aZ és a összetett szám (ha a = p, akkor az állítás igazolt), akkor a = a 1 q.

Legyen q a legkisebb osztó, mutassuk meg, hogy prímszám lesz. Ha feltételezzük, hogy q egy összetett szám, akkor q \u003d q 1 k és a \u003d a 1 q 1 k, mert q 1

4. feladat. Bizonyítsuk be, hogy egy természetes szám (n) legkisebb prímosztója (p) nem haladja meg a n értéket.

Bizonyíték.

Legyen n = pn 1, és p< n 1 и р - простое. Тогда n  р 2 =>R<n .

Ebből az állításból következik, hogy ha egy természetes szám (n) nem osztható egyetlen р n prímszámmal sem, akkor n prímszám, különben összetett lesz.

1. példa. Tudja meg, hogy a 137-es szám prímszám-e? tizenegy<137 <12.

Felírjuk a 137-nél nem nagyobb prímosztókat: 2, 3, 5, 7, 11. Ellenőrizzük, hogy a 137 nem osztható-e 2-vel, 3-mal, 5-tel, 7-tel, 11-gyel. Ezért a 137-es szám prím.

Euklidész tétele. A prímszámok halmaza végtelen.

Bizonyíték.

Tegyük fel az ellenkezőjét, legyen p 1 ,p 2, ..., p k mind prímszámok, ahol p 1 = 2 és p k a legnagyobb prímszám.

Állítsunk össze természetes számot  = p 1 p 2  ... p +1, as  p i , akkor összetettnek kell lennie, ekkor a legkisebb osztója egyszerű lesz (lásd 3. feladat).  azonban nem osztható sem p 1-gyel, sem p 2-vel,…, sem p k-vel, mert 1 nem osztható p I -vel.

Következésképpen téves volt az a feltételezésünk, hogy a prímszámok halmaza véges.

Van azonban egy tétel, amely kimondja, hogy a prímszámok a természetes sorozat számainak csak kis részét teszik ki.

Az intervallumtétel. A természetes sorozatban tetszőlegesen hosszú intervallumok vannak, amelyek egyetlen prímszámot sem tartalmaznak.

Bizonyíték.

Vegyünk egy tetszőleges természetes számot (n) és alkossunk természetes számsorozatot (n+1)!+2, n+1)!+3,…,(n+1)!+(n+1).

Ebben a sorozatban minden következő szám 1-gyel több, mint az előző, ezek a számok összetettek, mert mindegyiknek kettőnél több osztója van (például az első szám osztható 1-gyel, 2-vel és önmagával). Mivel n→∞ egy tetszőlegesen hosszú intervallumot kapunk, amely csak összetett számokból áll.

Euklidész tétele és intervallumtétele a prímszámok természetes sorozatbeli eloszlásának összetett természetéről tanúskodik.

Az aritmetika alaptétele

Bármely n>1 természetes szám egyedileg ábrázolható prímszámok szorzataként, a tényezők sorrendjéig.

Bizonyíték.

Bizonyítsuk be a reprezentáció lehetőségét:

Legyen nN és n>1, ha n prímszám, akkor n = p és a tétel bizonyítást nyer. Ha n összetett, akkor a legkisebb osztója egy prímszám lesz, és n = p 1 n 1, ahol n 1

Ezután hasonlóan vitatkozunk. Ha n 1 prímszám, akkor a tétel bizonyítva van, ha n 1 összetett szám, akkor n 1 = p 2 n 2, ahol n 2< n 1 и тогда n = p 1 p 2 n 2 . На каком-то шаге получим n = p 1 p 2 …p n , где все p i - простые числа.

Bizonyítsuk be a bővítés egyediségét:

Tegyük fel, hogy az (n) számnak két különböző reprezentációja van: n = p 1 p 2 …p k, n = q 1 q 2 …q n és n>k.

Ekkor azt kapjuk, hogy p 1 p 2 …p k = q 1 q 2 …q n (1). Az (1) egyenlőség bal oldala osztható p 1 -gyel, majd a prímszámok tulajdonságával (lásd 2. feladat), a jobb oldalon lévő tényezők közül legalább egy osztható p 1 -gyel.

Legyen (q 1 /p 1) => (q 1 =p 1). Ha az (1) egyenlőség mindkét oldalát elosztjuk p 1 -gyel, a p 2 p 3 …p k = q 2 q 3 …q n egyenlőséget kapjuk. Az előző gondolatmenetet többször (k-1) megismételve az 1 = q k +1 q k +2 …q n egyenlőséget kapjuk, mert minden q i >1, akkor ez az egyenlőség lehetetlen. Ezért mindkét bővítésben a faktorok száma azonos (k=n), és maguk a tényezők azonosak.

Megjegyzés. Az (n) szám prímtényezőkre történő bontása során ezek egy része megismétlődhet. Ha  1 , 2 ,…, k betűkkel jelöljük előfordulásuk (n-ben) többszörösét, megkapjuk az (n) szám úgynevezett kanonikus kiterjesztését:

2. példa

Az 588000 szám kanonikus kiterjesztése = 2 5 35 3 7 2

Következmény 1. Ha
akkor az (n) szám minden osztójának alakja:
ahol 0 i  i (i = 1, 2,…,k).

3. példa A 720 = 2 4 3 2 5 szám összes osztóját kapjuk, ha a kifejezésben
 1 ,  2 ,  3 helyett egymástól függetlenül a következő értékeket cseréljük:  1 =0, 1, 2, 3, 4,  2 =0, 1, 2,  3 = 0, 1 .

A kívánt osztók egyenlők lesznek: 1; 2; 4; 8; 16; 3; 6; 12; 24; 48; kilenc; tizennyolc; 36; 72; 144; öt; 10; húsz; 40; 80; 15; harminc; 60; 120; 240; 45; 90; 180; 360; 720.

2. következmény. Ha
És
akkor (a, b) = p 1  1 p 2  2 …p k  k , ahol i = min( I ,  i)

P 1  1 p 2  2 …p k  k , ahol i = max( I ,  i).

4. példa Keresse meg a gcd(a, b) és lcm(a, b) értékeket kanonikus felbontással if

(24, 42) = 23 = 6

A matematika tankönyveket néha nehéz olvasni. A szerzők száraz és tiszta nyelvezetét nem mindig könnyű megérteni. Igen, és az ottani témák mindig összefüggenek, kölcsönösen áramlanak. Egy-egy téma elsajátításához több korábbit is fel kell vetni, és néha át kell lapozni az egész tankönyvet. Nehéz? Igen. Vállaljuk meg e nehézségek megkerülésének kockázatát, és próbáljunk meg egy nem szabványos megközelítést találni a témához. Tegyünk egyfajta kirándulást a számok országába. A definíciót azonban változatlan formában hagyjuk, mert a matematika szabályait nem lehet törölni. Tehát a másodprímszámok természetes számok, amelyek közös osztója eggyel egyenlő. Ez világos? Egészen.

Vizuálisabb példához vegyük a 6-os és 13-as számokat. Mindkettő osztható eggyel (kölcsönösen prím). De a 12 és 14 számok nem lehetnek ilyenek, hiszen nem csak 1-gyel, hanem 2-vel is oszthatók. A következő számok - 21 és 47 szintén nem férnek bele a "koprímszámok" kategóriájába: nem csak oszthatók 1-én, hanem 7-én is.

A koprímszámokat a következőképpen jelöljük: ( de, y) = 1.

Még egyszerűbben is elmondható: a közös osztó (legnagyobb) itt egyenlő eggyel.
Miért van szükségünk ilyen tudásra? Elég ok.

Egyes titkosítási rendszerekben kölcsönösen szerepel. Azok, akik Hill titkosítással vagy a Caesar helyettesítési rendszerrel dolgoznak, megértik, hogy e tudás nélkül nem juthat el sehova. Ha hallott már a generátorokról, akkor valószínűleg nem meri letagadni: ott is használnak koprímszámokat.

Most beszéljünk az ilyen egyszerűek beszerzésének módjairól, amint megérti, csak két osztójuk lehet: oszthatók önmagukkal és eggyel. Tegyük fel, hogy a 11, 7, 5, 3 prímszámok, de a 9 nem, mert ez a szám már osztható 9-cel, 3-mal és 1-gyel.

És ha de egy prímszám, és nál nél- a készletből (1, 2, ... de- 1), akkor garantált ( de, nál nél) = 1, vagy másodprímszámok — deÉs nál nél.

Ez inkább nem is magyarázat, hanem az imént elmondottak megismétlése vagy összegzése.

Prímszámok beszerzése lehetséges, lenyűgöző számok (például milliárdok) esetén azonban ez a módszer túl hosszú, de a szuperképletekkel ellentétben, amelyek néha hibáznak, megbízhatóbb.

Választással működhet nál nél > de. Ehhez y-t úgy választjuk ki, hogy a szám be legyen de nem osztotta meg. Ehhez egy prímszámot megszorozunk egy természetes számmal, és hozzáadunk (vagy fordítva, kivonunk) egy értéket (pl. R), ami kevesebb de:

y= R a + k

Ha pl. de = 71, R= 3, q = 10, akkor rendre, nál nél itt 713 lesz. Más választás is lehetséges, fokokkal.

Az összetett számok a másodprímszámokkal ellentétben oszthatók önmagukkal, 1-gyel és más számokkal (szintén maradék nélkül).

Más szóval, (egy kivételével) összetett és egyszerű csoportokra oszthatók.

A prímszámok olyan természetes számok, amelyeknek nincs nem triviális osztója (kivéve magát a számot és az egységet). Szerepük különösen fontos a mai, modern, rohamosan fejlődő kriptográfiában, aminek köszönhetően a korábban rendkívül elvont tudományágnak számító kriptográfiának köszönhetően annyira keresett lett: folyamatosan fejlesztik az adatvédelmi algoritmusokat.

A legnagyobb prímszámot Martin Nowak szemész találta, aki a GIMPS (eloszlási számítástechnika) projektben is részt vett más lelkesekkel, akikből mintegy 15 ezren voltak, hat hosszú évbe telt a számítás. A Novak szemklinikáján található két és fél tucat számítógép érintett. Titáni munka és kitartás eredménye a 225964951-1 szám lett, 7816230 tizedesjegy pontossággal. Mellesleg a rekord egy nagy szám hat hónappal a felfedezés előtt szállították. És félmillióval kevesebb jel volt.

Egy zseninek, aki meg akar nevezni egy számot, ahol az időtartamot decimális jelölés"átugrani" a tízmilliós határt, nem csak világhírnévre, hanem 100 000 dollárra is van esély. Nayan Khairatwal egyébként kisebb összeget (50 000 dollárt) kapott a milliós határt átlépő számért.