Najveći zajednički djelitelj
Definicija 2
Ako je prirodan broj a djeljiv prirodnim brojem $b$, tada se $b$ naziva djelitelj od $a$, a $a$ se naziva višekratnik od $b$.
Neka su $a$ i $b$ prirodni brojevi. Broj $c$ se naziva zajedničkim djeliteljem i $a$ i $b$.
Skup zajedničkih djelitelja brojeva $a$ i $b$ je konačan, jer nijedan od ovih djelitelja ne može biti veći od $a$. To znači da među ovim djeliteljima postoji najveći, koji se naziva najveći zajednički djelitelj brojeva $a$ i $b$ i označava se sljedećim zapisom:
$GCD\(a;b)\ ili \D\(a;b)$
Da biste pronašli najveći zajednički djelitelj dva broja potrebno vam je:
- Pronađite proizvod brojeva pronađenih u koraku 2. Rezultirajući broj će biti željeni najveći zajednički djelitelj.
Primjer 1
Pronađite gcd 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 proizvod brojeva pronađenih u koraku 2. Rezultirajući broj će biti ž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:
Razložimo brojeve u 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 ovih brojeva
$63=3\cdot 3\cdot 7$
$81=3\cdot 3\cdot 3\cdot 3$
Nađimo proizvod brojeva pronađenih u koraku 2. Rezultirajući broj će biti željeni najveći zajednički djelitelj.
$GCD=3\cdot 3=9$
Možete pronaći gcd dva broja na drugi način, koristeći skup djelitelja brojeva.
Primjer 3
Pronađite gcd brojeva $48$ i $60$.
Rješenje:
Nađimo skup djelitelja broja $48$: $\left\((\rm 1,2,3.4.6,8,12,16,24,48)\right\)$
Sada pronađimo skup djelitelja broja $60$:$\ \left\((\rm 1,2,3,4,5,6,10,12,15,20,30,60)\desno\) $
Nađimo presjek ovih skupova: $\left\((\rm 1,2,3,4,6,12)\right\)$ - ovaj skup će odrediti skup zajedničkih djelitelja brojeva $48$ i $60 $. Najveći element u ovom setu će biti broj $12$. To znači da je najveći zajednički djelitelj brojeva $48$ i $60$ 12$.
Definicija NPL-a
Definicija 3
Zajednički višekratnici prirodnih brojeva$a$ i $b$ je prirodan broj koji je višekratnik i $a$ i $b$.
Uobičajeni višekratnici brojeva su brojevi koji su djeljivi originalnim brojevima 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 će se zvati najmanji zajednički višekratnik i označavat će se LCM$(a;b)$ ili K$(a;b).$
Da biste pronašli LCM dva broja, trebate:
- Faktor brojevi u proste faktore
- Zapišite faktore koji su dio prvog broja i dodajte im faktore koji su dio drugog, a nisu dio prvog
Primjer 4
Pronađite LCM brojeva $99$ i $77$.
Pronaći ćemo prema predstavljenom algoritmu. Za ovo
Faktor brojevi u proste faktore
$99=3\cdot 3\cdot 11$
Zapišite faktore uključene u prvi
dodajte im množitelje koji su dio drugog, a ne dio prvog
Pronađite proizvod brojeva pronađenih u koraku 2. Rezultirajući broj će biti željeni najmanji zajednički višekratnik
$NOK=3\cdot 3\cdot 11\cdot 7=693$
Sastavljanje lista djelitelja brojeva često je vrlo naporan zadatak. Postoji način da se pronađe GCD koji se zove Euklidski algoritam.
Izjave na kojima se zasniva Euklidski algoritam:
Ako su $a$ i $b$ prirodni brojevi, a $a\vdots 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 koji se razmatraju dok ne dođemo do para brojeva tako da je jedan od njih djeljiv drugim. Tada će manji od ovih brojeva biti željeni najveći zajednički djelitelj za brojeve $a$ i $b$.
Svojstva GCD i LCM
- Svaki zajednički višekratnik $a$ i $b$ je djeljiv sa K$(a;b)$
- Ako je $a\vdots b$, onda je K$(a;b)=a$
Ako je K$(a;b)=k$ i $m$ prirodan 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 je $a\vdots c$ i $b\vdots c$, tada je $\frac(ab)(c)$ zajednički višekratnik $a$ i $b$
Za bilo koje prirodne brojeve $a$ i $b$ vrijedi jednakost
$D(a;b)\cdot K(a;b)=ab$
Svaki zajednički djelitelj brojeva $a$ i $b$ je djelitelj broja $D(a;b)$
Najveći zajednički djelitelj i najmanji zajednički višekratnik su ključni aritmetički koncepti koji čine rad s razlomcima lakim. LCM i najčešće se koriste za pronalaženje zajedničkog nazivnika nekoliko razlomaka.
Osnovni koncepti
Delitelj cijelog broja X je drugi cijeli broj Y kojim je X podijeljen 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 sa X bez ostatka. Na primjer, 3 je višekratnik od 15, a 6 je višekratnik od 12.
Za bilo koji par brojeva možemo pronaći njihove zajedničke djelitelje i višekratnike. Na primjer, za 6 i 9, zajednički djelitelj je 18, a zajednički djelitelj je 3. Očigledno, parovi mogu imati nekoliko djelitelja i višekratnika, tako da se u proračunima koriste najveći djelitelj GCD i najmanji višestruki LCM.
Najmanji djelitelj je besmislen, jer je za bilo koji broj uvijek jedan. Najveći umnožak je također besmislen, jer niz višekratnika ide u beskonačnost.
Pronalaženje gcd
Postoji mnogo metoda za pronalaženje najvećeg zajedničkog djelitelja, od kojih su najpoznatije:
- sekvencijalno traženje djelitelja, odabir zajedničkih za par i traženje najvećeg od njih;
- dekompozicija brojeva na nedjeljive faktore;
- Euklidski algoritam;
- binarni algoritam.
Danas u obrazovnim institucijama najpopularnije metode su dekompozicija na osnovne faktore i Euklidski algoritam. Potonji se, pak, koristi pri rješavanju Diofantovih jednadžbi: traženje GCD-a je potrebno da bi se provjerila mogućnost rezolucije u cijelim brojevima.
Pronalaženje NOC-a
Najmanji zajednički višekratnik se također određuje sekvencijalnim pretraživanjem ili dekompozicijom 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 povezani su sljedećim odnosom:
LCD(X,Y) = X × Y / GCD(X,Y).
Na primjer, ako je GCM(15,18) = 3, tada je LCM(15,18) = 15 × 18 / 3 = 90. Najočigledniji primjer korištenja LCM je pronalaženje zajedničkog nazivnika, koji je najmanji zajednički višekratnik dati razlomci.
Koprosti brojevi
Ako par brojeva nema zajedničkih djelitelja, onda se takav par naziva koprostor. Gcd za takve parove je uvijek jednak jedan, a na osnovu veze između djelitelja i višekratnika, gcd za koprime parove jednak je njihovom proizvodu. Na primjer, brojevi 25 i 28 su relativno prosti, jer nemaju zajedničkih djelitelja, a LCM(25, 28) = 700, što odgovara njihovom proizvodu. Bilo koja dva nedjeljiva broja uvijek će biti relativno prosti.
Zajednički djelitelj i višestruki kalkulator
Koristeći naš kalkulator možete izračunati GCD i LCM za proizvoljan broj brojeva koje možete izabrati. Zadaci za izračunavanje zajedničkih djelitelja i višekratnika nalaze se u aritmetici 5. i 6. razreda, ali GCD i LCM su ključni pojmovi u matematici i koriste se u teoriji brojeva, planimetriji i komunikativnoj algebri.
Primjeri iz stvarnog života
Zajednički nazivnik razlomaka
Najmanji zajednički višekratnik se koristi kada se pronađe zajednički nazivnik nekoliko razlomaka. Recimo da u aritmetičkom zadatku trebate zbrojiti 5 razlomaka:
1/8 + 1/9 + 1/12 + 1/15 + 1/18.
Za dodavanje razlomaka, izraz se mora svesti na zajednički nazivnik, što se svodi na problem pronalaženja LCM. 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 definisani kao omjer LCM-a 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 odgovarajućim dodatnim faktorom i dobijemo:
45/360 + 40/360 + 30/360 + 24/360 + 20/360.
Lako možemo sabrati takve razlomke i dobiti rezultat kao 159/360. Smanjujemo razlomak za 3 i vidimo konačan odgovor - 53/120.
Rješavanje 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 jednačina da vidimo da li imaju cjelobrojno rješenje. Prvo, provjerimo jednačinu 150x + 8y = 37. Koristeći kalkulator, nalazimo GCD (150,8) = 2. Podijelimo 37/2 = 18,5. Broj nije cijeli broj, stoga jednadžba nema cjelobrojne korijene.
Provjerimo jednačinu 1320x + 1760y = 10120. Koristite kalkulator da nađete GCD(1320, 1760) = 440. Podijelite 10120/440 = 23. Kao rezultat, dobijamo cijeli broj, pa je Diofantov koeficijent tako u jednadžbi .
Zaključak
GCD i LCM igraju veliku ulogu u teoriji brojeva, a sami koncepti se široko koriste u raznim oblastima matematike. Koristite naš kalkulator za izračunavanje najvećih djelitelja i najmanjih višekratnika bilo kojeg broja brojeva.
Višekratnik je broj koji je djeljiv datim brojem bez ostatka. Najmanji zajednički višekratnik (LCM) grupe brojeva je najmanji broj koji je djeljiv sa svakim brojem u grupi bez ostavljanja ostatka. Da biste pronašli najmanji zajednički umnožak, morate pronaći proste faktore datih brojeva. LCM se također može izračunati korištenjem niza drugih metoda koje se primjenjuju na grupe od dva ili više brojeva.
Koraci
Serija višestrukih
- Na primjer, pronađite najmanji zajednički višekratnik 5 i 8. Ovo su mali brojevi, tako da možete koristiti ovu metodu.
-
Višekratnik je broj koji je djeljiv datim brojem bez ostatka. Višestruke možete pronaći u tablici množenja.
- Na primjer, brojevi koji su višekratnici broja 5 su: 5, 10, 15, 20, 25, 30, 35, 40.
-
Zapišite niz brojeva koji su višekratnici prvog broja. Uradite to pod višekratnicima prvog broja da biste uporedili dva skupa brojeva.
- Na primjer, brojevi koji su višekratnici broja 8 su: 8, 16, 24, 32, 40, 48, 56 i 64.
-
Pronađite najmanji broj koji je prisutan u oba skupa višekratnika. Možda ćete morati napisati duge nizove višekratnika da biste pronašli ukupan broj. Najmanji broj koji je prisutan u oba skupa višekratnika je najmanji zajednički višekratnik.
- Na primjer, najmanji broj koji se pojavljuje u nizu višekratnika 5 i 8 je broj 40. Dakle, 40 je najmanji zajednički višekratnik 5 i 8.
Primena faktorizacije
-
Pogledaj ove brojke. Ovdje opisani metod najbolje je koristiti kada su data dva broja, od kojih je svaki veći od 10. Ako su dati manji brojevi, koristite drugu metodu.
- Na primjer, pronađite najmanji zajednički višekratnik brojeva 20 i 84. Svaki od brojeva je veći od 10, tako da možete koristiti ovu metodu.
-
Faktori prvi broj u proste faktore. To jest, morate pronaći takve proste brojeve koji će, kada se pomnože, rezultirati datim brojem. Nakon što ste pronašli osnovne faktore, zapišite ih kao jednakosti.
- Na primjer, 2 × 10 = 20 (\displaystyle (\mathbf (2) )\puta 10=20) I 2 × 5 = 10 (\displaystyle (\mathbf (2) )\puta (\mathbf (5) )=10). Dakle, prosti činioci broja 20 su brojevi 2, 2 i 5. Napiši ih kao izraz: .
-
Faktori drugi broj u proste faktore. Uradite to na isti način kao što ste rastavili na faktore prvi broj, odnosno pronađite takve proste brojeve koji će, kada se pomnože, dati dati broj.
- Na primjer, 2 × 42 = 84 (\displaystyle (\mathbf (2) )\puta 42=84), 7 × 6 = 42 (\displaystyle (\mathbf (7) )\puta 6=42) I 3 × 2 = 6 (\displaystyle (\mathbf (3) )\puta (\mathbf (2) )=6). Dakle, prosti činioci broja 84 su brojevi 2, 7, 3 i 2. Napiši ih kao izraz: .
-
Zapišite faktore zajedničke za oba broja. Napišite takve faktore kao operaciju množenja. Dok pišete svaki faktor, precrtajte ga u oba izraza (izrazi koji opisuju faktorizaciju brojeva u proste faktore).
- Na primjer, oba broja imaju zajednički faktor 2, pa napišite 2 × (\displaystyle 2\puta) i precrtaj 2 u oba izraza.
- Ono što oba broja imaju zajedničko je još jedan faktor 2, pa napišite 2 × 2 (\displaystyle 2\puta 2) i precrtajte drugo 2 u oba izraza.
-
Dodajte preostale faktore operaciji množenja. To su faktori koji nisu precrtani u oba izraza, odnosno faktori koji nisu zajednički za oba broja.
- Na primjer, u izrazu 20 = 2 × 2 × 5 (\displaystyle 20=2\puta 2\puta 5) Obje dvije (2) su precrtane jer su zajednički faktori. Faktor 5 nije precrtan, pa zapišite operaciju množenja ovako: 2 × 2 × 5 (\displaystyle 2\puta 2\puta 5)
- U izrazu 84 = 2 × 7 × 3 × 2 (\displaystyle 84=2\puta 7\puta 3\puta 2) obje dvije (2) su također precrtane. Faktori 7 i 3 nisu precrtani, pa zapišite operaciju množenja ovako: 2 × 2 × 5 × 7 × 3 (\displaystyle 2\puta 2\puta 5\puta 7\puta 3).
-
Izračunajte najmanji zajednički višekratnik. Da biste to učinili, pomnožite brojeve u pismenoj operaciji množenja.
- Na primjer, 2 × 2 × 5 × 7 × 3 = 420 (\displaystyle 2\puta 2\puta 5\puta 7\puta 3=420). Dakle, najmanji zajednički višekratnik 20 i 84 je 420.
Pronalaženje zajedničkih faktora
-
Nacrtajte mrežu kao za igru tic-tac-toe. Takva mreža se sastoji od dvije paralelne linije koje se sijeku (pod pravim uglom) sa još dvije paralelne prave. Ovo će vam dati tri reda i tri kolone (rešetka mnogo liči na ikonu #). Upišite prvi broj u prvi red i drugi stupac. Upišite drugi broj u prvi red i treću kolonu.
- Na primjer, pronađite najmanji zajednički višekratnik brojeva 18 i 30. Upišite broj 18 u prvi red i drugi stupac, a broj 30 upišite u prvi red i treći stupac.
-
Pronađite djelitelj zajednički za oba broja. Zapišite to u prvi red i prvu kolonu. Bolje je tražiti primarne faktore, ali to nije uslov.
- Na primjer, 18 i 30 su parni brojevi, tako da je njihov zajednički faktor 2. Dakle, napišite 2 u prvom redu i prvoj koloni.
-
Podijelite svaki broj sa prvim djeliteljem. Upišite svaki količnik pod odgovarajućim brojem. Kvocijent je rezultat dijeljenja dva broja.
- Na primjer, 18 ÷ 2 = 9 (\displaystyle 18\div 2=9), pa napiši 9 ispod 18.
- 30 ÷ 2 = 15 (\displaystyle 30\div 2=15), pa zapiši 15 ispod 30.
-
Nađite djelitelj zajednički za oba količnika. Ako ne postoji takav djelitelj, preskočite sljedeća dva koraka. U suprotnom, upišite djelitelj u drugi red i prvi stupac.
- Na primjer, 9 i 15 su djeljivi sa 3, pa upišite 3 u drugi red i prvi stupac.
-
Podijelite svaki količnik njegovim drugim djeliteljem. Zapišite svaki rezultat dijeljenja pod odgovarajućim količnikom.
- Na primjer, 9 ÷ 3 = 3 (\displaystyle 9\div 3=3), pa upiši 3 ispod 9.
- 15 ÷ 3 = 5 (\displaystyle 15\div 3=5), pa napiši 5 ispod 15.
-
Ako je potrebno, dodajte dodatne ćelije u mrežu. Ponavljajte opisane korake dok količniki ne budu imali zajednički djelitelj.
-
Zaokružite brojeve u prvom stupcu i posljednjem redu mreže. Zatim napišite odabrane brojeve kao operaciju množenja.
- Na primjer, brojevi 2 i 3 su u prvom stupcu, a brojevi 3 i 5 su u posljednjem redu, pa napišite operaciju množenja ovako: 2 × 3 × 3 × 5 (\displaystyle 2\puta 3\puta 3\puta 5).
-
Pronađite rezultat množenja brojeva. Ovo će izračunati najmanji zajednički višekratnik dva data broja.
- Na primjer, 2 × 3 × 3 × 5 = 90 (\displaystyle 2\puta 3\puta 3\puts 5=90). Dakle, najmanji zajednički višekratnik 18 i 30 je 90.
Euklidov algoritam
-
Zapamtite terminologiju povezanu s operacijom podjele. Dividenda je broj koji se dijeli. Delitelj je broj kojim se dijeli. Kvocijent je rezultat dijeljenja dva broja. Ostatak je broj koji ostaje kada se podijele dva broja.
- Na primjer, u izrazu 15 ÷ 6 = 2 (\displaystyle 15\div 6=2) ost. 3:
15 je dividenda
6 je djelitelj
2 je količnik
3 je ostatak.
- Na primjer, u izrazu 15 ÷ 6 = 2 (\displaystyle 15\div 6=2) ost. 3:
Pogledaj ove brojke. Ovdje opisani metod najbolje je koristiti kada su data dva broja, od kojih je svaki manji od 10. Ako su dati veći brojevi, koristite drugu metodu.
