Najmanji zajednički višestruki kalkulator. Zašto uvoditi koncepte "najvećeg zajedničkog djelitelja (GCD)" i "najmanjeg zajedničkog višekratnika (LCM)" brojeva u školski tečaj matematike

60=2*2*3*5
75=3*5*5
2) Ispisujemo faktore uključene u proširenje prvog od ovih brojeva i dodamo im faktor 5 koji nedostaje iz proširenja drugog broja. Dobivamo: 2*2*3*5*5=300. Osnovan NOC, t.j. ovaj zbroj = 300. Ne zaboravite dimenziju i napišite odgovor:
Odgovor: Mama daje po 300 rubalja.

Definicija GCD-a: Najveći zajednički djelitelj (GCD) prirodni brojevi a i u imenovati najveći prirodni broj c, na koje i a, i b podijeljeno bez ostatka. Oni. c je najmanji prirodni broj za koji i a i b su višestruki.

Podsjetnik: Postoje dva pristupa definiciji prirodnih brojeva

• brojevi koji se koriste u: nabrajanju (numeriranju) predmeta (prvi, drugi, treći, ...); - u školama, obično.
• koji označava broj predmeta (bez pokemona - nula, jedan pokemon, dva pokemona, ...).

Negativni i necijeli (racionalni, realni, ...) brojevi nisu prirodni. Neki autori uključuju nulu u skup prirodnih brojeva, drugi ne. Skup svih prirodnih brojeva obično se označava simbolom N

Podsjetnik: Djelitelj prirodnog broja a nazovi broj b, u kojoj a podijeljeno bez ostatka. Višekratnik prirodnog broja b naziva prirodnim brojem a, koji je podijeljen sa b bez traga. Ako broj b- djelitelj brojeva a, onda a višestruko od b. Primjer: 2 je djelitelj broja 4, a 4 je višekratnik broja 2. 3 je djelitelj broja 12, a 12 je višekratnik broja 3.
Podsjetnik: Prirodni brojevi se nazivaju prostim ako su bez ostatka djeljivi samo sa sobom i s 1. Međuprosti su brojevi koji imaju samo jedan zajednički djelitelj jednak 1.

Definicija kako pronaći GCD u općem slučaju: Kako pronaći GCD (najveći zajednički djelitelj) Potrebno je nekoliko prirodnih brojeva:
1) Rastavite ih na proste faktore. (Tabela prostih brojeva može biti od velike pomoći za ovo.)
2) Napiši faktore uključene u proširenje jednog od njih.
3) Izbrišite one koji nisu uključeni u proširenje preostalih brojeva.
4) Pomnožite faktore dobivene u stavku 3).

Zadatak 2 na (NOK): Do nove godine Kolja Puzatov kupio je u gradu 48 hrčaka i 36 džezva. Fekla Dormidontova, kao najiskrenija djevojčica u razredu, dobila je zadatak da tu imovinu podijeli na što veći broj poklon setova za učitelje. Koliki je broj kompleta? Kakav je sastav setova?

Primjer 2.1. rješavanje problema pronalaženja GCD. Pronalaženje GCD odabirom.
Odluka: Svaki od brojeva 48 i 36 mora biti djeljiv s brojem darova.
1) Ispiši djelitelje 48: 48, 24, 16, 12 , 8, 6, 3, 2, 1
2) Ispiši djelitelje 36: 36, 18, 12 , 9, 6, 3, 2, 1 Odaberite najveći zajednički djelitelj. Op-la-la! Pronađeno, ovo je broj kompleta od 12 komada.
3) Podijelimo 48 sa 12, dobijemo 4, podijelimo 36 sa 12, dobijemo 3. Ne zaboravite dimenziju i napišite odgovor:
Odgovor: Dobit ćete 12 kompleta od 4 hrčka i 3 posude za kavu u svakom setu.

Najveći zajednički djelitelj i najmanji zajednički višekratnik ključni su aritmetički koncepti koji vam omogućuju da jednostavno radite s običnim razlomcima. LCM i najčešće se koriste za pronalaženje zajedničkog nazivnika nekoliko razlomaka.

Osnovni koncepti

Djelitelj cijelog broja X je drugi cijeli broj Y kojim je X djeljiv bez ostatka. Na primjer, djelitelj broja 4 je 2, a 36 je 4, 6, 9. Višekratnik cijelog broja X je broj Y koji je djeljiv s X bez ostatka. Na primjer, 3 je višekratnik broja 15, a 6 je višekratnik broja 12.

Za svaki par brojeva možemo pronaći njihove zajedničke djelitelje i višekratnike. Na primjer, za 6 i 9, zajednički višekratnik je 18, a zajednički djelitelj je 3. Očito, parovi mogu imati nekoliko djelitelja i višekratnika, tako da se u izračunima koriste najveći djelitelj GCD-a i najmanji višekratnik LCM-a. .

Najmanji djelitelj nema smisla jer je za svaki broj uvijek jedan. Najveći višekratnik je također besmislen, jer niz višekratnika teži beskonačnosti.

Pronalaženje GCD-a

Postoje mnoge metode za pronalaženje najvećeg zajedničkog djelitelja, od kojih su najpoznatije:

• sekvencijalno nabrajanje djelitelja, odabir zajedničkih za par i traženje najvećeg od njih;
• rastavljanje brojeva na nedjeljive faktore;
• Euklidov algoritam;
• binarni algoritam.

Danas su u obrazovnim ustanovama najpopularnije metode dekompozicije na proste faktore i Euklidov algoritam. Potonji se pak koristi u rješavanju Diofantovih jednadžbi: traženje GCD-a potrebno je za provjeru mogućnosti rješavanja jednadžbe u cijelim brojevima.

Pronalaženje NOO-a

Najmanji zajednički višekratnik također je točno određen iterativnim nabrajanjem ili faktoriziranjem na nedjeljive faktore. Osim toga, lako je pronaći LCM ako je najveći djelitelj već određen. Za brojeve X i Y, LCM i GCD su povezani sljedećom relacijom:

LCM(X,Y) = X × Y / GCM(X,Y).

Na primjer, ako je gcd(15,18) = 3, tada je LCM(15,18) = 15 × 18 / 3 = 90. Najočitija upotreba LCM-a je pronaći zajednički nazivnik, koji je najmanji zajednički višekratnik zadani razlomci.

Koprosti brojevi

Ako par brojeva nema zajedničkih djelitelja, onda se takav par naziva međusobno prostim. GCM za takve parove uvijek je jednak jedinici, a na temelju povezanosti djelitelja i višekratnika, GCM za koproste je jednak njihovom umnošku. Na primjer, brojevi 25 i 28 su prosti, jer nemaju zajedničkih djelitelja, a LCM(25, 28) = 700, što odgovara njihovom umnošku. Bilo koja dva nedjeljiva broja uvijek će biti međusobno prosti.

Zajednički djelitelj i višestruki kalkulator

S našim kalkulatorom možete izračunati GCD i LCM za bilo koji broj brojeva koje možete izabrati. Zadaci za izračunavanje zajedničkih djelitelja i višekratnika nalaze se u aritmetici 5. i 6. razreda, no GCD i LCM su ključni pojmovi matematike i koriste se u teoriji brojeva, planimetriji i komunikativnoj algebri.

Primjeri iz stvarnog života

Zajednički nazivnik razlomaka

Najmanji zajednički višekratnik koristi se kada se nalazi zajednički nazivnik nekoliko razlomaka. Pretpostavimo da je u aritmetičkom problemu potrebno zbrojiti 5 razlomaka:

1/8 + 1/9 + 1/12 + 1/15 + 1/18.

Za zbrajanje razlomaka, izraz se mora svesti na zajednički nazivnik, što se svodi na problem pronalaženja LCM-a. Da biste to učinili, odaberite 5 brojeva u kalkulatoru i unesite vrijednosti nazivnika u odgovarajuće ćelije. Program će izračunati LCM (8, 9, 12, 15, 18) = 360. Sada morate izračunati dodatne faktore za svaki razlomak, koji su definirani kao omjer LCM i nazivnika. Dakle, dodatni množitelji bi izgledali ovako:

• 360/8 = 45
• 360/9 = 40
• 360/12 = 30
• 360/15 = 24
• 360/18 = 20.

Nakon toga pomnožimo sve razlomke s odgovarajućim dodatnim faktorom i dobijemo:

45/360 + 40/360 + 30/360 + 24/360 + 20/360.

Takve razlomke možemo lako zbrojiti i dobiti rezultat u obliku 159/360. Smanjujemo razlomak za 3 i vidimo konačni odgovor - 53/120.

Rješenje linearnih diofantovih jednadžbi

Linearne Diofantove jednadžbe su izrazi oblika ax + by = d. Ako je omjer d / gcd(a, b) cijeli broj, onda je jednadžba rješiva ​​u cijelim brojevima. Provjerimo nekoliko jednadžbi za mogućnost cjelobrojnog rješenja. Prvo provjerite jednadžbu 150x + 8y = 37. Pomoću kalkulatora nalazimo gcd (150,8) = 2. Podijelite 37/2 = 18,5. Broj nije cijeli broj, stoga jednadžba nema cjelobrojne korijene.

Provjerimo jednadžbu 1320x + 1760y = 10120. Pomoću kalkulatora pronađite gcd(1320, 1760) = 440. Podijelite 10120/440 = 23. Kao rezultat, dobivamo cijeli broj, stoga je Diofantova jednadžba rješiva ​​u cjelobrojnim koeficijentima .

Zaključak

GCD i LCM igraju važnu ulogu u teoriji brojeva, a sami koncepti naširoko se koriste u raznim područjima matematike. Koristite naš kalkulator za izračun najvećih djelitelja i najmanjih višekratnika bilo kojeg broja brojeva.

Materijal prikazan u nastavku logičan je nastavak teorije iz članka pod naslovom LCM - najmanji zajednički višekratnik, definicija, primjeri, odnos između LCM i GCD. Ovdje ćemo razgovarati o pronalaženje najmanjeg zajedničkog višekratnika (LCM), a posebnu pažnju posvetiti rješavanju primjera. Pokažimo prvo kako se LCM dvaju brojeva izračunava u smislu GCD tih brojeva. Zatim razmislite o pronalaženju najmanjeg zajedničkog višekratnika rastavljanjem brojeva na proste faktore. Nakon toga ćemo se usredotočiti na pronalaženje LCM-a tri ili više brojeva, a također obratiti pažnju na izračun LCM-a negativnih brojeva.

Navigacija po stranici.

Izračunavanje najmanjeg zajedničkog višekratnika (LCM) kroz gcd

Jedan način da se pronađe najmanji zajednički višekratnik temelji se na odnosu između LCM i GCD. Postojeći odnos između LCM i GCD omogućuje vam izračunavanje najmanjeg zajedničkog višekratnika dvaju pozitivnih cijelih brojeva kroz poznati najveći zajednički djelitelj. Odgovarajuća formula ima oblik LCM(a, b)=a b: GCD(a, b) . Razmotrite primjere pronalaženja LCM-a prema gornjoj formuli.

Primjer.

Odredi najmanji zajednički višekratnik dvaju brojeva 126 i 70 .

Odluka.

U ovom primjeru a=126 , b=70 . Upotrijebimo odnos između LCM i GCD izražen formulom LCM(a, b)=a b: GCD(a, b). Odnosno, prvo moramo pronaći najveći zajednički djelitelj brojeva 70 i 126, nakon čega možemo izračunati LCM tih brojeva prema napisanoj formuli.

Pronađite gcd(126, 70) pomoću Euklidovog algoritma: 126=70 1+56 , 70=56 1+14 , 56=14 4 , dakle gcd(126, 70)=14 .

Sada nalazimo traženi najmanji zajednički višekratnik: LCM(126, 70)=126 70: GCM(126, 70)= 126 70:14=630 .

Odgovor:

LCM(126, 70)=630.

Primjer.

Što je LCM(68, 34)?

Odluka.

Kao 68 je ravnomjerno djeljiv s 34 , tada je gcd(68, 34)=34 . Sada izračunavamo najmanji zajednički višekratnik: LCM(68, 34)=68 34: LCM(68, 34)= 68 34:34=68 .

Odgovor:

LCM(68, 34)=68.

Imajte na umu da prethodni primjer odgovara sljedećem pravilu za pronalaženje LCM-a za pozitivne cijele brojeve a i b: ako je broj a djeljiv s b, tada je najmanji zajednički višekratnik ovih brojeva a.

Pronalaženje LCM rastavljanjem brojeva na proste faktore

Drugi način pronalaska najmanjeg zajedničkog višekratnika temelji se na rastavljanju brojeva na proste faktore. Ako napravimo umnožak svih prostih faktora tih brojeva, nakon čega iz tog umnoška isključimo sve zajedničke proste faktore koji su prisutni u proširenjima tih brojeva, tada će rezultirajući umnožak biti jednak najmanjem zajedničkom višekratniku tih brojeva.

Najavljeno pravilo za pronalaženje LCM slijedi iz jednakosti LCM(a, b)=a b: GCD(a, b). Doista, umnožak brojeva a i b jednak je umnošku svih faktora uključenih u proširenja brojeva a i b. S druge strane, gcd(a, b) jednak je umnošku svih prostih faktora koji su istovremeno prisutni u proširenjima brojeva a i b (što je opisano u odjeljku o pronalaženju gcd korištenjem dekompozicije brojeva na proste faktore ).

Uzmimo primjer. Neka znamo da je 75=3 5 5 i 210=2 3 5 7 . Sastavite umnožak svih faktora ovih proširenja: 2 3 3 5 5 5 7 . Sada iz ovog umnoška izuzimamo sve faktore koji su prisutni i u razvitku broja 75 i u razvitku broja 210 (takvi su faktori 3 i 5), tada će umnožak imati oblik 2 3 5 5 7 . Vrijednost ovog umnoška jednaka je najmanjem zajedničkom višekratniku brojeva 75 i 210, tj. LCM(75, 210)= 2 3 5 5 7=1 050.

Primjer.

Nakon rastavljanja brojeva 441 i 700 na proste faktore, pronađite najmanji zajednički višekratnik tih brojeva.

Odluka.

Rastavimo brojeve 441 i 700 na proste faktore:

Dobivamo 441=3 3 7 7 i 700=2 2 5 5 7 .

Sada napravimo umnožak svih faktora uključenih u proširenja ovih brojeva: 2 2 3 3 5 5 7 7 7 . Isključimo iz ovog umnoška sve faktore koji su istovremeno prisutni u oba proširenja (postoji samo jedan takav faktor - to je broj 7): 2 2 3 3 5 5 7 7 . Na ovaj način, LCM(441, 700)=2 2 3 3 5 5 7 7=44 100.

Odgovor:

LCM(441, 700)= 44 100 .

Pravilo za pronalaženje LCM-a pomoću dekompozicije brojeva na proste faktore može se formulirati malo drugačije. Ako faktorima iz proširenja broja a dodamo faktore koji nedostaju iz proširenja broja b, tada će vrijednost dobivenog umnoška biti jednaka najmanjem zajedničkom višekratniku brojeva a i b.

Na primjer, uzmimo sve iste brojeve 75 i 210, njihova proširenja na proste faktore su sljedeća: 75=3 5 5 i 210=2 3 5 7 . Faktorima 3, 5 i 5 iz rastavljanja broja 75 dodamo faktore koji nedostaju 2 i 7 iz rastavljanja broja 210, dobivamo umnožak 2 3 5 5 7 čija je vrijednost LCM(75 , 210) .

Primjer.

Pronađite najmanji zajednički višekratnik brojeva 84 i 648.

Odluka.

Prvo dobivamo rastavljanje brojeva 84 i 648 na proste faktore. Izgledaju kao 84=2 2 3 7 i 648=2 2 2 3 3 3 3 . Faktorima 2, 2, 3 i 7 iz rastavljanja broja 84 dodamo faktore koji nedostaju 2, 3, 3 i 3 iz rastavljanja broja 648, dobivamo umnožak 2 2 2 3 3 3 3 7 , što je jednako 4 536 . Dakle, željeni najmanji zajednički višekratnik brojeva 84 i 648 je 4,536.

Odgovor:

LCM(84, 648)=4 536 .

Pronalaženje LCM tri ili više brojeva

Najmanji zajednički višekratnik tri ili više brojeva može se pronaći uzastopnim pronalaženjem LCM dvaju brojeva. Prisjetite se odgovarajućeg teorema koji daje način da se pronađe LCM tri ili više brojeva.

Teorema.

Neka su zadani pozitivni cijeli brojevi a 1 , a 2 , …, a k, najmanji zajednički višekratnik m k ovih brojeva nalazi se u sekvencijalnom izračunu m 2 = LCM (a 1 , a 2) , m 3 = LCM (m 2 , a 3) , … , m k =LCM(m k−1 , a k) .

Razmotrimo primjenu ovog teorema na primjeru pronalaženja najmanjeg zajedničkog višekratnika četiriju brojeva.

Primjer.

Odredite LCM četiri broja 140, 9, 54 i 250.

Odluka.

U ovom primjeru a 1 =140, a 2 =9, a 3 =54, a 4 =250.

Prvo nalazimo m 2 \u003d LCM (a 1, a 2) \u003d LCM (140, 9). Da bismo to učinili, koristeći Euklidov algoritam, odredimo gcd(140, 9) , imamo 140=9 15+5 , 9=5 1+4 , 5=4 1+1 , 4=1 4 , dakle, gcd( 140, 9)=1 , odakle LCM(140, 9)=140 9: LCM(140, 9)= 140 9:1=1 260 . Odnosno, m 2 =1 260 .

Sada nalazimo m 3 \u003d LCM (m 2, a 3) \u003d LCM (1 260, 54). Izračunajmo ga preko gcd(1 260, 54) , koji je također određen Euklidovim algoritmom: 1 260=54 23+18 , 54=18 3 . Tada je gcd(1 260, 54)=18 , odakle je LCM(1 260, 54)= 1 260 54:gcd(1 260, 54)= 1 260 54:18=3 780 . Odnosno, m 3 \u003d 3 780.

Preostalo pronaći m 4 \u003d LCM (m 3, a 4) \u003d LCM (3 780, 250). Da bismo to učinili, nalazimo GCD(3 780, 250) pomoću Euklidovog algoritma: 3 780=250 15+30 , 250=30 8+10 , 30=10 3 . Prema tome, gcd(3 780, 250)=10, odakle je gcd(3 780, 250)= 3 780 250:gcd(3 780, 250)= 3 780 250:10=94 500 . Odnosno, m 4 \u003d 94 500.

Dakle, najmanji zajednički višekratnik originalna četiri broja je 94 500.

Odgovor:

LCM(140, 9, 54, 250)=94,500.

U mnogim slučajevima, najmanji zajednički višekratnik tri ili više brojeva lako se pronalazi korištenjem prostih faktora zadanih brojeva. U ovom slučaju treba se pridržavati sljedećeg pravila. Najmanji zajednički višekratnik više brojeva jednak je umnošku koji se sastavlja na sljedeći način: faktori koji nedostaju iz proširenja drugog broja pribrajaju se svim faktorima iz proširenja prvog broja, faktori koji nedostaju iz proširenja treći broj se dodaje dobivenim faktorima, i tako dalje.

Razmotrimo primjer pronalaženja najmanjeg zajedničkog višekratnika pomoću rastavljanja brojeva na proste faktore.

Primjer.

Odredi najmanji zajednički višekratnik pet brojeva 84, 6, 48, 7, 143.

Odluka.

Prvo, dobivamo proširenja ovih brojeva na proste faktore: 84=2 2 3 7 , 6=2 3 , 48=2 2 2 2 3 , 7 prostih faktora) i 143=11 13 .

Da biste pronašli LCM ovih brojeva, faktorima prvog broja 84 (to su 2 , 2 , 3 i 7 ) trebate dodati faktore koji nedostaju iz proširenja drugog broja 6 . Proširenje broja 6 ne sadrži faktore koji nedostaju, budući da su i 2 i 3 već prisutni u razvitku prvog broja 84 . Nadalje faktorima 2, 2, 3 i 7 dodamo faktore 2 i 2 koji nedostaju iz proširenja trećeg broja 48, dobivamo skup faktora 2, 2, 2, 2, 3 i 7. Nema potrebe dodavati faktore ovom skupu u sljedećem koraku, budući da je 7 već sadržan u njemu. Na kraju faktorima 2 , 2 , 2 , 2 , 3 i 7 pribrajamo faktore 11 i 13 koji nedostaju iz proširenja broja 143 . Dobivamo umnožak 2 2 2 2 3 7 11 13 koji je jednak 48 048 .

Najveći zajednički djelitelj

Definicija 2

Ako je prirodni broj a djeljiv s prirodnim brojem $b$, tada se $b$ naziva djeliteljom od $a$, a broj $a$ višekratnikom od $b$.

Neka su $a$ i $b$ prirodni brojevi. Broj $c$ naziva se zajedničkim djeliteljem i za $a$ i za $b$.

Skup zajedničkih djelitelja brojeva $a$ i $b$ je konačan, jer nijedan od tih djelitelja ne može biti veći od $a$. To znači da među tim djeliteljima postoji najveći, koji se naziva najvećim zajedničkim djeliteljem brojeva $a$ i $b$, a za njegovu oznaku koristi se oznaka:

$gcd \ (a;b) \ ​​​​ili \ D \ (a;b)$

Da biste pronašli najveći zajednički djelitelj dvaju brojeva:

1. Pronađite umnožak brojeva pronađenih u koraku 2. Rezultirajući broj bit će željeni najveći zajednički djelitelj.

Primjer 1

Odredite NNO brojeva $121$ i $132.$

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Odaberite brojeve koji su uključeni u proširenje ovih brojeva

$242=2\cdot 11\cdot 11$

$132=2\cdot 2\cdot 3\cdot 11$

Pronađite umnožak brojeva pronađenih u koraku 2. Rezultirajući broj bit će željeni najveći zajednički djelitelj.

$gcd=2\cdot 11=22$

Primjer 2

Pronađite GCD monoma $63$ i $81$.

Pronaći ćemo prema predstavljenom algoritmu. Za ovo:

Rastavimo brojeve na proste faktore

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Odabiremo brojeve koji su uključeni u proširenje tih brojeva

$63=3\cdot 3\cdot 7$

$81=3\cdot 3\cdot 3\cdot 3$

Pronađimo umnožak brojeva pronađenih u koraku 2. Rezultirajući broj bit će željeni najveći zajednički djelitelj.

$gcd=3\cdot 3=9$

GCD dvaju brojeva možete pronaći na drugi način, pomoću skupa djelitelja brojeva.

Primjer 3

Odredite NNO brojeva $48$ i $60$.

Odluka:

Pronađite skup djelitelja od $48$: $\lijevo\((\rm 1,2,3.4.6,8,12,16,24,48)\desno\)$

Pronađimo sada skup djelitelja od $60$:$\ \lijevo\((\rm 1,2,3,4,5,6,10,12,15,20,30,60)\desno\)$

Pronađimo presjek ovih skupova: $\lijevo\((\rm 1,2,3,4,6,12)\desno\)$ - ovaj skup će odrediti skup zajedničkih djelitelja brojeva $48$ i $60 $. Najveći element u ovom skupu bit će broj $12$. Dakle, najveći zajednički djelitelj $48$ i $60$ je $12$.

Definicija NOC-a

Definicija 3

zajednički višekratnik prirodnih brojeva$a$ i $b$ je prirodni broj koji je višekratnik i $a$ i $b$.

Zajednički višekratnici brojeva su brojevi koji su djeljivi s originalom bez ostatka. Na primjer, za brojeve $25$ i $50$, zajednički višekratnici će biti brojevi $50,100,150,200$, itd.

Najmanji zajednički višekratnik nazivat ćemo najmanji zajednički višekratnik i označavati ga s LCM$(a;b)$ ili K$(a;b).$

Da biste pronašli LCM dva broja, trebate:

1. Rastavite brojeve na proste faktore
2. Ispiši faktore koji su dio prvog broja i dodaj im faktore koji su dio drugog, a ne idu u prvi

Primjer 4

Pronađite LCM brojeva $99$ i $77$.

Pronaći ćemo prema predstavljenom algoritmu. Za ovo

Rastavite brojeve na proste faktore

99$=3\cdot 3\cdot 11$

Zapišite čimbenike uključene u prvi

dodajte im faktore koji su dio drugog i ne idu prvom

Pronađite umnožak brojeva pronađenih u koraku 2. Rezultirajući broj bit će željeni najmanji zajednički višekratnik

$LCC=3\cdot 3\cdot 11\cdot 7=693$

Sastavljanje popisa djelitelja brojeva često oduzima mnogo vremena. Postoji način da se pronađe GCD koji se zove Euklidov algoritam.

Tvrdnje na kojima se temelji Euklidov algoritam:

Ako su $a$ i $b$ prirodni brojevi, a $a\vtočkice b$, onda je $D(a;b)=b$

Ako su $a$ i $b$ prirodni brojevi takvi da je $b

Koristeći $D(a;b)= D(a-b;b)$, možemo sukcesivno smanjivati ​​brojeve koje razmatramo dok ne dođemo do para brojeva tako da je jedan od njih djeljiv s drugim. Tada će manji od tih brojeva biti željeni najveći zajednički djelitelj za brojeve $a$ i $b$.

Svojstva GCD i LCM

1. Svaki zajednički višekratnik $a$ i $b$ djeljiv je s K$(a;b)$
2. Ako $a\vtočke b$ , tada je K$(a;b)=a$

Ako je K$(a;b)=k$ i $m$-prirodni broj, onda je K$(am;bm)=km$

Ako je $d$ zajednički djelitelj za $a$ i $b$, tada je K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d ) $

Ako $a\vdots c$ i $b\vdots c$ , tada je $\frac(ab)(c)$ zajednički višekratnik $a$ i $b$

Za sve prirodne brojeve $a$ i $b$ vrijedi jednakost

$D(a;b)\cdot K(a;b)=ab$

Svaki zajednički djelitelj od $a$ i $b$ je djelitelj od $D(a;b)$

GCD je najveći zajednički djelitelj.

Da biste pronašli najveći zajednički djelitelj nekoliko brojeva:

• odrediti faktore zajedničke obama brojevima;
• pronaći umnožak zajedničkih faktora.

Primjer pronalaska GCD-a:

Nađi NOT brojeva 315 i 245.

315 = 5 * 3 * 3 * 7;

245 = 5 * 7 * 7.

2. Napiši faktore koji su zajednički za oba broja:

3. Nađite umnožak zajedničkih faktora:

gcd(315; 245) = 5 * 7 = 35.

Odgovor: GCD(315; 245) = 35.

Pronalaženje NOO-a

LCM je najmanji zajednički višekratnik.

Da biste pronašli najmanji zajednički višekratnik nekoliko brojeva:

• rastaviti brojeve na proste faktore;
• napiši faktore uključene u proširenje jednog od brojeva;
• dodati im faktore koji nedostaju iz proširenja drugog broja;
• pronaći umnožak dobivenih faktora.

Primjer pronalaska NOC-a:

Odredite LCM brojeva 236 i 328:

1. Rastavljamo brojeve na proste faktore:

236 = 2 * 2 * 59;

328 = 2 * 2 * 2 * 41.

2. Zapiši faktore koji su uključeni u proširenje jednog od brojeva i dodaj im faktore koji nedostaju iz proširenja drugog broja:

2; 2; 59; 2; 41.

3. Pronađite umnožak dobivenih faktora:

LCM(236; 328) = 2 * 2 * 59 * 2 * 41 = 19352.

Odgovor: LCM(236; 328) = 19352.

Da biste pronašli GCD (najveći zajednički djelitelj) dvaju brojeva, trebate:

2. Nađi (podcrtaj) sve zajedničke proste faktore u dobivenim proširenjima.

3. Pronađite umnožak zajedničkih prostih faktora.

Da biste pronašli LCM (najmanji zajednički višekratnik) dva broja, trebate:

1. Rastavite ove brojeve na proste faktore.

2. Dopuni proširenje jednog od njih onim faktorima proširenja drugog broja, koji nisu u proširenju prvog.

3. Izračunajte umnožak dobivenih faktora.