Didžiausieji bendrieji dalikliai ir Euklido algoritmas

Sudarykite didžiausius vienodus paketus, tinkančius abiem kiekiams

Turite 12 mėlynų žetonų ir 18 oranžinių žetonų. Kiekviename pakete turi būti tik vienos spalvos žetonai, visuose paketuose turi būti vienodas teigiamas sveikasis žetonų skaičius ir nė vieno žetono neturi likti. Paketų dydžiai 1, 2, 3 ir 6 tinka abiem kiekiams. Dydis 6 yra didžiausias: gaunami du mėlynų žetonų paketai ir trys oranžinių žetonų paketai. Nepakanka, kad dydis tiktų tik kiekiui 12, kaip, pavyzdžiui, 4.

Didžiausiasis bendrasis daliklis nusako šį didžiausią abiem kiekiams tinkantį dydį. Kai skaičiai maži, galima išvardyti visus daliklius; dalybos su liekana žingsniai leis rasti atsakymą prieš tai neskaidant nė vieno pradinio skaičiaus dauginamaisiais. Žetonų pavyzdyje natūraliai naudojami teigiami pradiniai skaičiai, tačiau toliau pateiktos sveikųjų skaičių apibrėžtys apima ir neigiamus skaičius bei nulį.

Naudinga iš anksto mokėti dalyti neneigiamus sveikuosius skaičius su liekana, suprasti neigiamus skaičius ir absoliučiąją vertę, skaityti lygybes abiem kryptimis ir taikyti daugybos skirstomąjį dėsnį skaičiams su ženklu. Šiuos įgūdžius ugdo nuorodose pateiktos paskelbtos pamokos. Dalumas, bendrieji dalikliai, tiesinės kombinacijos su sveikaisiais koeficientais ir algoritmas apibrėžiami čia; vėlesnės skaičių teorijos pamokos nėra būtinos.

Skaitydami pirmą kartą, sekite paketų pavyzdį, samprotavimą apie liekaną abiem kryptimis ir algoritmo taikymą skaičiams 48 ir 18. Tada išbandykite vieną atvejį su skaičiumi su ženklu arba nuliu. Prie koeficientų invarianto, mažiausios teigiamos kombinacijos įrodymo ir mažiausiojo bendrojo kartotinio įrodymo grįžkite tada, kai galėsite paaiškinti, kodėl dalybos su liekana žingsnis išsaugo kiekvieną bendrąjį daliklį.

Dalumas reiškia, kad skaičius yra sveikasis kartotinis

Sveikiesiems skaičiams d ir n rašome d | n, kai n = dk su kuriuo nors sveikuoju skaičiumi k. Tai skaitome taip: d dalija n. Taigi 3 | 12, nes 12 = 3×4, ir 3 | −12, nes −12 = 3×(−4). Tačiau 5 nedalija 12: dalmuo nėra sveikasis skaičius. Dalumas yra teiginys, o ne dalybos veiksmas.

Šiame apibrėžime leidžiame d = 0: 0 | n galioja tada ir tik tada, kai n = 0. Taigi 0 | 0 yra teisinga, nors dalmuo 0/0 neapibrėžtas. Kiekvienas nenulinis sveikasis skaičius dalija 0, nes 0 = d×0. Teigiamas daliklis reiškia d ≥ 1, todėl pats nulis niekada nebus galimas paketo dydis.

Pakeitus ženklą, teigiami dalikliai nepasikeičia. Pavyzdžiui, d | a tada ir tik tada, kai d | −a, nes pakeitus daugiklio ženklą pasikeičia sandaugos ženklas. Absoliučioji vertė |a| lygi a, kai a ≥ 0, ir −a, kai a < 0. Todėl teigiamus bendruosius daliklius galime rasti naudodami |a| ir |b|.

Jei d dalija a ir b, jis dalija ir kiekvieną tiesinę kombinaciją ax+by su sveikaisiais koeficientais: užrašę a = du ir b = dv, gauname ax+by = d(ux+vy). Koeficientai x ir y gali būti neigiami arba lygūs nuliui. Ši paprasta uždarumo savybė pagrįs ir samprotavimą apie liekaną, ir Bézout teoremos įrodymą.

Nurodykite, ką reiškia „didžiausias“, ir atskirkite susitarimą dėl nulio

Jei a ir b nėra abu lygūs nuliui, gcd(a,b) yra jų didžiausias teigiamas bendrasis daliklis. Toks daliklis egzistuoja: 1 yra bendrasis daliklis, o bet kurio nenulinio pradinio skaičiaus n teigiami dalikliai neviršija |n|, todėl galimi teigiami bendrieji dalikliai sudaro netuščią baigtinę aibę. Visada pasirenkame neneigiamą didžiausią bendrąjį daliklį, nepriklausomai nuo pradinių skaičių tvarkos ar ženklų.

Kai a ≠ 0, gcd(a,0) = |a|. Kiekvienas teigiamas a daliklis taip pat dalija 0, o |a| yra didžiausias teigiamas a daliklis. Taip pat gcd(0,b) = |b|, kai b ≠ 0. Poros (0,0) bendrieji dalikliai yra visi teigiami sveikieji skaičiai; didžiausio teigiamo bendrojo daliklio nėra. Pagal susitarimą apibrėžiame gcd(0,0) = 0, o ne teigiame, kad nulis yra didžiausias.

Skaičių 12 ir 18 visų teigiamų bendrųjų daliklių sąrašas yra 1,2,3,6, todėl jų didžiausias bendrasis daliklis yra 6. Skaičių 14 ir 25 vienintelis teigiamas bendrasis daliklis yra 1. Pirmųjų dvylikos poros (0,0) teigiamų bendrųjų daliklių išvardijimas iliustruoja susitarimą, bet negali aprėpti viso šio begalinio sąrašo.

Liekana mažesnė už teigiamą daliklį

Neneigiamą sveikąjį skaičių A dalijant iš teigiamo sveikojo skaičiaus B, gaunami vieninteliai sveikieji skaičiai q ≥ 0 ir r, kuriems A = qB+r ir 0 ≤ r < B. Pasirinkime q kaip didžiausią sveikąjį skaičių, kuriam qB ≤ A; toks skaičius egzistuoja, nes galimos q reikšmės yra nuo 0 iki ne daugiau kaip A. Tuomet r = A−qB yra neneigiamas, o jei būtų r ≥ B, tilptų dar viena pilna grupė, ir tai prieštarautų q pasirinkimui.

Norėdami įrodyti vienatinumą, tarkime, kad A = qB+r = q′B+r′, o abi liekanos priklauso intervalui [0,B). Tuomet (q−q′)B = r′−r. Dešiniosios pusės modulis mažesnis už B, todėl sveikasis skaičius q−q′ turi būti 0; vadinasi, q = q′ ir r = r′. Šią dalybos taisyklę algoritmas taiko paėmęs skaičių modulius.

Skaičiams 48 ir 18 turime 48 = 2×18+12, kur 0 ≤ 12 < 18. Skaičiams 18 ir 48 pirmoji dalyba yra 18 = 0×48+18: dalmuo gali būti lygus nuliui. Kai B = 0, liekanos skaičiavimo žingsnis neatliekamas; algoritmas sustoja prieš bandydamas dalyti iš nulio.

Ankstesnė ir naujoji poros turi tuos pačius bendruosius daliklius

Užrašykime A = qB+r, kur B > 0. Jei d | A ir d | B, tai d | r, nes r = A−qB. Ir atvirkščiai: jei d | B ir d | r, tai d | A, nes A = qB+r. Tai dvi kryptys: kiekvienas ankstesnis bendrasis daliklis išlieka ir neatsiranda nė vieno naujo.

Taigi gcd(A,B) = gcd(B,r). Kai 48 = 2×18+12, tiek poros (48,18), tiek poros (18,12) bendrieji teigiami dalikliai yra 1,2,3,6. Liekana gali būti mažesnė už pradinius skaičius, kuriems ieškoma atsakymo, tačiau atsakymas dėl to nesikeičia.

Taisyklė išsaugo visą bendrųjų daliklių aibę, o ne tik vieną daliklį, kurį atsitiktinai išbandėte. Parodžius, kad 6 dalija abu abiejų porų skaičius, patikrinamas šis kandidatas, tačiau neatmetama galimybė, kad yra didesnis kandidatas. Abiejų krypčių argumentas įrodo DBD lygybę bendruoju atveju.

Kartokite, kol antrasis poros narys bus lygus nuliui

Pradėkite nuo (A,B) = (|a|,|b|), išlaikydami įvesties skaičių tvarką. Jei B = 0, iš karto grąžinkite A. Kitu atveju atlikite dalybą A = qB+r ir pakeiskite (A,B) į (B,r). Kartokite. Jei pirmasis narys mažesnis, pirmasis dalmuo lygus nuliui; kitoje poroje jų vaidmenys automatiškai apsikeičia.

Kiekviename atliekamame žingsnyje B > 0 ir jis pakeičiamas liekana r, tenkinančia 0 ≤ r < B. Taigi teigiami antrieji porų nariai griežtai mažėja. Pradėję nuo baigtinio sveikojo skaičiaus, jie negali mažėti be galo: atlikus ne daugiau žingsnių su teigiamu antruoju nariu, nei pradinė B reikšmė, antrasis narys tampa lygus nuliui. Tai įrodo, kad algoritmas baigiasi; pirmieji porų nariai pradžioje nebūtinai sudaro mažėjančią seką.

Invariantas išsaugo DBD kiekviename žingsnyje. Galutinės poros (G,0) DBD yra G, kai G > 0, ir 0, kai taikomas susitarimas dėl (0,0). Todėl grąžinamas pirmasis narys yra pradinių skaičių neneigiamas DBD. Jei bent vienas įvesties skaičius nelygus nuliui, G yra paskutinė nenulinė liekana arba pradinis nenulinis narys, o ne galutinė nulinė liekana.

Porai (48,18) atliekamos dalybos 48 = 2×18+12, 18 = 1×12+6 ir 12 = 2×6+0. Galutinė pora yra (6,0), todėl gcd(48,18) = 6. Porai (17,0) neatliekamas nė vienas dalybos žingsnis, o rezultatas yra 17; porai (0,0) neatliekamas nė vienas žingsnis, o rezultatas yra pagal pasirinktą susitarimą nustatyta reikšmė 0.

Atgaline eiga iš liekanų lygčių gaukite DBD

Pavyzdyje su 48 ir 18 paskutinė nenulinė liekana yra 6 = 18−12. Iš ankstesnės lygties gauname 12 = 48−2×18. Įstatę visą šį reiškinį, gauname 6 = 18−(48−2×18) = −48+3×18. Taigi koeficientai x = −1 ir y = 3 tenkina lygtį 48x+18y = 6.

Bezu tapatybė teigia, kad kiekvienai sveikųjų skaičių a,b porai egzistuoja sveikieji skaičiai x,y, kuriems ax+by = gcd(a,b). Koeficientai gali būti neigiami: jie reiškia atimtį, o ne neigiamą DBD. Porai (−48,18) ta pati vertė gaunama taip: (−48)×1+18×3 = 6. Pakeitus pradinio skaičiaus ženklą, reikia atitinkamai pakeisti jo koeficientą.

Koeficientai nebūtinai yra vieninteliai. Skaičiams 12 ir 18 galioja ir 12×(−1)+18×1 = 6, ir 12×2+18×(−1) = 6. Algoritmas pateikia vieną sertifikatą, o ne vienintelę galimą porą. Porai (0,−18) koeficientai (0,−1) duoda 18. Porai (0,0) pasirinkus (0,0), gaunama sutartinė vertė 0, tačiau teigiamo tiesinio derinio nėra.

Prie kiekvienos liekanos išsaugokite koeficientų sertifikatą

Kad nereikėtų pakartotinai atlikti atgalinio įstatymo, saugokite eilutę (r,x,y) su invariantu r = ax+by. Pradėkite nuo eilučių (|a|,sgn(a),0) ir (|b|,0,sgn(b)), kur sgn(n) yra 1, kai n > 0, −1, kai n < 0, ir 0, kai n = 0. Abi pradinės lygybės galioja ir tada, kai pradiniai skaičiai yra nuliai.

Jei dvi ankstesnės eilutės yra (r₀,x₀,y₀) ir (r₁,x₁,y₁), o r₁ > 0, pažymėkite dalybos dalmenį q ir sudarykite eilutę (r₀−qr₁, x₀−qx₁, y₀−qy₁). Pritaikę skirstomumo dėsnį gauname a(x₀−qx₁)+b(y₀−qy₁) = r₀−qr₁, taigi naujoje eilutėje invariantas išlieka. Pastumkite abi naudojamas eilutes į priekį ir tęskite.

Kai antrosios naudojamos eilutės liekana tampa nuliu, imkite pirmąją naudojamą eilutę. Jos liekana yra įrodytasis DBD, o jos koeficientai patvirtina Bezu tapatybę. Tai įrodo koeficientų egzistavimą visiems pradiniams skaičiams, nepriklausomai nuo jų ženklų, įskaitant atvejus, kai vienas iš pradinių skaičių yra nulis. Eilutė su nuline liekana lieka lentelėje paskutinei dalybai patikrinti, tačiau ji nėra eilutė su teigiamu DBD.

Poros (48,18) lentelė prasideda eilutėmis (48,1,0) ir (18,0,1), o toliau gaunamos eilutės (12,1,−2), (6,−1,3) ir (0,3,−8). Patikrinkite kiekvieną lygybę naudodami pradinius skaičius. Konkrečiai, 48×3+18×(−8) = 0 patvirtina paskutinę eilutę, o ne pakeičia atsakymą į nulį.

DBD – mažiausias teigiamas tiesinis derinys su sveikaisiais koeficientais

Tarkime, g = gcd(a,b) > 0. Kadangi g dalija a ir b, jis dalija kiekvieną tiesinį derinį ax+by su sveikaisiais koeficientais. Kiekvienas teigiamas toks derinys yra teigiamas g kartotinis, taigi ne mažesnis už g. Bezu tapatybė pateikia derinį, lygų g. Todėl g yra mažiausia teigiama vertė tarp visų tiesinių derinių su sveikaisiais koeficientais, o ne tik tarp derinių, pavaizduotų baigtinėje diagramoje.

Sąlyga g > 0 neapima poros (0,0): visi jos tiesiniai deriniai lygūs nuliui, todėl mažiausio teigiamo derinio nėra. Koeficientai yra sveikieji, o ne bet kokie realieji skaičiai; leidus trupmeninius koeficientus, teiginys pasikeistų. Skaičių 12 ir 18 kiekvienas tiesinis derinys su sveikaisiais koeficientais yra 6 kartotinis, o vienas iš jų lygus 6.

Pirminis skaičius yra sveikasis skaičius, didesnis už 1, kurio vieninteliai teigiami dalikliai yra 1 ir jis pats; sudėtinis sveikasis skaičius, didesnis už 1, turi ir kitą teigiamą daliklį. Sveikieji skaičiai yra tarpusavyje pirminiai, kai jų didžiausias bendrasis daliklis yra 1. Lygiavertė sąlyga: egzistuoja jų tiesinė kombinacija su sveikaisiais koeficientais ax+by = 1. Skaičių 14 ir 25 tarpusavio pirminumą įrodo lygybė 14×9+25×(−5) = 1, nors nė vienas iš šių skaičių nėra pirminis. Taip pat (0,1) ir (0,−1) yra tarpusavyje pirminiai; (0,0) nėra.

Naudingą suprastinimo taisyklę galima gauti neskaidant į pirminius dauginamuosius. Jei gcd(u,v) = 1 ir v | uk, pasirinkime sveikuosius skaičius s,t, kuriems us+vt = 1. Padauginę iš k, gauname k = uks+vkt. Abu dešinės pusės dėmenys dalijasi iš v, todėl v | k. Jei skaičiai nėra tarpusavyje pirminiai, ši išvada gali negalioti: 6 dalija 4×3, bet nedalija 3.

Bendrieji kartotiniai atsako į kitą klausimą

Skaičių a ir b bendrasis kartotinis yra sveikasis skaičius M, kuriam a | M ir b | M. Jei abu skaičiai a,b yra nenuliniai, jų mažiausias bendrasis kartotinis lcm(a,b) yra mažiausias teigiamas bendrasis kartotinis. Skaičių 4 ir 6 pirmasis sutampantis teigiamas kartotinis yra 12. Jis skiriasi nuo jų didžiausio bendrojo daliklio 2, kuris dalija pradinius skaičius, o ne dalijasi iš jų.

Ženklai kartotinių nekeičia. Jei bent vienas pradinis skaičius yra nulis, vienintelis jų bendrasis kartotinis yra 0, nes iš 0 | M būtinai gauname M = 0. Teigiamo bendrojo kartotinio nėra; apibrėžiame lcm(a,0) = lcm(0,b) = 0, taip pat ir lcm(0,0) = 0. Tai dar vienas susitarimas, o ne teiginys apie mažiausią teigiamą kartotinį.

Kai pradiniai skaičiai nenuliniai, pažymėkime A = |a|, B = |b| ir g = gcd(A,B). Užrašykime A = gu ir B = gv, kur u,v yra teigiami sveikieji skaičiai. Bet kuriam teigiamam bendrajam u ir v dalikliui h skaičius gh būtų bendrasis A ir B daliklis; kadangi g yra didžiausias bendrasis daliklis, būtinai h ≤ 1. Taigi gcd(u,v) = 1.

Skaičius M = guv yra teigiamas tiek A, tiek B kartotinis. Ir atvirkščiai: teigiamą bendrąjį kartotinį N galima užrašyti N = Ak = guk, kur k yra teigiamas sveikasis skaičius. Kadangi B dalija N, tai v dalija uk; pagal tarpusavyje pirminių skaičių suprastinimo taisyklę v | k. Taigi M dalija N, todėl N ≥ M. Tai įrodo, kad M yra mažiausias teigiamas bendrasis kartotinis.

Vadinasi, lcm(a,b) = |ab|/gcd(a,b), kai bent vienas pradinis skaičius yra nenulinis: kai abu skaičiai nenuliniai, tai tiesiogiai gauname iš įrodymo, o kai vienas iš jų yra nulis, gauname 0, padalytą iš teigiamo didžiausio bendrojo daliklio. Nenaudokite šio dalmens porai (0,0), nes tuomet gautume 0/0. Pagal nurodytus susitarimus sandaugos tapatybė gcd(a,b)×lcm(a,b) = |ab| galioja visais atvejais.

Patikrinkite tikslų sertifikatą ir jo taikymo sritį

Jei teigiama, kad didžiausias bendrasis daliklis yra G > 0, patikrinkite, ar G dalija abu pradinius skaičius, ir raskite sveikuosius skaičius x,y, kuriems ax+by = G. Tuomet kiekvienas bendrasis daliklis dalija G, todėl nė vienas negali būti didesnis; taip patvirtinamas atsakymas. Reikšmė, kuri tik dalija abu skaičius, gali būti per maža. Porai (0,0) taikykite aiškiai nurodytą susitarimą, o ne šį teigiamo daliklio sertifikatu grindžiamą argumentą.

Interaktyviojoje tyrinėjimo priemonėje naudojami iš anksto nustatyti atvejai su nedideliais teigiamais ir neigiamais skaičiais bei nuliu. Jos pagrindinė dalis priima sveikuosius skaičius, kurių absoliučioji vertė neviršija 10,000 (dešimties tūkstančių), atmeta nesaugias aritmetines operacijas dar prieš jas atlikdama ir išlaiko kiekvienos dalybos su liekana lygties bei koeficientų lygybės tikslumą. Šios realizacijos ribos neapriboja teoremų apie sveikuosius skaičius. Daliklių lentelės yra išsamios ten, kur tai nurodyta; baigtinis (0,0) sąrašas arba baigtiniame intervale pateikti kartotiniai žymimi kaip pavyzdžiai arba pradinė sąrašo dalis.

Prieš atskleisdami rezultatą, numatykite didžiausią bendrąjį daliklį, galutinį didžiausią bendrąjį daliklį, tiesinės kombinacijos reikšmę arba pirmą teigiamą bendrąjį kartotinį. Palyginkite atvejus, kai pakeičiamas ženklas, sukeičiamas pradinių skaičių eiliškumas ir vienas skaičius yra nulis. Paaiškinkite, kodėl atsakymas arba susitarimas išplaukia iš apibrėžimo, o ne vien iš pavaizduoto žymeklio.

Išnagrinėti pavyzdžiai

Pabandykite patys

1. Ar teiginiai 0 | 0, 0 | 5 ir 5 | 0 yra teisingi? Ar kuris nors iš jų apibrėžia dalmenį 0/0?

   Rodyti atsakymą ir paaiškinimą

   Atitinkamai teisingas, klaidingas ir teisingas. Dalmuo 0/0 lieka neapibrėžtas.

   Dalumas nusako, ar egzistuoja sveikasis daugiklis: 0 = 0×k, 5 negali būti lygus 0×k, o 0 = 5×0. Dalybos dalmuo turėtų turėti vienintelę reikšmę, tačiau 0/0 jos neturi.

2. Raskite gcd(−20,30), gcd(−20,0) ir gcd(0,0), paaiškindami atvejus su nuliu.

   Rodyti atsakymą ir paaiškinimą

   Reikšmės yra atitinkamai 10, 20 ir 0.

   Didžiausias teigiamas bendrasis skaičių 20 ir 30 daliklis yra 10. Kiekvienas teigiamas skaičiaus −20 daliklis taip pat dalija 0, o didžiausias iš jų yra |−20| = 20. Skaičiai (0,0) neturi didžiausio teigiamo bendrojo daliklio; pagal susitarimą jų DBD yra 0.

3. Duota 85 = 2×32+21. Įrodykite, kad poros (85,32) ir (32,21) turi tuos pačius bendrus daliklius.

   Rodyti atsakymą ir paaiškinimą

   Bendras 85 ir 32 daliklis dalija 21 = 85−2×32; bendras 32 ir 21 daliklis dalija 85 = 2×32+21.

   Abiem kryptimis išsaugoma visa bendrų daliklių aibė. Patikrinus tik tai, kad vienas pasirinktas daliklis išlieka, didžiausių bendrų daliklių lygybė nebūtų įrodyta.

4. Atlikite Euklido algoritmą iki galo porai (85,32). Nurodykite algoritmo grąžinamą reikšmę, o ne galutinį nulį.

   Rodyti atsakymą ir paaiškinimą

   85 = 2×32+21; 32 = 1×21+11; 21 = 1×11+10; 11 = 1×10+1; 10 = 10×1+0. Didžiausias bendras daliklis yra 1.

   Antrieji porų nariai 32,21,11,10,1,0 griežtai mažėja. Kiekvienas pakeitimas išsaugo bendrų daliklių aibę, o galutinė pora yra (1,0).

5. Ar nulinis pirmasis dalmuo yra klaida, kai įvestis yra (18,48)? Kokia porų seka gaunama toliau?

   Rodyti atsakymą ir paaiškinimą

   Tai teisinga. Poros yra (18,48), (48,18), (18,12), (12,6), (6,0), todėl didžiausias bendras daliklis yra 6.

   Lygybėje 18 = 0×48+18 liekana 18 yra mažesnė už daliklį 48. Teigiami antrieji porų nariai griežtai mažėja, nors pirmieji nariai iš pradžių didėja.

6. Porai (48,18) aktyviosios eilutės yra (18,0,1) ir (12,1,−2). Kai q = 1, kokia kita eilutė išsaugo lygybę r = 48x+18y?

   Rodyti atsakymą ir paaiškinimą

   Kita eilutė yra (6,−1,3).

   Iš pirmosios eilutės vieną kartą atimkite antrąją: liekana 18−12 = 6, x = 0−1 = −1, y = 1−(−2) = 3. Patikrinkite: −48+54 = 6.

7. Paverskite 48×(−1)+18×3 = 6 poros (−48,−18) sertifikatu.

   Rodyti atsakymą ir paaiškinimą

   Naudokite koeficientus (1,−3): (−48)×1+(−18)×(−3) = 6.

   Pakeitus kiekvieno pradinio skaičiaus ženklą, reikia pakeisti ir jį atitinkančio koeficiento ženklą. DBD išlieka neneigiamas ir tebėra 6.

8. Ar sveikieji skaičiai x,y galėtų tenkinti lygybę 12x+18y = 3? Kodėl baigtinės paieškos nepakanka?

   Rodyti atsakymą ir paaiškinimą

   Ne. Kiekviena tokia tiesinė kombinacija dalijasi iš 6, o 3 nesidalija.

   Dalumo įrodymas apima visas sveikųjų koeficientų poras, įskaitant tas, kurios nepatenka į jokią pateiktą paiešką. Bezu tapatybė duoda mažiausią teigiamą tiesinę kombinaciją 6.

9. Ar tai, kad skaičiai yra tarpusavyje pirminiai, reiškia, kad abu jie yra pirminiai? Patikrinkite (14,25), (0,−1) ir (0,0).

   Rodyti atsakymą ir paaiškinimą

   Ne. Pirmųjų dviejų porų skaičiai yra tarpusavyje pirminiai, o poros (0,0) skaičiai – ne.

   Lygybės 14×9+25×(−5) = 1 ir 0×0+(−1)×(−1) = 1 patvirtina, kad DBD yra 1. Pagal susitarimą gcd(0,0) = 0, o tai nėra 1. Ir 14, ir 25 yra sudėtiniai skaičiai.

10. Raskite lcm(−8,12), lcm(0,12) ir lcm(0,0). Kuriuo atveju |ab|/gcd(a,b) yra neapibrėžtas?

    Rodyti atsakymą ir paaiškinimą

    MBK yra 24, 0 ir 0. Dalmenį nusakanti formulė neapibrėžta tik porai (0,0).

    Iš gcd(−8,12) = 4 gauname |−96|/4 = 24. Kai tik vienas iš skaičių yra nulis, DBD yra teigiamas ir gauname 0. Kai abu skaičiai yra nuliai, gautume 0/0, todėl taikykite atskirą susitarimą dėl MBK.

11. Kažkas teigia, kad gcd(12,18) = 3, nes 3 dalija abu skaičius. Ko trūksta ir kas įrodo teisingą reikšmę?

    Rodyti atsakymą ir paaiškinimą

    Bendrasis daliklis gali būti per mažas. Teisingas DBD yra 6; tai patvirtina dalumas ir lygybė 12×(−1)+18×1 = 6.

    Kiekvienas bendrasis daliklis dalija tą kombinaciją 6. Kadangi pats 6 dalija abu pradinius skaičius, jis yra didžiausias. Jokia sveikaskaitė tiesinė kombinacija negali būti lygi 3, nes kiekviena tokia kombinacija dalijasi iš 6.

12. Kodėl nuolatinis griežtas mažėjimas čia įrodo algoritmo baigtinumą? Ar pakaktų mažėjančios teigiamų realiųjų skaičių sekos?

    Rodyti atsakymą ir paaiškinimą

    Antrieji elementai yra neneigiami sveikieji skaičiai. Už pradinį teigiamą sveikąjį skaičių mažesnių teigiamų sveikųjų skaičių yra tik baigtinis skaičius; teigiamos realiosios reikšmės galėtų mažėti be galo.

    Liekanai keliamos abi sąlygos: 0 ≤ r < B ir sveikumas. Pavyzdžiui, 1,1/2,1/4,… išlieka teigiama ir griežtai mažėja, todėl vien griežtas mažėjimas, neapsiribojant sveikaisiais skaičiais, neįrodytų algoritmo baigtinumo.

Ką verta įsidėmėti

• Jei abu pradiniai skaičiai nėra kartu lygūs nuliui, DBD yra didžiausias teigiamas bendrasis daliklis; gcd(0,0) = 0 yra aiškiai nustatytas susitarimas.
• Dalybos su liekana žingsnis išsaugo kiekvieną bendrąjį daliklį abiem kryptimis, o teigiamas sveikasis antrasis elementas griežtai mažėja.
• Išplėstinio algoritmo eilutėse išlaikoma lygybė r = ax+by, todėl DBD eilutė pateikia tikslius Bezu koeficientus su ženklais.
• Kai DBD yra teigiamas, jis yra mažiausia teigiama sveikaskaitė tiesinė kombinacija; DBD 1 reiškia, kad skaičiai yra tarpusavyje pirminiai, o ne kad pradiniai skaičiai privalo būti pirminiai.
• Neneigiamų DBD ir MBK sandauga yra |ab|. Atvejai, kai MBK lygus nuliui, apibrėžiami susitarimu, o dalmens formulė netaikoma (0,0).