Įdomūs būdai rasti mazgus ir mazgus. Skaičių nod ir nok – didžiausias kelių skaičių bendras daliklis ir mažiausias bendras kartotinis

Daug daliklių

Apsvarstykite šią problemą: raskite skaičiaus 140 daliklį. Akivaizdu, kad skaičius 140 turi ne vieną daliklį, o kelis. Tokiais atvejais sakoma, kad užduotis turi daug sprendimus. Suraskime juos visus. Pirmiausia šį skaičių išskaidome į pirminius veiksnius:

140 = 2 ∙ 2 ∙ 5 ∙ 7.

Dabar galime lengvai užrašyti visus daliklius. Pradėkime nuo paprastų daliklių, ty tų, kurie yra aukščiau esančiame išplėtime:

Tada išrašome tuos, kurie gaunami poromis dauginant pirminius daliklius:

2∙2 = 4, 2∙5 = 10, 2∙7 = 14, 5∙7 = 35.

Tada - tie, kuriuose yra trys paprasti dalikliai:

2∙2∙5 = 20, 2∙2∙7 = 28, 2∙5∙7 = 70.

Galiausiai nepamirškime vieneto ir paties skaidomo skaičiaus:

Visi mūsų rasti dalikliai susidaro daug skaičiaus 140 dalikliai, rašoma naudojant riestinius skliaustus:

Skaičiaus 140 daliklių aibė =

{1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140}.

Kad būtų patogiau suvokti, čia išrašėme daliklius ( rinkinio elementai) didėjimo tvarka, bet paprastai tai nėra būtina. Be to, pristatome santrumpą. Vietoj „Skaičiaus 140 daliklių rinkinys“ rašysime „D (140)“. Šiuo būdu,

Panašiai galima rasti bet kurio kito natūraliojo skaičiaus daliklių rinkinį. Pavyzdžiui, nuo išsiplėtimo

105 = 3 ∙ 5 ∙ 7

mes gauname:

D(105) = (1, 3, 5, 7, 15, 21, 35, 105).

Iš visų daliklių aibės reikėtų išskirti pirminių daliklių aibę, kuri skaičiams 140 ir 105 yra atitinkamai lygūs:

PD(140) = (2, 5, 7).

PD(105) = (3, 5, 7).

Pabrėžtina, kad išskaidant skaičių 140 į pirminius veiksnius, du yra du kartus, o aibėje PD(140) – tik vienas. PD(140) aibė iš esmės yra visi atsakymai į uždavinį: „Rasti pirminį skaičiaus 140 koeficientą“. Akivaizdu, kad tas pats atsakymas neturėtų būti kartojamas daugiau nei vieną kartą.

Frakcijų mažinimas. Didžiausias bendras daliklis

Apsvarstykite trupmeną

Žinome, kad šią trupmeną galima sumažinti skaičiumi, kuris yra ir skaitiklio (105) ir vardiklio (140) daliklis. Pažiūrėkime į aibes D(105) ir D(140) ir užrašykime jų bendruosius elementus.

D(105) = (1, 3, 5, 7, 15, 21, 35, 105);

D(140) = (1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140).

Bendrieji aibių D(105) ir D(140) elementai =

Paskutinę lygybę galima parašyti trumpiau, būtent:

D(105) ∩ D(140) = (1, 5, 7, 35).

Čia speciali piktograma „∩“ („krepšys su skylute žemyn“) tik nurodo, kad iš dviejų rinkinių, parašytų priešingose jo pusėse, reikia pasirinkti tik bendrus elementus. Įrašas "D (105) ∩ D (140)" yra " sankryža rinkiniai Te nuo 105 ir Te nuo 140.

[Atkreipkite dėmesį, kad su rinkiniais galite atlikti įvairias dvejetaines operacijas, beveik kaip su skaičiais. Kita įprasta dvejetainė operacija yra sąjunga, kuri nurodoma piktograma „∪“ („krepšys su skylute“). Dviejų rinkinių sąjunga apima visus abiejų rinkinių elementus:

PD(105) = (3, 5, 7);

PD(140) = (2, 5, 7);

PD(105) ∪ PD(140) = (2, 3, 5, 7). ]

Taigi, mes sužinojome, kad trupmena

gali būti sumažintas iki bet kurio iš rinkiniui priklausančių skaičių

D(105) ∩ D(140) = (1, 5, 7, 35)

ir negali būti sumažintas jokiu kitu natūraliuoju skaičiumi. Štai visi galimi būdai sumažinti (išskyrus neįdomų sumažinimą vienu):

Akivaizdu, kad praktiškiausia trupmeną sumažinti skaičiumi, jei įmanoma, didesniu. Šiuo atveju tai yra skaičius 35, kuris, kaip teigiama, yra didžiausias bendras daliklis (GCD) skaičiai 105 ir 140. Tai parašyta kaip

gcd(105, 140) = 35.

Tačiau praktiškai, jei mums yra duoti du skaičiai ir reikia rasti didžiausią jų bendrą daliklį, mes neturime sudaryti jokių aibių. Pakanka tiesiog sudėti abu skaičius į pirminius veiksnius ir pabraukti tuos iš šių veiksnių, kurie yra bendri abiem faktoriams, pavyzdžiui:

105 = 3 ∙ 5 ∙ 7 ;

140 = 2 ∙ 2 ∙ 5 ∙ 7 .

Padauginus pabrauktus skaičius (bet kuriame išplėtime), gauname:

gcd(105, 140) = 5 ∙ 7 = 35.

Žinoma, gali būti, kad yra daugiau nei du pabrėžti veiksniai:

168 = 2 ∙ 2 ∙ 2 ∙ 3 ∙ 7;

396 = 2 ∙ 2 ∙ 3 ∙ 3 ∙ 11.

Iš čia aišku, kad

gcd(168, 396) = 2 ∙ 2 ∙ 3 = 12.

Atskirai verta paminėti situaciją, kai apskritai nėra bendrų veiksnių ir nėra ką pabrėžti, pavyzdžiui:

42 = 2 ∙ 3 ∙ 7;

Tokiu atveju,

gcd(42, 55) = 1.

Iškviečiami du natūralieji skaičiai, kurių gcd yra lygus vienetui koprime. Jei iš tokių skaičių padarysite trupmeną, pavyzdžiui,

tada tokia trupmena yra nesumažinamas.

Paprastai tariant, trupmenų mažinimo taisyklę galima parašyti taip:

		a/ gcd ( a, b)
		b/ gcd ( a, b)

Čia daroma prielaida, kad a Ir b yra natūralūs skaičiai, o visos trupmenos yra teigiamos. Jei dabar abiem šios lygybės pusėms priskirsime minuso ženklą, gautume atitinkamą neigiamų trupmenų taisyklę.

Trupmenų sudėjimas ir atėmimas. Mažiausias bendras kartotinis

Tarkime, kad norite apskaičiuoti dviejų trupmenų sumą:

Mes jau žinome, kaip vardikliai skaidomi į pirminius veiksnius:

105 = 3 ∙ 5 ∙ 7 ;

140 = 2 ∙ 2 ∙ 5 ∙ 7 .

Iš šio skilimo iš karto išplaukia, kad norint suvesti trupmenas į bendrą vardiklį, pakanka pirmosios trupmenos skaitiklį ir vardiklį padauginti iš 2∙ 2 (antrojo vardiklio nekirčiuotų pirminių koeficientų sandauga) ir antrosios trupmenos skaitiklis ir vardiklis 3 („produktas“ nepabraukti pirminiai pirmojo vardiklio koeficientai). Dėl to abiejų trupmenų vardikliai taps lygūs skaičiui, kurį galima pavaizduoti taip:

2 ∙ 2 ∙ 3 ∙ 5 ∙ 7 = 105 ∙ 2 ∙ 2 = 140 ∙ 3 = 420.

Nesunku pastebėti, kad abu pradiniai vardikliai (ir 105, ir 140) yra skaičiaus 420 dalikliai, o skaičius 420 savo ruožtu yra abiejų vardiklių kartotinis – ir ne tik kartotinis, tai yra mažiausias bendras kartotinis (NOC) skaičiai 105 ir 140. Tai parašyta taip:

LCM(105; 140) = 420.

Atidžiau pažvelgę į skaičių 105 ir 140 išplėtimą, matome, kad

105 ∙ 140 = LCM(105, 140) ∙ GCD(105, 140).

Panašiai ir savavališkiems natūraliems skaičiams b Ir d:

b ∙ d= LCM( b, d) ∙ GCD( b, d).

Dabar užbaigkime savo trupmenų sumavimą:


3 ∙ 5 ∙ 7		2 ∙ 2 ∙ 5 ∙ 7


2 ∙ 2 ∙ 3 ∙ 5 ∙ 7		2 ∙ 2 ∙ 3 ∙ 5 ∙ 7


2 ∙ 2 ∙ 3 ∙ 5 ∙ 7


2 ∙ 2 ∙ 3 ∙ 5 ∙ 7


2 ∙ 2 ∙ 3 ∙ 5

Pastaba. Norėdami išspręsti kai kurias problemas, turite žinoti, koks yra skaičiaus kvadratas. Skaičių kvadratas a paskambino numeriu a padaugintas iš savęs, tai yra a∙a. (Kaip matote, jis lygus kvadrato su kraštine plotui a).

Didžiausias bendras daliklis ir mažiausias bendras kartotinis yra pagrindinės aritmetinės sąvokos, leidžiančios lengvai operuoti su paprastosiomis trupmenomis. LCM ir dažniausiai naudojami kelių trupmenų bendram vardikliui rasti.

Pagrindinės sąvokos

Sveikojo skaičiaus X daliklis yra kitas sveikasis skaičius Y, iš kurio X dalijasi be liekanos. Pavyzdžiui, 4 daliklis yra 2, o 36 yra 4, 6, 9. Sveikojo skaičiaus X kartotinis yra skaičius Y, kuris dalijasi iš X be liekanos. Pavyzdžiui, 3 yra 15 kartotinis, o 6 yra 12 kartotinis.

Bet kuriai skaičių porai galime rasti bendrus jų daliklius ir kartotinius. Pavyzdžiui, 6 ir 9 bendras kartotinis yra 18, o bendras daliklis yra 3. Akivaizdu, kad poros gali turėti kelis daliklius ir kartotinius, todėl skaičiavimuose naudojamas didžiausias GCD daliklis ir mažiausias LCM kartotinis. .

Mažiausias daliklis neturi prasmės, nes bet kuriam skaičiui jis visada yra vienas. Didžiausias kartotinis taip pat neturi prasmės, nes kartotinių seka linkusi į begalybę.

GCD radimas

Yra daug būdų, kaip rasti didžiausią bendrą daliklį, iš kurių žinomiausi yra šie:

nuoseklus daliklių surašymas, poros bendrųjų parinkimas ir didžiausio iš jų paieška;
skaičių skaidymas į nedalomus veiksnius;
Euklido algoritmas;
dvejetainis algoritmas.

Šiandien švietimo įstaigose populiariausi skaidymo į pirminius veiksnius metodai ir euklido algoritmas. Pastaroji, savo ruožtu, naudojama sprendžiant diofantines lygtis: reikia ieškoti GCD, kad būtų galima patikrinti lygtį, ar įmanoma ją išspręsti sveikaisiais skaičiais.

NOC radimas

Mažiausias bendras kartotinis taip pat tiksliai nustatomas kartotiniu išvardinimu arba faktorinizavimu į nedalomus veiksnius. Be to, nesunku rasti LCM, jei didžiausias daliklis jau nustatytas. Skaičiams X ir Y LCM ir GCD yra susiję tokiu ryšiu:

LCM(X,Y) = X × Y / GCM(X,Y).

Pavyzdžiui, jei gcd(15,18) = 3, tada LCM(15,18) = 15 × 18 / 3 = 90. Akivaizdžiausias LCM panaudojimas yra rasti bendrą vardiklį, kuris yra mažiausias bendras kartotinis duotosios trupmenos.

Kopirminiai skaičiai

Jei skaičių pora neturi bendrų daliklių, tada tokia pora vadinama koprime. Tokių porų GCM visada yra lygus vienetui, o remiantis daliklių ir kartotinių jungtimi, koprime GCM yra lygus jų sandaugai. Pavyzdžiui, skaičiai 25 ir 28 yra pirminiai, nes neturi bendrų daliklių, o LCM(25, 28) = 700, o tai atitinka jų sandaugą. Bet kurie du nedalomi skaičiai visada bus pirminiai.

Bendras daliklis ir kelių skaičiuoklė

Naudodami mūsų skaičiuotuvą galite apskaičiuoti GCD ir LCM bet kokiam skaičių pasirinkimui. Bendrųjų daliklių ir kartotinių skaičiavimo užduotys yra 5 ir 6 klasių aritmetikoje, tačiau GCD ir LCM yra pagrindinės matematikos sąvokos ir naudojamos skaičių teorijoje, planimetrijoje ir komunikacinėje algebroje.

Realaus gyvenimo pavyzdžiai

Bendras trupmenų vardiklis

Mažiausias bendras kartotinis naudojamas ieškant kelių trupmenų bendrąjį vardiklį. Tarkime, aritmetiniame uždavinyje reikia susumuoti 5 trupmenas:

1/8 + 1/9 + 1/12 + 1/15 + 1/18.

Norint pridėti trupmenas, išraiška turi būti sumažinta iki bendro vardiklio, o tai sumažina iki LCM radimo problemos. Norėdami tai padaryti, skaičiuoklėje pasirinkite 5 skaičius ir atitinkamuose langeliuose įveskite vardiklio reikšmes. Programa apskaičiuos LCM (8, 9, 12, 15, 18) = 360. Dabar kiekvienai trupmenai reikia apskaičiuoti papildomus koeficientus, kurie apibrėžiami kaip LCM santykis su vardikliu. Taigi papildomi daugikliai atrodytų taip:

360/8 = 45
360/9 = 40
360/12 = 30
360/15 = 24
360/18 = 20.

Po to visas trupmenas padauginame iš atitinkamo papildomo koeficiento ir gauname:

45/360 + 40/360 + 30/360 + 24/360 + 20/360.

Mes galime lengvai pridėti tokias trupmenas ir gauti rezultatą 159/360. Sumažiname trupmeną 3 ir matome galutinį atsakymą – 53/120.

Tiesinių diofantinių lygčių sprendimas

Tiesinės diofantinės lygtys yra ax + by = d formos išraiškos. Jei santykis d / gcd(a, b) yra sveikasis skaičius, tai lygtis gali būti išspręsta sveikaisiais skaičiais. Patikrinkime keletą lygčių, kad būtų galima rasti sveikojo skaičiaus sprendimą. Pirmiausia patikrinkite lygtį 150x + 8y = 37. Naudodami skaičiuotuvą randame gcd (150,8) = 2. Padalinkite 37/2 = 18,5. Skaičius nėra sveikasis skaičius, todėl lygtis neturi sveikųjų skaičių šaknų.

Patikrinkime lygtį 1320x + 1760y = 10120. Skaičiuotuvu suraskite gcd(1320, 1760) = 440. Padalykime 10120/440 = 23. Rezultate gauname sveikąjį skaičių, todėl išsprendžiama Diofantinų koeficiento koeficientas. .

Išvada

GCD ir LCM vaidina svarbų vaidmenį skaičių teorijoje, o pačios sąvokos plačiai naudojamos įvairiose matematikos srityse. Naudokite mūsų skaičiuotuvą, kad apskaičiuotumėte didžiausius bet kokio skaičių daliklius ir mažiausius kartotinius.

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 skaičius $a$ vadinamas $b$ kartotiniu.

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

Skaičių $a$ ir $b$ bendrųjų daliklių aibė yra baigtinė, nes nė vienas iš šių daliklių negali būti didesnis už $a$. Tai reiškia, kad tarp šių daliklių yra didžiausias, kuris vadinamas didžiausiu skaičių $a$ ir $b$ bendruoju 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į:

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

1 pavyzdys

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

242 USD=2\cdot 11\cdot 11$

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

Pasirinkite skaičius, kurie yra įtraukti į šių skaičių išplėtimą

242 USD=2\cdot 11\cdot 11$

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

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

$gcd=2\cdot 11=22$

2 pavyzdys

Raskite monomijų GCD 63 USD ir 81 USD.

Rasime pagal pateiktą algoritmą. Už tai:

Išskaidykime skaičius į pirminius veiksnius

63 USD=3\cdot 3\cdot 7$

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

Mes pasirenkame skaičius, kurie yra įtraukti į šių skaičių išplėtimą

63 USD=3\cdot 3\cdot 7$

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

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

$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$ ir $60$ gcd.

Sprendimas:

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

Dabar suraskime $60$ daliklių rinkinį:$\ \left$(\rm 1,2,3,4,5,6,10,12,15,20,30,60)\right$$

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

NOC apibrėžimas

3 apibrėžimas

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

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

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:

Išskaidykite skaičius į pirminius veiksnius
Užrašykite veiksnius, kurie yra pirmojo skaičiaus dalis, ir pridėkite prie jų veiksnius, kurie yra antrojo skaičiaus dalis, o ne prie pirmojo skaičiaus

4 pavyzdys

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

Rasime pagal pateiktą algoritmą. Už tai

Išskaidykite skaičius į pirminius veiksnius

99 USD=3\cdot 3\cdot 11$

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

pridėkite prie jų veiksnius, kurie yra antrojo dalis, o ne į pirmąjį

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

$LCC=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 nuosekliai mažinti nagrinėjamus skaičius, kol pasieksime skaičių porą, kad vienas iš jų dalytųsi iš kito. Tada mažesnis iš šių skaičių bus norimas didžiausias skaičių $a$ ir $b$ bendras daliklis.

GCD ir LCM savybės

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

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

Jei $d$ yra bendras $a$ ir $b$ daliklis, tai 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 kurių natūraliųjų skaičių $a$ ir $b$ lygybė

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

Bet koks bendras $a$ ir $b$ daliklis yra $D(a;b)$ daliklis

Tačiau daugelis natūraliųjų skaičių dalijasi tolygiai iš kitų natūraliųjų skaičių.

Pavyzdžiui:

Skaičius 12 dalijasi iš 1, iš 2, iš 3, iš 4, iš 6, iš 12;

Skaičius 36 dalijasi iš 1, iš 2, iš 3, iš 4, iš 6, iš 12, iš 18, iš 36.

Skaičiai, iš kurių skaičius dalijasi (12 yra 1, 2, 3, 4, 6 ir 12), vadinami skaičių dalikliai. Natūralaus skaičiaus daliklis a yra natūralusis skaičius, dalijantis nurodytą skaičių a be pėdsakų. Vadinamas natūralusis skaičius, turintis daugiau nei du veiksnius sudėtinis. Atkreipkite dėmesį, kad skaičiai 12 ir 36 turi bendrus daliklius. Tai yra skaičiai: 1, 2, 3, 4, 6, 12. Didžiausias šių skaičių daliklis yra 12.

Bendras dviejų nurodytų skaičių daliklis a Ir b yra skaičius, iš kurio abu duoti skaičiai dalijasi be liekanos a Ir b. Bendras kelių skaičių daliklis (GCD) yra skaičius, kuris yra kiekvieno iš jų daliklis.

Trumpai – didžiausias bendras skaičių daliklis a Ir b parašyti taip:

Pavyzdys: gcd (12; 36) = 12.

Skaičių dalikliai sprendimo įraše žymimi didžiąja raide „D“.

Pavyzdys:

gcd (7; 9) = 1

Skaičiai 7 ir 9 turi tik vieną bendrą daliklį – skaičių 1. Tokie skaičiai vadinami koprimechi slam.

Kopirminiai skaičiai yra natūralūs skaičiai, turintys tik vieną bendrą daliklį – skaičių 1. Jų gcd yra 1.

Didžiausias bendras daliklis (GCD), savybės.

Pagrindinė savybė: didžiausias bendras daliklis m Ir n dalijasi iš bet kurio bendro šių skaičių daliklio. Pavyzdys: skaičių 12 ir 18 didžiausias bendras daliklis yra 6; jis dalijasi iš visų bendrųjų šių skaičių daliklių: 1, 2, 3, 6.
1 išvada: bendrųjų daliklių rinkinys m Ir n sutampa su daliklių rinkiniu gcd( m, n).
2 išvada: bendrųjų kartotinių rinkinys m Ir n sutampa su kelių LCM rinkiniu ( m, n).

Tai visų pirma reiškia, kad norint sumažinti trupmeną į neredukuojamą formą, jos skaitiklį ir vardiklį reikia padalyti iš jų gcd.

Didžiausias bendras skaičių daliklis m Ir n gali būti apibrėžtas kaip mažiausias teigiamas visų jų linijinių derinių aibės elementas:

ir todėl vaizduoja kaip tiesinę skaičių kombinaciją m Ir n:

Šis santykis vadinamas Bezouto santykis, ir koeficientus u Ir v — bezout koeficientai. Bézout koeficientai yra efektyviai apskaičiuojami išplėstiniu Euklido algoritmu. Šis teiginys apibendrintas natūraliųjų skaičių aibėms – jo reikšmė ta, kad aibės sugeneruotas grupės pogrupis yra ciklinis ir yra generuojamas vieno elemento: gcd ( a 1 , a 2 , … , a n).

Didžiausio bendrojo daliklio (gcd) apskaičiavimas.

Veiksmingi dviejų skaičių gcd apskaičiavimo būdai yra Euklido algoritmas Ir dvejetainisalgoritmas. Be to, GCD reikšmė ( m,n) galima nesunkiai apskaičiuoti, jei žinomas skaičių kanoninis išplėtimas m Ir n pagrindiniai veiksniai:

kur yra skirtingi pirminiai skaičiai ir ir yra neneigiami sveikieji skaičiai (jie gali būti lygūs nuliui, jei atitinkamo pirminio skaičiaus nėra skaidyme). Tada gcd ( m,n) ir LCM ( m,n) išreiškiami formulėmis:

Jei yra daugiau nei du skaičiai: , jų GCD randamas pagal šį algoritmą:

- tai norimas GCD.

Be to, norint rasti didžiausias bendras daliklis, galite išskaidyti kiekvieną iš pateiktų skaičių į pirminius veiksnius. Tada atskirai išrašykite tik tuos veiksnius, kurie yra įtraukti į visus pateiktus skaičius. Tada padauginame išrašytus skaičius tarpusavyje - daugybos rezultatas yra didžiausias bendras daliklis .

Žingsnis po žingsnio išanalizuokime didžiausio bendro daliklio apskaičiavimą:

1. Išskaidykite skaičių daliklius į pirminius veiksnius:

Skaičiavimai patogiai rašomi naudojant vertikalią juostą. Į kairę nuo eilutės pirmiausia užrašykite dividendą, dešinėje - daliklį. Toliau kairiajame stulpelyje užrašome privačias reikšmes. Iš karto paaiškinkime pavyzdžiu. Suskaidykime skaičius 28 ir 64 į pirminius koeficientus.

2. Abiejuose skaičiuose pabrėžiame tuos pačius pirminius veiksnius:

28 = 2 . 2 . 7

64 = 2 . 2 . 2 . 2 . 2 . 2

3. Randame identiškų pirminių veiksnių sandaugą ir užrašome atsakymą:

GCD (28; 64) = 2. 2 = 4

Atsakymas: GCD (28; 64) = 4

GCD vietą galite išdėstyti dviem būdais: stulpelyje (kaip buvo padaryta aukščiau) arba „eilėje“.

Pirmasis būdas parašyti GCD:

Raskite GCD 48 ir 36.

GCD (48; 36) = 2. 2. 3 = 12

Antrasis GCD rašymo būdas:

Dabar parašykime GCD paieškos sprendimą eilutėje. Raskite GCD 10 ir 15.

D(10) = (1, 2, 5, 10)

D(15) = (1, 3, 5, 15)

D(10, 15) = (1, 5)

Šis straipsnis skirtas tokiam klausimui kaip didžiausio bendro daliklio paieška. Pirmiausia paaiškinsime, kas tai yra, ir pateiksime kelis pavyzdžius, supažindinsime su didžiausio bendro 2, 3 ar daugiau skaičių daliklio apibrėžimais, po kurių pasiliksime ties bendromis šios sąvokos savybėmis ir jas įrodysime.

Yandex.RTB R-A-339285-1

Kas yra bendrieji dalikliai

Norėdami suprasti, kas yra didžiausias bendras daliklis, pirmiausia suformuluojame, kas yra bendras sveikųjų skaičių daliklis.

Straipsnyje apie kartotinius ir daliklius sakėme, kad sveikas skaičius visada turi kelis daliklius. Čia mus domina tam tikro skaičiaus sveikųjų skaičių dalikliai, ypač bendri (identiški) visiems. Užrašykime pagrindinį apibrėžimą.

1 apibrėžimas

Bendrasis kelių sveikųjų skaičių daliklis bus skaičius, kuris gali būti kiekvieno skaičiaus iš nurodytos aibės daliklis.

1 pavyzdys

Štai tokio daliklio pavyzdžiai: trigubas bus bendras skaičių - 12 ir 9 daliklis, nes lygybės 9 = 3 · 3 ir − 12 = 3 · (− 4) yra teisingos. Skaičiai 3 ir - 12 turi kitus bendrus daliklius, tokius kaip 1 , - 1 ir - 3 . Paimkime kitą pavyzdį. Keturi sveikieji skaičiai 3, −11, −8 ir 19 turės du bendrus daliklius: 1 ir -1.

Žinodami dalijamumo savybes, galime teigti, kad bet kurį sveikąjį skaičių galima padalyti iš vieneto ir atėmus vienetą, o tai reiškia, kad bet kuri sveikųjų skaičių aibė jau turės bent du bendruosius daliklius.

Taip pat atkreipkite dėmesį, kad jei turime bendrą kelių skaičių b daliklį, tada tuos pačius skaičius galima padalyti iš priešingo skaičiaus, tai yra iš - b. Iš esmės galime imti tik teigiamus daliklius, tada visi bendrieji dalikliai taip pat bus didesni už 0 . Šis metodas taip pat gali būti taikomas, tačiau nereikėtų visiškai ignoruoti neigiamų skaičių.

Kas yra didžiausias bendras daliklis (gcd)

Pagal dalijamumo savybes, jei b yra sveikojo skaičiaus a, kuris nėra lygus 0, daliklis, tada b modulis negali būti didesnis už modulį a, taigi bet koks skaičius, nelygus 0, turi baigtinį daliklių skaičių. . Tai reiškia, kad kelių sveikųjų skaičių, iš kurių bent vienas skiriasi nuo nulio, bendrųjų daliklių skaičius taip pat bus baigtinis, o iš visos jų aibės visada galime pasirinkti didžiausią skaičių (apie sąvoką didžiausias ir mažiausius sveikuosius skaičius, patariame pakartoti pateiktą medžiagą).

Tolesniuose samprotavimuose darysime prielaidą, kad bent viena iš skaičių aibės, kuriai reikia rasti didžiausią bendrąjį daliklį, skirsis nuo 0 . Jei jie visi lygūs 0 , tai jų daliklis gali būti bet koks sveikasis skaičius, o kadangi jų yra be galo daug, negalime pasirinkti didžiausio. Kitaip tariant, skaičių, lygių 0, neįmanoma rasti didžiausio bendro daliklio.

Mes pereiname prie pagrindinio apibrėžimo formulavimo.

2 apibrėžimas

Didžiausias bendras kelių skaičių daliklis yra didžiausias sveikasis skaičius, dalijantis visus tuos skaičius.

Raštu didžiausias bendras daliklis dažniausiai žymimas santrumpa GCD. Dviejų skaičių atveju jis gali būti parašytas kaip gcd (a, b) .

2 pavyzdys

Koks yra dviejų sveikųjų skaičių GCD pavyzdys? Pavyzdžiui, 6 ir -15 būtų 3. Pagrįskime tai. Pirmiausia užrašome visus šešių daliklius: ± 6, ± 3, ± 1, o tada visus penkiolikos daliklius: ± 15, ± 5, ± 3 ir ± 1. Po to pasirenkame bendruosius: tai − 3 , − 1 , 1 ir 3 . Iš jų reikia pasirinkti didžiausią skaičių. Tai bus 3.

Trims ar daugiau skaičių didžiausio bendro daliklio apibrėžimas bus beveik toks pat.

3 apibrėžimas

Didžiausias bendras trijų ar daugiau skaičių daliklis yra didžiausias sveikasis skaičius, dalijantis visus tuos skaičius tuo pačiu metu.

Skaičiams a 1 , a 2 , … , a n daliklis patogiai žymimas kaip GCD (a 1 , a 2 , … , a n). Pati daliklio reikšmė užrašoma kaip GCD (a 1 , a 2 , … , a n) = b .

3 pavyzdys

Štai kelių sveikųjų skaičių didžiausio bendro daliklio pavyzdžiai: 12 , - 8 , 52 , 16 . Jis bus lygus keturiems, o tai reiškia, kad galime parašyti, kad gcd (12, - 8, 52, 16) = 4.

Šio teiginio teisingumą galite patikrinti užrašydami visus šių skaičių daliklius ir pasirinkę didžiausią iš jų.

Praktikoje dažnai pasitaiko atvejų, kai didžiausias bendras daliklis yra lygus vienam iš skaičių. Taip atsitinka, kai visus kitus skaičius galima padalyti iš nurodyto skaičiaus (pirmoje straipsnio pastraipoje mes pateikėme šio teiginio įrodymą).

4 pavyzdys

Taigi, didžiausias bendras skaičių 60, 15 ir - 45 daliklis yra 15, nes penkiolika dalijasi ne tik iš 60 ir - 45, bet ir iš savęs, o didesnio visų šių skaičių daliklio nėra.

Kopirminiai skaičiai yra ypatingas atvejis. Jie yra sveikieji skaičiai, kurių didžiausias bendras daliklis yra 1.

Pagrindinės GCD savybės ir Euklido algoritmas

Didžiausias bendras daliklis turi keletą būdingų savybių. Jas formuluojame teoremų pavidalu ir kiekvieną iš jų įrodome.

Atkreipkite dėmesį, kad šios savybės yra suformuluotos sveikiesiems skaičiams, didesniems už nulį, ir mes atsižvelgiame tik į teigiamus daliklius.

4 apibrėžimas

Skaičiai a ir b turi didžiausią bendrąjį daliklį, lygų gcd b ir a , ty gcd (a , b) = gcd (b , a) . Skaičių vietų keitimas galutiniam rezultatui įtakos neturi.

Ši savybė išplaukia iš paties GCD apibrėžimo ir jai nereikia įrodymų.

5 apibrėžimas

Jei skaičių a galima padalyti iš skaičiaus b, tai šių dviejų skaičių bendrųjų daliklių aibė bus panaši į skaičiaus b daliklių aibę, tai yra, gcd (a, b) = b.

Įrodykime šį teiginį.

1 įrodymas

Jei skaičiai a ir b turi bendrus daliklius, tai bet kurį iš jų galima padalyti iš jų. Tuo pačiu metu, jei a yra b kartotinis, tai bet kuris b daliklis taip pat bus a daliklis, nes dalijamumas turi tokią savybę kaip tranzityvumas. Taigi bet koks daliklis b bus bendras skaičiams a ir b. Tai įrodo, kad jei galime padalinti a iš b , tai visų abiejų skaičių daliklių aibė sutampa su vieno skaičiaus b daliklių aibe. O kadangi didžiausias bet kurio skaičiaus daliklis yra pats skaičius, tai didžiausias skaičių a ir b bendras daliklis taip pat bus lygus b, t.y. gcd(a, b) = b. Jei a = b , tada gcd (a , b) = gcd (a , a) = gcd (b , b) = a = b , pvz., gcd (132 , 132) = 132 .

Naudodamiesi šia savybe, galime rasti didžiausią bendrą dviejų skaičių daliklį, jei vieną iš jų galima padalyti iš kito. Toks daliklis yra lygus vienam iš šių dviejų skaičių, iš kurio galima padalyti antrąjį skaičių. Pavyzdžiui, gcd (8, 24) = 8, nes 24 yra aštuonių kartotinis.

6 apibrėžimas 2 įrodymas

Pabandykime įrodyti šią savybę. Iš pradžių turime lygybę a = b q + c , o bet kuris bendras a ir b daliklis taip pat dalins c , o tai paaiškinama atitinkama dalijamumo savybe. Todėl bet kuris bendras b ir c daliklis dalins a . Tai reiškia, kad bendrųjų daliklių a ir b aibė sutaps su daliklių b ir c aibe, įskaitant didžiausią iš jų, o tai reiškia, kad lygybė gcd (a, b) = gcd (b, c) yra teisinga.

7 apibrėžimas

Ši savybė vadinama Euklido algoritmu. Su juo galite apskaičiuoti didžiausią bendrą dviejų skaičių daliklį, taip pat įrodyti kitas GCD savybes.

Prieš formuluojant savybę, patariame pakartoti teoremą, kurią įrodėme straipsnyje apie padalijimą su liekana. Pagal jį dalijamasis skaičius a gali būti pavaizduotas kaip bq + r, o čia b yra daliklis, q yra koks nors sveikasis skaičius (dar vadinamas nepilnuoju koeficientu), o r yra liekana, tenkinanti sąlygą 0 ≤ r ≤ b.

Tarkime, kad turime du sveikuosius skaičius, didesnius už 0, kuriems bus teisingos šios lygybės:

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

Šios lygybės baigiasi, kai r k + 1 tampa lygios 0 . Taip tikrai atsitiks, nes seka b > r 1 > r 2 > r 3 , … yra mažėjančių sveikųjų skaičių serija, kuri gali apimti tik baigtinį skaičių. Vadinasi, r k yra didžiausias bendras a ir b daliklis, tai yra, r k = gcd (a , b) .

Pirmiausia reikia įrodyti, kad r k yra bendras skaičių a ir b daliklis, o po to, kad r k yra ne tik daliklis, o didžiausias bendras dviejų pateiktų skaičių daliklis.

Pažvelkime į aukščiau esantį lygybių sąrašą iš apačios į viršų. Pagal paskutinę lygybę,
r k − 1 galima padalyti iš r k . Remiantis šiuo faktu, kaip ir anksčiau įrodyta didžiausio bendro daliklio savybe, galima teigti, kad r k − 2 galima padalyti iš r k , nes
r k − 1 dalijasi iš r k, o r k dalijasi iš r k .

Trečioji lygybė iš apačios leidžia daryti išvadą, kad r k − 3 galima padalyti iš r k ir pan. Antrasis iš apačios yra tas, kad b dalijasi iš r k, o pirmasis – kad a dalijasi iš r k. Iš viso to darome išvadą, kad r k yra bendras a ir b daliklis.

Dabar įrodykime, kad r k = gcd (a , b) . Ką man reikia daryti? Parodykite, kad bet kuris bendras a ir b daliklis dalins r k . Pažymėkime jį r 0 .

Pažiūrėkime į tą patį lygybių sąrašą, bet iš viršaus į apačią. Remiantis ankstesne savybe, galime daryti išvadą, kad r 1 dalijasi iš r 0, tai reiškia, kad pagal antrąją lygybę r 2 dalijasi iš r 0. Einame per visas lygybes ir iš paskutinės darome išvadą, kad r k dalijasi iš r 0 . Todėl r k = gcd (a , b) .

Įvertinę šią savybę, darome išvadą, kad a ir b bendrųjų daliklių aibė yra panaši į šių skaičių gcd daliklių aibę. Šis teiginys, kuris yra Euklido algoritmo pasekmė, leis mums apskaičiuoti visus bendruosius dviejų pateiktų skaičių daliklius.

Pereikime prie kitų savybių.

8 apibrėžimas

Jei a ir b yra sveikieji skaičiai, nelygūs 0, tai turi būti dar du sveikieji skaičiai u 0 ir v 0, kuriems galios lygybė gcd (a , b) = a · u 0 + b · v 0.

Savybės teiginyje pateikta lygybė yra tiesinis didžiausio bendro a ir b daliklio atvaizdas. Jis vadinamas Bezout koeficientu, o skaičiai u 0 ir v 0 vadinami Bezout koeficientais.

3 įrodymas

Įrodykime šią savybę. Lygybių seką užrašome pagal Euklido algoritmą:

Pirmoji lygybė mums sako, kad r 1 = a − b · q 1 . Pažymėkite 1 = s 1 ir − q 1 = t 1 ir perrašykite šią lygybę į r 1 = s 1 · a + t 1 · b . Čia skaičiai s 1 ir t 1 bus sveikieji skaičiai. Antroji lygybė leidžia daryti išvadą, kad 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 . Pažymėkite − s 1 q 2 = s 2 ir 1 − t 1 q 2 = t 2 ir perrašykite lygybę į r 2 = s 2 a + t 2 b , kur s 2 ir t 2 taip pat bus sveikieji skaičiai. Taip yra todėl, kad sveikųjų skaičių suma, jų sandauga ir skirtumas taip pat yra sveikieji skaičiai. Lygiai taip pat iš trečiosios lygybės gauname r 3 = s 3 · a + t 3 · b , iš šios r 4 = s 4 · a + t 4 · b ir t.t. Galiausiai darome išvadą, kad r k = s k a + t k b sveikiesiems skaičiams s k ir t k . Kadangi rk \u003d GCD (a, b) , žymime sk \u003d u 0 ir tk \u003d v 0. Dėl to galime gauti linijinį GCD vaizdą reikiama forma: GCD (a, b) \u003d au 0 + bv 0.

9 apibrėžimas

gcd (m a, m b) = m gcd (a, b) bet kuriai gamtinei vertei m.

4 įrodymas

Šią savybę galima pateisinti taip. Padauginkite iš skaičiaus m abi kiekvienos lygybės Euklido algoritme puses ir gausime, kad gcd (m a , m b) = m r k , o r k yra gcd (a , b) . Vadinasi, gcd (m a, m b) = m gcd (a, b) . Būtent ši didžiausio bendro daliklio savybė naudojama ieškant GCD faktorizavimo metodu.

10 apibrėžimas

Jei skaičiai a ir b turi bendrą daliklį p , tai gcd (a: p , b: p) = gcd (a , b) : p . Tuo atveju, kai p = gcd (a , b) gauname gcd (a: gcd (a , b) , b: gcd (a , b) = 1, todėl skaičiai a: gcd (a , b) ir b : gcd (a , b) yra pirminiai.

Kadangi a = p (a: p) ir b = p (b: p) , tai remiantis ankstesne savybe, galime sukurti gcd (a , b) = gcd (p (a: p) formos lygybes, p · (b: p)) = p · GCD (a: p , b: p) , tarp kurių bus ir šios savybės įrodymas. Šį teiginį naudojame, kai įprastąsias trupmenas redukuojame į neredukuojamą formą.

11 apibrėžimas

Didžiausias bendras daliklis a 1 , a 2 , ... , ak bus skaičius dk , kurį galima rasti paeiliui apskaičiuojant gcd (a 1 , a 2) = d 2 , gcd (d 2 , a 3) = d 3 , gcd (d 3 , a 4) = d 4 , … , gcd (dk - 1 , ak) = dk .

Ši savybė naudinga ieškant didžiausio bendro trijų ar daugiau skaičių daliklio. Su juo galite sumažinti šį veiksmą iki operacijų su dviem skaičiais. Jos pagrindas yra Euklido algoritmo išplaukimas: jei bendrųjų daliklių a 1, a 2 ir a 3 aibė sutampa su aibėmis d 2 ir a 3 , tai ji taip pat sutampa su dalikliais d 3 . Skaičių a 1 , a 2 , a 3 ir a 4 dalikliai sutaps su d 3 dalikliais, vadinasi, jie sutaps ir su d 4 dalikliais ir pan. Galų gale gauname, kad bendrieji skaičių a 1 , a 2 , … , ak dalikliai sutaps su dalikliais dk , o kadangi pats skaičius bus didžiausias skaičiaus dk daliklis, tada gcd (a 1 , a 2 , … , ak) = dk .

Tai viskas, ką norėtume pakalbėti apie didžiausio bendro daliklio savybes.

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