Kako odrediti da li su brojevi međusobno prosti. Koprosti brojevi

$p$ se naziva prostim brojem ako ima samo $2$ djelitelje: $1$ i sebe.

razdjelnik prirodni broj$a$ je prirodan broj kojim je originalni broj $a$ djeljiv bez ostatka.

Primjer 1

Pronađite djelitelje broja $6$.

Rješenje: Moramo pronaći sve brojeve kojima je dati broj $6$ djeljiv bez ostatka. To će biti brojevi: $1,2,3, 6$. Dakle, djelitelj broja $6$ će biti brojevi $1,2,3,6.$

Odgovor: $1,2,3,6$.

Dakle, da biste pronašli djelitelje broja, morate pronaći sve prirodne brojeve kojima je dato djeljivo bez ostatka. Lako je vidjeti da će broj $1$ biti djelitelj bilo kojeg prirodnog broja.

Definicija 2

Kompozitni Brojem se naziva broj koji osim jedinice i sebe ima i druge djelitelje.

Primjer jednostavnog broja bi bio $13$, primjer složenog broja bi bio $14,$

Napomena 1

Broj $1$ ima samo jedan djelitelj - sam ovaj broj, tako da nije klasifikovan ni kao prost ni kao složen.

Koprosti brojevi

Definicija 3

Koprosti brojevi pozivaju se oni čiji je GCD jednak $1$. Dakle, da bismo saznali da li su brojevi međusobno prosti, potrebno je pronaći njihov GCD i uporediti ga sa $1$.

Pairwise coprime

Definicija 4

Ako su u skupu brojeva bilo koja dva međusobno prosta, onda se takvi brojevi nazivaju parno jednoznačan. Za dva broja, koncepti "koprimenog" i "parno jednostavnog" su isti.

Primjer 2

$8, 15$ - nije jednostavno, već koprime.

6, 8, 9 $ - obostrano primarni brojevi, ali ne i parno prost.

$8, 15, 49$ su parovi međusobno prosti.

Kao što vidimo, da biste utvrdili da li su brojevi međusobno prosti, prvo ih morate razložiti na proste faktore. Obratimo pažnju na to kako to učiniti ispravno.

Primena faktorizacije

Na primjer, hajde da faktoriziramo broj $180$:

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

Koristimo svojstvo stepeni, onda dobijamo,

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

Takav prikaz dekompozicije na proste faktore naziva se kanonskim, tj. da bi se broj faktorizirao u kanonskom obliku, potrebno je koristiti svojstvo stepena i predstaviti broj kao proizvod potencija s različitim bazama

Kanonska dekompozicija prirodnog broja u opštem obliku

Kanonska dekompozicija prirodnog broja u opšti pogled izgleda kao:

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

gdje su $p_1,p_2\dots \dots .p_k$ prosti brojevi i eksponenti stepeni - prirodni brojevi.

Predstavljanje broja kao kanonske dekompozicije na jednostavne skupove olakšava pronalaženje najvećeg zajedničkog djelitelja brojeva i djeluje kao posljedica dokaza ili definicije koprostih brojeva.

Primjer 3

Pronađite najveći zajednički djelitelj $180$ i $240$.

Rješenje: Rastavite brojeve na jednostavne skupove koristeći kanonsku dekompoziciju

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

$240=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 5$, zatim $240=2^4\cdot 3\cdot 5$

Hajde sada da pronađemo GCD ovih brojeva, za to biramo stepene sa istom bazom i najmanjim eksponentom, onda

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

Hajde da komponujemo algoritam za pronalaženje gcd uzimajući u obzir kanonsku dekompoziciju na proste faktore.

Da biste pronašli najveći zajednički djelitelj dva broja koristeći kanonsko proširenje, morate:

rastaviti brojeve u proste faktore u kanonskom obliku
izabrati stupnjeve sa istom bazom i najmanjim eksponentom od brojeva uključenih u dekompoziciju ovih brojeva
Pronađite proizvod brojeva pronađenih u koraku 2. Rezultirajući broj će biti željeni najveći zajednički djelitelj.

Primjer 4

Odredite da li su brojevi $195$ i $336$ prosti, međusobno prosti brojevi.

$195=3\cdot 5\cdot 13$

$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$

Vidimo da se gcd ovih brojeva razlikuje od $1$, što znači da brojevi nisu međusobno prosti. Takođe vidimo da svaki od brojeva uključuje faktore, pored $1$ i samog broja, što znači da ni brojevi neće biti prosti, već će biti složeni.

Primjer 5

Odredite da li su brojevi $39$ i $112$ prosti, međusobno prosti brojevi.

Rješenje: Koristimo kanonsku faktorizaciju za faktorizaciju:

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

$gcd \ (39;112)=1$

Vidimo da je gcd ovih brojeva jednak $1$, što znači da su brojevi međusobno prosti. Takođe vidimo da svaki od brojeva uključuje faktore, pored $1$ i samog broja, što znači da ni brojevi neće biti prosti, već će biti složeni.

Primjer 6

Odredite da li su brojevi $883$ i $997$ prosti, međusobno prosti brojevi.

Rješenje: Koristimo kanonsku faktorizaciju za faktorizaciju:

$883=1\cdot 883$

$997=1\cdot 997$

$gcd \ (883;997)=1$

Vidimo da je gcd ovih brojeva jednak $1$, što znači da su brojevi međusobno prosti. Takođe vidimo da svaki od brojeva uključuje samo faktore jednake $1$ i sam broj, što znači da će brojevi biti prosti.

Osim ±1.

14 i 25 su međusobno prosti jer nemaju zajedničkih djelitelja;
15 i 25 nisu relativno prosti jer imaju zajednički djelitelj 5;

Vizuelna reprezentacija: ako izgradite „šumu“ na ravni postavljajući „drveće“ nulte debljine na tačke sa celobrojnim koordinatama, tada su samo stabla čije su koordinate jednako proste vidljive iz ishodišta, pogledajte sliku na desnoj strani kao primjer vidljivost „drveta“ sa koordinatama (9, 4).

Notacija

Da ukaže na međusobnu jednostavnost brojeva m (\displaystyle m) i n (\displaystyle n) koristi se notacija:

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

Međutim, ne prepoznaju svi matematičari i ne koriste ovu notaciju. Najčešće korištena formulacija ili ekvivalentna notacija gcd (a, b) = 1 (\displaystyle \gcd(a,b)=1), što znači: "najveći zajednički djelitelj brojeva a i b jednako 1".

Povezane definicije

Ako je u nizu brojeva bilo koji dva broja su međusobno prosta, onda se takvi brojevi nazivaju parno jednoznačan. Za dva broja, koncepti "koprimenog" i "parno jednostavnog" su isti.

Primjeri

8, 15 - nije prost, već koprost.
6, 8, 9 su međusobno prosti (kolektivno) brojevi, ali ne i parno jednostavni brojevi.
8, 15, 49 su parno prosti.

Svojstva

Brojevi a (\displaystyle a) i b (\displaystyle b) koprimeran ako i samo ako je zadovoljen jedan od ekvivalentnih uslova:
Bilo koja dva (različita) prosta broja su relativno prosti.
Ako a a (\displaystyle a)- djelitelj proizvoda bc (\displaystyle bc), i a (\displaystyle a) obostrano jednostavno sa b (\displaystyle b), onda a (\displaystyle a)- razdjelnik c (\displaystyle c).
Ako brojevi a 1 , … , a n (\displaystyle a_(1),\ldots ,a_(n)) onda su parno prosti brojevi NOC(a 1 , … , a n) = | a 1 ⋅ … ⋅ a n | (\displaystyle (a_(1),\ldots ,a_(n))=|a_(1)\cdot \ldots \cdot a_(n)|). Na primjer, NOC (9, 11) = 9 ⋅ 11 = 99 (\displaystyle (9,11)=9\cdot 11=99).
Vjerovatnoća da bilo koja k (\displaystyle k) nasumično odabrani pozitivni cijeli brojevi će biti relativno prosti, jednaki , u smislu kada N → ∞ (\displaystyle N\do \infty ) vjerovatnoća da k (\displaystyle k) pozitivni cijeli brojevi manji od N (\displaystyle (\textstyle (N)))(i odabrani nasumično) će biti koprimetan, teži tome 1 ζ (k) (\displaystyle (\dfrac (1)(\zeta (k)))). Evo ζ (k) (\displaystyle \zeta (k))- Ovo

$p$ se naziva prostim brojem ako ima samo $2$ djelitelje: $1$ i sebe.

Delitelj prirodnog broja $a$ je prirodan broj kojim je originalni broj $a$ djeljiv bez ostatka.

Primjer 1

Pronađite djelitelje broja $6$.

Rješenje: Moramo pronaći sve brojeve kojima je dati broj $6$ djeljiv bez ostatka. To će biti brojevi: $1,2,3, 6$. Dakle, djelitelj broja $6$ će biti brojevi $1,2,3,6.$

Odgovor: $1,2,3,6$.

Dakle, da biste pronašli djelitelje broja, morate pronaći sve prirodne brojeve kojima je dato djeljivo bez ostatka. Lako je vidjeti da će broj $1$ biti djelitelj bilo kojeg prirodnog broja.

Definicija 2

Kompozitni Brojem se naziva broj koji osim jedinice i sebe ima i druge djelitelje.

Primjer jednostavnog broja bi bio $13$, primjer složenog broja bi bio $14,$

Napomena 1

Broj $1$ ima samo jedan djelitelj - sam ovaj broj, tako da nije klasifikovan ni kao prost ni kao složen.

Koprosti brojevi

Definicija 3

Koprosti brojevi pozivaju se oni čiji je GCD jednak $1$. Dakle, da bismo saznali da li su brojevi međusobno prosti, potrebno je pronaći njihov GCD i uporediti ga sa $1$.

Pairwise coprime

Definicija 4

Ako su u skupu brojeva bilo koja dva međusobno prosta, onda se takvi brojevi nazivaju parno jednoznačan. Za dva broja, koncepti "koprimenog" i "parno jednostavnog" su isti.

Primjer 2

$8, 15$ - nije jednostavno, već koprime.

$6, 8, 9$ su međusobno prosti brojevi, ali nisu parno prosti brojevi.

$8, 15, 49$ su parovi međusobno prosti.

Kao što vidimo, da biste utvrdili da li su brojevi međusobno prosti, prvo ih morate razložiti na proste faktore. Obratimo pažnju na to kako to učiniti ispravno.

Primena faktorizacije

Na primjer, hajde da faktoriziramo broj $180$:

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

Koristimo svojstvo stepeni, onda dobijamo,

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

Kanonska dekompozicija prirodnog broja u opštem obliku

Kanonsko proširenje prirodnog broja općenito ima oblik:

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

gdje su $p_1,p_2\dots \dots .p_k$ prosti brojevi, a eksponenti prirodni brojevi.

Primjer 3

Pronađite najveći zajednički djelitelj $180$ i $240$.

Rješenje: Rastavite brojeve na jednostavne skupove koristeći kanonsku dekompoziciju

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

$240=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 5$, zatim $240=2^4\cdot 3\cdot 5$

Hajde sada da pronađemo GCD ovih brojeva, za to biramo stepene sa istom bazom i najmanjim eksponentom, onda

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

Hajde da komponujemo algoritam za pronalaženje gcd uzimajući u obzir kanonsku dekompoziciju na proste faktore.

Da biste pronašli najveći zajednički djelitelj dva broja koristeći kanonsko proširenje, morate:

rastaviti brojeve u proste faktore u kanonskom obliku
izabrati stupnjeve sa istom bazom i najmanjim eksponentom od brojeva uključenih u dekompoziciju ovih brojeva
Pronađite proizvod brojeva pronađenih u koraku 2. Rezultirajući broj će biti željeni najveći zajednički djelitelj.

Primjer 4

Odredite da li su brojevi $195$ i $336$ prosti, međusobno prosti brojevi.

$195=3\cdot 5\cdot 13$

$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$

Primjer 5

Odredite da li su brojevi $39$ i $112$ prosti, međusobno prosti brojevi.

Rješenje: Koristimo kanonsku faktorizaciju za faktorizaciju:

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

$gcd \ (39;112)=1$

Primjer 6

Odredite da li su brojevi $883$ i $997$ prosti, međusobno prosti brojevi.

Rješenje: Koristimo kanonsku faktorizaciju za faktorizaciju:

$883=1\cdot 883$

$997=1\cdot 997$

$gcd \ (883;997)=1$

Definicija1. Cijeli brojevi a 1 ,a 2 ,…,a k nazivaju se međusobno prosti ako (a 1 ,a 2 ,…,a k) =1

Definicija 2. Cijeli brojevi a 1 ,a 2 ,…,ak nazivaju se parno prosti ako je i,s (i, s = 1, 2, .. , k, is, (a i , a s) =1) .

Ako brojevi zadovoljavaju definiciju 2, onda oni takođe zadovoljavaju definiciju 1. Obrnuto nije tačno u opštem slučaju, na primer: (15, 21, 19)= 1, ali (15, 21) = 3

Teorema (kriterijum uzajamne primarnosti)

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

dokaz:

Dokažimo neophodnost. Neka je (a, b) = 1. Gore smo pokazali da ako je d=(a, b), onda je  x, y  Z: d = ax + by.

Jer u ovom slučaju d =1, tada će biti  x, y Z (određeno iz Euklidovog algoritma): 1 = ax + bu.

Adekvatnost. Neka (*) ax + by = 1, dokazujemo da je (a, b)=1. Pretpostavimo da je (a, b) = d, a zatim na lijevoj strani jednakosti (*)

(a / d ) & ( b/d ) => (sjekira + po) /d => (1/d) => (d=l) => (a, b) = 1.

§4. Nok cijelih brojeva i njegova svojstva.

Definicija 1. Zajednički višekratnik konačnog skupa cijelih brojeva različitih od nule a 1 ,a 2 ,…,a k je cijeli broj m koji je djeljiv sa svim brojevima a i (i=l, 2,…, k)

Definicija 2. Cijeli broj (m) naziva se najmanji zajednički višekratnik brojeva koji nisu nula a 1,a 2,…,a k, ako:

1 m - njihov zajednički višekratnik;

2 (m) dijeli bilo koji drugi zajednički višekratnik ovih brojeva.

Oznaka: m = LCM (a 1, a 2,…, a k) ili m = [a 1, a 2,…, a k]

Primjer. Zadati brojevi: 2, 3, 4, 6, 12.

Brojevi 12, 24. 48. 96 su zajednički višekratnici 2, 3, 4, 6, 12. Najmanji zajednički višekratnik je 12. tj.

LCM je jedinstveno određen do reda faktora. Zaista, ako pretpostavimo da je 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)]. Postoji odnos između najmanjeg zajedničkog višekratnika i najvećeg zajedničkog djelitelja dva cijela broja, koji se izražava formulom: [a, b] = ab / (a, b) (izvedite sami)

Ovaj odnos nam omogućava da tvrdimo da za bilo koji par cijelih brojeva koji nisu nula postoji njihov najmanji zajednički višekratnik. Zaista, (a, b) se uvijek može jednoznačno izvesti iz Euklidovog algoritma i po definiciji (a, b)  0, tada će razlomak ab/(a, b)  0 biti jednoznačno određen.

Najjednostavniji LCM od dva cijela broja izračunava se kada je (a, b) = 1, tada je [a, b] = ab/1 = a b

Na primjer, = 215/1 = 105, jer je (21, 5) = 1.

§5. Prosti brojevi i njihova svojstva.

Definicija 1. Prirodni broj (p) naziva se prost ako je p > 1 i nema položaj. djelitelji osim 1 i p.

Definicija 2. Prirodni broj a > 1 koji osim 1 ima i druge pozitivne djelitelje naziva se kompozitni.

Iz ovih definicija proizilazi da se skup prirodnih brojeva može podijeliti u tri klase:

a) složeni brojevi;

b) prosti brojevi;

c) jedinica.

Ako je a složen, onda je a = nq, gdje je 1

Zadatak 1. Dokažite da ako je aZ i p prost broj, tada je (a, p) = 1 v (a / p)

Dokaz.

Neka je d = (a, p) => (a / d) & (p / d), jer p je prost broj, tada ima dva djelitelja 1 i p. Ako je (a, p) = 1, tada su a i p relativno prosti; ako je (a, p) = p, onda (a/p).

Zadatak 2. Ako je proizvod više faktora djeljiv sa p, tada je barem jedan od faktora djeljiv sa p.

Odluka.

Neka proizvod (a 1, a 2, ..., i k)/p, ako svi a i nisu djeljivi sa p, tada će proizvod biti koprost sa p, dakle, neki faktor je djeljiv sa p.

Zadatak 3. Dokažite da je najmanji djelitelj cijelog broja a > 1 koji nije 1 prost broj.

Dokaz.

Neka su aZ i a složeni broj (ako je a = p, onda je tvrdnja dokazana), tada je a = a 1 q.

Neka je q najmanji djelitelj, pokažimo da će to biti prost broj. Ako pretpostavimo da je q složeni broj, tada je q = q 1 k i a = a 1 q 1 k, jer q 1

Zadatak 4. Dokazati da najmanji prosti djelitelj (p) prirodnog broja (n) ne prelazi n .

Dokaz.

Neka je n = pn 1 i p< n 1 и р - простое. Тогда n  р 2 =>R<n .

Iz ove tvrdnje slijedi da ako prirodni broj (n) nije djeljiv ni sa jednim prostim brojem r n, onda je n prost, inače će biti složen.

Primjer 1. Saznajte da li je broj 137 prost? jedanaest<137 <12.

Zapisujemo proste djelitelje koji ne prelaze 137: 2, 3, 5, 7, 11. Provjeravamo da 137 nije deljivo sa 2, sa 3, sa 5, sa 7, sa 11. Dakle, broj 137 je prime.

Euklidov teorem. Skup prostih brojeva je beskonačan.

Dokaz.

Pretpostavimo suprotno, neka je p 1 ,p 2 , ..., p k su svi prosti brojevi, gdje je p 1 = 2 i p k je najveći prosti broj.

Sastavimo prirodni broj  = p 1 p 2  ... p do +1, kao  p i , onda mora biti složen, tada će njegov najmanji djelitelj biti jednostavan (vidi problem 3). Međutim,  nije djeljiv ni sa p 1 ni sa p 2 ,..., ili p k , jer 1 nije djeljivo ni sa jednim p I .

Prema tome, naša pretpostavka da je skup prostih brojeva konačan bila je pogrešna.

Međutim, postoji teorema koja kaže da prosti brojevi čine samo mali dio brojeva u prirodnom nizu.

Teorema intervala. U prirodnom nizu postoje proizvoljno dugi intervali koji ne sadrže niti jedan prost broj.

Dokaz.

Uzmimo proizvoljan prirodan broj (n) i sastavimo niz prirodnih brojeva (n+1)!+2, n+1)!+3,…,(n+1)!+(n+1).

U ovom nizu svaki sljedeći broj je za 1 veći od prethodnog, svi ovi brojevi su kompozitni, jer svaki ima više od dva djelitelja (na primjer, prvi broj je djeljiv sa 1, sa 2 i sam po sebi). Kao n→∞ dobijamo proizvoljno dug interval koji se sastoji samo od kompozitnih brojeva.

Euklidova teorema i teorema intervala svjedoče o složenoj prirodi raspodjele prostih brojeva u prirodnom nizu.

Osnovna teorema aritmetike

Bilo koji prirodni broj n>1 može se jedinstveno predstaviti kao proizvod prostih brojeva, do reda faktora.

Dokaz.

Dokažimo mogućnost reprezentacije:

Neka je nN i n>1, ako je n prost broj, onda je n = p i teorema je dokazana. Ako je n složen, tada će njegov najmanji djelitelj biti prost broj i n = p 1 n 1, gdje je n 1

Dalje, raspravljamo slično. Ako je n 1 prost broj, onda je teorema dokazana, ako je n 1 složeni broj, onda je n 1 = p 2 n 2, gdje je n 2< n 1 и тогда n = p 1 p 2 n 2 . На каком-то шаге получим n = p 1 p 2 …p n , где все p i - простые числа.

Dokažimo jedinstvenost dekompozicije:

Pretpostavimo da postoje dva različita prikaza broja (n): n = p 1 p 2 …p k , n = q 1 q 2 …q n i n>k.

Tada dobijamo da je p 1 p 2 …p k = q 1 q 2 …q n (1). Lijeva strana jednakosti (1) je djeljiva sa p 1 , zatim svojstvom prostih brojeva (vidi problem 2), barem jedan od faktora na desnoj strani mora biti djeljiv sa p 1 .

Neka (q 1 /p 1) => (q 1 =p 1). Podijeleći obje strane jednakosti (1) sa p 1 , dobijamo jednakost p 2 p 3 …p k = q 2 q 3 …q n . Ponavljajući prethodno rezonovanje više (k-1) puta, dobijamo jednakost 1 = q k +1 q k +2 …q n , jer sve q i >1, onda je ova jednakost nemoguća. Dakle, u oba proširenja broj faktora je isti (k=n) i sami faktori su isti.

Komentar. U dekompoziciji broja (n) na proste faktore, neki od njih se mogu ponoviti. Označavajući slovima  1 , 2 ,…, k višestrukost njihovog pojavljivanja u (n), dobijamo takozvanu kanonsku ekspanziju broja (n):

Primjer 2

Kanonsko proširenje broja 588000 = 2 5 35 3 7 2

Posljedica 1. Ako a
tada svi djelitelji broja (n) imaju oblik:
gdje je 0 i  i (i = 1, 2,…,k).

Primjer 3 Sve djelitelje broja 720 = 2 4 3 2 5 dobijamo ako u izrazu
umjesto  1 ,  2 ,  3 , nezavisno jedna od druge, zamijenit ćemo vrijednosti:  1 =0, 1, 2, 3, 4,  2 =0, 1, 2,  3 = 0, 1 .

Željeni djelitelji će biti jednaki: 1; 2; 4; osam; šesnaest; 3; 6; 12; 24; 48; devet; osamnaest; 36; 72; 144; 5; deset; 20; 40; 80; petnaest; trideset; 60; 120; 240; 45; 90; 180; 360; 720.

Posljedica 2. Ako a
i
tada (a, b) = p 1  1 p 2  2 …p k  k , gdje je i = min( I ,  i)

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

Primjer 4 Pronađite gcd(a, b) i lcm(a, b) koristeći kanonsku dekompoziciju if

(24, 42) = 23 = 6

Udžbenike matematike je ponekad teško čitati. Suv i jasan jezik autora nije uvijek lak za razumijevanje. Da, i tamo su teme uvijek međusobno povezane, međusobno tekuće. Da biste savladali jednu temu, morate pokrenuti niz prethodnih, a ponekad i prelistati cijeli udžbenik. Komplikovano? Da. I hajde da preuzmemo rizik da zaobiđemo ove poteškoće i pokušamo pronaći nestandardan pristup temi. Napravimo svojevrsni izlet u zemlju brojeva. Međutim, definiciju ćemo ostaviti istu, jer se pravila matematike ne mogu poništiti. Dakle, međusobno prosti brojevi su prirodni brojevi sa zajedničkim djeliteljem jednakim jedan. Ovo je jasno? Sasvim.

Za vizuelniji primjer, uzmimo brojeve 6 i 13. Oba su djeljiva s jednim (međusobno prosti). Ali brojevi 12 i 14 ne mogu biti takvi, jer su djeljivi ne samo sa 1, već i sa 2. Sljedeći brojevi - 21 i 47 također se ne uklapaju u kategoriju "koprostih brojeva": mogu se podijeliti ne samo za 1, ali i za 7.

Koprosti brojevi se označavaju na sljedeći način: ( a, y) = 1.

Može se reći još jednostavnije: zajednički djelitelj (najveći) ovdje je jednak jedinici.
Zašto nam je potrebno takvo znanje? Dovoljan razlog.

Međusobno uključeni u neke sisteme šifriranja. Oni koji rade sa Hill šiframa ili sa Cezarovim sistemom zamjene razumiju da bez ovog znanja ne možete stići nigdje. Ako ste čuli za generatore, malo je vjerovatno da ćete se usuditi poreći: i tamo se koriste koprosti brojevi.

Hajde sada da razgovaramo o načinima da dobijemo tako jednostavne, kao što razumete, oni mogu imati samo dva djelitelja: djeljivi su sami sobom i jednim. Recimo da su 11, 7, 5, 3 prosti brojevi, ali 9 nije, jer je ovaj broj već djeljiv sa 9, 3 i 1.

I ako a je prost broj, i at- iz seta (1, 2, ... a- 1), onda je zagarantovano ( a, at) = 1, ili međusobno prosti brojevi — a i at.

Ovo, prije, nije čak ni objašnjenje, već ponavljanje ili sumiranje onoga što je upravo rečeno.

Dobivanje prostih brojeva je moguće, međutim, za impresivne brojeve (milijarde, na primjer), ovaj metod je predugačak, ali je, za razliku od superformula koje ponekad griješe, pouzdaniji.

Može raditi po izboru at > a. Da biste to učinili, y se bira tako da je broj uključen a nije podijelio. Da biste to učinili, prost broj se množi prirodnim brojem i dodaje se vrijednost (ili, obrnuto, oduzima) (na primjer, R), što je manje a:

y= R a + k

Ako je npr. a = 71, R= 3, q=10, tada, respektivno, at ovdje će biti jednako 713. Moguća je još jedna selekcija, sa stepenima.

Složeni brojevi, za razliku od međusobno prostih brojeva, djeljivi su sami sa sobom, s 1 i drugim brojevima (također bez ostatka).

Drugim riječima, (osim jedne) dijele se na složene i jednostavne.

Prosti brojevi su prirodni brojevi koji nemaju netrivijalne djelitelje (osim samog broja i jedinice). Njihova uloga je posebno važna u današnjoj, modernoj, kriptografiji koja se brzo razvija, zahvaljujući kojoj je, ranije smatrana izuzetno apstraktnom disciplinom, postala toliko tražena: algoritmi zaštite podataka se stalno poboljšavaju.

Najveći prost broj pronašao je oftalmolog Martin Nowak, koji je zajedno sa drugim entuzijastima, kojih je bilo oko 15 hiljada, učestvovao u projektu GIMPS (distributivno računanje), kojih je bilo oko 15. Izračunavanje je trajalo dugih šest godina. Uključeno je dva i po desetina kompjutera koji se nalaze u Novakovoj očnoj klinici. Rezultat titanskog rada i upornosti bio je broj 225964951-1, napisan na 7816230 decimalnih mjesta. Uzgred, rekord veliki broj isporučen je šest mjeseci prije ovog otkrića. A znakova je bilo pola miliona manje.

Za genija koji želi da imenuje broj, gde je trajanje decimalni zapis"preskočite" deset miliona, postoji šansa da steknete ne samo svjetsku slavu, već i 100.000 dolara. Inače, Nayan Khairatwal dobio je manji iznos (50.000 dolara) za broj koji je prešao milionsku granicu.