Euklido algoritmo mokymasis mokykloje. Euklido algoritmas – didžiausio bendro daliklio radimas

Plačiai paplitęs elektroninėje prekyboje. Taip pat algoritmas naudojamas sprendžiant tiesines diofantines lygtis, konstruojant tęstines trupmenas, Šturmo metodu. Euklido algoritmas yra pagrindinė šiuolaikinės skaičių teorijos teoremų, tokių kaip Lagranžo teorema apie keturių kvadratų sumą ir pagrindinė aritmetikos teorema, įrodinėjimo įrankis.

Enciklopedinis „YouTube“.

1 / 5

✪ Matematika. Natūralūs skaičiai: Euklido algoritmas. Foksfordo internetinis mokymosi centras

✪ Euklido algoritmas

✪ Euklido algoritmas, greitas būdas rasti gcd

✪ Matematika 71. Didžiausias bendras daliklis. Euklido algoritmas – Pramoginių mokslų akademija

✪ 20, o kilpos Euklido Python algoritmas

Subtitrai

Istorija

Senovės Graikijos matematikai pavadino šį algoritmą ἀνθυφαίρεσις arba ἀνταναίρεσις - „abipusis atėmimas“. Šio algoritmo Euklidas neatrado, nes jis jau paminėtas Topeka Aristotelis. Euklido „Elementuose“ jis aprašytas du kartus – VII knygoje ieškant dviejų natūraliųjų skaičių didžiausio bendro daliklio, o X knygoje – ieškant dviejų vienarūšių dydžių didžiausio bendro mato. Abiem atvejais pateikiamas geometrinis algoritmo aprašymas, norint rasti dviejų segmentų „bendrą matą“.

apibūdinimas

Euklido algoritmas sveikiesiems skaičiams

Leisti a (\displaystyle a) Ir b (\displaystyle b)- sveikieji skaičiai, kurie tuo pačiu metu nėra lygūs nuliui, ir skaičių seka

a > b > r 1 > r 2 > r 3 > r 4 > … > r n (\displaystyle a>b>r_(1)>r_(2)>r_(3)>r_(4)>\ \dots \ >r_(n))

lemia tai, kad kiekvienas r k (\displaystyle r_(k))- tai likusi dalis padalijus ankstesnį skaičių iš ankstesnio, o priešpaskutinis - iš paskutinio, tai yra:

a = b q 0 + r 1 , (\displaystyle a=bq_(0)+r_(1),) b = r 1 q 1 + r 2 , (\displaystyle b=r_(1)q_(1)+r_(2),) r 1 = r 2 q 2 + r 3 , (\displaystyle r_(1)=r_(2)q_(2)+r_(3),) ⋯ (\displaystyle \cdots ) r k − 2 = r k − 1 q k − 1 + r k , (\displaystyle r_(k-2)=r_(k-1)q_(k-1)+r_(k),) ⋯ (\displaystyle \cdots ) r n − 2 = r n − 1 q n − 1 + r n , (\displaystyle r_(n-2)=r_(n-1)q_(n-1)+r_(n),) r n − 1 = r n q n . (\displaystyle r_(n-1)=r_(n)q_(n).)

Tada gcd ( a, b), didžiausias bendras daliklis a Ir b, yra lygus r n , paskutinis nenulinis šios sekos narys.

Egzistavimas toks r 1 , r 2 , ..., r n , tai yra, dalybos su liekana galimybė mįjungta n bet kokiai visumai m ir visa n≠ 0 įrodoma įjungus indukciją m.

Teisingumasšis algoritmas išplaukia iš šių dviejų teiginių:

• Leisti a = b⋅q + r, tada gcd(a, b) = gcd(b, r).

Įrodymas

• GCD( r, 0) = r bet kokiam ne nuliui r(nes 0 dalijasi iš bet kurio sveikojo skaičiaus, išskyrus nulį).

Euklido geometrinis algoritmas

Pateikiame du ilgio segmentus a Ir b. Atimkite mažesnį segmentą iš didesnio segmento ir pakeiskite didesnį segmentą gautu skirtumu. Kartokite šią operaciją, kol segmentai bus lygūs. Jei taip atsitiks, pradiniai segmentai yra palyginami, o paskutinis gautas segmentas yra didžiausias bendras jų matas. Jei nėra bendro mato, procesas yra begalinis. Šioje formoje algoritmą aprašo Euklidas ir jis įgyvendinamas naudojant kompasą ir liniuotę.

Pavyzdys

Norėdami iliustruoti, gcd rasti bus naudojamas Euklido algoritmas a= 1071 ir b= 462. Pirmiausia iš 1071 atimkite 462 kartotinį, kol gausime skirtumą, mažesnį nei 462. Turime du kartus atimti 462, ( q 0 = 2), o likusi dalis yra 147:

1071 = 2 × 462 + 147.

Tada iš 462 atimame 147 kartotinį, kol gauname skirtumą, mažesnį nei 147. Turime tris kartus atimti 147 ( q 1 = 3), o likusi dalis yra 21:

462 = 3 x 147 + 21.

Tada iš 147 atimame 21 kartotinį, kol gauname skirtumą, mažesnį nei 21. Turime septynis kartus atimti 21 ( q 2 = 7), lieka be likučio:

147 = 7 x 21 + 0.

Taigi seka a > b > r 1 > r 2 > r 3 > … > r n šiuo konkrečiu atveju atrodytų taip:

1071 > 462 > 147 > 21.

Kadangi paskutinė liekana yra nulis, algoritmas baigiasi 21 ir gcd(1071, 462) = 21.

Lentelės pavidalu veiksmai buvo tokie:

Programos

Išplėstas Euklido algoritmas ir Bezouto ryšys

Formulės, skirtos r i (\displaystyle r_(i)) galima perrašyti taip:

r 1 = a + b (− q 0) (\displaystyle r_(1)=a+b(-q_(0))) r 2 = b − r 1 q 1 = a (− q 1) + b (1 + q 1 q 0) (\displaystyle r_(2)=b-r_(1)q_(1)=a(-q_( 1))+b(1+q_(1)q_(0))) ⋮ (\displaystyle \vdots ) GCD (a , b) = r n = a s + b t (\displaystyle (a,b)=r_(n)=as+bt)

Čia s Ir t visas. Šis didžiausio bendro daliklio vaizdas vadinamas Bezout ryšiu, o skaičiai s Ir t- koeficientai Bezu . Bezout ryšys yra pagrindinis Euklido lemos įrodymas ir pagrindinė aritmetikos teorema.

Tęstinės trupmenos

Euklido algoritmas yra gana glaudžiai susijęs su tęstinėmis trupmenomis. Požiūris a/b leidžia tęsti trupmenos vaizdavimą:

ab = [q0; q 1 , q 2 , ⋯ , q n ] (\displaystyle (\frac (a)(b))=).

Šiuo atveju tęstinė trupmena be paskutinio nario yra lygi Bezout koeficientų santykiui t/s paimta su minuso ženklu:

[q 0; q 1 , q 2 , ⋯ , q n − 1 ] = − t s (\displaystyle =-(\frac (t)(s))).

Lygybių seka, apibrėžianti Euklido algoritmą, gali būti perrašyta tokia forma:

a b = q 0 + r 0 b b r 0 = q 1 + r 1 r 0 r 0 r 1 = q 2 + r 2 r 1 ⋮ r k − 2 r k − 1 = q k + r k r k − 1 ⋮ r N − 2 r N − 1 = q N (\displaystyle (\begin (lygiuotas)(\frac (a)(b))&=q_(0)+(\frac (r_(0))(b))\\(\frac (b) )(r_(0)))&=q_(1)+(\frac (r_(1))(r_(0)))\\(\frac (r_(0))(r_(1)))& =q_(2)+(\frac (r_(2))(r_(1)))\\&()\ \vdots \\(\frac (r_(k-2))(r_(k-1) ))&=q_(k)+(\frac (r_(k))(r_(k-1)))\\&()\ \vdots \\(\frac (r_(N-2))(r_ (N-1)))&=q_(N)\end(sulygiuotas)))

Paskutinis narys dešinėje lygties pusėje visada yra lygus kitos lygties kairės pusės atvirkštiniam dydžiui. Todėl pirmąsias dvi lygtis galima sujungti tokia forma:

a b = q 0 + 1 q 1 + r 1 r 0 (\displaystyle (\frac (a)(b))=q_(0)+(\cfrac (1)(q_(1)+(\cfrac (r_( 1))(r_(0))))))

Trečiąja lygybe galima pakeisti išraiškos vardiklį r 1 /r 0, gauname:

a b = q 0 + 1 q 1 + 1 q 2 + r 2 r 1 (\displaystyle (\frac (a)(b))=q_(0)+(\cfrac (1)(q_(1)+(\ cfrac (1)(q_(2)+(\cfrac (r_(2))(r_(1))))))))

Paskutinis likučių santykis r k /r k−1 visada gali būti pakeistas naudojant sekančią lygybę ir taip iki paskutinės lygties. Rezultatas yra tęstinė trupmena:

a b = q 0 + 1 q 1 + 1 q 2 + 1 ⋱ + 1 q N = [ q 0 ; q 1 , q 2 , … , q N ] (\displaystyle (\frac (a)(b))=q_(0)+(\cfrac (1)(q_(1)+(\cfrac (1)(q_) (2)+(\cfrac (1)(\ddots +(\cfrac (1)(q_(N))))))))))=)

Apibendrintas Euklido algoritmas daugianariams

Euklido algoritmas ir išplėstinis Euklido algoritmas natūraliai apibendrina į polinomų žiedą k[x] iš vieno kintamojo per savavališką lauką k, kadangi tokiems daugianariams apibrėžiamas padalijimo su liekana operacija. Vykdant Euklido algoritmą polinomams, panašiai kaip Euklido algoritmą sveikiesiems skaičiams, gaunama polinomo liekanų seka (PRS).

Žiedo pavyzdys Z[x]

Tegu cont(f) pagal apibrėžimą yra daugianario f(x) koeficientų gcd iš Z[x] - turinys daugianario. Vadinamas koeficientas, dalijantis f(x) iš cont(f). primityvioji dalis daugianaris f(x) ir žymimas primpart(f(x)). Šie apibrėžimai bus reikalingi norint rasti dviejų daugianario gcd 1 p. (x) Ir 2 p. (x)žiede Z[x]. Polinomams virš sveikųjų skaičių teisinga:

C o n t ((\displaystyle cont() NODNOD ( c o n t (p 1 (x)) , c o n t (p 2 (x)) ), (\displaystyle \(tęsinys(p_(1)(x)),tęsinys(p_(2)(x))\),)

P r i m p a r t ((\displaystyle primpart() GCD (p 1 (x) , p 2 (x) )) = (\displaystyle \(p_(1)(x),p_(2)(x)\))=) GCD (p r i m p a r t (p 1 (x)) , p r i m p a r t (p 2 (x)) ). (\displaystyle \(primpart(p_(1)(x)),primpart(p_(2)(x))\).)

Taigi dviejų savavališkų daugianarių gcd suradimo problema sumažinama iki primityvių daugianario gcd nustatymo problemos.

Tegul iš Z[x] yra du primityvūs daugianariai p 1 (x) ir p 2 (x), kurių santykis tarp jų laipsnių tenkinamas: deg(p 1 (x)) = m ir deg(p 2 (x) ) = n, m > n. Daugiavardžių dalijimas su liekana reiškia tikslų didžiausio dividendo koeficiento dalijimąsi iš didžiausio daliklio koeficiento; bendruoju atveju dalyti su liekana negalima. Todėl įvedamas pseudodalybos algoritmas, kuris vis dėlto leidžia gauti pseudodaltį ir pseudolikutį (prem), kurie patys priklausys daugianarių aibei sveikųjų skaičių atžvilgiu.

Sakydami pseudodalybą turime galvoje, kad prieš patį padalijimą yra daugianario daugyba p 1 (x) (\displaystyle p_(1)(x))įjungta (l c (p 2 (x))) m − n + 1 (\displaystyle (lc(p_(2)(x)))^(m-n+1)), tai yra

L c (p 2 (x)) m − n + 1 p 1 (x) = p 2 (x) q (x) + r 2 (x) , deg⁡ (r (x))< deg ⁡ (p 2 (x)) , {\displaystyle lc(p_{2}(x))^{m-n+1}p_{1}(x)=p_{2}(x)q(x)+r_{2}(x),\deg(r(x))<\deg(p_{2}(x)),}

Kur q (x) (\displaystyle q(x)) Ir r (x) (\displaystyle r(x))- atitinkamai pseudodalinė ir pseudolieka.

Taigi, p 1 (x) , p 2 (x) ∈ Z [ x ] (\displaystyle p_(1)(x), p_(2)(x)\in Z[x]), be to deg ⁡ (p 1) = n 1 ≥ deg ⁡ (p 2) = n 2 (\displaystyle \deg(p_(1))=n_(1)\geq \deg(p_(2))=n_(2) ). Tada Euklido algoritmas susideda iš šių žingsnių:

1. GCD turinio apskaičiavimas:

C:= (\displaystyle c:=) GCD ( c o n t (p 1) , c o n t (p 2) ) (\displaystyle \(tęsinys(p_(1)),tęsinys(p_(2))\)).

2. Primityviųjų dalių skaičiavimas:

P 1 ′ (x) := p r i m p a r t (p 1 (x)) ; (\displaystyle p_(1)"(x):=primpart(p_(1)(x));)

P 2 ′ (x) := p r i m p a r t (p 2 (x)) . (\displaystyle p_(2)"(x):=primpart(p_(2)(x)).)

3. Polinomo liekanų sekos sudarymas:

P 1 ′ (x) , (\displaystyle p_(1)"(x),)

P 2 ′ (x) , (\displaystyle p_(2)"(x),)

P 3 (x) := p r e m (p 1 ′ (x) , p 2 ′ (x)) , (\displaystyle p_(3)(x):=prem(p_(1)"(x), p_(2 )"(x)))

P 4 (x) := p r e m (p 2 ′ (x) , p 3 (x)) , (\displaystyle p_(4)(x):=prem(p_(2)"(x), p_(3) (x)))

P 5 (x) := p r e m (p 3 (x) , p 4 (x)) , (\displaystyle p_(5) (x):=prem(p_(3) (x), p_(4) (x) ))))

. . . (\displaystyle...)

P h (x) := p r e m (p h − 2 (x) , p h − 1 (x)) . (\displaystyle p_(h)(x):=prem(p_(h-2)(x),p_(h-1)(x)).)

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į:

1. 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 $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:

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

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ėti prie jų veiksnius, kurie yra antrojo dalis, o ne pirmajame

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 pageidaujamas didžiausias skaičių $a$ ir $b$ bendras daliklis.

GCD ir LCM savybės

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

Jei K$(a;b)=k$ ir $m$-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 kuris bendras $a$ ir $b$ daliklis yra $D(a;b)$ daliklis

Euklido algoritmas yra būdas rasti didžiausią bendrą dviejų sveikųjų skaičių daliklį (gcd). Originalią algoritmo versiją, kai GCD randamas atimant, atrado Euklidas (III a. pr. Kr.). Šiuo metu padalijimas dažniau naudojamas apskaičiuojant GCD pagal Euklido algoritmą, nes šis metodas yra efektyvesnis.

Gcd apskaičiavimas dalijant

Didžiausias bendras skaičių poros daliklis yra didžiausias skaičius, dalijantis abu poros skaičius. Tegul reikia apskaičiuoti GCD skaičiams 108 ir 72. Padalinimo skaičiavimo algoritmas bus toks:

1. Padalinkite didesnį skaičių (dalyklą) iš mažesnio (daliklio): 108 / 72 = 1, likutis 36.
2. Kadangi liekana nebuvo lygi nuliui, daliklį padalysime dalikliu, o likutį – dalikliu: 72 / 36 = 2, likusioji dalis yra 0.
3. Kai liekana lygi nuliui, tada daliklis yra norimas gcd duotųjų skaičių porai. Tai yra, gcd(108, 72) = 36. Iš tiesų, 108/36 = 3 ir 72/36 = 2.

Šiame algoritme padalijimas kartojamas tol, kol liekana lygi nuliui. Kai jis tampa GCD yra paskutinio padalijimo daliklis. Pavyzdžiui, norite rasti GCD(106, 16):

1. 106/16 = 6, likusi dalis 10
2. 16/10 = 1, likusi dalis 6
3. 10/6 = 1, likusioji dalis 4
4. 6/4 = 1, likusi dalis 2
5. 4/2 = 2, likusioji dalis 0
6. gcd(106, 16) = 2

GCD skaičiavimas atimant

Atimant GCD, taip pat reikia pasiekti nulį. Algoritmas panašus į padalijimo metodą, tik čia kiekviename sekančiame etape atimama ir sumažinama dalis ir skirtumas nuo ankstesnio žingsnio. Mažesnis skaičius visada atimamas iš didesnio skaičiaus. Toks algoritmas tinka tik teigiamiems sveikiesiems skaičiams.

Tegul reikia rasti GCD(108, 72):

1. 108 - 72 = 36
2. 72 - 36 = 36
3. 36 - 36 = 0
4. gcd(108, 72) = 36

Raskite gcd(44, 60):

1. 60 - 44 = 16
2. 44 - 16 = 28
3. 28 - 16 = 12
4. 16 - 12 = 4
5. 12 - 4 = 8
6. 8 - 4 = 4
7. 4 - 4 = 0
8. gcd(44, 60) = 4

Šis algoritmas kartais apibūdinamas kitaip. Atimtis baigiasi anksčiau, tame žingsnyje, kai vienas skaičius dalija kitą. Tai yra, jie derina atimtį su dalijamumo testu. Tada 44 ir 60 GCD radimas atrodys taip:

1. Ar 44 lygiai padalija 60? Nr. 60–44 = 16.
2. Ar 16 tolygiai padalija 44? Nr. 44–16 = 28.
3. Ar 16 tolygiai padalija 28? Nr. 28–16 = 12.
4. Ar 12 tolygiai padalija 16? Nr. 16–12 = 4.
5. Ar 4 tolygiai padalija 12? Taip. Taigi gcd(44, 60) = 4.

Pastaba, GCD yra ne koeficientas, o daliklis. Jei pavyzdyje dalijame 12 iš 4, gauname koeficientą 3. Bet tai nėra GCD.

Euklido algoritmo įrodymas

Atsižvelgkime į tai, kad jei vienas natūralusis skaičius iš poros padalija kitą, tada jų gcd bus lygus mažesniajam iš jų. Galite parašyti taip:

jei a / b yra sveikasis skaičius, tada gcd(a, b) = b. Pavyzdžiui, gcd(15, 5) = 5.

Taigi, jei gausime skaičių porą, iš kurių vienas dalijasi kitą, tada mažesnis bus didžiausias bendras abiejų daliklis. Būtent tokios skaičių poros ir ieško Euklido algoritmas: vienas skaičius visiškai padalija kitą.

Antras faktas. Reikia įrodyti, kad jei vienas skaičius yra didesnis už kitą, tai jų didžiausias bendras daliklis yra lygus didžiausio mažesnio poros skaičiaus bendrajam dalikliui ir skirtumui tarp didesnių ir mažesnių skaičių. Tai galima parašyti taip:

jeigu< b, то НОД(a, b) = НОД(a, b - a).

Galime įrodyti, kad gcd(a, b) = gcd(a, b - a) taip. Tegu b – a = c. Jei bet kuris skaičius x dalijasi a ir b, tada jis taip pat dalins c. Juk jei a ir b skiriasi, tai daliklis į juos telpa sveikasis skaičius, bet skirtingą skaičių kartų. Ir jei atimsite vieną iš kito, tada daliklis taip pat turi tilpti į gautą skirtumą sveikąjį skaičių kartų.

Jei paeiliui mažinsime a ir b, tai anksčiau ar vėliau pasieksime tokią mažesniojo iš jų reikšmę, kuri visiškai padalija didesnę. Mažesnė iš tokios poros bus didžiausias bendras pradinės natūraliųjų skaičių poros daliklis. Tai yra Euklido algoritmo esmė.

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

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 įjungta 48 .

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

Antras žingsnis – padalinti 48 iki 16 gauname 3 . Tai yra 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 įjungta 111 . Pagal Euklido algoritmą gauname lygybių grandinę 432 = 111 3 + 99 , 111 = 99 1 + 12 , 99 = 12 8 + 3 , 12 = 3 4 .

Taigi didžiausias bendras skaičių daliklis 111 Ir 432 yra 3.

Atsakymas: gcd(111, 432) = 3.

3 pavyzdys

Raskite didžiausią bendrąjį 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 išskaidysime skaičius 220 ir 600 į pirminius veiksnius, gausime 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, vykdysime 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

Euklido algoritmas

Didžiausias bendras daliklis

Apsvarstykite šią problemą: reikia parašyti programą dviejų natūraliųjų skaičių didžiausiam bendrajam dalikliui (GCD) nustatyti.

Prisiminkime matematiką. Didžiausias bendras dviejų natūraliųjų skaičių daliklis yra didžiausias natūralusis skaičius, iš kurio jie dalijasi tolygiai. Pavyzdžiui, skaičiai 12 ir 18 turi bendrus daliklius: 2, 3, 6. Didžiausias bendras daliklis yra 6. Tai parašyta taip:

gcd(12, 18) = 6.

Pradinius duomenis pažymėkite M u N. Problemos teiginys yra toks:
Duota: M, N
Rasti: GCD (M, N).

Šiuo atveju papildomo matematinio įforminimo nereikia. Pats problemos teiginys yra formalaus matematinio pobūdžio. Nėra formulės, kaip apskaičiuoti GCD(M, N) iš M ir N reikšmių. Tačiau, kita vertus, gana seniai, dar prieš kompiuterių atsiradimą, buvo žinomas algoritminis šios problemos sprendimo būdas. . Tai vadinama Euklido algoritmas .

Euklido algoritmo idėja

Šio algoritmo idėja pagrįsta savybe, kad jei M>N, tada

GCD(M, N) = GCD(M – N, N).

Kitaip tariant, dviejų natūraliųjų skaičių gcd yra lygus jų teigiamo skirtumo gcd (jų skirtumo moduliui) ir mažesniam skaičiui.

Įrodyti šią savybę lengva. Tegu K yra bendras daliklis M u N (M > N). Tai reiškia, kad M \u003d mK, N \u003d nK, kur m, n yra natūralūs skaičiai, o m > n. Tada M - N \u003d K (m - n), o tai reiškia, kad K yra skaičiaus M - N daliklis. Vadinasi, visi bendrieji skaičių M ir N dalikliai yra jų skirtumo M - N dalikliai, įskaitant didžiausią bendras daliklis.

Antroji akivaizdi savybė:

GCD(M, M) = M.

„Rankiniam“ skaičiavimui Euklido algoritmas atrodo taip:

1) jei skaičiai lygūs, paimkite bet kurį iš jų kaip atsakymą, kitu atveju tęskite algoritmą;

2) pakeiskite didesnį skaičių skirtumu tarp didesnio ir mažesnio skaičiaus;

3) grįžti prie 1 dalies įgyvendinimo.

Apsvarstykite šį algoritmą M = 32, N = 24 pavyzdyje:

Algoritmo struktūra yra while-ciklas su įdėtomis šakomis. Ciklas kartojamas tol, kol M ir N reikšmės bus lygios viena kitai. Išsišakojus didesnė iš dviejų reikšmių pakeičiama jų skirtumu.

Dabar pažiūrėkite į pradinių verčių M = 32, N = 24 algoritmo sekimo lentelę.

Žingsnis	Operacija	M	N	Būklė
1	įvestis M	32
2	įvestis N		24
3	M¹N			32 ¹ 24, taip
4	M>N			32>24, taip
5	M: = M-N	8
6	M¹N			8 ¹ 24, taip
7	M>N			8>24, Nr
8	N:=N-M		16
9	M¹N			8 ¹ 16, taip
10	M>N			8>16, Nr
11	N:=N-M		8
12	M¹N			8 ¹ 8, Nr
13	terminalas M	8
14	galas

Galutinis rezultatas yra teisingas.

Programa AZ ir Pascal

Algoritmą rašome AI, o programą Pascal.

Klausimai ir užduotys

1. Kompiuteryje paleiskite programą Evklid. Išbandykite M=32, N=24; M = 696, N = 234.

2. Parašykite programą, kuri rastų didžiausią bendrą trijų skaičių daliklį pagal šią formulę:

gcd(A, B, C) = gcd(gcd(A, B), C).

3. Parašykite programą, kuri rastų dviejų skaičių mažiausiąjį bendrąjį kartotinį (LCM), naudodami formulę:

A × B = GCD(A, B) × LCM(A, B).