Najväčší spoločný deliteľ

Definícia 2

Ak je prirodzené číslo a deliteľné prirodzeným číslom $b$, potom $b$ sa nazýva deliteľ $a$ a $a$ sa nazýva násobok $b$.

Nech $a$ a $b$ sú prirodzené čísla. Číslo $c$ sa nazýva spoločný deliteľ $a$ a $b$.

Množina spoločných deliteľov čísel $a$ a $b$ je konečná, pretože žiadny z týchto deliteľov nemôže byť väčší ako $a$. To znamená, že medzi týmito deliteľmi je jeden najväčší, ktorý sa nazýva najväčší spoločný deliteľ čísel $a$ a $b$ a označuje sa nasledujúcim zápisom:

$GCD\(a;b)\ alebo \D\(a;b)$

Na nájdenie najväčšieho spoločného deliteľa dvoch čísel potrebujete:

  1. Nájdite súčin čísel nájdených v kroku 2. Výsledné číslo bude požadovaný najväčší spoločný deliteľ.

Príklad 1

Nájdite gcd čísel $ 121 $ a $ 132, $

    $242=2\cdot 11\cdot 11$

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

    Vyberte čísla, ktoré sú zahrnuté v rozšírení týchto čísel

    $242=2\cdot 11\cdot 11$

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

    Nájdite súčin čísel nájdených v kroku 2. Výsledné číslo bude požadovaný najväčší spoločný deliteľ.

    $GCD=2\cdot 11=22$

Príklad 2

Nájdite gcd monomiálií $ 63 $ a $ 81 $.

Nájdeme podľa prezentovaného algoritmu. Pre to:

    Zoberme si čísla do prvočísel

    $63=3\cdot 3\cdot 7$

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

    Vyberáme čísla, ktoré sú zahrnuté do rozšírenia týchto čísel

    $63=3\cdot 3\cdot 7$

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

    Nájdite súčin čísel nájdených v kroku 2. Výsledné číslo bude požadovaný najväčší spoločný deliteľ.

    $GCD=3\cdot 3=9$

Gcd dvoch čísel môžete nájsť iným spôsobom, pomocou množiny deliteľov čísel.

Príklad 3

Nájdite gcd čísel $ 48 $ a $ 60 $.

Riešenie:

Nájdite množinu deliteľov čísla $48$: $\left\((\rm 1,2,3.4.6,8,12,16,24,48)\right\)$

Teraz nájdime množinu deliteľov čísla $60$:$\ \left\((\rm 1,2,3,4,5,6,10,12,15,20,30,60)\right\) $

Nájdeme priesečník týchto množín: $\left\((\rm 1,2,3,4,6,12)\right\)$ - táto množina určí množinu spoločných deliteľov čísel $48$ a $60 $. Najväčší prvok v tejto sade bude číslo $12$. To znamená, že najväčší spoločný deliteľ čísel $48$ a $60$ je $12$.

Definícia NPL

Definícia 3

Spoločné násobky prirodzených čísel$a$ a $b$ je prirodzené číslo, ktoré je násobkom $a$ aj $b$.

Spoločné násobky čísel sú čísla, ktoré sú bezo zvyšku deliteľné pôvodnými číslami. Napríklad pre čísla $25$ a $50$ budú spoločnými násobkami čísla $50,100,150,200 $ atď.

Najmenší spoločný násobok sa bude nazývať najmenší spoločný násobok a bude označený LCM$(a;b)$ alebo K$(a;b).$

Ak chcete nájsť LCM dvoch čísel, musíte:

  1. Rozdeľte čísla na prvočísla
  2. Zapíšte si faktory, ktoré sú súčasťou prvého čísla a pridajte k nim faktory, ktoré sú súčasťou druhého a nie sú súčasťou prvého

Príklad 4

Nájdite LCM čísel 99 $ a 77 $.

Nájdeme podľa prezentovaného algoritmu. Pre to

    Rozdeľte čísla na prvočísla

    $99=3\cdot 3\cdot 11$

    Zapíšte si faktory zahrnuté v prvom

    pridajte k nim multiplikátory, ktoré sú súčasťou druhého a nie sú súčasťou prvého

    Nájdite súčin čísel nájdených v kroku 2. Výsledné číslo bude požadovaný najmenší spoločný násobok

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

    Zostavovanie zoznamov deliteľov čísel je často veľmi pracná úloha. Existuje spôsob, ako nájsť GCD nazývaný Euklidovský algoritmus.

    Tvrdenia, na ktorých je založený euklidovský algoritmus:

    Ak $a$ a $b$ sú prirodzené čísla a $a\vbodky b$, potom $D(a;b)=b$

    Ak $a$ a $b$ sú prirodzené čísla také, že $b

Pomocou $D(a;b)= D(a-b;b)$ môžeme postupne zmenšovať uvažované čísla, až kým nedosiahneme dvojicu čísel tak, že jedno z nich je deliteľné druhým. Potom menšie z týchto čísel bude požadovaným najväčším spoločným deliteľom pre čísla $a$ a $b$.

Vlastnosti GCD a LCM

  1. Každý spoločný násobok $a$ a $b$ je deliteľný K$(a;b)$
  2. Ak $a\vdots b$ , potom К$(a;b)=a$

    3. Ak K$(a;b)=k$ a $m$ je prirodzené číslo, potom K$(am;bm)=km$

    Ak $d$ je spoločný deliteľ pre $a$ a $b$, potom K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d ) $

    Ak $a\vdots c$ a $b\vdots c$ , potom $\frac(ab)(c)$ je spoločný násobok $a$ a $b$

    Pre ľubovoľné prirodzené čísla $a$ a $b$ platí rovnosť

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

    Akýkoľvek spoločný deliteľ čísel $a$ a $b$ je deliteľom čísla $D(a;b)$

Tento článok je venovaný problematike hľadania najväčšieho spoločného deliteľa. Najprv si vysvetlíme, čo to je a uvedieme niekoľko príkladov, predstavíme definície najväčšieho spoločného deliteľa 2, 3 alebo viacerých čísel, potom sa budeme venovať všeobecným vlastnostiam tohto pojmu a dokážeme ich.

Aké sú spoločné deliče

Aby sme pochopili, čo je najväčší spoločný deliteľ, najprv sformulujeme, čo je to spoločný deliteľ pre celé čísla.

V článku o násobkoch a deliteľoch sme si povedali, že celé číslo má vždy niekoľko deliteľov. Tu nás zaujímajú delitele určitého počtu celých čísel naraz, najmä tie spoločné (identické) pre všetky. Napíšme si hlavnú definíciu.

Definícia 1

Spoločný deliteľ niekoľkých celých čísel je číslo, ktoré môže byť deliteľom každého čísla zo zadanej množiny.

Príklad 1

Tu sú príklady takéhoto deliteľa: trojka bude spoločným deliteľom pre čísla - 12 a 9, pretože rovnosti 9 = 3 · 3 a − 12 = 3 · (− 4) sú pravdivé. Čísla 3 a -12 majú ďalšie spoločné faktory, ako napríklad 1, -1 a -3. Uveďme si ďalší príklad. Štyri celé čísla 3, − 11, − 8 a 19 budú mať dva spoločné faktory: 1 a - 1.

Keď poznáme vlastnosti deliteľnosti, môžeme povedať, že každé celé číslo možno deliť jednou a mínus jedna, čo znamená, že každá množina celých čísel už bude mať aspoň dvoch spoločných deliteľov.

Všimnite si tiež, že ak máme spoločného deliteľa b pre niekoľko čísel, potom tie isté čísla možno deliť opačným číslom, teda - b. V zásade môžeme brať iba kladné deliče, potom budú aj všetky spoločné deliče väčšie ako 0. Tento prístup je tiež možné použiť, ale záporné čísla by sa nemali úplne ignorovať.

Aký je najväčší spoločný deliteľ (GCD)

Podľa vlastností deliteľnosti, ak b je deliteľ celého čísla a, ktoré sa nerovná 0, potom modul b nemôže byť väčší ako modul a, preto každé číslo, ktoré sa nerovná 0, má konečný počet deliteľmi. To znamená, že počet spoločných deliteľov viacerých celých čísel, z ktorých aspoň jeden je odlišný od nuly, bude tiež konečný a z celej ich množiny môžeme vždy vybrať najväčšie číslo (už sme hovorili o pojme najväčšieho a najmenšie celé číslo, odporúčame vám tento materiál zopakovať).

V ďalších diskusiách budeme predpokladať, že aspoň jedno z množiny čísel, pre ktoré potrebujeme nájsť najväčšieho spoločného deliteľa, sa bude líšiť od 0. Ak sú všetky rovné 0, potom ich deliteľ môže byť ľubovoľné celé číslo a keďže ich je nekonečne veľa, nemôžeme vybrať najväčšieho. Inými slovami, nie je možné nájsť najväčšieho spoločného deliteľa pre množinu čísel rovných 0.

Prejdime k formulácii hlavnej definície.

Definícia 2

Najväčší spoločný deliteľ niekoľkých čísel je najväčšie celé číslo, ktoré delí všetky tieto čísla.

Písomne ​​sa najväčší spoločný deliteľ najčastejšie označuje skratkou GCD. Pre dve čísla to môže byť napísané ako gcd (a, b).

Príklad 2

Aký je príklad gcd pre dve celé čísla? Napríklad pre 6 a - 15 by to bolo 3. Zdôvodnime to. Najprv si zapíšeme všetkých deliteľov šiestich: ± 6, ± 3, ± 1 a potom všetkých deliteľov pätnástich: ± 15, ± 5, ± 3 a ± 1. Potom vyberieme spoločné: sú to − 3, − 1, 1 a 3. Z nich musíte vybrať najväčší počet. Toto bude 3.

Pre tri alebo viac čísel bude určenie najväčšieho spoločného činiteľa takmer rovnaké.

Definícia 3

Najväčší spoločný deliteľ troch alebo viacerých čísel bude najväčšie celé číslo, ktoré rozdelí všetky tieto čísla súčasne.

Pre čísla a 1, a 2, …, a n je vhodné označiť deliteľa ako GCD (a 1, a 2, …, a n). Samotná hodnota deliteľa sa zapíše ako GCD (a 1, a 2, ..., a n) = b.

Príklad 3

Tu sú príklady najväčšieho spoločného deliteľa niekoľkých celých čísel: 12, - 8, 52, 16. Bude sa rovnať štyrom, čo znamená, že môžeme napísať, že GCD (12, - 8, 52, 16) = 4.

Správnosť tohto tvrdenia môžete skontrolovať tak, že si zapíšete všetkých deliteľov týchto čísel a potom vyberiete najväčšieho z nich.

V praxi sa často vyskytujú prípady, keď sa najväčší spoločný deliteľ rovná jednému z čísel. To sa stane, keď všetky ostatné čísla možno vydeliť daným číslom (v prvom odseku článku sme poskytli dôkaz tohto tvrdenia).

Príklad 4

Najväčší spoločný deliteľ čísel 60, 15 a - 45 je teda 15, keďže pätnásť je deliteľné nielen 60 a - 45, ale aj samo sebou a pre všetky tieto čísla neexistuje väčší deliteľ.

Špeciálny prípad tvoria prvočísla. Sú to celé čísla s najväčším spoločným deliteľom 1.

Základné vlastnosti GCD a Euklidovho algoritmu

Najväčší spoločný deliteľ má niektoré charakteristické vlastnosti. Sformulujme ich vo forme viet a dokážme každú z nich.

Všimnite si, že tieto vlastnosti sú formulované pre celé čísla väčšie ako nula a budeme brať do úvahy iba kladné deliče.

Definícia 4

Čísla a a b majú najväčšieho spoločného deliteľa rovného gcd pre b a a, teda gcd (a, b) = gcd (b, a). Obrátenie čísel nemá vplyv na konečný výsledok.

Táto vlastnosť vyplýva zo samotnej definície GCD a nepotrebuje dôkaz.

Definícia 5

Ak je možné číslo a deliť číslom b, potom množina spoločných deliteľov týchto dvoch čísel bude podobná množine deliteľov čísla b, teda gcd (a, b) = b.

Dokážme toto tvrdenie.

Dôkaz 1

Ak čísla a a b majú spoločných deliteľov, potom nimi možno deliť ktorékoľvek z nich. Zároveň, ak a je násobkom b, potom každý deliteľ b bude tiež deliteľom a, pretože deliteľnosť má takú vlastnosť ako tranzitivita. To znamená, že ľubovoľný deliteľ b bude spoločný s číslami a a b. To dokazuje, že ak dokážeme deliť a b, potom sa množina všetkých deliteľov oboch čísel bude zhodovať s množinou deliteľov jedného čísla b. A keďže najväčším deliteľom akéhokoľvek čísla je toto číslo samotné, potom sa najväčší spoločný deliteľ čísel a a b bude rovnať aj b, t.j. GCD (a, b) = b . Ak a = b, potom gcd (a, b) = gcd (a, a) = gcd (b, b) = a = b, napríklad gcd (132, 132) = 132.

Pomocou tejto vlastnosti môžeme nájsť najväčšieho spoločného deliteľa dvoch čísel, ak jedno z nich možno deliť druhým. Tento deliteľ sa rovná jednému z týchto dvoch čísel, ktorým možno deliť druhé číslo. Napríklad gcd (8, 24) = 8, pretože 24 je násobkom ôsmich.

Definícia 6 Dôkaz 2

Skúsme túto vlastnosť dokázať. Na začiatku máme rovnosť a = b q + c a každý spoločný deliteľ a a b bude deliť aj c, čo je vysvetlené zodpovedajúcou vlastnosťou deliteľnosti. Preto každý spoločný deliteľ b a c bude deliť a. To znamená, že množina spoločných deliteľov a a b sa bude zhodovať s množinou deliteľov b a c, vrátane najväčšieho z nich, čo znamená, že platí rovnosť gcd (a, b) = gcd (b, c).

Definícia 7

Nasledujúca vlastnosť sa nazýva euklidovský algoritmus. S jeho pomocou môžete vypočítať najväčšieho spoločného deliteľa dvoch čísel, ako aj dokázať ďalšie vlastnosti GCD.

Pred formulovaním vlastnosti vám odporúčame zopakovať vetu, ktorú sme dokázali v článku o delení zvyškom. Podľa nej možno deliteľné číslo a znázorniť ako b · q + r, pričom b je tu deliteľ, q je nejaké celé číslo (nazývané aj neúplný kvocient) a r je zvyšok, ktorý spĺňa podmienku 0 ≤ r ≤ b.

Povedzme, že máme dve celé čísla väčšie ako 0, pre ktoré budú platiť nasledujúce rovnosti:

a = bqi + r1, 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

Tieto rovnosti končia, keď sa r k + 1 rovná 0. To sa určite stane, pretože postupnosť b > r 1 > r 2 > r 3, ... je rad klesajúcich celých čísel, ktoré môžu obsahovať len konečný počet. To znamená, že rk je najväčší spoločný deliteľ aab, teda rk = gcd (a, b).

Najprv musíme dokázať, že r k je spoločný deliteľ čísel a a b, a potom, že r k nie je len deliteľ, ale skôr najväčší spoločný deliteľ dvoch daných čísel.

Pozrime sa na zoznam rovnosti vyššie, zdola nahor. Podľa poslednej rovnosti,
r k − 1 možno deliť rk . Na základe tejto skutočnosti, ako aj predchádzajúcej preukázanej vlastnosti najväčšieho spoločného deliteľa, možno tvrdiť, že r k − 2 možno deliť r k , keďže
r k − 1 je delené rk a rk je delené rk .

Tretia rovnosť zdola nám umožňuje dospieť k záveru, že r k − 3 možno deliť rk atď. Druhé zdola je, že b je deliteľné rk a prvé je, že a je deliteľné rk. Z toho všetkého usudzujeme, že r k je spoločným deliteľom a a b.

Teraz dokážme, že r k = GCD (a, b) . Čo mám urobiť? Ukážte, že každý spoločný deliteľ aab bude deliť r k. Označme to r 0 .

Pozrime sa na rovnaký zoznam rovnosti, ale zhora nadol. Na základe predchádzajúcej vlastnosti môžeme konštatovať, že r 1 je deliteľné r 0, čo znamená, že podľa druhej rovnosti je r 2 delené r 0. Ideme dole po všetkých rovnosti a z poslednej usúdime, že r k je deliteľné r 0 . Preto rk = gcd (a, b) .

Po zvážení tejto vlastnosti sme dospeli k záveru, že množina spoločných deliteľov aab je podobná množine GCD deliteľov týchto čísel. Toto tvrdenie, ktoré je dôsledkom Euklidovho algoritmu, nám umožní vypočítať všetkých spoločných deliteľov dvoch daných čísel.

Prejdime k ďalším vlastnostiam.

Definícia 8

Ak a a b sú celé čísla, ktoré sa nerovnajú 0, potom musia existovať ďalšie dve celé čísla u 0 a v 0, pre ktoré bude platiť rovnosť GCD (a, b) = a · u 0 + b · v 0.

Rovnosť uvedená vo výkaze vlastností je lineárnym vyjadrením najväčšieho spoločného deliteľa a a b. Nazýva sa to Bezoutov vzťah a čísla u 0 a v 0 sa nazývajú Bezoutove koeficienty.

Dôkaz 3

Dokážme túto vlastnosť. Zapíšme si postupnosť rovníc pomocou euklidovského algoritmu:

a = bqi + r1, 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1

Prvá rovnosť nám hovorí, že r 1 = a − b · q 1 . Označme 1 = s 1 a − q 1 = t 1 a túto rovnosť prepíšme v tvare r 1 = s 1 · a + t 1 · b. Tu budú čísla s 1 a t 1 celé čísla. Druhá rovnosť nám umožňuje dospieť k záveru, že r 2 = b − r 1 · q 2 = b − (s 1 · a + t 1 · b) · q 2 = − s 1 · q 2 · a + (1 − t 1 · q 2) b . Označme − s 1 · q 2 = s 2 a 1 − t 1 · q 2 = t 2 a prepíšme rovnosť ako r 2 = s 2 · a + t 2 · b, kde s 2 a t 2 budú tiež celé čísla. Je to preto, že súčet celých čísel, ich súčin a rozdiel sú tiež celé čísla. Presne rovnakým spôsobom získame z tretej rovnosti r 3 = s 3 · a + t 3 · b, z ďalšej r 4 = s 4 · a + t 4 · b atď. Nakoniec sme dospeli k záveru, že r k = s k · a + t k · b pre celé číslo s k a tk . Keďže r k = GCD (a, b), značíme s k = u 0 a t k = v 0. V dôsledku toho môžeme získať lineárne zobrazenie GCD v požadovanom tvare: GCD (a, b) = a · u 0 + b · v 0.

Definícia 9

GCD (m a, m b) = m GCD (a, b) pre akúkoľvek prirodzenú hodnotu m.

Dôkaz 4

Túto vlastnosť možno zdôvodniť nasledovne. Vynásobme obe strany každej rovnosti v euklidovskom algoritme číslom m a dostaneme, že GCD (m · a, m · b) = m · rk a rk je GCD (a, b). To znamená gcd (ma, mb) = m gcd (a, b). Práve táto vlastnosť najväčšieho spoločného deliteľa sa využíva pri hľadaní GCD metódou faktorizácie.

Definícia 10

Ak čísla a a b majú spoločného deliteľa p, potom gcd (a: p, b: p) = gcd (a, b): p. V prípade, že p = GCD (a, b) dostaneme GCD (a: GCD (a, b), b: GCD (a, b) = 1, teda čísla a: GCD (a, b) a b : GCD (a, b) sú relatívne prvočísla.

Keďže a = p (a: p) a b = p (b: p), potom na základe predchádzajúcej vlastnosti môžeme vytvoriť rovnosti v tvare gcd (a, b) = gcd (p (a: p), p · (b: p)) = p · GCD (a: p , b: p) , medzi ktorými bude dôkaz tejto vlastnosti. Toto tvrdenie používame, keď obyčajné zlomky redukujeme na neredukovateľnú formu.

Definícia 11

Najväčším spoločným deliteľom a 1, a 2, …, a k bude číslo d k, ktoré možno nájsť postupným výpočtom GCD (a 1, a 2) = d 2, GCD (d 2, a 3) = d 3 GCD (d3, a4) = d4, ..., GCD (dk-1, ak) = dk.

Táto vlastnosť je užitočná pri hľadaní najväčšieho spoločného deliteľa troch alebo viacerých čísel. Pomocou neho môžete túto akciu zredukovať na operácie s dvomi číslami. Jeho základom je dôsledok euklidovského algoritmu: ak sa množina spoločných deliteľov a 1, a 2 a a 3 zhoduje s množinou d 2 a a 3, bude sa zhodovať aj s deliteľmi d 3. Deliče čísel a 1, a 2, a 3 a a 4 sa budú zhodovať s deliteľmi d 3, čo znamená, že sa budú zhodovať aj s deliteľmi d 4 atď. Nakoniec dostaneme, že spoloční delitelia čísel a 1, a 2, ..., a k sa budú zhodovať s deliteľmi d k, a keďže najväčším deliteľom čísla d k bude toto samotné číslo, potom GCD (a 1, a 2, ..., a k) = d k.

To je všetko, čo by sme vám chceli povedať o vlastnostiach najväčšieho spoločného deliteľa.

Ak si všimnete chybu v texte, zvýraznite ju a stlačte Ctrl+Enter

Poďme vyriešiť problém. Máme dva typy cookies. Niektoré sú čokoládové a iné obyčajné. Čokoládových je 48, obyčajných 36. Z týchto koláčikov musíte vyrobiť maximálny možný počet darčekov a musíte ich všetky použiť.

Najprv si zapíšme všetkých deliteľov každého z týchto dvoch čísel, keďže obe tieto čísla musia byť deliteľné počtom darov.

Dostaneme

  • 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48.
  • 36: 1, 2, 3, 4, 6, 9, 12, 18, 36.

Nájdite medzi spoločnými deliteľmi, ktoré majú prvé aj druhé číslo.

Bežné faktory budú: 1, 2, 3, 4, 6, 12.

Najväčším spoločným činiteľom zo všetkých je číslo 12. Toto číslo sa nazýva najväčší spoločný činiteľ čísel 36 a 48.

Na základe získaných výsledkov môžeme konštatovať, že zo všetkých cookies je možné vyrobiť 12 darčekov. Jeden takýto darček bude obsahovať 4 čokoládové sušienky a 3 bežné sušienky.

Nájdenie najväčšieho spoločného deliteľa

  • Najväčšie prirodzené číslo, ktoré delí dve čísla a a b bez zvyšku, sa nazýva najväčší spoločný deliteľ týchto čísel.

Niekedy sa na skrátenie zápisu používa skratka GCD.

Niektoré dvojice čísel majú jedničku ako najväčšieho spoločného deliteľa. Takéto čísla sa nazývajú vzájomne prvočísla. Napríklad čísla 24 a 35 majú GCD = 1.

Ako nájsť najväčšieho spoločného deliteľa

Na nájdenie najväčšieho spoločného deliteľa nie je potrebné zapisovať všetkých deliteľov daných čísel.

Môžete to urobiť inak. Najprv započítajte obe čísla do prvočísel.

  • 48 = 2*2*2*2*3,
  • 36 = 2*2*3*3.

Teraz z faktorov, ktoré sú zahrnuté v rozšírení prvého čísla, vyškrtneme všetky, ktoré nie sú zahrnuté v rozšírení druhého čísla. V našom prípade ide o dve dvojky.

  • 48 = 2*2*2*2*3 ,
  • 36 = 2*2*3 *3.

Zostávajúce faktory sú 2, 2 a 3. Ich súčin je 12. Toto číslo bude najväčším spoločným deliteľom čísel 48 a 36.

Toto pravidlo možno rozšíriť na prípad troch, štyroch atď. čísla.

Všeobecná schéma na nájdenie najväčšieho spoločného deliteľa

  • 1. Rozdeľte čísla na prvočiniteľa.
  • 2. Z faktorov zahrnutých do rozšírenia jedného z týchto čísel prečiarknite tie, ktoré nie sú zahrnuté v rozšírení iných čísel.
  • 3. Vypočítajte súčin zostávajúcich faktorov.

Kapitola 1. Prirodzené čísla

1.6. Najväčší spoločný deliteľ a najmenší spoločný násobok

Predtým sme pomenovali deliteľov čísel. Teraz sa pokúsme rozdeliť zložené čísla na prvočísla.

Definícia

Rozložiť číslo do prvočísel znamená reprezentovať ho ako rovnaký súčin prvočísel.

Rozklad čísel na prvočísla bude vyzerať takto:
; .
Rozklad čísel , , na prvočísla možno znázorniť v inej forme:


198 2
2574 2
255 3
3 1287 3
5
3
3 17
11
11



13










Teraz to napíšem na riadok
.

Veľmi dobre! Si proste génius.

Stále nechápem, ako si tak rýchlo uhádol, že číslo je deliteľné ?

A je to jednoduché. Použil som test deliteľnosti podľa . Venujme pozornosť skutočnosti, že v dielach, ktoré ste práve nahrali, sa číslo opakuje.

Definícia

Číslo, ktorým je každé z týchto čísel delené, sa nazýva spoločný deliteľ týchto čísel.

Tie. v našom prípade je číslo spoločný deliteľ?

Áno, to som chcel povedať. A ak vezmete čísla a , potom, ako vidíte, majú troch spoločných deliteľov: , a (nepočítajúc ).

nerozumiem?...

Definícia

Najväčší spoločný deliteľ týchto čísel sa nazýva ich najväčší spoločný deliteľ a označuje sa skratkou GCD.

Musíte si uvedomiť, že GCD hrá veľkú úlohu v matematike.

Už vidím, že v matematike hrajú veľkú rolu všetky pojmy. A ako si ich všetky zapamätať? Ako nájsť toto GCD?

Nebojte sa, ak ich budete pravidelne používať, časom sa stanú zapamätateľnými.
Pokračujme teda. Nájsť GCD niekoľko čísel, môžete ich rozdeliť na prvočísla, zapísať ich spoločné prvočísla a vynásobiť.

Toto je dobré. Existujú však čísla, ktoré nemajú žiadneho spoločného deliteľa okrem jedného! Napríklad a , a .

Áno, máte pravdu.

Definícia

Čísla, ktoré nemajú spoločných deliteľov (okrem jedného), sa nazývajú relatívne prvočísla.

Čo to teda znamená: všetky prvočísla budú aj relatívne prvočísla?

A v tomto prípade máte pravdu! Stále však musíme považovať takýto koncept za najmenší spoločný násobok LCM.

Definícia

Číslo, ktoré je deliteľné každým z týchto čísel, sa nazýva spoločný násobok týchto čísel.

Takže pre čísla a spoločný násobok bude každé z čísel: , , , , LCM.

Výborne. Aký bude podľa vás LCM coprime čísel?

Teraz na to prídem. Nemajú žiadnych spoločných deliteľov okrem jednoty, a preto ich produktom je ich LCM!

Toto je jednoducho úžasné! Aký skvelý záver.
A na konci nášho výskumu vám chcem povedať, ako nájsť LOC, ak to nie je zrejmé.

V tomto prípade sa tieto čísla rozložia na hlavné faktory. Potom sa od najväčšieho čísla vypíšu všetky faktory a k nim sa pripočítajú chýbajúce faktory z rozšírení zostávajúcich čísel.

Áno, som spokojný, páčilo sa mi to.


Tento článok je o nájdenie najväčšieho spoločného deliteľa (GCD) dve alebo viac čísel. Najprv sa pozrime na Euclidov algoritmus, ktorý vám umožňuje nájsť gcd dvoch čísel. Potom sa zameriame na metódu, ktorá nám umožňuje vypočítať gcd čísel ako súčin ich spoločných prvočísel. Ďalej sa pozrieme na nájdenie najväčšieho spoločného deliteľa troch alebo viacerých čísel a tiež uvedieme príklady výpočtu gcd záporných čísel.

Navigácia na stránke.

Euklidovský algoritmus na nájdenie GCD

Všimnite si, že keby sme sa hneď od začiatku obrátili na tabuľku prvočísel, zistili by sme, že čísla 661 a 113 sú prvočísla, z ktorých by sme hneď mohli povedať, že ich najväčší spoločný deliteľ je 1.

odpoveď:

GCD(661,113)=1.

Nájdenie GCD rozdelením čísel na prvočísla

Zvážme iný spôsob, ako nájsť GCD. Najväčší spoločný deliteľ možno nájsť rozdelením čísel na prvočiniteľa. Sformulujme pravidlo: Gcd dvoch kladných celých čísel aab sa rovná súčinu všetkých spoločných prvočíselných faktorov, ktoré sa nachádzajú v rozklade čísel a a b..

Uveďme príklad na vysvetlenie pravidla pre nájdenie GCD. Poznáme rozklady čísel 220 a 600 na prvočiniteľa, majú tvar 220=2·2·5·11 a 600=2·2·2·3·5·5. Bežné prvočísla zapojené do faktorizácie čísel 220 a 600 sú 2, 2 a 5. Preto GCD(220, 600)=2·2·5=20.

Ak teda rozdelíme čísla a a b do prvočiniteľov a nájdeme súčin všetkých ich spoločných faktorov, nájdeme najväčšieho spoločného deliteľa čísel a a b.

Zoberme si príklad nájdenia GCD podľa uvedeného pravidla.

Príklad.

Nájdite najväčšieho spoločného deliteľa čísel 72 a 96.

Riešenie.

Rozložme čísla 72 a 96 do prvočísel:

To znamená, že 72 = 2 · 2 · 2 · 3 · 3 a 96 = 2 · 2 · 2 · 2 · 2 · 3. Bežné hlavné faktory sú 2, 2, 2 a 3. GCD(72, 96)=2·2·2·3=24.

odpoveď:

GCD(72,96)=24.

Na záver tohto odseku poznamenávame, že platnosť vyššie uvedeného pravidla pre zistenie GCD vyplýva z vlastnosti najväčšieho spoločného deliteľa, ktorá hovorí, že GCD(m a1, mb1)=m GCD(a1, b1), kde m je ľubovoľné kladné celé číslo.

Nájdenie gcd troch alebo viacerých čísel

Hľadanie najväčšieho spoločného deliteľa troch alebo viacerých čísel možno zredukovať na postupné hľadanie gcd dvoch čísel. Spomenuli sme to pri štúdiu vlastností GCD. Tam sme sformulovali a dokázali vetu: najväčší spoločný deliteľ viacerých čísel a 1, a 2, ..., a k sa rovná číslu d k, ktoré sa zistí postupným výpočtom GCD(a 1, a 2)=d 2 GCD(d2,a3)=d3, GCD(d3,a4)=d4,..., GCD(dk-l, ak)=dk.

Pozrime sa, ako vyzerá proces hľadania gcd niekoľkých čísel, keď sa pozrieme na riešenie príkladu.

Príklad.

Nájdite najväčší spoločný činiteľ štyroch čísel 78, 294, 570 a 36.

Riešenie.

V tomto príklade a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

Najprv pomocou euklidovského algoritmu určíme najväčšieho spoločného deliteľa d2 prvých dvoch čísel 78 a 294. Pri delení dostaneme rovnosti 294 = 78 3 + 60 ; 78=60-1+18; 60=18,3+6 a 18=6,3. Teda d2=GCD(78,294)=6.

Teraz poďme počítať d3=GCD(d2, a3)=GCD(6, 570). Aplikujme znova Euklidovský algoritmus: 570=6·95, teda d 3 = GCD(6, 570)=6.

Zostáva vypočítať d4=GCD(d3, a4)=GCD(6; 36). Keďže 36 je deliteľné 6, potom d4 = GCD(6, 36) = 6.

Najväčší spoločný deliteľ štyroch daných čísel je teda d 4 =6, teda gcd(78, 294, 570, 36) = 6.

odpoveď:

GCD(78,294,570,36)=6.

Rozdelenie čísel na prvočísla vám tiež umožňuje vypočítať gcd troch alebo viacerých čísel. V tomto prípade najväčší spoločný deliteľ nájdeme ako súčin všetkých spoločných prvočísel daných čísel.

Príklad.

Vypočítajte gcd čísel z predchádzajúceho príkladu pomocou ich prvočíselných rozkladov.

Riešenie.

Rozložme čísla 78, 294, 570 a 36 na prvočísla, dostaneme 78=2·3·13, 294=2·3·7·7, 570=2·3·5·19, 36=2·2 ·3· 3. Spoločné prvočísla všetkých týchto štyroch čísel sú čísla 2 a 3. teda GCD(78, 294, 570, 36) = 2,3 = 6.