Si lidhen nyjet dhe nyjet? Gjetja e GCD duke përdorur algoritmin e Euklidit dhe duke përdorur faktorizimin e thjeshtë

Për të mësuar se si të gjeni pjesëtuesin më të madh të përbashkët të dy ose më shumë numrave, duhet të kuptoni se çfarë janë numrat natyrorë, të thjeshtë dhe kompleksë.

Një numër natyror është çdo numër që përdoret për të numëruar numra të plotë.

Nëse një numër natyror mund të ndahet vetëm me vetveten dhe një, atëherë ai quhet i thjeshtë.

Të gjithë numrat natyrorë mund të pjesëtohen nga vetvetja dhe një, por i vetmi numër i thjeshtë çift është 2, të gjithë të tjerët mund të pjesëtohen me dy. Prandaj, vetëm numrat tek mund të jenë të thjeshtë.

Shumë numra të thjeshtë listën e plotë ato nuk ekzistojnë. Për të gjetur GCD, është e përshtatshme të përdorni tabela speciale me numra të tillë.

Shumica numrat natyrorë mund të ndahen jo vetëm me një, vetveten, por edhe me numra të tjerë. Kështu, për shembull, numri 15 mund të ndahet me 3 dhe 5. Të gjithë quhen pjesëtues të numrit 15.

Kështu, pjesëtuesi i çdo A është numri me të cilin mund të ndahet pa mbetje. Nëse një numër ka më shumë se dy pjesëtues natyrorë, ai quhet i përbërë.

Numri 30 ka pjesëtues të tillë si 1, 3, 5, 6, 15, 30.

Ju mund të shihni se 15 dhe 30 kanë pjesëtues të njëjtë 1, 3, 5, 15. Pjesëtuesi më i madh i përbashkët i këtyre dy numrave është 15.

Kështu, pjesëtuesi i përbashkët i numrave A dhe B është numri me të cilin mund t'i ndani plotësisht. Maksimumi mund të konsiderohet maksimumi numri total në të cilat mund të ndahen.

Për të zgjidhur problemet, përdoret mbishkrimi i shkurtuar i mëposhtëm:

GCD (A; B).

Për shembull, GCD (15; 30) = 30.

Për të shkruar të gjithë pjesëtuesit e një numri natyror, përdoret shënimi:

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

gcd (9; 15) = 1

AT ky shembull Numrat natyrorë kanë vetëm një pjesëtues të përbashkët. Ata quhen coprime, përkatësisht, njësia është pjesëtuesi i tyre më i madh i përbashkët.

Si të gjeni pjesëtuesin më të madh të përbashkët të numrave

Për të gjetur GCD të disa numrave, ju duhet:

Gjeni veçmas të gjithë pjesëtuesit e secilit numër natyror, pra zbërthejini në faktorë (numra të thjeshtë);

Zgjidhni të gjithë faktorët e njëjtë për numrat e dhënë;

Shumëzojini ato së bashku.

Për shembull, për të llogaritur pjesëtuesin më të madh të përbashkët të 30 dhe 56, do të shkruani sa vijon:

Për të mos u ngatërruar me , është e përshtatshme të shkruani shumëzuesit duke përdorur kolona vertikale. Në anën e majtë të vijës, duhet të vendosni dividentin, dhe në të djathtë - pjesëtuesin. Nën dividentin, duhet të tregoni koeficientin që rezulton.

Pra, në kolonën e djathtë do të jenë të gjithë faktorët e nevojshëm për zgjidhjen.

Pjesëtuesit identikë (faktorët e gjetur) mund të nënvizohen për lehtësi. Ato duhet të rishkruhen dhe shumëzohen dhe pjesëtuesi më i madh i përbashkët duhet të shkruhet.

GCD (30; 56) = 2 * 5 = 10

Është vërtet kaq e thjeshtë të gjesh pjesëtuesin më të madh të përbashkët të numrave. Me pak praktikë, mund ta bëni pothuajse automatikisht.

Shumë pjesëtues

Shqyrtoni problemin e mëposhtëm: gjeni pjesëtuesin e numrit 140. Është e qartë se numri 140 nuk ka një pjesëtues, por disa. Në raste të tilla, thuhet se detyra ka një tufë me Zgjidhjet. Le t'i gjejmë të gjitha. Para së gjithash, le ta zbërthejmë këtë numër në faktorët kryesorë:

140 = 2 ∙ 2 ∙ 5 ∙ 7.

Tani mund të shkruajmë lehtësisht të gjithë pjesëtuesit. Le të fillojmë me pjesëtuesit e thjeshtë, domethënë ata që janë të pranishëm në zgjerimin e mësipërm:

Pastaj shkruajmë ato që fitohen nga shumëzimi në çift i pjesëtuesve të thjeshtë:

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

Pastaj - ato që përmbajnë tre pjesëtues të thjeshtë:

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

Së fundi, të mos harrojmë njësinë dhe vetë numrin e zbërthyeshëm:

Të gjithë pjesëtuesit e gjetur nga ne formojnë një tufë me pjesëtuesit e numrit 140, i cili është shkruar duke përdorur kllapa kaçurrelë:

Bashkësia e pjesëtuesve të numrit 140 =

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

Për lehtësinë e perceptimit, ne kemi shkruar pjesëtuesit këtu ( elementet e vendosur) në rend rritës, por në përgjithësi, kjo nuk është e nevojshme. Përveç kësaj, ne prezantojmë një shkurtim. Në vend të "Bashkësia e pjesëtuesve të numrit 140" do të shkruajmë "D (140)". Kështu,

Në mënyrë të ngjashme, mund të gjendet bashkësia e pjesëtuesve për çdo numër tjetër natyror. Për shembull, nga dekompozimi

105 = 3 ∙ 5 ∙ 7

marrim:

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

Nga bashkësia e të gjithë pjesëtuesve, duhet dalluar bashkësia e pjesëtuesve të thjeshtë, të cilët për numrat 140 dhe 105 janë përkatësisht të barabartë:

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

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

Duhet theksuar se në zbërthimin e numrit 140 në faktorë të thjeshtë dy është i pranishëm dy herë, ndërsa në bashkësinë PD(140) është vetëm një. Bashkësia e PD(140) është, në thelb, të gjitha përgjigjet e problemit: "Gjeni një faktor kryesor të numrit 140". Është e qartë se e njëjta përgjigje nuk duhet të përsëritet më shumë se një herë.

Reduktimi i fraksionit. Pjesëtuesi më i madh i përbashkët

Konsideroni një fraksion

Ne e dimë se kjo thyesë mund të zvogëlohet me një numër që është edhe pjesëtues i numëruesit (105) dhe pjesëtues i emëruesit (140). Le të shohim grupet D(105) dhe D(140) dhe të shkruajmë elementet e tyre të përbashkëta.

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

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

Elementet e përbashkëta të bashkësive D(105) dhe D(140) =

Barazia e fundit mund të shkruhet më e shkurtër, domethënë:

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

Këtu, shenja speciale "∩" ("çantë me vrimën poshtë") vetëm tregon atë nga dy grupet e shkruara sipas anët e ndryshme prej tij, ju duhet të zgjidhni vetëm elementë të zakonshëm. Hyrja "D (105) ∩ D (140)" thotë " kryqëzim grupe Te nga 105 dhe Te nga 140.

[Vini re gjatë rrugës se mund të kryeni operacione të ndryshme binare me grupe, pothuajse si me numrat. Një tjetër operacion binar i zakonshëm është Bashkimi, e cila tregohet me ikonën "∪" ("çantë me vrimën lart"). Bashkimi i dy grupeve përfshin të gjithë elementët e të dy grupeve:

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

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

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

Pra, zbuluam se fraksioni

mund të reduktohet në cilindo nga numrat që i përkasin grupit

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

dhe nuk mund të reduktohet me asnjë numër tjetër natyror. Kjo eshte e gjitha mënyrat e mundshme reduktime (me përjashtim të reduktimit jo interesant me një):

Është e qartë se është më praktike të zvogëlohet thyesa me një numër, nëse është e mundur, një më të madh. Në këtë rast, është numri 35, i cili thuhet se është pjesëtuesi më i madh i përbashkët (GCD) numrat 105 dhe 140. Kjo shkruhet si

gcd(105, 140) = 35.

Megjithatë, në praktikë, nëse na jepen dy numra dhe duhet të gjejmë pjesëtuesin e tyre më të madh të përbashkët, nuk kemi pse të ndërtojmë fare bashkësi. Mjafton thjesht të faktorizohen të dy numrat në faktorë të thjeshtë dhe të nënvizohen ata nga këta faktorë që janë të përbashkët për të dy faktorizimet, për shembull:

105 = 3 ∙ 5 ∙ 7 ;

140 = 2 ∙ 2 ∙ 5 ∙ 7 .

Duke shumëzuar numrat e nënvizuar (në cilindo nga zgjerimet), marrim:

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

Sigurisht, është e mundur që të ketë më shumë se dy faktorë të nënvizuar:

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

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

Nga këtu është e qartë se

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

Përmendja e veçantë meriton situatën kur nuk ka fare faktorë të përbashkët dhe nuk ka asgjë për të theksuar, për shembull:

42 = 2 ∙ 3 ∙ 7;

Në këtë rast,

gcd(42, 55) = 1.

Quhen dy numra natyrorë për të cilët gcd është e barabartë me një coprime. Nëse bëni një thyesë nga numra të tillë, për shembull,

atëherë një thyesë e tillë është e pareduktueshme.

Në përgjithësi, rregulli për zvogëlimin e thyesave mund të shkruhet si më poshtë:

Këtu supozohet se a dhe b janë numra natyrorë dhe të gjitha thyesat janë pozitive. Nëse tani caktojmë një shenjë minus për të dy anët e kësaj barazie, marrim rregullin përkatës për thyesat negative.

Mbledhja dhe zbritja e thyesave. Shumëfishi më pak i zakonshëm

Supozoni se doni të llogaritni shumën e dy thyesave:

Ne tashmë e dimë se si emëruesit zbërthehen në faktorët kryesorë:

105 = 3 ∙ 5 ∙ 7 ;

140 = 2 ∙ 2 ∙ 5 ∙ 7 .

Nga ky zbërthim del menjëherë se, për t'i sjellë thyesat në një emërues të përbashkët, mjafton të shumëzojmë numëruesin dhe emëruesin e thyesës së parë me 2 ∙ 2 (produkti i faktorëve kryesorë të patheksuar të emëruesit të dytë), dhe numëruesi dhe emëruesi i thyesës së dytë me 3 (“produkt” faktorët e thjeshtë të pa nënvizuar të emëruesit të parë). Si rezultat, emëruesit e të dy thyesave do të bëhen të barabartë me një numër që mund të përfaqësohet si më poshtë:

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

Është e lehtë të shihet se të dy emëruesit origjinal (të dy 105 dhe 140) janë pjesëtues të numrit 420, dhe numri 420, nga ana tjetër, është një shumëfish i të dy emëruesve - dhe jo vetëm një shumëfish, ai është shumëfishi më pak i zakonshëm (NOC) numrat 105 dhe 140. Kjo është shkruar kështu:

LCM(105, 140) = 420.

Duke parë më nga afër zgjerimin e numrave 105 dhe 140, shohim se

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

Në mënyrë të ngjashme, për numrat natyrorë arbitrarë b dhe d:

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

Tani le të plotësojmë përmbledhjen e thyesave tona:

Por shumë numra natyrorë janë të pjesëtueshëm në mënyrë të barabartë me numra të tjerë natyrorë.

për shembull:

Numri 12 pjesëtohet me 1, me 2, me 3, me 4, me 6, me 12;

Numri 36 pjesëtohet me 1, me 2, me 3, me 4, me 6, me 12, me 18, me 36.

Numrat me të cilët pjesëtohet numri (për 12 është 1, 2, 3, 4, 6 dhe 12) quhen pjesëtuesit e numrave. Pjesëtues i një numri natyror aështë numri natyror që pjesëton numrin e dhënë a pa lënë gjurmë. Një numër natyror që ka më shumë se dy faktorë quhet të përbëra. Vini re se numrat 12 dhe 36 kanë pjesëtues të përbashkët. Këta janë numrat: 1, 2, 3, 4, 6, 12. Pjesëtuesi më i madh i këtyre numrave është 12.

Pjesëtues i përbashkët i dy numrave të dhënë a dhe bështë numri me të cilin të dy numrat e dhënë janë të pjesëtueshëm pa mbetje a dhe b. Pjesëtues i përbashkët i numrave të shumëfishtë (GCD)është numri që shërben si pjesëtues për secilën prej tyre.

Shkurtimisht pjesëtuesi më i madh i përbashkët i numrave a dhe b janë shkruar kështu:

Shembull: gcd (12; 36) = 12.

Pjesëtuesit e numrave në shënimin e zgjidhjes shënojnë shkronje e madhe"D".

Shembull:

gcd (7; 9) = 1

Numrat 7 dhe 9 kanë vetëm një pjesëtues të përbashkët - numrin 1. Numrat e tillë quhen coprimechi slam.

Numrat e dyfishtë janë numra natyrorë që kanë vetëm një pjesëtues të përbashkët - numrin 1. Gcd e tyre është 1.

Pjesëtuesi më i madh i përbashkët (GCD), vetitë.

• Vetia kryesore: pjesëtuesi më i madh i përbashkët m dhe nështë i pjesëtueshëm me çdo pjesëtues të përbashkët të këtyre numrave. Shembull: për numrat 12 dhe 18 pjesëtuesi më i madh i përbashkët është 6; është i pjesëtueshëm me të gjithë pjesëtuesit e zakonshëm të këtyre numrave: 1, 2, 3, 6.
• Përfundimi 1: grup pjesëtuesish të përbashkët m dhe n përkon me bashkësinë e pjesëtuesve gcd( m, n).
• Përfundimi 2: grup shumëfishësh të përbashkët m dhe n përkon me grupin e LCM-ve të shumta ( m, n).

Kjo do të thotë, në veçanti, që për të reduktuar një thyesë në një formë të pakalueshme, është e nevojshme të ndahet numëruesi dhe emëruesi i saj me gcd-në e tyre.

• Pjesëtuesi më i madh i përbashkët i numrave m dhe n mund të përkufizohet si elementi më i vogël pozitiv i grupit të të gjitha kombinimeve të tyre lineare:

dhe për këtë arsye përfaqësojnë si një kombinim linear i numrave m dhe n:

Ky raport quhet raporti i Bezout, dhe koeficientët u dhe v — koeficientët bezout. Koeficientët Bézout llogariten në mënyrë efikase nga algoritmi i zgjeruar i Euklidit. Kjo deklaratë përgjithësohet në grupe të numrave natyrorë - kuptimi i saj është se nëngrupi i grupit të krijuar nga grupi është ciklik dhe gjenerohet nga një element: gcd ( a 1 , a 2 , … , a n).

Llogaritja e pjesëtuesit më të madh të përbashkët (gcd).

Mënyrat efikase për të llogaritur gcd-në e dy numrave janë Algoritmi i Euklidit dhe binarealgoritmi. Përveç kësaj, vlera GCD ( m,n) mund të llogaritet lehtësisht nëse dihet zgjerimi kanonik i numrave m dhe n për faktorët kryesorë:

ku janë numrat e thjeshtë të dallueshëm dhe dhe janë numra të plotë jo negativ (ato mund të jenë zero nëse numri i thjeshtë përkatës nuk është në zbërthim). Pastaj gcd ( m,n) dhe LCM ( m,n) shprehen me formulat:

Nëse ka më shumë se dy numra: , GCD e tyre gjendet sipas algoritmit të mëposhtëm:

- kjo është GCD e dëshiruar.

Gjithashtu, për të gjetur pjesëtuesi më i madh i përbashkët, secilin nga numrat e dhënë mund ta zbërtheni në faktorë të thjeshtë. Pastaj shkruani veçmas vetëm ata faktorë që përfshihen në të gjithë numrat e dhënë. Pastaj ne shumëzojmë numrat e shkruar ndërmjet tyre - rezultati i shumëzimit është pjesëtuesi më i madh i përbashkët .

Le të analizojmë hap pas hapi llogaritjen e pjesëtuesit më të madh të përbashkët:

1. Zbërthejini pjesëtuesit e numrave në faktorë të thjeshtë:

Llogaritjet shkruhen me lehtësi duke përdorur një shirit vertikal. Në të majtë të rreshtit, së pari shkruani dividentin, në të djathtë - pjesëtuesin. Më tej në kolonën e majtë shkruajmë vlerat e privates. Le të shpjegojmë menjëherë me një shembull. Le të faktorizojmë numrat 28 dhe 64 në faktorë të thjeshtë.

2. Nënvizojmë të njëjtët faktorë kryesorë në të dy numrat:

28 = 2 . 2 . 7

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

3. Gjejmë produktin e faktorëve të thjeshtë identikë dhe shkruajmë përgjigjen:

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

Përgjigje: GCD (28; 64) = 4

Ju mund të rregulloni vendndodhjen e GCD në dy mënyra: në një kolonë (siç u bë më lart) ose "në një rresht".

Mënyra e parë për të shkruar GCD:

Gjeni GCD 48 dhe 36.

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

Mënyra e dytë për të shkruar GCD:

Tani le të shkruajmë zgjidhjen e kërkimit GCD në një rresht. Gjeni GCD 10 dhe 15.

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

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

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

Ky artikull i kushtohet një pyetjeje të tillë si gjetja e pjesëtuesit më të madh të përbashkët. Së pari, do të shpjegojmë se çfarë është dhe do të japim disa shembuj, do të prezantojmë përkufizimet e pjesëtuesit më të madh të përbashkët të 2, 3 ose më shumë numrave, pas së cilës do të ndalemi në vetitë e përgjithshme këtë koncept dhe vërtetojini ato.

Yandex.RTB R-A-339285-1

Cilët janë pjesëtuesit e përbashkët

Për të kuptuar se cili është pjesëtuesi më i madh i përbashkët, fillimisht ne formulojmë se çfarë është një pjesëtues i përbashkët për numrat e plotë.

Në artikullin mbi shumëfishat dhe pjesëtuesit, thamë se një numër i plotë ka gjithmonë pjesëtues të shumëfishtë. Këtu na interesojnë pjesëtuesit e një numri të caktuar numrash të plotë menjëherë, veçanërisht të zakonshëm (identikë) për të gjithë. Le të shkruajmë përkufizimin kryesor.

Përkufizimi 1

Pjesëtuesi i përbashkët i disa numrave të plotë do të jetë një numër që mund të jetë pjesëtues i secilit numër nga grupi i specifikuar.

Shembulli 1

Këtu janë shembuj të një pjesëtuesi të tillë: trefishi do të jetë një pjesëtues i përbashkët për numrat - 12 dhe 9, pasi barazitë 9 = 3 · 3 dhe − 12 = 3 · (− 4) janë të vërteta. Numrat 3 dhe - 12 kanë pjesëtues të tjerë të përbashkët, si 1 , - 1 dhe - 3 . Le të marrim një shembull tjetër. Katër numrat e plotë 3 , − 11 , − 8 dhe 19 do të kenë dy pjesëtues të përbashkët: 1 dhe - 1 .

Duke ditur vetitë e pjesëtueshmërisë, mund të themi se çdo numër i plotë mund të ndahet me një dhe minus një, që do të thotë se çdo grup numrash të plotë do të ketë tashmë të paktën dy pjesëtues të përbashkët.

Gjithashtu vini re se nëse kemi një pjesëtues b të përbashkët për disa numra, atëherë të njëjtët numra mund të pjesëtohen me numër i kundërt, pra më - b . Në parim, ne mund të marrim vetëm pjesëtues pozitivë, atëherë të gjithë pjesëtuesit e zakonshëm do të jenë gjithashtu më të mëdhenj se 0. Kjo qasje gjithashtu mund të përdoret, por të injorohet plotësisht numrat negativë mos e bej.

Cili është pjesëtuesi më i madh i përbashkët (gcd)

Sipas vetive të pjesëtueshmërisë, nëse b është pjesëtues i një numri të plotë a që nuk është i barabartë me 0, atëherë moduli i b nuk mund të jetë më i madh se moduli i a, prandaj çdo numër jo i barabartë me 0 ka një numër të fundëm pjesëtuesish. . Kjo do të thotë se numri i pjesëtuesve të përbashkët të disa numrave të plotë, të paktën njëri prej të cilëve ndryshon nga zero, do të jetë gjithashtu i fundëm, dhe nga e gjithë bashkësia e tyre ne gjithmonë mund të zgjedhim numrin më të madh. numër i madh(Më parë kemi folur tashmë për konceptin e numrit të plotë më të madh dhe më të vogël, ju këshillojmë ta përsërisni këtë material).

Në arsyetimin e mëtejshëm, do të supozojmë se të paktën një nga grupi i numrave për të cilin duhet të gjeni pjesëtuesin më të madh të përbashkët do të jetë i ndryshëm nga 0. Nëse të gjithë janë të barabartë me 0, atëherë pjesëtuesi i tyre mund të jetë çdo numër i plotë, dhe meqenëse ka pafundësisht shumë prej tyre, ne nuk mund të zgjedhim më të madhin. Me fjalë të tjera, është e pamundur të gjesh pjesëtuesin më të madh të përbashkët për bashkësinë e numrave të barabartë me 0.

Kalojmë në formulimin e përkufizimit kryesor.

Përkufizimi 2

Pjesëtuesi më i madh i përbashkët i numrave të shumtë është numri i plotë më i madh që i ndan të gjithë ata numra.

Me shkrim, pjesëtuesi më i madh i përbashkët më së shpeshti shënohet me shkurtesën GCD. Për dy numra, mund të shkruhet si gcd (a, b) .

Shembulli 2

Cili është një shembull i GCD për dy numra të plotë? Për shembull, për 6 dhe - 15 do të ishte 3. Le ta vërtetojmë këtë. Së pari, shkruajmë të gjithë pjesëtuesit e gjashtë: ± 6, ± 3, ± 1, dhe më pas të gjithë pjesëtuesit e pesëmbëdhjetë: ± 15, ± 5, ± 3 dhe ± 1. Pas kësaj, ne zgjedhim ato të zakonshme: këto janë − 3 , − 1 , 1 dhe 3 . Nga këto, ju duhet të zgjidhni numrin më të madh. Kjo do të jetë 3.

Për tre ose më shumë numra, përkufizimi i pjesëtuesit më të madh të përbashkët do të jetë pothuajse i njëjtë.

Përkufizimi 3

Pjesëtuesi më i madh i përbashkët i tre ose më shumë numrave është numri i plotë më i madh që i ndan të gjithë ata numra në të njëjtën kohë.

Për numrat a 1 , a 2 , ... , a n pjesëtuesi shënohet me lehtësi si GCD (a 1 , a 2 , ... , a n) . Vetë vlera e pjesëtuesit shkruhet si GCD (a 1 , a 2 , … , a n) = b .

Shembulli 3

Këtu janë shembuj të pjesëtuesit më të madh të përbashkët të disa numrave të plotë: 12 , - 8 , 52 , 16 . Do të jetë e barabartë me katër, që do të thotë se mund të shkruajmë se gcd (12, - 8, 52, 16) = 4.

Ju mund të kontrolloni saktësinë e këtij pohimi duke shkruar të gjithë pjesëtuesit e këtyre numrave dhe më pas duke zgjedhur më të madhin prej tyre.

Në praktikë, ka shpesh raste kur pjesëtuesi më i madh i përbashkët është i barabartë me një nga numrat. Kjo ndodh kur të gjithë numrat e tjerë mund të pjesëtohen me një numër të caktuar (në paragrafin e parë të artikullit kemi dhënë vërtetimin e kësaj deklarate).

Shembulli 4

Pra, pjesëtuesi më i madh i përbashkët i numrave 60, 15 dhe - 45 është 15, pasi pesëmbëdhjetë është i pjesëtueshëm jo vetëm me 60 dhe - 45, por edhe me vetveten, dhe nuk ka pjesëtues më të madh për të gjithë këta numra.

Numrat coprime janë një rast i veçantë. Ata janë numra të plotë me një pjesëtues më të madh të përbashkët prej 1.

Karakteristikat kryesore të GCD dhe algoritmit të Euklidit

Pjesëtuesi më i madh i përbashkët ka disa veti karakteristike. Ne i formulojmë ato në formën e teoremave dhe vërtetojmë secilën prej tyre.

Vini re se këto veti janë formuluar për numra të plotë më të mëdhenj se zero, dhe ne konsiderojmë vetëm pjesëtues pozitivë.

Përkufizimi 4

Numrat a dhe b kanë pjesëtuesin më të madh të përbashkët të barabartë me gcd për b dhe a , pra gcd (a , b) = gcd (b , a) . Ndryshimi i vendeve të numrave nuk ndikon në rezultatin përfundimtar.

Kjo veti rrjedh nga vetë përkufizimi i GCD dhe nuk ka nevojë për prova.

Përkufizimi 5

Nëse numri a mund të pjesëtohet me numrin b, atëherë bashkësia e pjesëtuesve të përbashkët të këtyre dy numrave do të jetë e ngjashme me bashkësinë e pjesëtuesve të numrit b, domethënë gcd (a, b) = b.

Le ta vërtetojmë këtë deklaratë.

Prova 1

Nëse numrat a dhe b kanë pjesëtues të përbashkët, atëherë secili prej tyre mund të ndahet me ta. Në të njëjtën kohë, nëse a është një shumëfish i b, atëherë çdo pjesëtues i b do të jetë gjithashtu pjesëtues i a , pasi pjesëtueshmëria ka një veti të tillë si kalueshmëria. Prandaj, çdo pjesëtues b do të jetë i përbashkët për numrat a dhe b. Kjo vërteton se nëse mund të pjesëtojmë a me b, atëherë bashkësia e të gjithë pjesëtuesve të të dy numrave përkon me bashkësinë e pjesëtuesve të një numri b. Dhe meqenëse pjesëtuesi më i madh i çdo numri është vetë numri, atëherë pjesëtuesi më i madh i përbashkët i numrave a dhe b do të jetë gjithashtu i barabartë me b, d.m.th. gcd(a, b) = b. Nëse a = b, atëherë gcd (a, b) = gcd (a, a) = gcd (b, b) = a = b, p.sh. gcd (132, 132) = 132.

Duke përdorur këtë veti, ne mund të gjejmë pjesëtuesin më të madh të përbashkët të dy numrave nëse njëri prej tyre mund të ndahet me tjetrin. Një pjesëtues i tillë është i barabartë me njërin nga këta dy numra me të cilin mund të pjesëtohet numri i dytë. Për shembull, gcd (8, 24) = 8, sepse 24 është shumëfish i tetës.

Përkufizimi 6 Prova 2

Le të përpiqemi të vërtetojmë këtë pronë. Fillimisht kemi barazinë a = b q + c, dhe çdo pjesëtues i përbashkët i a dhe b do të pjesëtojë gjithashtu c, gjë që shpjegohet me vetinë përkatëse të pjesëtueshmërisë. Prandaj, çdo pjesëtues i përbashkët i b dhe c do të ndajë a . Kjo do të thotë se bashkësia e pjesëtuesve të përbashkët a dhe b do të përkojë me bashkësinë e pjesëtuesve b dhe c, duke përfshirë më të madhin prej tyre, që do të thotë se barazia gcd (a, b) = gcd (b, c) është e vërtetë.

Përkufizimi 7

Vetia e mëposhtme quhet algoritmi i Euklidit. Me të, ju mund të llogarisni pjesëtuesin më të madh të përbashkët të dy numrave, si dhe të provoni vetitë e tjera të GCD.

Përpara se të formuloni pronën, ju këshillojmë të përsërisni teoremën që vërtetuam në artikullin mbi ndarjen me një mbetje. Sipas tij, numri i pjesëtueshëm a mund të përfaqësohet si b q + r, dhe këtu b është një pjesëtues, q është një numër i plotë (quhet edhe një herës jo i plotë), dhe r është një mbetje që plotëson kushtin 0 ≤ r ≤ b.

Le të themi se kemi dy numra të plotë më të mëdhenj se 0 për të cilët barazitë e mëposhtme do të jenë të vërteta:

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

Këto barazi mbarojnë kur r k + 1 bëhet e barabartë me 0. Kjo do të ndodhë patjetër, pasi sekuenca b > r 1 > r 2 > r 3 , … është një seri numrash të plotë në rënie, që mund të përfshijë vetëm një numër të fundëm të tyre. Prandaj, r k është pjesëtuesi më i madh i përbashkët i a dhe b , pra r k = gcd (a , b) .

Para së gjithash, ne duhet të vërtetojmë se r k është një pjesëtues i përbashkët i numrave a dhe b, dhe pas kësaj, se r k nuk është thjesht një pjesëtues, por pjesëtuesi më i madh i përbashkët i dy numrave të dhënë.

Le të shohim listën e barazive më sipër, nga poshtë lart. Sipas barazisë së fundit,
r k − 1 mund të pjesëtohet me r k . Bazuar në këtë fakt, si dhe në vetinë e mëparshme të vërtetuar të pjesëtuesit më të madh të përbashkët, mund të argumentohet se r k − 2 mund të pjesëtohet me r k, pasi
r k − 1 pjesëtohet me r k dhe r k pjesëtohet me r k .

Barazia e tretë nga fundi na lejon të konkludojmë se r k − 3 mund të pjesëtohet me r k, e kështu me radhë. E dyta nga fundi është se b është i pjesëtueshëm me r k, dhe i pari është që a është i pjesëtueshëm me r k. Nga e gjithë kjo arrijmë në përfundimin se r k është pjesëtues i përbashkët i a dhe b .

Tani le të vërtetojmë se r k = gcd (a , b) . Çfarë duhet të bëj? Tregoni se çdo pjesëtues i përbashkët i a dhe b do të ndajë r k. Le ta shënojmë r 0 .

Le të shohim të njëjtën listë të barazive, por nga lart poshtë. Bazuar në vetinë e mëparshme, mund të konkludojmë se r 1 pjesëtohet me r 0 , që do të thotë se sipas barazisë së dytë, r 2 pjesëtohet me r 0 . Ne zbresim nëpër të gjitha barazitë dhe nga e fundit arrijmë në përfundimin se r k pjesëtohet me r 0 . Prandaj, r k = gcd (a , b) .

Duke shqyrtuar këtë veti, arrijmë në përfundimin se bashkësia e pjesëtuesve të përbashkët të a dhe b është e ngjashme me bashkësinë e pjesëtuesve të gcd-së së këtyre numrave. Ky pohim, i cili është pasojë e algoritmit të Euklidit, do të na lejojë të llogarisim të gjithë pjesëtuesit e përbashkët të dy numrave të dhënë.

Le të kalojmë te pronat e tjera.

Përkufizimi 8

Nëse a dhe b janë numra të plotë jo të barabartë me 0, atëherë duhet të ketë dy numra të tjerë të plotë u 0 dhe v 0 për të cilët barazia gcd (a , b) = a · u 0 + b · v 0 do të jetë e vlefshme.

Barazia e dhënë në pasqyrën e vetive është një paraqitje lineare e pjesëtuesit më të madh të përbashkët të a dhe b. Quhet raporti Bezout, dhe numrat u 0 dhe v 0 quhen koeficientë Bezout.

Prova 3

Le ta vërtetojmë këtë pronë. Ne shkruajmë sekuencën e barazive sipas algoritmit të Euklidit:

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

Barazia e parë na tregon se r 1 = a − b · q 1 . Shënoni 1 = s 1 dhe − q 1 = t 1 dhe rishkruani këtë barazi si r 1 = s 1 · a + t 1 · b . Këtu numrat s 1 dhe t 1 do të jenë numra të plotë. Barazia e dytë na lejon të konkludojmë se 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 . Shënoni − s 1 q 2 = s 2 dhe 1 − t 1 q 2 = t 2 dhe rishkruani barazinë si r 2 = s 2 a + t 2 b , ku s 2 dhe t 2 do të jenë gjithashtu numra të plotë. Kjo është për shkak se shuma e numrave të plotë, produkti dhe ndryshimi i tyre janë gjithashtu numra të plotë. Pikërisht në të njëjtën mënyrë, marrim nga barazia e tretë r 3 = s 3 · a + t 3 · b , nga sa vijon r 4 = s 4 · a + t 4 · b, etj. Së fundi, arrijmë në përfundimin se r k = s k a + t k b për numrat e plotë s k dhe t k . Meqenëse r k \u003d GCD (a, b) , ne shënojmë s k \u003d u 0 dhe t k \u003d v 0. Si rezultat, mund të marrim një paraqitje lineare të GCD në formën e kërkuar: GCD (a, b) \u003d a u 0 + b v 0.

Përkufizimi 9

gcd (m a, m b) = m gcd (a, b) për çdo vlerë natyrore m.

Prova 4

Kjo pronë mund të justifikohet si më poshtë. Shumëzojmë me numrin m të dyja anët e çdo barazie në algoritmin Euklidi dhe marrim se gcd (m a , m b) = m r k , dhe r k është gcd (a , b) . Prandaj, gcd (m a, m b) = m gcd (a, b) . Është kjo veti e pjesëtuesit më të madh të përbashkët që përdoret gjatë gjetjes së GCD me metodën e faktorizimit.

Përkufizimi 10

Nëse numrat a dhe b kanë një pjesëtues të përbashkët p , atëherë gcd (a: p , b: p) = gcd (a , b) : p . Në rastin kur p = gcd (a , b) marrim gcd (a: gcd (a , b) , b: gcd (a , b) = 1, pra, numrat a: gcd (a , b) dhe b : gcd (a , b) janë coprime.

Meqenëse a = p (a: p) dhe b = p (b: p) , atëherë, bazuar në vetinë e mëparshme, mund të krijojmë barazi të formës gcd (a , b) = gcd (p (a: p) , p (b: p)) = p GCD (a: p, b: p) , ndër të cilat do të ketë një provë pronë e dhënë. Ne e përdorim këtë pohim kur japim thyesat e zakonshme në formë të pareduktueshme.

Përkufizimi 11

Pjesëtuesi më i madh i përbashkët a 1 , a 2 , ... , a k do të jetë numri d k , i cili mund të gjendet duke llogaritur me radhë 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 .

Kjo veti është e dobishme për gjetjen e pjesëtuesit më të madh të përbashkët të tre ose më shumë numrave. Me të, ju mund ta reduktoni këtë veprim në operacione me dy numra. Baza e tij është një përfundim nga algoritmi i Euklidit: nëse bashkësia e pjesëtuesve të përbashkët a 1 , a 2 dhe a 3 përputhet me bashkësinë d 2 dhe a 3 , atëherë ajo përkon edhe me pjesëtuesit d 3 . Pjesëtuesit e numrave a 1 , a 2 , a 3 dhe a 4 do të përputhen me pjesëtuesit e d 3 , që do të thotë se do të përputhen edhe me pjesëtuesit e d 4 , e kështu me radhë. Në fund, marrim se pjesëtuesit e përbashkët të numrave a 1 , a 2 , ... , a k do të përkojnë me pjesëtuesit e d k , dhe meqënëse pjesëtuesi më i madh numri d k do të jetë vetë ky numër, pastaj gcd (a 1 , a 2 , … , a k) = d k .

Kjo është gjithçka që do të dëshironim të flisnim për vetitë e pjesëtuesit më të madh të përbashkët.

Nëse vëreni një gabim në tekst, ju lutemi theksoni atë dhe shtypni Ctrl+Enter

Ky artikull ka të bëjë me gjetja e pjesëtuesit më të madh të përbashkët (gcd) dy dhe më shumë numrat. Së pari, merrni parasysh algoritmin e Euklidit, ai ju lejon të gjeni GCD të dy numrave. Pas kësaj, ne do të ndalemi në një metodë që na lejon të llogarisim GCD-në e numrave si produkt i faktorëve të tyre të thjeshtë të përbashkët. Më pas, do të merremi me gjetjen e pjesëtuesit më të madh të përbashkët të tre ose më shumë numrave, dhe gjithashtu do të japim shembuj të llogaritjes së GCD të numrave negativë.

Navigimi i faqes.

Algoritmi i Euklidit për gjetjen e GCD

Vini re se nëse do t'i kishim kthyer tabelës së numrave të thjeshtë që në fillim, do të kishim zbuluar se numrat 661 dhe 113 janë të thjeshtë, nga të cilët mund të themi menjëherë se pjesëtuesi më i madh i përbashkët i tyre është 1.

Përgjigje:

gcd(661, 113)=1.

Gjetja e GCD me faktorizimin e numrave në faktorët kryesorë

Konsideroni një mënyrë tjetër për të gjetur GCD. Pjesëtuesi më i madh i përbashkët mund të gjendet duke faktorizuar numrat në faktorë të thjeshtë. Le të formulojmë rregullin: GCD prej dy numrash të plotë numra pozitiv a dhe b është i barabartë me produktin e të gjithë faktorëve të thjeshtë të zakonshëm në zgjerimin e numrave a dhe b në faktorë të thjeshtë.

Le të japim një shembull për të shpjeguar rregullin për gjetjen e GCD. Të njohim zgjerimet e numrave 220 dhe 600 në faktorë të thjeshtë, ata kanë formën 220=2 2 5 11 dhe 600=2 2 2 3 5 5 . Faktorët kryesorë të zakonshëm të përfshirë në zgjerimin e numrave 220 dhe 600 janë 2, 2 dhe 5. Prandaj gcd(220, 600)=2 2 5=20 .

Kështu, nëse i zbërthejmë numrat a dhe b në faktorë të thjeshtë dhe gjejmë prodhimin e të gjithë faktorëve të tyre të përbashkët, atëherë ky do të gjejë pjesëtuesin më të madh të përbashkët të numrave a dhe b.

Konsideroni një shembull të gjetjes së GCD sipas rregullit të shpallur.

Shembull.

Gjeni pjesëtuesin më të madh të përbashkët të 72 dhe 96.

Vendimi.

Le të faktorizojmë numrat 72 dhe 96:

Domethënë 72=2 2 2 3 3 dhe 96=2 2 2 2 2 3 . Faktorët kryesorë të zakonshëm janë 2, 2, 2 dhe 3. Pra gcd(72, 96)=2 2 2 3=24 .

Përgjigje:

gcd(72, 96)=24 .

Në përfundim të këtij seksioni, vërejmë se vlefshmëria e rregullit të mësipërm për gjetjen e gcd-së rrjedh nga vetia e pjesëtuesit më të madh të përbashkët, i cili thotë se GCD(m a 1 , m b 1) = m GCD(a 1 , b 1), ku m është çdo numër i plotë pozitiv.

Gjetja e GCD me tre ose më shumë numra

Gjetja e pjesëtuesit më të madh të përbashkët të tre ose më shumë numrave mund të reduktohet në gjetjen e njëpasnjëshme të gcd të dy numrave. Ne e përmendëm këtë kur studiojmë vetitë e GCD. Aty formuluam dhe vërtetuam teoremën: pjesëtuesi më i madh i përbashkët i disa numrave a 1 , a 2 , ..., a k është e barabartë me numrin d k , e cila gjendet në llogaritjen vijuese 1 , a k)=d k .

Le të shohim se si duket procesi i gjetjes së GCD të disa numrave duke marrë parasysh zgjidhjen e shembullit.

Shembull.

Gjeni pjesëtuesin më të madh të përbashkët të katër numrave 78 , 294 , 570 dhe 36 .

Vendimi.

Në këtë shembull a 1 =78, a 2 =294, a 3 =570, a 4 =36.

Së pari, duke përdorur algoritmin e Euklidit, ne përcaktojmë pjesëtuesin më të madh të përbashkët d 2 të dy numrave të parë 78 dhe 294. Gjatë pjesëtimit, marrim barazitë 294=78 3+60 ; 78=60 1+18 ; 60=18 3+6 dhe 18=6 3 . Kështu, d 2 =GCD(78, 294)=6.

Tani le të llogarisim d 3 \u003d GCD (d 2, a 3) \u003d GCD (6, 570). Përsëri zbatojmë algoritmin e Euklidit: 570=6·95 , pra, d 3 =GCD(6, 570)=6 .

Mbetet për të llogaritur d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36). Meqenëse 36 është i pjesëtueshëm me 6, atëherë d 4 \u003d GCD (6, 36) \u003d 6.

Kështu, pjesëtuesi më i madh i përbashkët i katër numrave të dhënë është d 4 =6, pra gcd(78, 294, 570, 36)=6.

Përgjigje:

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

Zbërthimi i numrave në faktorë të thjeshtë ju lejon gjithashtu të llogaritni GCD-në e tre ose më shumë numrave. Në këtë rast, pjesëtuesi më i madh i përbashkët gjendet si prodhim i të gjithë faktorëve të thjeshtë të thjeshtë të numrave të dhënë.

Shembull.

Llogaritni GCD-në e numrave nga shembulli i mëparshëm duke përdorur faktorizimin e tyre të thjeshtë.

Vendimi.

Numrat 78, 294, 570 dhe 36 i zbërthejmë në faktorë të thjeshtë, marrim 78=2 3 13, 294=2 3 7 7, 570=2 3 5 19, 36=2 2 3. 3. Faktorët e thjeshtë të përbashkët të të katër numrave të dhënë janë numrat 2 dhe 3. Prandaj, GCD(78, 294, 570, 36)=2 3=6.