Euklido algoritmas ir jo modifikacijos. Euklido algoritmas

Euklido algoritmas Algoritmas, skirtas rasti didžiausią sveikųjų skaičių poros bendrą daliklį (GCD).

Didžiausias bendras daliklis (GCD) Yra skaičius, kuris padalija du skaičius be liekanos ir be likučio dalijasi iš bet kurio kito šių dviejų skaičių daliklio. Paprasčiau tariant, tai yra didžiausias skaičius, iš kurio du skaičiai, kuriems reikia GCD, gali būti padalyti be liekanos.

Algoritmas ieškant GCD pagal padalijimą

1. Didesnį skaičių padalinkite iš mažesnio.
2. Jei jis padalintas be liekanos, mažesnis skaičius yra GCD (turėtumėte išeiti iš ciklo).
3. Jei yra likutis, didesnis skaičius pakeičiamas likusia padalijimo dalimi.
4. Mes pereiname prie 1 punkto.

Pavyzdys:
Raskite GCD 30 ir 18.
30/18 = 1 (likę 12)
18/12 = 1 (likęs 6)
12/6 = 2 (likęs 0)
Pabaiga: GCD yra 6 daliklis.
GCD (30, 18) = 6

a = 50 b = 130, o a! = 0 ir b! = 0: jei a> b: a = a% b kitur: b = b% a spausdinti (a + b)

Cikle likusi dalybos dalis įrašoma į kintamąjį a arba b. Ciklas baigiasi, kai bent vienas iš kintamųjų yra lygus nuliui. Tai reiškia, kad kitame yra GCD. Tačiau kuris iš jų, mes nežinome. Todėl GCD randame šių kintamųjų sumą. Kadangi vienas iš kintamųjų yra nulis, jis neturi įtakos rezultatui.

Algoritmas ieškant GCD atimant

1. Iš didesnio skaičiaus atimkite mažesnį.
2. Jei paaiškėja, kad jis yra 0, tai reiškia, kad skaičiai yra lygūs vienas kitam ir yra GCD (turėtumėte išeiti iš ciklo).
3. Jei atimties rezultatas nėra 0, tada didesnis skaičius pakeičiamas atimties rezultatu.
4. Mes pereiname prie 1 punkto.

Pavyzdys:
Raskite GCD 30 ir 18.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
Pabaiga: GCD yra išskaitomas arba atimamas.
GCD (30, 18) = 6

a = 50 b = 130, o a! = b: jei a> b: a = a - b kitur: b = b - spausdinimas (a)

1.1 Euklido algoritmo taikymas

Kaip ir bet kuris geras atliktas darbas, Euklido algoritmas suteikia daug daugiau, nei iš pradžių tikėtasi. Pažiūrėjus aišku, pavyzdžiui, kad daliklių a ir b aibė sutampa su daliklių aibe (a, b). Jis taip pat pateikia praktinį būdą, kaip rasti skaičius u ir v iš Z (arba, jei norite, iš 2 punkto teoremos) taip, kad

r n = au + bv = (a, b).

Iš tiesų, iš lygybių grandinės turime:

r n = r n -2 - r n -1 q n = r n -2 - (r n -3 - r n -2 q n -1) q n = ...

(einame lygybių grandine iš apačios į viršų, išreikšdami kiekvienos kitos lygybės likutį ir pakeisdami jį šiuo momentu gauta išraiška)

Au + bv = (a, b).

Be jokios abejonės, Euklido aprašyta procedūra dviejų dydžių bendram matui nustatyti skaičių atžvilgiu (o bendras dviejų natūraliųjų skaičių matas, be abejo, yra didžiausias jų bendras daliklis), buvo išrasta dar gerokai prieš Euklidą. Senovės kinų matematikai taip pat rado GCD. Ir tik tai, kad ši procedūra Renesanso laikais tapo žinoma iš „Principų“, suteikė jai pavadinimą „Euklido algoritmas“.

Greičiausiai tai kilo iš senovės pirklių komercinės praktikos, kai reikėjo lyginti skirtingus sveikųjų skaičių santykius. Kaip, pavyzdžiui, galite palyginti skaičių 3703700 ir 1234567 bei skaičių 22962965 ir 7654321 santykius? Gana natūralu buvo bandyti išsiaiškinti, kiek kartų mažesnis skaičius telpa į didesnį. Nesunku patikrinti, ar 3703700 = 2 · 1234567 + 1234566 ir 22962965 = 3 · 7654321 + 2. Taigi dabar aišku, kad santykis 3703700 ir 1234567 yra mažesnis už santykį 62 ir 4, dabar rašome 2 3 676. kaip

2,99999919 <= 3, 000000261,

Senovės skaičiuotuvai paaiškino ilga fraze.

Jei reikėtų palyginti, pavyzdžiui, artimesnius skaičių santykius ir, tada skaičiavimai būtų sudėtingesni:

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.

Euklido algoritmas čia leidžia nustatyti skaičių 71755875 ir 61735500 GCD, lygų 3375 ir atitinka santykio 71755875 ir 61735500 išplėtimą tęstinėje trupmenoje:

Euklido algoritmas pasirodo esąs lygiavertis šiuolaikinei skaičiaus išplėtimo į tęstinę trupmeną procedūrai, be to, leidžia „suapvalinti“ skaičių santykį, t.y. trupmeną su dideliu vardikliu pakeisti labai artima trupmena mažesniu vardikliu. Tikrai, išraiška

lygi trupmenai, šiuolaikinėje matematikoje vadinama „tinkama trupmena“ santykio b = išplėtimo į tęstinę (arba tęstinę) trupmeną.

Tai aišku

b = 1 +< 1 + и б=1 + > 1+ = ,

kiek

Minėtas palyginimas buvo atliktas III a. pr. Kr. Aristarchas iš Samoso savo traktate „Apie Mėnulio ir Saulės atstumą ir dydžius“.

Dabar žinoma, kad tinkamos trupmenos tęsiant bet kurio (racionalaus ar neracionalaus) skaičiaus trupmenų plėtimą yra geriausi racionalūs šio skaičiaus aproksimacijos.

Algoritmai su daugianariais

Euklido algoritmas yra metodas, leidžiantis rasti didžiausią bendrą dviejų sveikųjų skaičių daliklį, taip pat du daugianorius viename kintamajame ...

Vienas iš seniausių matematinių algoritmų yra Euklido algoritmas, skirtas dviejų teigiamų skaičių didžiausio bendro daliklio paieškai. Čia yra paprasčiausia jo forma. Tegu pateikti du sveikieji skaičiai. Jei jie lygūs...

Euklido algoritmo Euklido žieduose analizė

Prieš pradėdami analizuoti Euklido algoritmą, apsvarstykite Fibonačio skaičius. Fibonačio sekos esmė ta, kad pradedant nuo 1.1 sekantis skaičius gaunamas sudėjus du ankstesnius. 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ... ...

Sąvokos „algoritmas“ formavimosi istorija. Žymiausi algoritmai matematikos istorijoje

Euklido algoritmas yra universalus metodas, apskaičiuojantis didžiausią bendrą dviejų teigiamų sveikųjų skaičių daliklį. GCD radimo dalijant algoritmo aprašymas: 1. Didesnį skaičių padalinkite iš mažesnio 2. Jei jis padalintas be liekanos ...

Gauso sveikojo skaičiaus žiedas

Mes naudojame įprastą didžiausio bendro žiedų daliklio apibrėžimą. Dviejų Gauso skaičių GCD yra jų bendras daliklis, kuris dalijasi iš bet kurio kito bendro daliklio. Kaip ir su daugeliu sveikųjų skaičių...

Likutinės klasių sistemos matematiniai pagrindai

Pažiūrėkime į pavyzdį. Tegu p = 6. Tada turime šešias sveikųjų skaičių aibės skaidinio modulo 6 klases: r = 0; r = 1; r = 2; r = 3; r = 4; r = 5; kur r reiškia sveikojo skaičiaus dalijimo iš 6 likutį...

Daugiavardžių mokymosi metodai pasirenkamosiose klasėse vidurinės mokyklos vyresnėje klasėje

Tegul daugianario žiedas baigiasi. 1 apibrėžimas: Tegu ir, jei yra daugianario, tada dalybos liekana lygi nuliui, tada ji vadinama daugianario dalikliu ir žymima: () ...

Pagrindiniai šiuolaikinės matematikos formavimosi ir sandaros etapai

III amžiuje prieš Kristų Aleksandrijoje pasirodė to paties pavadinimo Euklido knyga „Pradžia“ į rusų kalbą. Terminas „elementarioji geometrija“ kilo iš lotyniško pavadinimo „Pradžia“. Nepaisant...

Tam tikro miesto N teritorijoje yra gamyklos ir parduotuvės, į kurias tiekiama šių gamyklų produkcija. Plėtros metu buvo nustatyti galimi komunikacijų tiesimo maršrutai ir apskaičiuota jų sukūrimo kaina kiekvienam maršrutui ...

Diskrečiosios matematikos metodų taikymas ekonomikoje

Greitai gendančių prekių gabenimu užsiimanti įmonė turi pristatyti prekes iš Suifenhe į Chabarovską, yra keli maršrutai, kuriais galima pristatyti. Atstumas tarp Suifenhe ir City 2 yra 15 km ...

„Erdvės“ ir neeuklido geometrijos sampratos kūrimas

Specialūs racionalių išraiškų integravimo metodai

Tegul reikia rasti daugianario GCD ir. Neprarasdami bendrumo, manysime, kad laipsnis nėra aukštesnis už laipsnį. Dauginamą pavaizduojame formoje: kur yra dalybos iš liekana. Tada laipsnis yra mažesnis už daliklio laipsnį. Toliau...

Likučių teorija

Likučių teorija

Apibrėžimas. Skaičius d ? Z, vienu metu dalijantis skaičius a, b, c, ..., k ? Z, vadinamas bendruoju šių skaičių dalikliu. Didžiausias d, turintis šią savybę, vadinamas didžiausiu bendruoju dalikliu. Žymėjimas: d = (a, b, c, ..., k). Teorema. Jei (a, b) = d ...

Likučių teorija

Tegul reikia išspręsti tiesinę Diofanto lygtį: ax + by = c, kur a, b, c ??Z; a ir b nėra nuliai. Pabandykime spėlioti žiūrėdami į šią lygtį. Tegul (a, b) = d. Tada a = a 1 d; b = b 1 d ir lygtis atrodo taip: a 1 d x + b 1 d y = c, t.y. d (a 1 x + b 1 y) = c ...

Euklido algoritmas ieškant GCD (didžiausio bendro daliklio)

Duoti du neneigiami sveikieji skaičiai ir. Reikia surasti jų didžiausią bendrą daliklį, t.y. didžiausias skaičius, kuris yra abiejų ir, ir daliklis. Anglų kalboje "greatest common divisor" yra parašyta "greatest common divisor", o jo bendras pavadinimas yra:

(čia simbolis "" reiškia dalijimąsi, t. y. "" reiškia "dalijasi")

Kai vienas iš skaičių lygus nuliui, o kitas yra ne nulis, didžiausias jų bendras daliklis pagal apibrėžimą bus šis antrasis skaičius. Kai abu skaičiai yra nuliai, rezultatas neapibrėžtas (tiks bet koks be galo didelis skaičius), didžiausią bendrą daliklį šiuo atveju nustatome į nulį. Todėl galime kalbėti apie tokią taisyklę: jei vienas iš skaičių lygus nuliui, tai jų didžiausias bendras daliklis yra lygus antrajam skaičiui.

Euklido algoritmas, nagrinėjamas toliau, išsprendžia didžiausio bendro dviejų skaičių ir už daliklio radimo užduotį.

Šis algoritmas pirmą kartą buvo aprašytas Euklido knygoje „Pradžia“ (apie 300 m. pr. Kr.), nors, tikėtina, šis algoritmas turi ankstesnę kilmę.

Algoritmas

Pats algoritmas yra labai paprastas ir apibūdinamas tokia formule:

Įgyvendinimas

int gcd (int a, int b) (jei (b == 0) grąžina a; kitaip grąžina gcd (b, a% b);)

Naudojant C ++ trinarinį sąlyginį operatorių, algoritmas gali būti parašytas dar trumpiau:

int gcd (int a, int b) (grąžinti b? gcd (b, a% b): a;)

Galiausiai, čia yra nerekursinė algoritmo forma:

int gcd (int a, int b) (o (b) (a% = b; apsikeitimas (a, b);) grąža a;)

Teisingumo įrodymas

Pirma, atkreipkite dėmesį, kad su kiekviena Euklido algoritmo iteracija antrasis jo argumentas griežtai mažėja, todėl, kadangi jis nėra neigiamas, Euklido algoritmas visada baigiasi.

Dėl teisingumo įrodymas turime tai parodyti bet kokiam>.

Parodykime, kad reikšmė kairėje lygybės pusėje dalijasi iš tikrosios vertės dešinėje, o vertė dešinėje dalijasi iš reikšmės kairėje. Akivaizdu, kad tai reikš, kad kairė ir dešinė pusės sutampa, o tai įrodys Euklido algoritmo teisingumą.

Mes pažymime ... Tada pagal apibrėžimą ir.

Bet iš to išplaukia:

Taigi, prisiminę teiginį, gauname sistemą:

Dabar naudokime tokį paprastą faktą: jei kai kuriems trims skaičiams: ir yra patenkinti, tai ir: yra tiesa. Mūsų situacijoje gauname:

Arba, pakeisdami jo apibrėžimą, gauname:

Taigi, mes atlikome pusę įrodinėjimo: parodėme, kad kairioji pusė skiria dešinę. Antroji įrodymo pusė panaši.

Darbo valandos

Apskaičiuojamas algoritmo veikimo laikas Lamé teorema, kuris sukuria nuostabų ryšį tarp Euklido algoritmo ir Fibonačio sekos:

Jei> ir kai kuriems, tada Euklido algoritmas atliks daugiausia rekursinius skambučius.

Apsvarstykite du pagrindinius GCD nustatymo būdus dviem pagrindiniais būdais: naudojant Euklido algoritmą ir įtraukiant į pirminius veiksnius. Taikykime abu metodus dviem, trims ar daugiau skaičių.

Euklido algoritmas ieškant GCD

Euklido algoritmas leidžia lengvai apskaičiuoti didžiausią bendrąjį dviejų teigiamų skaičių daliklį. Euklido algoritmo formuluotes ir įrodymus pateikėme skyriuje „Didžiausias bendras daliklis: determinantas, pavyzdžiai“.

Algoritmo esmė yra nuosekliai atlikti padalijimą su liekana, kurios metu gaunama keletas formos lygybių:

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

Galime baigti padalijimą, kai r k + 1 = 0, kuriame r k = gcd (a, b).

1 pavyzdys

64 ir 48 .

Sprendimas

Įveskime žymėjimą: a = 64, b = 48.

Remdamiesi Euklido algoritmu, atliekame padalijimą 64 įjungta 48 .

Gauname 1 ir likusią 16. Pasirodo, q 1 = 1, r 1 = 16.

Antrame žingsnyje mes padaliname 48 iki 16 gauname 3. Tai yra q 2 = 3, a r 2 = 0. Taigi skaičius 16 yra didžiausias bendras sąlygoje esančių skaičių daliklis.

Atsakymas: GCD (64, 48) = 16.

2 pavyzdys

Kas yra skaičių GCD 111 ir 432 ?

Sprendimas

Padalinti 432 įjungta 111 ... Pagal Euklido algoritmą gauname lygybių grandinę 432 = 111 3 + 99, 111 = 99 1 + 12, 99 = 12 8 + 3, 12 = 3 4.

Taigi didžiausias bendras skaičių daliklis 111 ir 432 Yra 3.

Atsakymas: GCD (111 432) = 3.

3 pavyzdys

Raskite didžiausią bendrą 661 ir 113 vardiklį.

Sprendimas

Atlikime skaičių nuoseklų padalijimą ir gaukime gcd (661 , 113) = 1 ... Tai reiškia, kad 661 ir 113 yra pirminiai skaičiai. Prieš pradėdami skaičiuoti, galėtume tai išsiaiškinti, jei pažvelgtume į pirminių skaičių lentelę.

Atsakymas: GCD (661, 113) = 1.

Gcd radimas faktorinuojant skaičius į pirminius veiksnius

Norint faktorizavimo metodu rasti didžiausią bendrąjį dviejų skaičių daliklį, reikia padauginti visus pirminius veiksnius, gautus išskaidžius šiuos du skaičius ir jiems bendrus.

4 pavyzdys

Jei į pirminius koeficientus įtrauksime skaičius 220 ir 600, gausime du produktus: 220 = 2 2 5 11 ir 600 = 2 2 2 3 5 5... Šių dviejų produktų bendri veiksniai bus 2, 2 ir 5. Tai reiškia, kad GCD (220, 600) = 2 2 5 = 20.

5 pavyzdys

Raskite didžiausią bendrą skaičių daliklį 72 ir 96 .

Sprendimas

Raskite visus pirminius skaičių veiksnius 72 ir 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

Pirminiai koeficientai, bendri dviem skaičiams, yra 2, 2, 2 ir 3. Tai reiškia, kad GCD (72, 96) = 2 2 2 3 = 24.

Atsakymas: GCD (72, 96) = 24.

Dviejų skaičių didžiausio bendro daliklio radimo taisyklė pagrįsta didžiausio bendrojo daliklio savybėmis, pagal kurias GCD (ma 1, mb 1) = m GCD (a 1, b 1), kur m yra bet koks teigiamas sveikasis skaičius .

Trijų ar daugiau skaičių GCD radimas

Nepriklausomai nuo skaičių, kuriems reikia rasti GCD, veiksme pagal tą patį algoritmą, kurį sudaro nuoseklus dviejų skaičių GCD nustatymas. Šis algoritmas pagrįstas šios teoremos taikymu: Kelių skaičių GCD a 1, a 2,…, a k lygus skaičiui d k, kuris randamas nuosekliai apskaičiuojant GCD (a 1, a 2) = d 2, GCD (d 2, a 3) = d 3, GCD (d 3, a 4) = d 4, ..., GCD (d k - 1, a k) = d k.

6 pavyzdys

Raskite didžiausią bendrą keturių skaičių koeficientą 78, 294, 570 ir 36 .

Sprendimas

Įveskime žymėjimą: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

Pradėkime nuo 78 ir 294 skaičių GCD: d 2 = Gcd (78 , 294) = 6 .

Dabar pradėkime ieškoti d 3 = gcd (d 2, a 3) = gcd (6, 570). Pagal Euklido algoritmą 570 = 6 · 95. Tai reiškia kad d 3 = Gcd (6 , 570) = 6 .

Raskite d 4 = gcd (d 3, a 4) = gcd (6, 36). 36 dalijasi iš 6 be liekanos. Tai leidžia mums gauti d 4 = Gcd (6 , 36) = 6 .

d 4 = 6, tai yra, gcd (78 , 294 , 570 , 36) = 6 .

Atsakymas:

Dabar pažvelkime į kitą būdą, kaip apskaičiuoti šių ir kitų skaičių GCD. GCD galime rasti padauginę visus bendrus pirminius skaičių veiksnius.

7 pavyzdys

Apskaičiuokite skaičių 78, 294, 570 ir gcd 36 .

Sprendimas

Išskaidykime šiuos skaičius į pirminius koeficientus: 78 = 2 · 3 · 13, 294 = 2 · 3 · 7 · 7, 570 = 2 · 3 · 5 · 19, 36 = 2 · 2 · 3 · 3.

Visų keturių skaičių pirminiai koeficientai yra 2 ir 3.

Pasirodo, kad GCD (78, 294, 570, 36) = 2 3 = 6.

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

Rasti gcd neigiamiems skaičiams

Jei turime susidoroti su neigiamais skaičiais, galime naudoti šių skaičių absoliučias reikšmes, kad surastume didžiausią bendrą daliklį. Tai galime padaryti žinodami skaičių, turinčių priešingus ženklus, savybę: skaičius n ir - n turi tuos pačius daliklius.

8 pavyzdys

Raskite neigiamų sveikųjų skaičių gcd − 231 ir − 140 .

Sprendimas

Norėdami atlikti skaičiavimus, paimkite sąlygoje pateiktų skaičių modulius. Tai bus skaičiai 231 ir 140. Parašykime trumpai: GCD (− 231 , − 140) = GCD (231, 140). Dabar taikysime Euklido algoritmą dviejų skaičių pirminiams veiksniams rasti: 231 = 140 · 1 + 91; 140 = 91 * 1 + 49; 91 = 49 * 1 + 42; 49 = 42 1 + 7 ir 42 = 7 6... Gauname, kad gcd (231, 140) = 7 .

Ir nuo GCD (− 231 , − 140) = Gcd (231 , 140) , tada gcd skaičiai − 231 ir − 140 yra lygus 7 .

Atsakymas: GCD (- 231, - 140) = 7.

9 pavyzdys

Nustatykite trijų skaičių GCD - 585, 81 ir − 189 .

Sprendimas

Neigiamus skaičius aukščiau esančiame sąraše pakeičiame jų absoliučiomis reikšmėmis, gauname GCD (− 585 , 81 , − 189) = Gcd (585 , 81 , 189) ... Tada visus šiuos skaičius išskaidome į pirminius veiksnius: 585 = 3 3 5 13, 81 = 3 3 3 3 ir 189 = 3 3 3 7... Šie trys skaičiai turi bendrų pirminių koeficientų 3 ir 3. Pasirodo, GCD (585, 81, 189) = GCD (- 585, 81, - 189) = 9.

Atsakymas: GCD (- 585, 81, - 189) = 9.

Jei tekste pastebėjote klaidą, pažymėkite ją ir paspauskite Ctrl + Enter

Didžiausias bendras daliklis

2 apibrėžimas

Jei natūralusis skaičius a dalijasi iš natūraliojo skaičiaus $ b $, tai $ b $ vadinamas $ a $ dalikliu, o $ a $ vadinamas $ b $ kartotiniu.

Tegul $ a $ ir $ b $ yra natūralieji skaičiai. Skaičius $ c $ vadinamas bendruoju ir $ a $, ir $ b $ dalikliu.

$ a $ ir $ b $ bendrųjų daliklių rinkinys yra baigtinis, nes nė vienas iš šių daliklių negali būti didesnis nei $ a $. Tai reiškia, kad tarp šių daliklių yra didžiausias, vadinamas didžiausiu bendruoju skaičių $ a $ ir $ b $ dalikliu, ir jam žymėti naudojamas užrašas:

$ Gcd \ (a; b) \ arba \ D \ (a; b) $

Norėdami rasti didžiausią bendrą dviejų skaičių daliklį, turite:

1. Raskite skaičių sandaugą, rastą 2 veiksme. Gautas skaičius bus norimas didžiausias bendras koeficientas.

1 pavyzdys

Raskite skaičių $ 121 $ ir $ 132. $ gcd

242 USD = 2 \ cdot 11 \ cdot 11 USD

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

Pasirinkite skaičius, kurie yra įtraukti į šių skaičių skaidymą

242 USD = 2 \ cdot 11 \ cdot 11 USD

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

Raskite skaičių sandaugą, rastą 2 veiksme. Gautas skaičius bus norimas didžiausias bendras koeficientas.

$ Gcd = 2 \ cdot 11 = 22 $

2 pavyzdys

Raskite 63 USD ir 81 USD kainuojantį GCD.

Rasime pagal pateiktą algoritmą. Už tai:

Išskaidykite skaičius į pirminius veiksnius

63 USD = 3 \ cdot 3 \ cdot 7 USD

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

Mes pasirenkame skaičius, kurie yra įtraukti į šių skaičių skaidymą

63 USD = 3 \ cdot 3 \ cdot 7 USD

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

Raskime skaičių sandaugą, rastą 2 veiksme. Gautas skaičius bus norimas didžiausias bendras koeficientas.

$ Gcd = 3 \ cdot 3 = 9 $

Dviejų skaičių GCD galite rasti kitu būdu, naudodami skaičių daliklių rinkinį.

3 pavyzdys

Raskite skaičių 48 USD ir 60 USD GCD.

Sprendimas:

Raskite skaičiaus $ 48 daliklių rinkinį: $ \ left \ ((\ rm 1,2,3.4.6,8,12,16,24,48) \ right \) $

Dabar randame skaičiaus $ 60 daliklių rinkinį: $ \ \ left \ ((\ rm 1,2,3,4,5,6,10,12,15,20,30,60) \ dešinė \ ) $

Raskime šių aibių sankirtą: $ \ left \ ((\ rm 1,2,3,4,6,12) \ right \) $ - šis rinkinys nustatys skaičių bendrųjų daliklių aibę $ 48 $ ir 60 USD. Didžiausias šio rinkinio elementas bus skaičius 12 USD. Taigi didžiausias bendras 48 USD ir 60 USD daliklis bus 12 USD.

LCM apibrėžimas

3 apibrėžimas

Bendrasis natūraliųjų skaičių kartotinis$ a $ ir $ b $ yra natūralusis skaičius, kuris yra $ a $ ir $ b $ kartotinis.

Bendrieji kartotiniai yra skaičiai, kurie dalijasi iš originalo be liekanos. Pavyzdžiui, skaičiams $ 25 $ ir $ 50 bendrieji kartotiniai bus skaičiai $ 50 100 150 200 ir tt.

Mažiausias bendras kartotinis bus vadinamas mažiausiu bendruoju kartotiniu ir žymimas LCM $ (a; b) $ arba K $ (a; b). $

Norėdami rasti dviejų skaičių LCM, jums reikia:

1. Veiksnių skaičiai
2. Užrašykite veiksnius, kurie yra pirmojo skaičiaus dalis, ir pridėkite prie jų veiksnius, kurie yra antrojo skaičiaus dalis ir neįeina į pirmąjį.

4 pavyzdys

Raskite skaičių 99 USD ir 77 USD LCM.

Rasime pagal pateiktą algoritmą. Už tai

Veiksnių skaičiai

99 USD = 3 \ cdot 3 \ cdot 11 USD

Užrašykite veiksnius, įtrauktus į pirmąjį

pridėkite prie jų veiksnius, kurie yra antrojo dalis ir nesigilinkite į pirmąjį

Raskite skaičių sandaugą, rastą 2 veiksme. Gautas skaičius bus norimas mažiausias bendras kartotinis

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

Skaičių daliklių sąrašų sudarymas dažnai užima daug laiko. Yra būdas rasti GCD, vadinamas Euklido algoritmu.

Teiginiai, kuriais grindžiamas Euklido algoritmas:

Jei $ a $ ir $ b $ yra natūralūs skaičiai, o $ a \ vdots b $, tai $ D (a; b) = b $

Jei $ a $ ir $ b $ yra natūralūs skaičiai, tokie, kad $ b

Naudodami $ D (a; b) = D (a-b; b) $, galime paeiliui mažinti nagrinėjamus skaičius, kol pasieksime tokią skaičių porą, kad vienas iš jų dalytųsi iš kito. Tada mažesnis iš šių skaičių bus pageidaujamas didžiausias skaičių $ a $ ir $ b $ daliklis.

GCD ir LCM savybės

1. Bet koks bendras $ a $ ir $ b $ kartotinis dalijasi iš K $ (a; b) $
2. Jei $ a \ vdots b $, tai K $ (a; b) = a $

Jei K $ (a; b) = k $ ir $ m $ yra natūralusis skaičius, tai K $ (am; bm) = km $

Jei $ d $ yra bendras $ a $ ir $ b $ daliklis, tada K ($ \ frac (a) (d); \ frac (b) (d) $) = $ \ \ frac (k) (d ) $

Jei $ a \ vdots c $ ir $ b \ vdots c $, tai $ \ frac (ab) (c) $ yra bendras $ a $ ir $ b $ kartotinis

Bet kokių natūraliųjų skaičių $ a $ ir $ b $ lygybė

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

Bet koks bendras skaičių $ a $ ir $ b $ daliklis yra skaičiaus $ D daliklis (a; b) $