Mazgų paieška naudojant Euklido algoritmą ir naudojant pirminį faktorių. Nok radimas faktorinuojant skaičius į pirminius veiksnius Euklido algoritmas ieškant gcd

Apsvarstykite du būdus, kaip rasti didžiausią bendrą daliklį.

Faktoringo nustatymas

Pirmasis būdas yra rasti didžiausią bendrą daliklį, suskirstant duotus skaičius į pirminius veiksnius.

Norint rasti kelių skaičių GCD, pakanka juos išskaidyti į pirminius veiksnius ir padauginti iš jų tuos, kurie yra bendri visiems duotiesiems skaičiams.

1 pavyzdys Raskime GCD (84, 90).

Skaičius 84 ir 90 išskaidome į pirminius veiksnius:

Taigi, mes pabrėžėme visus bendrus pirminius veiksnius, belieka juos padauginti tarpusavyje: 1 2 3 = 6.

Taigi gcd(84, 90) = 6.

2 pavyzdys Raskime GCD (15, 28).

15 ir 28 išskaidome į pirminius veiksnius:

Skaičiai 15 ir 28 yra pirminiai, nes jų didžiausias bendras daliklis yra vienas.

gcd (15, 28) = 1.

Euklido algoritmas

Antrasis metodas (kitaip vadinamas Euklido metodu) yra rasti GCD dalijant iš eilės.

Pirmiausia pažvelgsime į šį metodą, taikomą tik dviem nurodytiems skaičiams, o tada išsiaiškinsime, kaip jį pritaikyti trims ar daugiau skaičių.

Jei didesnis iš dviejų pateiktų skaičių dalijasi iš mažesniojo, tada mažesnis skaičius bus didžiausias jų bendras daliklis.

1 pavyzdys Paimkite du skaičius 27 ir 9. Kadangi 27 dalijasi iš 9, o 9 dalijasi iš 9, tai 9 yra bendras skaičių 27 ir 9 daliklis. Šis daliklis taip pat yra didžiausias, nes 9 negali dalytis iš jokio skaičiaus, didesnis nei 9. Todėl gcd (27, 9) = 9.

Kitais atvejais, norint rasti didžiausią bendrą dviejų skaičių daliklį, naudojama tokia procedūra:

1. Iš dviejų pateiktų skaičių didesnis skaičius dalijamas iš mažesnio.
2. Tada mažesnis skaičius padalijamas iš likusios dalies, gaunamos padalijus didesnį skaičių iš mažesnio.
3. Be to, pirmoji liekana dalijama iš antrosios liekanos, kuri gaunama padalijus mažesnį skaičių iš pirmosios liekanos.
4. Antroji liekana dalijama iš trečiosios, kuri gaunama padalijus pirmąją liekaną iš antrosios ir pan.
5. Taigi, padalijimas tęsiamas tol, kol likutis bus lygus nuliui. Paskutinis daliklis bus didžiausias bendras daliklis.

2 pavyzdys Raskime didžiausią bendrąjį skaičių 140 ir 96 daliklį:

1) 140: 96 = 1 (likęs 44)

2) 96: 44 = 2 (likę 8)

3) 44: 8 = 5 (likęs 4)

Paskutinis daliklis yra 4, o tai reiškia, kad gcd(140, 96) = 4.

Nuoseklus padalijimas taip pat gali būti parašytas stulpelyje:

Norėdami rasti didžiausią bendrąjį trijų ar daugiau nurodytų skaičių daliklį, naudokite šią procedūrą:

1. Pirmiausia suraskite didžiausią bendrąjį bet kurių dviejų skaičių daliklį iš kelių duomenų rinkinių.
2. Tada randame rasto daliklio GCD ir kažkokį trečiąjį duotąjį skaičių.
3. Tada randame paskutinio rasto daliklio GCD ir ketvirtąjį duotąjį skaičių ir pan.

3 pavyzdys Raskime didžiausią skaičių 140, 96 ir 48 bendrąjį daliklį. Skaičių 140 ir 96 GCD jau radome ankstesniame pavyzdyje (tai skaičius 4). Belieka rasti didžiausią skaičių 4 ir trečiojo duoto skaičiaus daliklį - 48:

48 dalijasi iš 4 be liekanos. Taigi gcd(140, 96, 48) = 4.

Skaičių vaizdavimas pirminių skaičių sandauga vadinamas išskaidydami šį skaičių į pirminius veiksnius.

Pavyzdžiui, įrašas 110 = 2 5 11 rodo, kad skaičius 110 yra išskaidytas į pirminius koeficientus 2, 5 ir 11.

Apskritai, bet koks sudėtinis skaičius gali būti išskaidytas į pirminius veiksnius ir bet kuriuo metodu gaunamas toks pat skaidymas, jei neatsižvelgiama į veiksnių eilę. Todėl skaičiaus 110 atvaizdavimas kaip 2 · 5 · 11 sandauga arba 5 · 2 · 11 sandauga iš esmės yra tas pats skaičiaus 110 išskaidymas į pirminius veiksnius.

Skaičius skaidydami į pirminius veiksnius, naudodami dalybos iš 2, 3, 5 ir kt. ženklus, prisiminkime, kaip rašyti skaičiaus skaidymą į pirminius veiksnius. Išskaidykime, pavyzdžiui, skaičių 720 į pirminius veiksnius. Skaičius 720 dalijasi iš 2. Vadinasi, 2 yra vienas iš pirminių skaičiaus 720 skaidymo faktorių. Skaičius 720 padalinamas iš 2. Skaičius 2 rašomas į lygybės ženklo dešinė, o dalinys 360 rašomas po skaičiumi 720. Skaičius 360 padalijus iš 2, gauname 180. 180 padaliname iš 2, gauname 90, 90 padalijame iš 2, gauname 45, 45 3, gauname 15, 15 padalijame iš 3, gauname 5. Skaičius 5 yra pirminis, padalijus iš 5 gauname 1. Faktorizacija baigta.

720 = 2 2 2 2 3 3 5

Įprasta identiškų faktorių sandaugą pakeisti laipsniu: 720 = 5. Toks skaičiaus 720 vaizdavimas vadinamas kanoninis požiūrisšis skaičius.

Skaičių faktorinavimas į pirminius veiksnius naudojamas didžiausiam bendrajam dalikliui ir mažiausiam bendrajam kartotiniui rasti.

Raskite, pavyzdžiui, didžiausią skaičių 3600 ir 288 bendrąjį daliklį ir mažiausią bendrą kartotinį.

Pavaizduokime kiekvieną iš šių skaičių kanonine forma.

3600 = 2 2 2 2 3 3 5 5 = ; 288 = 2 2 2 2 2 3 3 =

Skaičių 3600 ir 288 didžiausio bendro daliklio pirminėje faktorizacijoje visi paprastas dauginimasis, kurios yra pateiktų skaičių plėtiniuose, ir kiekvienas iš jų turi būti paimtas iš žemiausias rodiklis su kuria jis patenka į abu plėtimus. Todėl didžiausio skaičiaus 3600 ir 288 daliklio išplėtimas apims veiksnius ir . Taigi D (3600? 288) = · = 144.

Mažiausio bendrojo 3600 ir 288 kartotinio pirminis faktorius turi apimti visus pirminius veiksnius. bent viename iš skaičių 3600 ir 288 išplėtimų, ir kiekvienas iš jų turi būti paimtas su aukščiausiu balu,įtraukta į abu šių skaičių išplėtimus. Todėl 3600 ir 288 mažiausio bendro kartotinio išplėtimas apims koeficientus , , 5. Taigi,

K (3600, 288) = 5 = 7200.

Apskritai, norėdami rasti didžiausią bendrąjį nurodytų skaičių daliklį:

2) Sudarome pirminių faktorių, bendrų visiems duotiesiems skaičiams, sandaugą ir kiekvienas iš jų paimamas su mažiausiu rodikliu, su kuriuo jis įeina į visus šių skaičių plėtimus;

3) Surandame šio produkto vertę – tai bus didžiausias bendras šių skaičių daliklis.

Norėdami rasti mažiausią bendrąjį nurodytų skaičių kartotinį:

1) Kiekvieną duotą skaičių pavaizduojame kanonine forma;

2) Sudarome sandaugą iš visų pirminių faktorių, kurie yra šių skaičių plėtiniuose, ir kiekvienas imamas su didžiausiu eksponentu, su kuriuo jis įeina į visus šių skaičių plėtimus;

3) Surandame šio produkto vertę – tai bus mažiausias bendras šių skaičių kartotinis.

Bilieto numeris 45. Mažiausias bendras skaičių kartotinis. Jo savybės ir radimo būdai. Pavyzdžiai.

Mažiausio bendro kartotinio (LCM) apskaičiavimas per gcd (mažiausias bendras daliklis)

Vienas iš būdų rasti mažiausią bendrą kartotinį yra pagrįstas ryšiu tarp LCM ir GCD. Esamas ryšys tarp LCM ir GCD leidžia apskaičiuoti mažiausią bendrą dviejų teigiamų sveikųjų skaičių kartotinį per žinomą didžiausią bendrą daliklį. Atitinkama formulė turi formą LCM(a, b)=a b: GCM(a, b) . Apsvarstykite pavyzdžius, kaip rasti LCM pagal aukščiau pateiktą formulę.

Pavyzdys.

Raskite mažiausią bendrąjį dviejų skaičių kartotinį 126 ir 70 .

Sprendimas.

Šiame pavyzdyje a = 126, b = 70. Naudokime formule išreikštą ryšį tarp LCM ir GCD LCM(a, b)=a b: GCM(a, b). Tai yra, pirmiausia turime rasti didžiausią bendrą skaičių daliklį 70 ir 126 , po to pagal parašytą formulę galime apskaičiuoti šių skaičių LCM.

Raskime GCD(126; 70), naudojant Euklido algoritmą: 126=70 1+56, 70=56 1+14, 56=14 4, vadinasi, gcd(126, 70)=14.

Dabar randame reikalingą mažiausią bendrąjį kartotinį: LCM (126, 70) = 126 70: GCM (126, 70) = 126 70:14 = 630.

Atsakymas:

LCM(126, 70)=630.

Pavyzdys.

Kas yra lygus NOC(68, 34)?

Sprendimas.

Kaip 68 visiškai padalintas į 34 , tada GCD(68, 34)=34. Dabar apskaičiuojame mažiausią bendrąjį kartotinį: LCM (68, 34) = 68 34: GCM (68, 34) = 68 34:34 = 68.

Atsakymas:

LCM(68, 34)=68.

Atminkite, kad ankstesnis pavyzdys atitinka šią taisyklę, kaip rasti teigiamų sveikųjų skaičių LCM a ir b: jei numeris a padalytą b, tada mažiausias bendras šių skaičių kartotinis yra a.

LCM radimas faktorinuojant skaičius į pirminius veiksnius

Kitas būdas rasti mažiausią bendrą kartotinį yra pagrįstas skaičių padalijus į pirminius veiksnius. Jei padarysime visų pirminių šių skaičių sandaugą, po kurios iš šios sandaugos išskirsime visus bendruosius pirminius veiksnius, kurie yra šių skaičių plėtiniuose, tada gauta sandauga bus lygi mažiausiam bendrajam šių skaičių kartotiniui.

Paskelbta LCM radimo taisyklė išplaukia iš lygybės LCM(a, b)=a b: GCM(a, b). Iš tiesų, skaičių sandauga a ir b yra lygus visų veiksnių, dalyvaujančių skaičių plėtime, sandaugai a ir b. Savo ruožtu gcd (a, b) yra lygus visų pirminių veiksnių, vienu metu esančių skaičių plėtiniuose, sandaugai a ir b(kuri aprašyta skirsnyje apie GCD nustatymą, skaičiuojant skaičius į pirminius veiksnius).

Paimkime pavyzdį. Praneškite mums tai 75 = 3 5 5 ir 210=2 3 5 7. Sudarykite visų šių išplėtimų veiksnių sandaugą: 2 3 3 5 5 5 7. Dabar iš šio produkto neįtraukiame visų veiksnių, kurie taip pat yra plečiant skaičių 75 ir skaičiaus išplėtimas 210 (tokie veiksniai yra 3 ir 5 ), tada produktas įgaus formą 2 3 5 5 7. Šio sandaugos vertė lygi mažiausiam bendrajam skaičių kartotiniui 75 ir 210 , t.y, LCM(75; 210) = 2 3 5 5 7 = 1 050.

Pavyzdys.

Skaičių išplėtimas 441 ir 700 į pirminius veiksnius, raskite mažiausią bendrą šių skaičių kartotinį.

Sprendimas.

Išskaidykime skaičius 441 ir 700 pagrindiniai veiksniai:

Mes gauname 441=3 3 7 7 ir 700 = 2 2 5 5 7.

Dabar padarykime sandaugą iš visų veiksnių, susijusių su šių skaičių išplėtimu: 2 2 3 3 5 5 7 7 7. Išskirkime iš šio produkto visus veiksnius, kurie vienu metu yra abiejuose plėtiniuose (yra tik vienas toks veiksnys - tai skaičius 7 ): 2 2 3 3 5 5 7 7. Taigi, LCM(441, 700) = 2 2 3 3 5 5 7 7 = 44 100.

Atsakymas:

LCM(441; 700) = 44 100.

Taisyklė, kaip rasti LCM naudojant skaičių skaidymą į pirminius veiksnius, gali būti suformuluota šiek tiek kitaip. Jei prie faktorių iš skaičiaus išplėtimo a pridėkite trūkstamus koeficientus iš skaičiaus išplėtimo b, tada gautos sandaugos reikšmė bus lygi mažiausiam bendrajam skaičių kartotiniui a ir b .

Pavyzdžiui, paimkime visus tuos pačius skaičius 75 ir 210 , jų faktorizacija yra tokia: 75 = 3 5 5 ir 210=2 3 5 7. Į daugiklius 3 , 5 ir 5 nuo skaičiaus skilimo 75 2 ir 7 nuo skaičiaus skilimo 210 , gauname prekę 2 3 5 5 7, kurio vertė yra NOC(75, 210).

Pavyzdys.

Raskite mažiausią bendrą skaičių kartotinį 84 ir 648 .

Sprendimas.

Pirmiausia gauname skaičių skaidymą 84 ir 648 prie pagrindinių veiksnių. Jie atrodo kaip 84 = 2 2 3 7 ir 648=2 2 2 3 3 3 3. Į daugiklius 2 , 2 , 3 ir 7 nuo skaičiaus skilimo 84 pridedant trūkstamus veiksnius 2 , 3 , 3 ir 3 nuo skaičiaus skilimo 648 , gauname prekę 2 2 2 3 3 3 3 7, kuris yra lygus 4 536 . Taigi, norimas mažiausias bendras skaičių kartotinis 84 ir 648 lygus 4 536 .

Atsakymas:

LCM(84, 648)=4536.

Panagrinėkime du pagrindinius GCD nustatymo būdus dviem pagrindiniais būdais: naudojant Euklido algoritmą ir faktoringo metodą. Taikykime abu metodus dviem, trims ir daugiau skaičių.

Yandex.RTB R-A-339285-1

Euklido algoritmas GCD paieškai

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

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

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 rk + 1 = 0, kuriame r k = gcd (a , b).

1 pavyzdys

64 ir 48 .

Sprendimas

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

Remdamiesi Euklido algoritmu, atliksime padalijimą 64 ant 48 .

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

Antras žingsnis – padalinti 48 iki 16 gauname 3 . T.y q2 = 3, a r 2 = 0 . Taigi skaičius 16 yra didžiausias bendras skaičių iš sąlygos daliklis.

Atsakymas: gcd(64, 48) = 16.

2 pavyzdys

Kas yra skaičių GCD 111 ir 432 ?

Sprendimas

Padalinti 432 ant 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ą skaičių 661 ir 113 daliklį.

Sprendimas

Iš eilės padalinsime skaičius ir gausime GCD (661 , 113) = 1 . Tai reiškia, kad 661 ir 113 yra santykinai pirminiai skaičiai. Mes galėtume tai išsiaiškinti prieš pradėdami skaičiavimus, jei pažvelgtume į pirminių skaičių lentelę.

Atsakymas: gcd(661, 113) = 1.

GCD radimas faktorinuojant skaičius į pirminius veiksnius

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

4 pavyzdys

Jei skaičius 220 ir 600 išskaidysime į pirminius veiksnius, gautume du sandaugus: 220 = 2 2 5 11 ir 600 = 2 2 2 3 5 5. Bendri šių dviejų produktų faktoriai bus 2, 2 ir 5. Tai reiškia, kad NOD (220, 600) = 2 2 5 = 20.

5 pavyzdys

Raskite didžiausią bendrąjį 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

Dviejų skaičių bendrieji pirminiai koeficientai: 2 , 2 , 2 ir 3 . Tai reiškia, kad NOD (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 (m a 1 , m b 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 dviejų skaičių iš eilės GCD paieška. Šis algoritmas pagrįstas šios teoremos taikymu: Kelių skaičių GCD a 1 , a 2 , … , a k yra lygus skaičiui dk, 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ų 78, 294, 570 ir 36 .

Sprendimas

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

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

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

Raskite d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36). 36 dalijasi iš 6 be liekanos. Tai leidžia mums gauti d4= GCD (6 , 36) = 6 .

d4 = 6, tai yra, GCD (78 , 294 , 570 , 36) = 6 .

Atsakymas:

O 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 .

Visiems keturiems skaičiams bendrieji pirminiai koeficientai bus skaičiai 2 ir 3.

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

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

Neigiamų skaičių gcd radimas

Jei turime susidoroti su neigiamais skaičiais, galime naudoti šių skaičių modulius, 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, paimkime sąlygoje pateiktų skaičių modulius. Tai bus skaičiai 231 ir 140. Trumpai pasakykime: GCD (− 231 , − 140) = GCD (231, 140). Dabar pritaikykime 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 NOD (− 231 , − 140) = GCD (231 , 140) , tada skaičių gcd − 231 ir − 140 lygus 7 .

Atsakymas: gcd (− 231 , − 140) = 7 .

9 pavyzdys

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

Sprendimas

Pakeiskime neigiamus skaičius aukščiau pateiktame sąraše jų absoliučiomis reikšmėmis, gausime GCD (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . Tada visus pateiktus skaičius išskaidome į pirminius veiksnius: 585 = 3 3 5 13, 81 = 3 3 3 3 ir 189 = 3 3 3 7. Pirminiai koeficientai 3 ir 3 yra bendri trims skaičiams. 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