Zovu se koprosti brojevi. Koprosti brojevi: definicija, primjeri i svojstva

U ovom članku ćemo govoriti o tome šta su koprosti brojevi. U prvom paragrafu formulišemo definicije za dva, tri ili više koprostih brojeva, dajemo nekoliko primera i pokazujemo u kojim slučajevima se dva broja mogu smatrati prostima jedan u odnosu na drugi. Nakon toga prelazimo na formulaciju glavnih svojstava i njihove dokaze. U posljednjem dijelu ćemo govoriti o povezanom konceptu, parnim prostim brojevima.

Yandex.RTB R-A-339285-1

Šta su koprosti brojevi

Oba cijela broja i više njih mogu biti međusobno prosti. Za početak uvodimo definiciju za dva broja, za koja nam je potreban koncept njihovog najvećeg zajedničkog djelitelja. Ako je potrebno, ponovite materijal posvećen njemu.

Definicija 1

Dva takva broja a i b bit će međusobno prosti, čiji je najveći zajednički djelitelj jednak 1, tj. gcd (a, b) = 1.

Iz ove definicije možemo zaključiti da će jedini pozitivni zajednički djelitelj dvaju međusobno prostih brojeva biti jednak 1. Samo dva takva broja imaju dva zajednička djelitelja - jedan i minus jedan.

Koji su neki primjeri relativno prostih brojeva? Na primjer, takav par bi bio 5 i 11. Imaju samo jedan zajednički pozitivni djelitelj, jednak 1, što je potvrda njihove međusobne jednostavnosti.

Ako uzmemo dva prosta broja, onda će oni jedan u odnosu na drugi biti relativno prosti u svim slučajevima, ali se takvi međusobni odnosi formiraju i između složenih brojeva. Postoje slučajevi kada je jedan broj u paru zajedničkih brojeva složen, a drugi prost, ili su oba kompozitna.

Ova tvrdnja je ilustrovana sledećim primerom: složeni brojevi - 9 i 8 čine koprost par. Dokažimo to tako što ćemo izračunati njihov najveći zajednički djelitelj. Da bismo to učinili, zapisujemo sve njihove djelitelje (preporučamo da ponovo pročitate članak o pronalaženju djelitelja broja). Za 8, to će biti brojevi ± 1, ± 2, ± 4, ± 8, a za 9 - ± 1, ± 3, ± 9. Od svih djelitelja biramo onaj koji će biti zajednički i najveći - ovo je jedan. Prema tome, ako je gcd (8, - 9) = 1, tada će 8 i - 9 biti međusobno prosti.

500 i 45 nisu međusobno prosti brojevi, jer imaju još jedan zajednički djelitelj - 5 (pogledajte članak o znakovima djeljivosti sa 5). Pet je veće od jedan i pozitivan je broj. Drugi sličan par mogao bi biti - 201 i 3 , budući da se oba mogu podijeliti sa 3 , kao što je naznačeno odgovarajućim znakom djeljivosti.

U praksi je prilično uobičajeno odrediti međusobnu jednostavnost dva cijela broja. Pronalaženje ovoga može se svesti na pronalaženje najvećeg zajedničkog djelitelja i njegovo poređenje s jednim. Također je zgodno koristiti tablicu prostih brojeva kako ne biste pravili nepotrebne proračune: ako se jedan od datih brojeva nalazi u ovoj tablici, onda je djeljiv samo s jednim i sam po sebi. Pogledajmo rješenje ovog problema.

Primjer 1

Stanje: saznati da li su brojevi 275 i 84 međusobno prosti.

Rješenje

Oba broja jasno imaju više od jednog djelitelja, tako da ih ne možemo odmah nazvati međusobno prostima.

Izračunajte najveći zajednički djelitelj koristeći Euklidov algoritam: 275 = 84 3 + 23 , 84 = 23 3 + 15 , 23 = 15 1 + 8 , 15 = 8 1 + 7 , 8 = 7 1 + 1 , 7 = 7.

odgovor: pošto je gcd (84, 275) = 1, onda će ovi brojevi biti međusobno prosti.

Kao što smo ranije rekli, definicija takvih brojeva može se proširiti na slučajeve u kojima nemamo dva broja, već više.

Definicija 2

Koprosti cijeli brojevi a 1, a 2, …, a k, k > 2 će biti kada imaju najveći zajednički djelitelj jednak 1.

Drugim riječima, ako imamo skup nekih brojeva s najvećim pozitivnim djeliteljem većim od 1, onda svi ovi brojevi nisu međusobno inverzni jedan prema drugom.

Uzmimo nekoliko primjera. Dakle, cijeli brojevi - 99 , 17 i - 27 su međusobno prosti. Bilo koji broj prostih brojeva će biti koprost u odnosu na sve članove populacije, kao što je niz 2 , 3 , 11 , 19 , 151 , 293 i 667 . Ali brojevi 12 , − 9 , 900 i − 72 koprostor neće biti, jer će pored jedinice imati još jedan pozitivni djelitelj jednak 3. Isto vrijedi i za brojeve 17, 85 i 187: osim jednog, svi se mogu podijeliti sa 17.

Obično međusobna jednostavnost brojeva nije očigledna na prvi pogled, tu činjenicu treba dokazati. Da biste saznali jesu li neki brojevi međusobno prosti, potrebno je pronaći njihov najveći zajednički djelitelj i izvući zaključak na osnovu njegovog poređenja s jedinicom.

Primjer 2

Stanje: odrediti jesu li brojevi 331, 463 i 733 međusobno prosti.

Rješenje

Provjerimo tabelu prostih brojeva i utvrdimo da se u njoj nalaze sva tri ova broja. Tada njihov zajednički djelitelj može biti samo jedan.

odgovor: svi ovi brojevi će biti relativno prosti jedan prema drugom.

Primjer 3

Stanje: dati dokaz da brojevi − 14 , 105 , − 2 107 i − 91 nisu međusobno prosti.

Rješenje

Počnimo od pronalaženja njihovog najvećeg zajedničkog djelitelja, nakon čega se uvjerimo da nije jednak 1. Pošto negativni brojevi imaju iste djelitelje kao i odgovarajući pozitivni, onda je gcd (− 14 , 105 , 2 107 , − 91) = gcd (14 , 105 , 2 107 , 91) . Prema pravilima koja smo dali u članku o pronalaženju najvećeg zajedničkog djelitelja, u ovom slučaju GCD će biti jednak sedam.

odgovor: sedam je veće od jedan, što znači da ovi brojevi nisu međusobno prosti.

Osnovna svojstva međusobno prostih brojeva

Takvi brojevi imaju neka praktično važna svojstva. Navodimo ih redom i dokazujemo.

Definicija 3

Ako cijele brojeve a i b podijelimo brojem koji odgovara njihovom najvećem zajedničkom djelitelju, dobićemo relativno proste brojeve. Drugim riječima, a: gcd(a, b) i b: gcd(a, b) će biti međusobno prosti.

Ovo svojstvo smo već dokazali. Dokaz se može naći u članku o svojstvima najvećeg zajedničkog djelitelja. Zahvaljujući njemu, možemo definirati parove međusobno prostih brojeva: samo uzmite bilo koja dva cijela broja i podijelite sa gcd. Kao rezultat, trebali bismo dobiti međusobno proste brojeve.

Definicija 4

Neophodan i dovoljan uslov za međusobnu jednostavnost brojeva a i b je postojanje takvih celih brojeva u 0 i v0, za koje je jednakost a u 0 + b v 0 = 1 biće istina.

Dokaz 1

Počinjemo s dokazivanjem neophodnosti ovog uslova. Recimo da imamo dva relativno prosta broja, označena kao a i b. Tada će, po definiciji ovog koncepta, njihov najveći zajednički djelitelj biti jednak jedan. Iz svojstava gcd znamo da za cijele brojeve a i b postoji Bezoutova relacija a u 0 + b v 0 = gcd (a, b). Iz toga dobijamo to a u 0 + b v 0 = 1. Nakon toga moramo dokazati dovoljnost uslova. Neka jednakost a u 0 + b v 0 = 1 biće istina ako gcd (a, b) deli i a , i b , tada će se dijeliti i zbrajati a u 0 + b v 0, i jedinica, respektivno (ovo se može tvrditi na osnovu svojstava djeljivosti). A ovo je moguće samo ako gcd(a, b) = 1, što dokazuje međusobnu jednostavnost a i b .

Zaista, ako su a i b međusobno prosti, onda će prema prethodnom svojstvu jednakost biti tačna a u 0 + b v 0 = 1. Pomnožimo oba njegova dijela sa c i dobijemo to a c u 0 + b c v 0 = c. Možemo podijeliti prvi pojam a c u 0 + b c v 0 sa b , jer je to moguće za a c , a drugi član je također djeljiv sa b , jer je jedan od faktora koji imamo b . Iz ovoga zaključujemo da se cijeli zbir može podijeliti sa b, a pošto je ovaj zbir jednak c, onda se c može podijeliti sa b.

Definicija 5

Ako su dva cijela broja a i b međusobno prosta, onda je gcd(a c, b) = gcd(c, b) .

Dokaz 2

Dokažimo da će gcd (a c , b) podijeliti gcd (c , b) , a nakon toga - da gcd (c , b) dijeli gcd (a c , b) , čime ćemo dokazati ispravnost jednakosti gcd (a · c, b) = gcd (c, b) .

Pošto gcd (a c, b) dijeli i a c i b, a gcd (a c, b) dijeli b, također će dijeliti b c. Dakle, gcd (a c, b) dijeli i a c i b c, dakle, zbog svojstava gcd, dijeli i gcd (a c, b c), što će biti jednako c gcd (a, b ) = c. Dakle, gcd(a c, b) dijeli i b i c, stoga gcd(c, b) također dijeli.

Također možete reći da pošto gcd (c, b) dijeli i c i b, onda će podijeliti i c i a c. To znači da GCD (c , b) dijeli i a c i b, dakle, GCD (a c, b) također dijeli.

Dakle, gcd (a c, b) i gcd (c, b) se međusobno dijele, što znači da su jednake.

Definicija 6

Ako su brojevi u nizu a 1 , a 2 , … , a kće biti koprost u odnosu na brojeve niza b 1 , b 2 , … , b m(za prirodne vrijednosti k i m), zatim njihove proizvode a 1 a 2 … a k i b 1 b 2 … b m takođe su međusobno prosti, posebno, a 1 = a 2 = … = a k = a i b 1 = b 2 = ... = b m = b, onda a k i b m su coprime.

Dokaz 3

Prema prethodnom svojstvu, možemo napisati jednakosti sljedećeg oblika: gcd (a 1 a 2 … a k , b m) = gcd (a 2 a k , b m) = … = gcd (a k , b m) = 1 . Mogućnost posljednje tranzicije je osigurana činjenicom da su a k i b m po pretpostavci međusobno prosti. Dakle, GCD (a 1 · a 2 · … · a k , b m) = 1 .

Označimo a 1 a 2 … a k = A i dobijemo da je gcd (b 1 b 2 … b m , a 1 a 2 … a k) = gcd (b 1 b 2 … b m , A) = GCD (b 2 · … · b · b m , A) = … = GCD (b m , A) = 1 . Ovo će biti tačno zbog poslednje jednakosti iz lanca koji je gore konstruisan. Tako smo dobili jednakost gcd (b 1 b 2 … b m , a 1 a 2 … a k) = 1, koja se može koristiti za dokazivanje međusobne jednostavnosti proizvoda a 1 a 2 … a k i b 1 b 2 … b m

Ovo su sva svojstva koprostih brojeva o kojima bismo vam htjeli reći.

Koncept parnih prostih brojeva

Znajući šta su međusobno prosti brojevi, možemo formulisati definiciju prostih brojeva u paru.

Definicija 7

Parni prosti brojevi je niz cijelih brojeva a 1 , a 2 , … , a k , gdje je svaki broj koprost u odnosu na ostale.

Primjer niza prostih brojeva u paru bi bio 14, 9, 17 i −25. Ovdje su svi parovi (14 i 9 , 14 i 17 , 14 i − 25 , 9 i 17 , 9 i − 25 , 17 i − 25) međusobno prosti. Imajte na umu da je koprost uslov obavezan za uparene proste brojeve, ali koprosti brojevi neće biti parno prosti u svim slučajevima. Na primjer, u nizu 8, 16, 5 i 15 brojevi nisu takvi jer 8 i 16 neće biti međusobno prosti.

Treba se zadržati i na konceptu skupa određenog broja prostih brojeva. Oni će uvijek biti i međusobno i parno jednostavni. Primjer bi bio niz 71 , 443 , 857 , 991 . U slučaju prostih brojeva, koncepti međusobne i parne jednostavnosti će se poklopiti.

Ako primijetite grešku u tekstu, označite je i pritisnite Ctrl+Enter

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, teče se međusobno. Da biste savladali jednu temu, morate pokrenuti niz prethodnih, a ponekad i prelistati cijeli udžbenik. Tesko? 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 vizualniji 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 sa 1, ali i 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) je ovdje 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 koprosti 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 se broj uključi 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 npr. a = 71, R= 3, q=10, tada, respektivno, at ovdje će biti jednako 713. Moguća je druga 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 jednog) 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, brzo razvijajućoj kriptografiji, 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 učestvovao u projektu GIMPS (distributivno računarstvo), zajedno sa drugim entuzijastima, kojih je bilo oko 15 hiljada. Proračuni su trajali 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. Inače, rekord za najveći broj postavljen je šest mjeseci prije ovog otkrića. A znakova je bilo pola miliona manje.

Genije koji želi da imenuje broj u kojem trajanje decimalnog zapisa "skoči" preko deset miliona ima šansu da dobije 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.

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

Prime faktorizacija

Na primjer, hajde da faktorizujemo 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

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.

Predstavljanje broja u obliku 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 u 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$

Sada pronađimo GCD ovih brojeva, za to biramo stupnjeve sa istom bazom i najmanjim eksponentom, tada

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

1. rastaviti brojeve u proste faktore u kanonskom obliku
2. izabrati stupnjeve s istom bazom i najmanjim eksponentom brojeva uključenih u dekompoziciju ovih brojeva
3. 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.

Šta su koprosti brojevi?

Definicija koprostih brojeva

Definicija koprostih brojeva:

Koprosti brojevi su cijeli brojevi koji nemaju zajedničkih djelitelja osim jedan.

Primjeri koprostih brojeva

Coprime primjer:

2 i 3 nemaju druge zajedničke djelitelje osim jedan.

Još jedan primjer relativno prostih brojeva:

3 i 7 nemaju druge zajedničke djelitelje osim jedan.

Još jedan primjer uzajamno prostih brojeva:

11 i 13 nemaju druge zajedničke djelitelje osim jedan.

Sada možemo odgovoriti na pitanje šta znače međusobno prosti brojevi.

Šta znači prost broj?

To su cijeli brojevi koji nemaju zajedničkih djelitelja osim jedan.

Dva međusobno prosta broja

Svaki od ovih parova su dva relativno prosta broja.

11 i 15
15 i 16
16 i 23

Zajednički djelitelji međusobno prostih brojeva

Zajednički djelitelji zajedničkih brojeva su samo jedan, kao što slijedi iz definicije koprostih brojeva.

Najveći zajednički djelitelj koprostih brojeva

Najveći zajednički djelitelj koprostih brojeva je jedan, kao što slijedi iz definicije koprostih brojeva.

Da li su brojevi relativno prosti?

Da li su brojevi 3 i 13 međusobno prosti? Da, jer nemaju zajedničkih djelitelja, osim jednog.

Da li su brojevi 3 i 12 međusobno prosti? Ne, jer imaju zajedničke djelitelje 1 i 3. A prema definiciji koprostih brojeva, samo jedan bi trebao biti zajednički djelitelj.

Da li su brojevi 3 i 108 međusobno prosti? Ne, jer imaju zajedničke djelitelje 1 i 3. A prema definiciji koprostih brojeva, samo jedan bi trebao biti zajednički djelitelj.

Da li su brojevi 108 i 5 međusobno prosti? Da, jer nemaju zajedničkih djelitelja, osim jednog.

Informacije u ovom članku pokrivaju temu " relativno prosti brojevi". Najprije je data definicija dva koprosta broja, kao i definicija tri ili više međusobno prostih brojeva. Nakon toga slijede primjeri međusobno prostih brojeva i kako dokazati da su dati brojevi međusobno prosti. Nadalje, navedena su i dokazana glavna svojstva međusobno prostih brojeva. U zaključku se spominju prosti brojevi u paru, budući da su usko povezani sa koprostim brojevima.

Navigacija po stranici.

Često postoje zadaci u kojima je potrebno dokazati da su dati cijeli brojevi međusobno prosti. Dokaz se svodi na izračunavanje najvećeg zajedničkog djelitelja datih brojeva i provjeru jednakosti gcd s jedinicom. Također je korisno pogledati tabelu prostih brojeva prije izračunavanja GCD: odjednom su originalni cijeli brojevi prosti, a znamo da je najveći zajednički djelitelj prostih brojeva jednak jedan. Razmotrimo primjer rješenja.

Primjer.

Dokažite da su brojevi 84 i 275 međusobno prosti.

Rješenje.

Očigledno, ovi brojevi nisu prosti, tako da ne možemo odmah govoriti o međusobnoj jednostavnosti brojeva 84 i 275, te ćemo morati izračunati GCD. Koristite Euklidski algoritam da pronađete GCD: 275=84 3+23 , 84=23 3+15 , 23=15 1+8 , 15=8 1+7 , 8=7 1+1 , 7=7 1 , dakle gcd (84, 275)=1. Ovo dokazuje da su brojevi 84 i 275 međusobno prosti.

Definicija međusobno prostih brojeva može se proširiti na tri ili više brojeva.

Definicija.

Pozivaju se cijeli brojevi a 1 , a 2 , …, a k , k>2 coprime ako je najveći zajednički djelitelj ovih brojeva jednak jedan.

Iz gornje definicije slijedi da ako određeni skup cijelih brojeva ima pozitivan zajednički djelitelj koji nije jedan, onda ti cijeli brojevi nisu međusobno prosti.

Navedimo primjere. Tri cijela broja -99, 17 i -27 su međusobno prosti. Bilo koja zbirka prostih brojeva čini skup relativno prostih brojeva, na primjer, 2 , 3 , 11 , 19 , 151 , 293 i 677 su relativno prosti brojevi. A četiri broja 12, −9, 900 i −72 nisu relativno prosti jer imaju pozitivan zajednički djelitelj 3, koji je različit od 1. Brojevi 17, 85 i 187 također nisu međusobno prosti, jer je svaki od njih djeljiv sa 17.

Obično je daleko od očiglednog da su neki brojevi međusobno prosti i tu činjenicu treba dokazati. Da biste saznali da li su ovi brojevi međusobno prosti, morate pronaći najveći zajednički djelitelj ovih brojeva i na osnovu definicije koprostih brojeva izvući zaključak.

Primjer.

Da li su brojevi 331, 463 i 733 relativno prosti?

Rješenje.

Gledajući tabelu prostih brojeva, nalazimo da je svaki od brojeva 331, 463 i 733 prost. Dakle, oni imaju jedan pozitivan zajednički djelitelj, jedan. Dakle, tri broja 331, 463 i 733 su relativno prosti brojevi.

odgovor:

Da.

Primjer.

Dokažite da brojevi −14 , 105 , −2 107 i −91 nisu međusobno prosti.

Rješenje.

Da biste dokazali da ovi brojevi nisu međusobno prosti, možete pronaći njihov gcd i uvjeriti se da nije jednak jedinici. Pa hajde da to uradimo.

Pošto su djelitelji negativnih cijelih brojeva isti kao i djelitelji odgovarajućih, onda gcd(−14, 105, 2107, −91)= gcd(14, 105, 2 107, 91) . Vraćajući se na materijal članka, pronalazeći najveći zajednički djelitelj tri ili više brojeva, saznajemo da je GCD(14, 105, 2 107, 91)=7. Dakle, najveći zajednički djelitelj originalnih brojeva je sedam, tako da ovi brojevi nisu međusobno prosti.

Svojstva međusobno prostih brojeva

Koprosti brojevi imaju niz svojstava. Razmotrite glavne coprime svojstva.

Brojevi dobijeni dijeljenjem cijelih brojeva a i b njihovim najvećim zajedničkim djeliteljem su međusobno prosti, odnosno a:gcd(a, b) i b:gcd(a, b) su međusobno prosti.

Ovo svojstvo smo dokazali kada smo analizirali svojstva GCD.

Razmatrano svojstvo međusobno prostih brojeva omogućava pronalaženje parova međusobno prostih brojeva. Da biste to učinili, dovoljno je uzeti bilo koja dva cijela broja i podijeliti ih najvećim zajedničkim djeliteljem, rezultirajući brojevi će biti međusobno prosti.

Da bi cijeli brojevi a i b bili međusobno prosti potrebno je i dovoljno da postoje takvi cijeli brojevi u 0 i v 0 da su a·u 0 +b·v 0 =1 .

Hajde da prvo dokažemo neophodnost.

Neka su brojevi a i b međusobno prosti. Tada po definiciji koprostih brojeva gcd(a, b)=1 . A iz svojstava gcd, znamo da je za cijele brojeve a i b Bezoutova relacija a u 0 +b v 0 =gcd(a, b) tačna. Dakle, a·u 0 +b·v 0 =1 .

Ostaje da se dokaže dovoljnost.

Neka je tačna jednakost a·u 0 +b·v 0 =1. Pošto gcd(a, b) dijeli i a i b, onda gcd(a, b) zbog svojstava djeljivosti mora podijeliti zbir a u 0 + b v 0 , a time i jedinicu. A to je moguće samo kada je gcd(a, b)=1. Dakle, a i b su međusobno prosti brojevi.

Sljedeće svojstvo međusobno prostih brojeva je ovo: ako su brojevi a i b međusobno prosti, a proizvod a c je djeljiv sa b, tada je c djeljiv sa b.

Zaista, pošto su a i b međusobno prosti, iz prethodnog svojstva imamo jednakost a u 0 +b v 0 =1 . Množenjem obje strane ove jednakosti sa c , imamo a·c·u 0 +b·c·v 0 =c . Prvi član zbira a c u 0 +b c v 0 je djeljiv sa b, pošto je a c djeljiv sa b po uslovu, drugi član ove sume je također djeljiv sa b, pošto je jedan od faktora jednak b, dakle, cijeli zbir je djeljiv sa b. A pošto je zbir a·c·u 0 +b·c·v 0 jednak c, onda je c takođe deljiv sa b.

Ako su brojevi a i b relativno prosti, onda je gcd(a c, b)=gcd(c, b) .

Pokažimo, prvo, da gcd(a c, b) dijeli gcd(c, b) , i drugo, da gcd(c, b) dijeli gcd(a c, b) , to će dokazati jednakost gcd(a c, b) =gcd(c, b) .

GCD(a c, b) dijeli i a c i b, a pošto gcd(a c, b) dijeli b, dijeli i b c. Odnosno, gcd(a c, b) dijeli i a c i b c , dakle, zbog svojstava najvećeg zajedničkog djelitelja, dijeli i gcd(a c, b c) , što je, prema svojstvima gcd, c c gcd(a , b)=c . Dakle, gcd(a c, b) dijeli i b i c , dakle gcd(c, b) također dijeli.

S druge strane, gcd(c, b) dijeli i c i b, a pošto dijeli c, dijeli i a c. Dakle, gcd(c, b) dijeli i a c i b , dakle gcd(a c, b) također dijeli.

Tako smo pokazali da se gcd(a c, b) i gcd(c, b) međusobno dijele, što znači da su jednake.

Ako je svaki od brojeva a 1 , a 2 , …, a k koprost sa svakim od brojeva b 1 , b 2 , …, b m (gdje su k i m neki prirodni brojevi), tada su proizvodi a 1 a 2 … a k i b 1 b 2 ... b m su međusobno prosti brojevi, posebno ako su a 1 =a 2 =...=a k =a i b 1 =b 2 =...=b m =b , tada su a k i b m koprosti brojevi.

Prethodno svojstvo koprostih brojeva omogućava nam da zapišemo niz jednakosti oblika GCD(a 1 a 2 ... a k , b m)= GCD(a 2 ... a k , b m)=…= GCD(a k, b m)=1, gdje je posljednji prijelaz moguć, budući da su a k i b m koprosti brojevi po pretpostavci. dakle, GCD(a 1 a 2 ... a k , b m)=1.

Sada, označavajući a 1 ·a 2 ·…·a k =A , imamo
GCD(b 1 b 2 ... b m , a 1 a 2 ... a k)= GCD(b 1 b 2 ... b m , A)=
=gcd(b 2 ... b m , A)=... =gcd(b m , A)=1
(zadnji prelaz je validan, po osnovu poslednje jednakosti iz prethodnog stava). Tako da imamo jednakost GCD(b 1 b 2 ... b m , a 1 a 2 ... a k)=1, što dokazuje da su proizvodi a 1 ·a 2 ·…·a k i b 1 ·b 2 ·…·b m međusobno prosti brojevi.

Ovim je završen pregled glavnih svojstava koprostih brojeva.

Parni prosti brojevi - definicije i primjeri

Dato je u terminima koprostih brojeva definicija prostih brojeva u paru.

Definicija.

Cijeli brojevi a 1 , a 2 , …, a k , od kojih je svaki kopriman sa svim ostalima, nazivaju se prosti brojevi u paru.

Navedimo primjer prostih brojeva u paru. Brojevi 14, 9, 17 i -25 su parovi prosti, jer su parovi brojeva 14 i 9, 14 i 17, 14 i -25, 9 i 17, 9 i -25, 17 i -25 međusobno prosti brojevi. Ovdje primjećujemo da su prosti brojevi u paru uvijek međusobno prosti.

S druge strane, relativno prosti brojevi nisu uvijek prosti u paru, što potvrđuje sljedeći primjer. Brojevi 8, 16, 5 i 15 nisu prosti u paru, jer brojevi 8 i 16 nisu međusobno prosti. Međutim, brojevi 8, 16, 5 i 15 su međusobno prosti. Dakle, 8, 16, 5 i 15 su relativno prosti brojevi, ali ne i prosti brojevi u paru.

Potrebno je naglasiti skup određenog broja prostih brojeva. Ovi brojevi su uvijek i međusobno prosti i prosti u paru. Na primjer, 71 , 443 , 857 , 991 su oba prosti i međusobno prosti brojevi.

Takođe je jasno da kada govorimo o dva cijela broja, onda se za njih koncepti "prostog broja u paru" i "kopromnog broja" poklapaju.

Bibliografija.

• Vilenkin N.Ya. itd. Matematika. 6. razred: udžbenik za obrazovne ustanove.
• Vinogradov I.M. Osnove teorije brojeva.
• Mikhelovich Sh.Kh. Teorija brojeva.
• Kulikov L.Ya. i dr. Zbirka zadataka iz algebre i teorije brojeva: Udžbenik za studente fiz.-mat. specijalnosti pedagoških instituta.