Euklidovský algoritmus a jeho modifikácie. Euklidov algoritmus
Euklidov algoritmus Je to algoritmus na nájdenie najväčšieho spoločného deliteľa (GCD) dvojice celých čísel.
Najväčší spoločný deliteľ (GCD) Je číslo, ktoré delí dve čísla bez zvyšku a delí sa bezo zvyšku akýmkoľvek iným deliteľom týchto dvoch čísel. Jednoducho povedané, ide o najväčšie číslo, ktorým možno bezo zvyšku rozdeliť dve čísla, pre ktoré sa hľadá GCD.
Algoritmus na nájdenie GCD delením
- Vydeľte väčšie číslo menším.
- Ak sa delí bezo zvyšku, potom menšie číslo je GCD (mali by ste ukončiť cyklus).
- Ak existuje zvyšok, potom väčšie číslo je nahradené zvyškom delenia.
- Prejdeme k bodu 1.
Príklad:
Nájdite GCD pre 30 a 18.
30/18 = 1 (zvyšok 12)
18/12 = 1 (zvyšok 6)
12/6 = 2 (zvyšok 0)
Koniec: GCD je deliteľ čísla 6.
GCD (30, 18) = 6
a = 50 b = 130, zatiaľ čo a! = 0 a b! = 0: ak a> b: a = a% b inak: b = b% a tlač (a + b)
V slučke sa zvyšok delenia zapíše do premennej a alebo b. Cyklus končí, keď sa aspoň jedna z premenných rovná nule. To znamená, že druhý obsahuje GCD. Ktorý však, nevieme. Preto pre GCD nájdeme súčet týchto premenných. Keďže jedna z premenných je nula, nemá to žiadny vplyv na výsledok.
Algoritmus na nájdenie GCD odčítaním
- Odčítajte menšie od väčšieho čísla.
- Ak sa ukáže, že je 0, znamená to, že čísla sa navzájom rovnajú a sú GCD (mali by ste ukončiť cyklus).
- Ak výsledok odčítania nie je 0, potom sa väčšie číslo nahradí výsledkom odčítania.
- Prejdeme k bodu 1.
Príklad:
Nájdite GCD pre 30 a 18.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
Koniec: GCD je odpočítateľné alebo odpočítané.
GCD (30, 18) = 6
a = 50 b = 130, zatiaľ čo a! = b: ak a> b: a = a - b inak: b = b - tlač (a)
1.1 Aplikácia Euklidovho algoritmu
Ako každá dobre vykonaná práca, aj Euklidov algoritmus dáva oveľa viac, ako sa pôvodne očakávalo. Pri pohľade naň je napríklad jasné, že množina deliteľov a a b sa zhoduje s množinou deliteľov (a, b). Uvádza tiež praktický spôsob, ako nájsť čísla u a v zo Z (alebo, ak chcete, z vety bodu 2) tak, že
rn = au + bv = (a, b).
V skutočnosti z reťazca rovnosti máme:
r n = r n -2 - r n -1 q n = r n -2 - (r n -3 - r n -2 q n -1) q n = ...
(ideme pozdĺž reťazca rovnosti zdola nahor, pričom vyjadríme zvyšok z každej ďalšej rovnosti a dosadíme ho do výrazu získaného týmto momentom)
Au + bv = (a, b).
Postup, ktorý opísal Euklides na určenie spoločnej miery dvoch veličín vo vzťahu k číslam (a spoločná miera dvoch prirodzených čísel je, samozrejme, ich najväčším spoločným deliteľom), bol nepochybne vynájdený dávno pred Euklidom. Starí čínski matematici tiež našli GCD rovnakým spôsobom. A iba skutočnosť, že tento postup sa stal známym v renesancii z „Princípov“, mu dal názov „Euklidov algoritmus“
S najväčšou pravdepodobnosťou to vzniklo z obchodnej praxe dávnych obchodníkov, keď museli porovnávať rôzne pomery celých čísel. Ako môžete napríklad porovnať pomery čísel 3703700 a 1234567 a čísel 22962965 a 7654321? Bolo celkom prirodzené pokúsiť sa zistiť, koľkokrát sa menšie číslo zmestí do väčšieho. Je ľahké skontrolovať, či 3703700 = 2 · 1234567 + 1234566 a 22962965 = 3 · 7654321 + 2. Teraz je jasné, že pomer 3703700 k 1234567 je menší ako pomer 2703700 k 1234567, ktorý teraz zapíšeme 26,549. ako
2,99999919 <= 3, 000000261,
Staroveké kalkulačky vysvetlili dlhou frázou.
Ak by sme museli porovnať užšie pomery čísel, napríklad a, výpočty by boli zložitejšie:
71755875 = 61735500 + 10020375;
61735500 = 6 10020375 + 1613250;
10020375 = 6 1613250 + 340875;
1613250 = 4 * 340875 + 249750;
340875 = 249750 + 91125;
249750 = 2 * 91125 + 67500;
91125 = 67500 + 23625;
67500 = 22625 + 20250;
23625 = 20250 + 3375;
20250 = 63375.
Euklidov algoritmus vám tu umožňuje určiť GCD čísel 71755875 a 61735500 rovných 3375 a zodpovedá rozšíreniu pomeru 71755875 k 61735500 v pokračujúcom zlomku:
Euklidov algoritmus sa ukazuje ako ekvivalentný modernému postupu rozširovania čísla na pokračujúci zlomok a navyše umožňuje „zaokrúhliť“ pomer čísel, t.j. nahradiť zlomok s veľkým menovateľom zlomkom, ktorý je mu veľmi blízky, s nižším menovateľom. Naozaj, výraz
rovný zlomku sa v modernej matematike nazýva „vhodný zlomok“ rozšírenia podielu b = na pokračujúci (alebo pokračovací) zlomok.
To je jasné
b = 1 +< 1 + и б=1 + > 1+ = ,
pokiaľ
Vyššie uvedené porovnanie bolo vykonané v III storočí. pred Kr. Aristarchos zo Samosu vo svojom pojednaní O vzdialenosti a veľkosti Mesiaca a Slnka.
Teraz je známe, že vhodné zlomky v pokračujúcej zlomkovej expanzii akéhokoľvek (racionálneho alebo iracionálneho) čísla sú najlepšími racionálnymi aproximáciami tohto čísla.
Algoritmy s polynómami
Euklidov algoritmus je metóda na nájdenie najväčšieho spoločného deliteľa dvoch celých čísel, ako aj dvoch polynómov v jednej premennej ...
Jedným z najstarších matematických algoritmov je Euklidov algoritmus na nájdenie najväčšieho spoločného deliteľa dvoch kladných čísel. Tu je jeho najjednoduchšia forma. Nech sú dané dve celé čísla. Ak sú si rovní...
Analýza euklidovského algoritmu v euklidovských kruhoch
Predtým, ako budete pokračovať v analýze euklidovského algoritmu, zvážte Fibonacciho čísla. Podstatou Fibonacciho postupnosti je, že od 1.1 sa ďalšie číslo získa pridaním predchádzajúcich dvoch. 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ... ...
História vzniku pojmu „algoritmus“. Najznámejšie algoritmy v histórii matematiky
Euklidov algoritmus je všestranná metóda, ktorá počíta najväčšieho spoločného deliteľa dvoch kladných celých čísel. Popis algoritmu na nájdenie GCD delením: 1. Vydeľte väčšie číslo menším 2. Ak sa delí bezo zvyšku ...
Gaussovský celočíselný kruh
Pre kruhy používame obvyklú definíciu najväčšieho spoločného deliteľa. GCD dvoch Gaussových čísel je ich spoločný deliteľ, ktorý je deliteľný akýmkoľvek iným spoločným deliteľom. Rovnako ako u mnohých celých čísel...
Matematické základy systému zvyškových tried
Pozrime sa na príklad. Nech p = 6. Potom máme šesť tried delenia množiny celých čísel modulo 6: r = 0; r = 1; r = 2; r = 3; r = 4; r = 5; kde r predstavuje zvyšok delenia celého čísla 6...
Metódy štúdia polynómov vo voliteľných triedach 2. ročníka strednej školy
Nech sa kruh polynómov skončí. Definícia 1: Nech a ak existuje polynóm, potom zvyšok delenia je nula, potom sa nazýva deliteľ polynómu a označuje sa: () ...
Hlavné etapy formovania a štruktúry modernej matematiky
V treťom storočí pred naším letopočtom sa Euklidova kniha s rovnakým názvom objavila v Alexandrii v ruskom preklade „Začiatky“. Pojem „elementárna geometria“ vznikol z latinského názvu „Začiatky“. Napriek...
Na území určitého mesta N sa nachádzajú továrne a obchody, do ktorých sa dodávajú výrobky z týchto tovární. V dôsledku vývoja boli identifikované možné trasy pre kladenie komunikácií a náklady na ich vytvorenie boli odhadnuté pre každú trasu ...
Aplikácia metód diskrétnej matematiky v ekonómii
Spoločnosť zaoberajúca sa prepravou tovaru podliehajúceho skaze potrebuje dodať tovar zo Suifenhe do Chabarovska a existuje niekoľko trás, po ktorých je možné doručiť tovar. Vzdialenosť medzi Suifenhe a City 2 je 15 km ...
Vývoj konceptu „priestoru“ a neeuklidovskej geometrie
Špeciálne metódy integrácie racionálnych výrazov
Nech je potrebné nájsť GCD polynómov a. Bez straty všeobecnosti budeme predpokladať, že stupeň nie je vyšší ako stupeň. Polynóm predstavujeme v tvare: kde je zvyšok delenia podľa. Potom je stupeň menší ako stupeň deliteľa. Ďalej...
Reziduálna teória
Reziduálna teória
Definícia. Číslo d + Z, súčasne deliace čísla a, b, c, ..., k + Z, sa nazýva spoločný deliteľ týchto čísel. Najväčšie d s touto vlastnosťou sa nazýva najväčší spoločný deliteľ. Zápis: d = (a, b, c, ..., k). Veta. Ak (a, b) = d ...
Reziduálna teória
Nech je potrebné vyriešiť lineárnu diofantínsku rovnicu: ax + by = c, kde a, b, c = Z; a a b nie sú nuly. Skúsme špekulovať pri pohľade na túto rovnicu. Nech (a, b) = d. Potom a = a 1 d; b = b 1 d a rovnica vyzerá takto: a 1 d x + b 1 d y = c, t.j. d (a 1 x + b 1 y) = c ...
Euklidov algoritmus na nájdenie GCD (najväčší spoločný deliteľ)
Sú dané dve nezáporné celé čísla a. Vyžaduje sa nájsť ich najväčšieho spoločného deliteľa, t.j. najväčšie číslo, ktoré je deliteľom oboch a, a. V angličtine sa „najväčší spoločný deliteľ“ píše „najväčší spoločný deliteľ“ a jeho spoločné označenie je:
(symbol "" tu označuje deliteľnosť, t.j. "" znamená "delí")
Keď sa jedno z čísel rovná nule a druhé je nenulové, ich najväčším spoločným deliteľom bude podľa definície toto druhé číslo. Keď sú obe čísla nula, výsledok je nedefinovaný (postačí akékoľvek nekonečne veľké číslo), v tomto prípade nastavíme najväčšieho spoločného deliteľa na nulu. Preto môžeme hovoriť o takomto pravidle: ak sa jedno z čísel rovná nule, potom sa ich najväčší spoločný deliteľ rovná druhému číslu.
Euklidov algoritmus, uvažované nižšie, rieši problém nájdenia najväčšieho spoločného deliteľa dvoch čísel a pre.
Tento algoritmus bol prvýkrát opísaný v Euklidovej knihe „Začiatky“ (asi 300 pred Kristom), hoci je dosť možné, že tento algoritmus má skorší pôvod.
Algoritmus
Samotný algoritmus je veľmi jednoduchý a je opísaný nasledujúcim vzorcom:
Implementácia
int gcd (int a, int b) (ak (b == 0) vráťte a; inak vráťte gcd (b, a% b);)Použitím ternárneho podmieneného operátora C++ je možné algoritmus napísať ešte kratšie:
int gcd (int a, int b) (návrat b? gcd (b, a % b): a;)Nakoniec tu je nerekurzívna forma algoritmu:
int gcd (int a, int b) (zatiaľ čo (b) (a% = b; zameniť (a, b);) vrátiť a;)Dôkaz o správnosti
Po prvé, všimnite si, že s každou iteráciou euklidovského algoritmu sa jeho druhý argument striktne znižuje, a preto, keďže je nezáporný, euklidovský algoritmus vždy končí.
Pre dôkaz o správnosti musíme to ukázať pre všetky>.
Ukážme, že hodnota na ľavej strane rovnosti je deliteľná skutočnou hodnotou vpravo a hodnota vpravo je deliteľná hodnotou vľavo. Je zrejmé, že to bude znamenať, že ľavá a pravá strana sa zhodujú, čo potvrdí správnosť Euklidovho algoritmu.
Označujeme 
... Potom podľa definície a.
Ale potom z toho vyplýva:
Keď si teda zapamätáme výrok, dostaneme systém:
Využime teraz jednoduchý fakt: ak pre nejaké tri čísla platí: a je splnené, potom a: je pravdivé. V našej situácii dostaneme:
Alebo ak namiesto toho nahradíme jeho definíciu, dostaneme:
Polovicu dôkazu sme teda vykonali: ukázali sme, že ľavá strana rozdeľuje pravú. Druhá polovica dôkazu je podobná.
Pracovný čas
Odhaduje sa čas chodu algoritmu Lamého veta, ktorý vytvára úžasné spojenie medzi euklidovským algoritmom a Fibonacciho sekvenciou:
Ak> a pre niektorých, potom Euklidov algoritmus vykoná nanajvýš rekurzívne volania.
Zvážte dve hlavné metódy na nájdenie GCD dvoma hlavnými spôsobmi: pomocou euklidovského algoritmu a zohľadnením hlavných faktorov. Aplikujme obe metódy na dve, tri alebo viac čísel.
Euklidov algoritmus na nájdenie GCD
Euklidov algoritmus uľahčuje výpočet najväčšieho spoločného deliteľa pre dve kladné čísla. Formulácie a dôkaz Euklidovho algoritmu sme uviedli v časti "Najväčší spoločný deliteľ: determinant, príklady".
Podstatou algoritmu je postupne vykonávať delenie so zvyškom, počas ktorého sa získa niekoľko rovností formulára:
a = b q 1 + r 1, 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
Rozdelenie môžeme ukončiť kedy rk + 1 = 0, kde r k = gcd (a, b).
Príklad 1
64 a 48 .
Riešenie
Zavedme zápis: a = 64, b = 48.
Na základe euklidovského algoritmu vykonáme delenie 64 na 48 .
Dostaneme 1 a zvyšok 16. Ukazuje sa, že q 1 = 1, r 1 = 16.
V druhom kroku sa rozdelíme 48 do 16, dostaneme 3. To jest q 2 = 3, a r2 = 0.Číslo 16 je teda najväčším spoločným deliteľom čísel v podmienke.
odpoveď: GCD (64, 48) = 16.
Príklad 2
Čo je GCD čísel 111 a 432 ?
Riešenie
Rozdeliť 432 na 111 ... Podľa Euklidovho algoritmu dostaneme reťazec rovnosti 432 = 111 3 + 99, 111 = 99 1 + 12, 99 = 12 8 + 3, 12 = 3 4.
Teda najväčší spoločný deliteľ čísel 111 a 432 je 3.
odpoveď: GCD (111, 432) = 3.
Príklad 3
Nájdite najväčšieho spoločného menovateľa 661 a 113.
Riešenie
Vykonajme postupné delenie čísel a získajme gcd (661 , 113) = 1 ... To znamená, že 661 a 113 sú prvočísla. Mohli by sme to zistiť pred začatím výpočtu, keby sme sa pozreli na tabuľku prvočísel.
odpoveď: GCD (661, 113) = 1.
Nájdenie gcd rozdelením čísel na prvočísla
Aby sme metódou rozkladu našli najväčšieho spoločného deliteľa dvoch čísel, je potrebné vynásobiť všetky prvočísla, ktoré získame rozkladom týchto dvoch čísel a sú im spoločné.
Príklad 4
Ak zahrnieme čísla 220 a 600 do prvočíselných faktorov, dostaneme dva produkty: 220 = 2 2 5 11 a 600 = 2 2 2 3 5 5... Spoločné faktory v týchto dvoch produktoch budú 2, 2 a 5. To znamená, že GCD (220, 600) = 2 2 5 = 20.
Príklad 5
Nájdite najväčšieho spoločného deliteľa čísel 72 a 96 .
Riešenie
Nájdite všetky prvočísla čísel 72 a 96 :
72 36 18 9 3 1 2 2 2 3 3
96 48 24 12 6 3 1 2 2 2 2 2 3
Prvočísla spoločné pre dve čísla sú 2, 2, 2 a 3. To znamená, že GCD (72, 96) = 2 2 2 3 = 24.
odpoveď: GCD (72, 96) = 24.
Pravidlo na nájdenie najväčšieho spoločného deliteľa dvoch čísel je založené na vlastnostiach najväčšieho spoločného deliteľa, podľa ktorého GCD (ma 1, mb 1) = m GCD (a 1, b 1), kde m je ľubovoľné kladné celé číslo. .
Nájdenie GCD troch alebo viacerých čísel
Bez ohľadu na počet čísel, pre ktoré potrebujeme nájsť GCD, budeme konať podľa rovnakého algoritmu, ktorý spočíva v postupnom hľadaní GCD dvoch čísel. Tento algoritmus je založený na aplikácii nasledujúcej vety: GCD niekoľkých čísel a 1, a 2,…, a k rovná sa číslu d k, ktorý sa nachádza v sekvenčnom výpočte GCD (a 1, a 2) = d2 GCD (d2, a3) = d3, GCD (d3, a4) = d4, ..., GCD (dk - 1, ak) = dk.
Príklad 6
Nájdite najväčší spoločný činiteľ štyroch čísel 78, 294, 570 a 36 .
Riešenie
Zavedme zápis: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.
Začnime nájdením GCD čísel 78 a 294: d2 = Gcd (78 , 294) = 6 .
Teraz začnime hľadať d 3 = gcd (d 2, a 3) = gcd (6, 570). Podľa Euklidovho algoritmu 570 = 6 · 95. Znamená to, že d3 = Gcd (6 , 570) = 6 .
Nájdite d 4 = gcd (d 3, a 4) = gcd (6, 36). 36 je bezo zvyšku deliteľné 6. To nám umožňuje prijímať d4 = Gcd (6 , 36) = 6 .
d4 = 6, teda gcd (78 , 294 , 570 , 36) = 6 .
odpoveď:
Teraz sa pozrime na iný spôsob výpočtu GCD pre tieto a ďalšie čísla. GCD môžeme nájsť vynásobením všetkých bežných prvočísel čísel.
Príklad 7
Vypočítajte gcd čísel 78, 294, 570 a 36 .
Riešenie
Rozložme tieto čísla na prvočísla: 78 = 2 · 3 · 13, 294 = 2 · 3 · 7 · 7, 570 = 2 · 3 · 5 · 19, 36 = 2 · 2 · 3 · 3.
Pre všetky štyri čísla sú spoločné prvočísla 2 a 3.
Ukazuje sa, že GCD (78, 294, 570, 36) = 2 3 = 6.
odpoveď: GCD (78, 294, 570, 36) = 6.
Hľadanie gcd pre záporné čísla
Ak sa musíme vysporiadať so zápornými číslami, potom môžeme použiť absolútne hodnoty týchto čísel na nájdenie najväčšieho spoločného deliteľa. Môžeme to urobiť tak, že poznáme vlastnosť čísel s opačnými znamienkami: čísla n a - n majú rovnakých deliteľov.
Príklad 8
Nájdite gcd záporných celých čísel − 231 a − 140 .
Riešenie
Ak chcete vykonať výpočty, vezmite moduly čísel uvedených v podmienke. Pôjde o čísla 231 a 140. Napíšme to stručne: GCD (− 231 , − 140) = GCD (231, 140). Teraz použijeme Euklidov algoritmus na nájdenie prvočiniteľov dvoch čísel: 231 = 140 · 1 + 91; 140 = 91 * 1 + 49; 91 = 49 * 1 + 42; 49 = 42 1 + 7 a 42 = 7 6... Dostaneme, že gcd (231, 140) = 7 .
A od GCD (− 231 , − 140) = Gcd (231 , 140) , potom čísla gcd − 231 a − 140 rovná sa 7 .
odpoveď: GCD (- 231, - 140) = 7.
Príklad 9
Určte GCD troch čísel - 585, 81 a − 189 .
Riešenie
Záporné čísla vo vyššie uvedenom zozname nahradíme ich absolútnymi hodnotami, dostaneme GCD (− 585 , 81 , − 189) = Gcd (585 , 81 , 189) ... Potom všetky tieto čísla rozložíme na prvočísla: 585 = 3 3 5 13, 81 = 3 3 3 3 a 189 = 3 3 3 7... Tieto tri čísla majú spoločné prvočísla 3 a 3. Ukazuje sa, že GCD (585, 81, 189) = GCD (- 585, 81, - 189) = 9.
odpoveď: GCD (- 585, 81, - 189) = 9.
Ak si všimnete chybu v texte, vyberte ju a stlačte Ctrl + Enter
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ľ pre $ a $ a $ b $.
Množina spoločných deliteľov pre $ 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 najväčší, ktorý sa nazýva najväčší spoločný deliteľ čísel $ a $ a $ b $ a na jeho označenie sa používa zápis:
$ Gcd \ (a; b) \ alebo \ D \ (a; b) $
Ak chcete nájsť najväčšieho spoločného deliteľa dvoch čísel, musíte:
- Nájdite súčin čísel nájdených v kroku 2. Výsledné číslo bude požadovaným najväčším spoločným faktorom.
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 rozklade 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ým najväčším spoločným faktorom.
$ Gcd = 2 \ cdot 11 = 22 $
Príklad 2
Nájdite GCD vo výške 63 USD a 81 USD monomials.
Nájdeme podľa prezentovaného algoritmu. Pre to:
Rozložte čísla na prvočísla
63 $ = 3 \ cdot 3 \ cdot 7 $
81 $ = 3 \ cdot 3 \ cdot 3 \ cdot 3 $
Vyberáme čísla, ktoré sú zahrnuté v rozklade 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 želaným najväčším spoločným faktorom.
$ 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 $: $ \ vľavo \ ((\ rm 1,2,3.4.6,8,12,16,24,48) \ vpravo \) $
Teraz nájdeme množinu deliteľov čísla $ 60 $: $ \ \ vľavo \ ((\ rm 1,2,3,4,5,6,10,12,15,20,30,60) \ vpravo \ ) $
Nájdeme priesečník týchto množín: $ \ vľavo \ ((\ rm 1,2,3,4,6,12) \ vpravo \) $ - táto množina určí množinu spoločných deliteľov čísel $ 48 $ a $ 60 $. Najväčší prvok v danej množine bude číslo $ 12 $. Takže najväčší spoločný deliteľ 48 USD a 60 USD bude 12 USD.
Definícia LCM
Definícia 3
Spoločný násobok prirodzených čísel$ a $ a $ b $ je prirodzené číslo, ktoré je násobkom oboch $ a $ a $ b $.
Spoločné násobky čísel sú čísla, ktoré možno bezo zvyšku deliť originálom. Napríklad pre čísla 25 $ a 50 $ budú spoločné násobky čísla 50 100 150 200 $ atď.
Najmenší spoločný násobok sa bude nazývať najmenší spoločný násobok a označí sa LCM $ (a; b) $ alebo K $ (a; b). $
Ak chcete nájsť LCM dvoch čísel, potrebujete:
- Čísla faktorov
- Vypíšte faktory, ktoré sú súčasťou prvého čísla a pridajte k nim faktory, ktoré sú súčasťou druhého čísla a nevstupujte do prvého
Príklad 4
Nájdite LCM čísel 99 $ a 77 $.
Nájdeme podľa prezentovaného algoritmu. Pre to
Čísla faktorov
99 $ = 3 \ cdot 3 \ cdot 11 $
Napíšte faktory zahrnuté v prvom
pridajte k nim faktory, ktoré sú súčasťou druhého a nevstupujú do prvého
Nájdite súčin čísel nájdených v kroku 2. Výsledné číslo bude požadovaný najmenší spoločný násobok
$ LCM = 3 \ cdot 3 \ cdot 11 \ cdot 7 = 693 $
Zostavovanie zoznamov deliteľov čísel je často časovo veľmi náročné. Existuje spôsob, ako nájsť GCD nazývaný Euklidov algoritmus.
Výroky, na ktorých je založený Euklidov algoritmus:
Ak $ a $ a $ b $ sú prirodzené čísla a $ a \ vdots 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 takú dvojicu čísel, ž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
- Každý spoločný násobok $ a $ a $ b $ je deliteľný K $ (a; b) $
- Ak $ a \ vdots b $, potom K $ (a; b) = a $
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 akékoľvek prirodzené čísla $ a $ a $ b $ je 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) $
