$p$ se naziva prostim brojem ako ima samo $2$ djelitelja: $1$ i sebe.
Šestar prirodni broj$a$ je prirodni broj kojim je izvorni broj $a$ djeljiv bez ostatka.
Primjer 1
Pronađite djelitelje broja $6$.
Rješenje: Trebamo pronaći sve brojeve kojima je zadani broj $6$ djeljiv bez ostatka. Ovo će biti brojevi: $1,2,3, 6$. Dakle, djelitelj broja $6$ bit će brojevi $1,2,3,6.$
Odgovor: 1,2,3,6$.
To znači da je za pronalaženje djelitelja nekog broja potrebno pronaći sve prirodne brojeve kojima je zadani broj djeljiv bez ostatka. Lako je vidjeti da će broj $1$ biti djelitelj bilo kojeg prirodnog broja.
Definicija 2
Kompozitni Nazivaju broj koji ima i druge djelitelje osim jednog i samog sebe.
Primjer prostog broja bio bi broj $13$, primjer složenog broja bi bio $14.$
Napomena 1
Broj $1$ ima samo jedan djelitelj - sam broj, tako da nije ni prost ni složen.
Koprosti brojevi
Definicija 3
Međusobno prosti brojevi to su oni čiji je gcd jednak $1$. To znači da da biste saznali jesu li brojevi relativno prosti, trebate pronaći njihov gcd i usporediti ga s $1$.
Upareni međusobno prosti
Definicija 4
Ako su u skupu brojeva bilo koja dva međusobno prosta, tada se takvi brojevi nazivaju upareno međusobno prosti. Za dva broja, pojmovi "koprime" i "pairwise coprime" se podudaraju.
Primjer 2
$8, $15 - nije jednostavno, ali relativno jednostavno.
$6, 8, 9$ su međusobno prosti brojevi, ali ne i upareni međusobno prosti brojevi.
$8, 15, 49$ su upareni relativno prosti.
Kao što vidimo, da bismo odredili jesu li brojevi međusobno prosti, prvo ih moramo rastaviti na glavni faktori. Obratimo pozornost na to kako to učiniti ispravno.
Rastavljanje na proste faktore
Na primjer, faktorizirajmo broj $180$ na proste faktore:
180$=2\cdot 2\cdot 3\cdot 3\cdot 5$
Iskoristimo svojstvo moći, tada ćemo dobiti,
180$=2^2\cdot 3^2\cdot 5$
Ovaj zapis rastavljanja na proste faktore zove se kanonski, tj. da bi se broj faktorizirao u kanonskom obliku, potrebno je koristiti svojstvo potencija i prikazati broj kao umnožak potencija s različitim bazama
Kanonsko širenje prirodnog broja u općem obliku
Kanonsko širenje prirodnog broja u opći pogled 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 kao kanonske dekompozicije na proste skupove olakšava pronalaženje najvećeg zajedničkog djelitelja brojeva i djeluje kao posljedica dokaza ili definicije međusobno prostih brojeva.
Primjer 3
Pronađite najveći zajednički djelitelj brojeva $180$ i $240$.
Rješenje: Rastavimo brojeve na jednostavne skupove pomoću kanonske dekompozicije
$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$
Nađimo sada gcd ovih brojeva, za to biramo potencije s istom bazom i s najmanjim eksponentom, zatim
$GCD\(180;240)= 2^2\cdot 3\cdot 5=60$
Sastavljajmo algoritam za pronalaženje GCD-a uzimajući u obzir kanoničku faktorizaciju na proste faktore.
Da biste pronašli najveći zajednički djelitelj dvaju brojeva pomoću kanonske ekspanzije, trebate:
- rastavite brojeve na proste faktore u kanonskom obliku
- odabrati potencije s istom bazom i s najmanjim eksponentom potencija uključenih u proširenje tih brojeva
- Pronađite umnožak brojeva pronađenih u koraku 2. Rezultirajući broj bit će željeni najveći zajednički djelitelj.
Primjer 4
Odredite jesu li brojevi $195$ i $336$ prosti i 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 relativno prosti. Također vidimo da svaki od brojeva uključuje faktore, osim $1$ i samog broja, što znači da brojevi neće biti prosti, već će biti složeni.
Primjer 5
Odredite jesu li brojevi $39$ i $112$ prosti i međusobno prosti brojevi.
Rješenje: Upotrijebimo kanonsku 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 relativno prosti. Također vidimo da svaki od brojeva uključuje faktore, osim $1$ i samog broja, što znači da brojevi neće biti prosti, već će biti složeni.
Primjer 6
Odredite jesu li brojevi $883$ i $997$ prosti i međusobno prosti brojevi.
Rješenje: Upotrijebimo kanonsku 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 relativno prosti. Također vidimo da svaki broj uključuje samo faktore jednake $1$ i sam broj, što znači da će brojevi biti prosti.
U ovom ćemo članku govoriti o tome što su međusobno prosti brojevi. U prvom odlomku formuliramo definicije za dva, tri ili više relativno prostih brojeva, dajemo nekoliko primjera i pokazujemo u kojim se slučajevima dva broja mogu smatrati prostima jedan u odnosu na drugi. Nakon toga prelazimo na formulaciju glavnih svojstava i njihovih dokaza. U zadnjem odlomku govorit ćemo o srodnom konceptu - prostim brojevima u paru.
Što su međusobno prosti brojevi
Dva cijela broja ili više njih mogu biti međusobno prosti. Prvo, uvedimo definiciju za dva broja, za koje nam je potreban pojam njihovog najvećeg zajedničkog djelitelja. Ako je potrebno, ponovite materijal posvećen tome.
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 međusobno prostih brojeva? Na primjer, takav bi par bio 5 i 11. Imaju samo jedan zajednički pozitivni djelitelj, jednak 1, što potvrđuje njihovu međusobnu jednostavnost.
Ako uzmemo dva prosta broja, onda će oni u svakom slučaju međusobno biti prosti, ali takvi međusobni odnosi nastaju i između složenih brojeva. Postoje slučajevi kada je jedan broj u paru relativno prostih brojeva složen, a drugi prost ili su oba složena.
Ovu tvrdnju ilustrira sljedeći primjer: složeni brojevi 9 i 8 čine relativno prosti par. Dokažimo to izračunavanjem njihovog najvećeg zajedničkog djelitelja. Da bismo to učinili, zapisujemo sve njihove djelitelje (preporučujemo ponovno čitanje članka o pronalaženju djelitelja broja). Za 8 ti će brojevi biti ± 1, ± 2, ± 4, ± 8, a za 9 – ± 1, ± 3, ± 9. Od svih djelitelja biramo onaj koji će biti zajednički i najveći - to je jedinstvo. Stoga, ako je GCD (8, − 9) = 1, tada će 8 i - 9 biti međusobno prosti.
Koprosti brojevi nisu 500 i 45, jer imaju još jedan zajednički djelitelj - 5 (vidi članak o kriterijima djeljivosti s 5). Pet je veći od jedan i pozitivan je broj. Drugi sličan par mogao bi biti - 201 i 3, budući da se oba mogu podijeliti s 3, kao što je naznačeno odgovarajućim znakom djeljivosti.
U praksi je vrlo često potrebno odrediti relativnu primarnost dva cijela broja. Pronalaženje ovoga može se svesti na pronalaženje najvećeg zajedničkog djelitelja i njegovu usporedbu s jedinicom. Također je zgodno koristiti tablicu prostih brojeva kako ne bi radili nepotrebne izračune: ako je jedan od zadanih brojeva u ovoj tablici, onda je djeljiv samo s jednim i sam sa sobom. Pogledajmo rješenje takvog problema.
Primjer 1
Stanje: saznati jesu li brojevi 275 i 84 međusobno prosti.
Riješenje
Oba broja jasno imaju više od jednog djelitelja, pa ih ne možemo odmah nazvati relativno prostima.
Najveći zajednički djelitelj izračunavamo 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 · 1.
Odgovor: budući da je GCD (84, 275) = 1, tada će ti brojevi biti relativno prosti.
Kao što smo ranije rekli, definicija takvih brojeva može se proširiti na slučajeve kada nemamo dva broja, već više.
Definicija 2
Cijeli brojevi a 1 , a 2 , … , a k , k > 2 bit će međusobno prosti kad 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, tada svi ti brojevi nisu međusobno inverzni u odnosu na druge.
Uzmimo nekoliko primjera. Dakle, cijeli brojevi − 99, 17 i − 27 su relativno prosti. Bilo koji broj prostih brojeva bit će međusobno prosti u odnosu na sve članove populacije, kao u nizovima 2, 3, 11, 19, 151, 293 i 667. Ali brojevi 12, − 9, 900 i − 72 neće biti relativno prosti, jer će osim jedinice imati još jedan pozitivan djelitelj jednak 3. Isto vrijedi i za brojeve 17, 85 i 187: osim jednog, svi se mogu podijeliti sa 17.
Obično međusobna primarnost brojeva nije očita na prvi pogled; tu činjenicu treba dokazati. Da biste saznali jesu li neki brojevi relativno prosti, potrebno je pronaći njihov najveći zajednički djelitelj i donijeti zaključak na temelju njegove usporedbe s jedinicom.
Primjer 2
Stanje: odrediti jesu li brojevi 331, 463 i 733 relativno prosti.
Riješenje
Provjerimo tablicu 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 ti brojevi će biti međusobno prosti.
Primjer 3
Stanje: dajte dokaz da brojevi − 14, 105, − 2 107 i − 91 nisu međusobno prosti.
Riješenje
Počnimo s identificiranjem njihovog najvećeg zajedničkog djelitelja, a zatim se uvjerimo da nije jednak 1. Budući da negativni brojevi imaju iste djelitelje kao i odgovarajući pozitivni, tada 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 ti brojevi nisu relativno prosti.
Osnovna svojstva međusobno prostih brojeva
Takvi brojevi imaju neka praktično važna svojstva. Nabrojimo ih redom i dokažimo.
Definicija 3
Ako cijele brojeve a i b podijelimo brojem koji odgovara njihovom najvećem zajedničkom djelitelju, dobit ćemo relativno proste brojeve. Drugim riječima, a: gcd (a, b) i b: gcd (a, b) će biti relativno prosti.
Ovo svojstvo smo već dokazali. Dokaz se nalazi u članku o svojstvima najvećeg zajedničkog djelitelja. Zahvaljujući njemu možemo odrediti parove relativno prostih brojeva: samo trebamo uzeti bilo koja dva cijela broja i podijeliti ih s GCD. Kao rezultat, trebali bismo dobiti međusobno proste brojeve.
Definicija 4
Nužan i dovoljan uvjet za međusobnu primarnost brojeva a i b je postojanje takvih cijelih brojeva u 0 I v 0, za koje jednakost a · u 0 + b · v 0 = 1 bit će istina.
Dokazi 1
Počnimo s dokazivanjem nužnosti ovog uvjeta. Recimo da imamo dva relativno prosta broja, označena s a i b. Tada će, prema definiciji ovog pojma, 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 dobivamo to a · u 0 + b · v 0 = 1. Nakon toga trebamo dokazati dostatnost uvjeta. Neka ravnopravnost a · u 0 + b · v 0 = 1 bit će istina u ovom slučaju ako GCD (a, b) dijeli i a , i b , tada će također podijeliti zbroj a · u 0 + b · v 0, odnosno jedinica (ovo se može tvrditi na temelju svojstava djeljivosti). A to je moguće samo ako GCD (a, b) = 1, što dokazuje međusobnu jednostavnost a i b.
Zapravo, ako su a i b međusobno prosti, tada će prema prethodnom svojstvu postojati istinska jednakost a · u 0 + b · v 0 = 1. Pomnožimo obje strane sa c i dobijemo to a · c · u 0 + b · c · v 0 = c. Prvi član možemo podijeliti a · c · u 0 + b · c · v 0 s b, jer je to moguće za a · c, a drugi član je također djeljiv s b, jer je jedan od naših faktora jednak b. Iz ovoga zaključujemo da se cijeli zbroj može podijeliti s b, a kako je taj zbroj jednak c, onda se c može podijeliti s b.
Definicija 5
Ako su dva cijela broja a i b međusobno prosti, tada je gcd (a c, b) = gcd (c, b).
Dokazi 2
Dokažimo da će NOT (a c, b) dijeliti NOT (c, b), a nakon toga da će NOT (c, b) dijeliti NOT (a c, b), što će biti dokaz točnosti jednakosti NOT (a · c , b) = NTO (c , b) .
Budući da GCD (a · c, b) dijeli i a · c i b, a GCD (a · c, b) dijeli b, tada će također dijeliti b · c. To znači da GCD (a c, b) dijeli i a c i b c, dakle, zbog svojstava GCD, također dijeli GCD (a c, b c), što će biti jednako c GCD (a, b ) = c . Dakle, NOT (a · c, b) dijeli i b i c, dakle, također dijeli NOT (c, b).
Također se može reći da budući da GCD (c, b) dijeli i c i b, tada će dijeliti i c i a c. To znači da GCD (c, b) dijeli i a · c i b, dakle, također dijeli GCD (a · c, b).
Dakle, gcd (a c, b) i gcd (c, b) međusobno se dijele, što znači da su jednake.
Definicija 6
Ako su brojevi iz niza a 1 , a 2 , … , a k bit će relativno prosti u odnosu na brojeve niza b 1, b 2, …, b m(za prirodne vrijednosti k i m), zatim njihovi produkti a 1 · a 2 · … · a k I b 1 · b 2 · … · b m također su relativno prosti, posebno, a 1 = a 2 = … = a k = a I b 1 = b 2 = … = b m = b, To a k I b m- međusobno jednostavno.
Dokazi 3
Prema prethodnom svojstvu možemo napisati jednakosti sljedeći tip: NOT (a 1 · a 2 · … · a k , b m) = NOT (a 2 · … · a k , b m) = … = NOT (a k , b m) = 1 . Mogućnost posljednjeg prijelaza osigurava činjenica da su a k i b m relativno prosti prema uvjetu. To znači GCD (a 1 · a 2 · … · a k , b m) = 1 .
Označimo a 1 · a 2 · … · a k = A i dobijemo da je NOT (b 1 · b 2 · … · b m , a 1 · a 2 · … · a k) = NOT (b 1 · b 2 · … · b m , A) = NOT (b 2 · … · b · b m , A) = … = NOT (b m , A) = 1 . To će biti točno zbog posljednje jednakosti iz gore konstruiranog lanca. Dakle, imamo jednakost GCD (b 1 · b 2 · … · b m, a 1 · a 2 · … · a k) = 1, kojom možemo dokazati međusobnu jednostavnost umnožaka. a 1 · a 2 · … · a k I b 1 · b 2 · … · b m
Ovo su sva svojstva međusobno prostih brojeva o kojima bismo vam željeli govoriti.
Pojam uparenih prostih brojeva
Znajući što su međusobno prosti brojevi, možemo formulirati definiciju parnih prostih brojeva.
Definicija 7
Prosti brojevi u paru je niz cijelih brojeva a 1 , a 2 , ... , a k , gdje će svaki broj biti relativno prost u odnosu na ostale.
Primjer niza prostih brojeva u paru bio bi 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 uvjet uzajamno prostih brojeva obavezan za uparene proste brojeve, ali uzajamno prosti brojevi neće biti upareni prosti u svim slučajevima. Na primjer, u nizu 8, 16, 5 i 15, brojevi nisu takvi brojevi, budući da 8 i 16 neće biti međusobno prosti.
Također biste se trebali zadržati na konceptu zbirke određenog broja prostih brojeva. Oni će uvijek biti i međusobno i upareno jednostavni. Primjer bi bio niz 71, 443, 857, 991. U slučaju prostih brojeva, pojmovi međusobnog i uparenog prostog broja će se podudarati.
Ako primijetite grešku u tekstu, označite je i pritisnite Ctrl+Enter
Prirodni brojevi a i b nazivaju se međusobno prosti, ako je njihov najveći zajednički djelitelj 1 (NOD(a; b) = 1). Drugim riječima, ako brojevi a i b nemaju zajedničkih faktora osim 1, tada su međusobno prosti.
Primjeri parova međusobno prostih brojeva: 2 i 5, 13 i 16, 35 i 88 itd. Možete navesti nekoliko međusobno prostih brojeva, na primjer, brojevi 7, 9, 16 su međusobno prosti.
Često se međusobno prosti brojevi označavaju na sljedeći način: (a, b) = 1. Na primjer, (23, 30) = 1. Ova oznaka je, takoreći, skraćena oznaka za najveći zajednički djelitelj dvaju brojeva (NOT(23 , 30) = 1), i kaže da je njihov najveći zajednički djelitelj 1.
Dva susjedna prirodna broja uvijek će biti relativno prosti. Na primjer, 15 i 16 su par relativno prostih brojeva, baš kao i 16 i 17. To je lako razumjeti ako uzmete u obzir "pravilo" da ako su dva prirodna broja a i b djeljiva istim prirodnim brojem većim od 1 ( n > 1), onda i njihova razlika mora biti djeljiva s ovim brojem n (ovdje mislimo da su a, b i njihova razlika djeljivi cijelim brojem, tj. da su višekratnici broja n). Ali ako su a i b dva susjedna broja (neka a< b ), то b – a = 1; но 1 делится только на 1 (из ряда натуральных чисел). Следовательно, a и b не имеют других общих делителей, кроме 1.
Iz definicije međusobno prostih brojeva i prostih brojeva također slijedi da različiti prosti brojevi uvijek su međusobno prosti. Uostalom, djelitelji bilo kojeg prostog broja su samo on sam i 1.
Svojstva međusobno prostih brojeva
- Najmanji zajednički višekratnik (LCM) para međusobno prostih brojeva jednak je njihovom umnošku. Na primjer, (3, 8) = 1 (ovo znači međusobno prosti), stoga je njihov LCM 3 × 8 = 24 (LCM (3, 8) = 24). Doista, nećete pronaći manji broj od 24 koji je višekratnik i 3 i 8.
- Ako su brojevi a i b međusobno prosti i broj c je višekratnik i a i b, tada će i ovaj broj biti višekratnik umnoška ab. Ovo se može napisati ovako: ako c a i c b, onda c ab. Na primjer, (3, 10) = 1, broj 60 je višekratnik i 3 i 10, a također je i višekratnik 30 (3 × 10).
- Ako su brojevi a i b međusobno prosti i broj c je višekratnik b (c b ), tada će umnožak ac također biti višekratnik b (ac b ). Na primjer, (2, 17) = 1, neka je c = 34. Broj 34 je višekratnik b = 17, tada je ac = 2 × 34 = 68. Provjeravamo: 68 ÷ 17 = 4, tj. djeljiv je s cjelina, što znači da je 68 višekratnik 17.
Obično postoji više svojstava nego što je ovdje navedeno. Osim toga, svojstva međusobno prostih brojeva formulirana su na različite načine. Također može biti potrebno dokazati ta svojstva (u ovom slučaju se ne daje nikakav dokaz).
Ključne riječi: teorija brojeva, predavanja, međusobno prosti brojevi.
Definicija. Kaže se da su cijeli brojevi a i b relativno prosti ako je (a, b) = 1.
Dva broja a i b su prosti ako i samo ako postoje cijeli brojevi u i v takvi da je au + bv = 1.
Neka je X = ( x n | n = 1, 2,...) proizvoljan striktno rastući niz prirodnih brojeva (ili, ako želite, X je proizvoljan podskup prirodnih brojeva, poredanih na prirodan način). Označimo s ξ(N; X) broj članova niza X koji ne prelaze N .
Definicija. Broj se naziva (gornja asimptotička) gustoća niza X = (x n | n = 1, 2,...) u skupu N.
Primjer 1. Neka je x n = 2n, gdje n prolazi kroz N, niz svih parnih brojeva. Očito je da
Usput, ovo se dobro slaže s našim intuitivnim idejama da postoji polovica parnih brojeva.
Primjer 2. Neka je x n =2 n, gdje n prolazi kroz N, geometrijska progresija. Intuitivno je jasno da takvih brojeva u prirodnom nizu ima malo, jer što se u prirodnom nizu ide dalje u šumu, to su potencije dvojke rjeđe. Koncept gustoće potvrđuje ovaj osjećaj: ξ (2 k; ( x n )) = k, a lako je provjeriti da
Gustoća je vjerojatnost slučajnog odabira broja iz prirodnog niza koji pripada zadanom nizu.
Slično definiciji gustoće niza, možemo definirati i gustoću skupa parova prirodnih brojeva. Neka postoji proizvoljan skup X uređenih parova prirodnih brojeva. Označimo s ξ (N ; X) broj parova iz skupa X čija svaka komponenta ne prelazi N. Korisno je zamisliti parove brojeva iz skupa X kao koordinate točaka na koordinatnoj ravnini, tada je ξ (N; X) jednostavno broj točaka skupa X koje padaju u kvadrat ((x, y) | 0< x ≤ N ; 0 < y ≤ N }.
Definicija. Broj
naziva se (gornja asimptotska) gustoća skupa parova X u skupu N 2 .
Primjer 3. Neka je X skup svih parova prirodnih brojeva čija je prva komponenta strogo više od drugog. Skup X odgovara točkama prve četvrtine koordinatne ravnine, koje leže ispod simetrale y = x. Gustoću takvog skupa lako je izračunati:
Neka je X skup svih uređenih parova (u, v) prirodnih brojeva takvih da je (u, v) = 1, tj. skup svih parova međusobno prostih brojeva.
Teorem (Cesaro). Vjerojatnost odabira para međusobno prostih brojeva iz N jednaka je 6/π 2, točnije Dokaz. Pretpostavimo odmah da postoji vjerojatnost p da su slučajno odabrani prirodni brojevi a i b međusobno prosti. Neka d ∈ N. Neka P(S) označava, kao i obično, vjerojatnost događaja S. Rezoniramo: R
$p$ se naziva prostim brojem ako ima samo $2$ djelitelja: $1$ i sebe.
Djelitelj prirodnog broja $a$ je prirodni broj koji dijeli izvorni broj $a$ bez ostatka.
Primjer 1
Pronađite djelitelje broja $6$.
Rješenje: Trebamo pronaći sve brojeve kojima je zadani broj $6$ djeljiv bez ostatka. Ovo će biti brojevi: $1,2,3, 6$. Dakle, djelitelj broja $6$ bit će brojevi $1,2,3,6.$
Odgovor: 1,2,3,6$.
To znači da je za pronalaženje djelitelja nekog broja potrebno pronaći sve prirodne brojeve kojima je zadani broj djeljiv bez ostatka. Lako je vidjeti da će broj $1$ biti djelitelj bilo kojeg prirodnog broja.
Definicija 2
Kompozitni Nazivaju broj koji ima i druge djelitelje osim jednog i samog sebe.
Primjer prostog broja bio bi broj $13$, primjer složenog broja bi bio $14.$
Napomena 1
Broj $1$ ima samo jedan djelitelj - sam broj, tako da nije ni prost ni složen.
Koprosti brojevi
Definicija 3
Međusobno prosti brojevi to su oni čiji je gcd jednak $1$. To znači da da biste saznali jesu li brojevi relativno prosti, trebate pronaći njihov gcd i usporediti ga s $1$.
Upareni međusobno prosti
Definicija 4
Ako su u skupu brojeva bilo koja dva međusobno prosta, tada se takvi brojevi nazivaju upareno međusobno prosti. Za dva broja, pojmovi "koprime" i "pairwise coprime" se podudaraju.
Primjer 2
$8, $15 - nije jednostavno, ali relativno jednostavno.
$6, 8, 9$ su međusobno prosti brojevi, ali ne i upareni međusobno prosti brojevi.
$8, 15, 49$ su upareni relativno prosti.
Kao što vidimo, da bismo odredili jesu li brojevi relativno prosti, potrebno ih je prvo rastaviti na proste faktore. Obratimo pozornost na to kako to učiniti ispravno.
Rastavljanje na proste faktore
Na primjer, faktorizirajmo broj $180$ na proste faktore:
180$=2\cdot 2\cdot 3\cdot 3\cdot 5$
Iskoristimo svojstvo moći, tada ćemo dobiti,
180$=2^2\cdot 3^2\cdot 5$
Ovaj zapis rastavljanja na proste faktore zove se kanonski, tj. da bi se broj faktorizirao u kanonskom obliku, potrebno je koristiti svojstvo potencija i prikazati broj kao umnožak potencija s različitim bazama
Kanonsko širenje prirodnog broja u općem obliku
Kanonsko širenje prirodnog broja u općem obliku 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 kao kanonske dekompozicije na proste skupove olakšava pronalaženje najvećeg zajedničkog djelitelja brojeva i djeluje kao posljedica dokaza ili definicije međusobno prostih brojeva.
Primjer 3
Pronađite najveći zajednički djelitelj brojeva $180$ i $240$.
Rješenje: Rastavimo brojeve na jednostavne skupove pomoću kanonske dekompozicije
$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$
Nađimo sada gcd ovih brojeva, za to biramo potencije s istom bazom i s najmanjim eksponentom, zatim
$GCD\(180;240)= 2^2\cdot 3\cdot 5=60$
Sastavljajmo algoritam za pronalaženje GCD-a uzimajući u obzir kanoničku faktorizaciju na proste faktore.
Da biste pronašli najveći zajednički djelitelj dvaju brojeva pomoću kanonske ekspanzije, trebate:
- rastavite brojeve na proste faktore u kanonskom obliku
- odabrati potencije s istom bazom i s najmanjim eksponentom potencija uključenih u proširenje tih brojeva
- Pronađite umnožak brojeva pronađenih u koraku 2. Rezultirajući broj bit će željeni najveći zajednički djelitelj.
Primjer 4
Odredite jesu li brojevi $195$ i $336$ prosti i 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 relativno prosti. Također vidimo da svaki od brojeva uključuje faktore, osim $1$ i samog broja, što znači da brojevi neće biti prosti, već će biti složeni.
Primjer 5
Odredite jesu li brojevi $39$ i $112$ prosti i međusobno prosti brojevi.
Rješenje: Upotrijebimo kanonsku 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 relativno prosti. Također vidimo da svaki od brojeva uključuje faktore, osim $1$ i samog broja, što znači da brojevi neće biti prosti, već će biti složeni.
Primjer 6
Odredite jesu li brojevi $883$ i $997$ prosti i međusobno prosti brojevi.
Rješenje: Upotrijebimo kanonsku 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 relativno prosti. Također vidimo da svaki broj uključuje samo faktore jednake $1$ i sam broj, što znači da će brojevi biti prosti.
