Eukleidilise algoritmi õppimine koolis. Eukleidese algoritm – suurima ühise jagaja leidmine

Laialt levinud e-kaubanduses. Samuti kasutatakse algoritmi lineaarsete diofantiine võrrandite lahendamisel, jätkumurdude konstrueerimisel Sturmi meetodil. Eukleidese algoritm on tänapäevase arvuteooria põhiline tööriist teoreemide tõestamiseks, näiteks Lagrange'i teoreem nelja ruudu summa kohta ja aritmeetika põhiteoreem.

Entsüklopeediline YouTube

1 / 5

✪ Matemaatika. Naturaalarvud: Eukleidese algoritm. Foxfordi veebiõppekeskus

✪ Eukleidese algoritm

✪ Eukleidese algoritm, kiire tee leia gcd

✪ Matemaatika 71. Suurim ühine jagaja. Eukleidese algoritm – Meelelahutusteaduste Akadeemia

✪ 20, kui loop Euclid Python algoritm

Subtiitrid

Lugu

Vana-Kreeka matemaatikud nimetasid seda algoritmi ἀνθυφαίρεσις või ἀνταναίρεσις - "vastastikune lahutamine". Seda algoritmi Euclid ei avastanud, kuna seda on juba mainitud Topeka Aristoteles. Eukleidese "Elementides" on seda kirjeldatud kaks korda – VII raamatus kahe naturaalarvu suurima ühisjagaja leidmiseks ja raamatus X kahe homogeense suuruse suurima ühismõõdu leidmiseks. Mõlemal juhul antakse kahe segmendi "ühismõõdu" leidmiseks algoritmi geomeetriline kirjeldus.

Kirjeldus

Eukleidese algoritm täisarvude jaoks

Lase a (\displaystyle a) Ja b (\displaystyle b)- täisarvud, mis ei ole samal ajal võrdsed nulliga, ja numbrijada

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))

määrab asjaolu, et iga r k (\displaystyle r_(k))- see on eelmise arvu jagamise jääk eelmisega ja eelviimane jagatakse viimasega, see tähendab:

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 , (\kuvastiil 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).)

Siis gcd( a, b), suurim ühine jagaja a Ja b, on võrdne r n , selle jada viimane nullist erinev liige.

Olemasolu selline r 1 , r 2 , ..., r n ehk jäägiga jagamise võimalus m peal n mis tahes terviku jaoks m ja terve n≠ 0 on tõestatud induktsiooniga sees m.

Korrektsus see algoritm tuleneb kahest järgmisest väitest:

• Lase a = b⋅q + r, siis gcd(a, b) = gcd(b, r).

Tõestus

• GCD( r, 0) = r iga nullist erineva jaoks r(sest 0 jagub mis tahes täisarvuga peale nulli).

Eukleidese geomeetriline algoritm

Olgu antud kaks pikkusesegmenti a Ja b. Lahutage väiksem segment suuremast segmendist ja asendage suurem segment saadud erinevusega. Korrake seda toimingut, kuni segmendid on võrdsed. Kui see juhtub, on algsed segmendid võrreldavad ja viimane saadud segment on nende suurim ühine mõõt. Kui ühist mõõtu pole, on protsess lõputu. Sellisel kujul kirjeldab algoritmi Euclid ja see on rakendatud kompassi ja joonlaua abil.

Näide

Illustreerimiseks kasutatakse gcd leidmiseks Eukleidese algoritmi a= 1071 ja b= 462. Alustuseks lahutage 1071-st 462 kordne, kuni saame erinevuse, mis on väiksem kui 462. Me peame lahutama 462 kaks korda, ( q 0 = 2), jäädes 147-ga:

1071 = 2 × 462 + 147.

Seejärel lahutame 462-st 147 kordse, kuni saame erinevuse, mis on väiksem kui 147. Me peame lahutama 147 kolm korda ( q 1 = 3), ülejäänud 21:

462 = 3 x 147 + 21.

Seejärel lahutame 147-st 21 kordse, kuni saame erinevuse, mis on väiksem kui 21. Me peame lahutama 21 seitse korda ( q 2 = 7), jäädes ilma jäägita:

147 = 7 x 21 + 0.

Seega jada a > b > r 1 > r 2 > r 3 > … > r n sel konkreetsel juhul näeks välja selline:

1071 > 462 > 147 > 21.

Kuna viimane jääk on null, lõpeb algoritm 21-ga ja gcd(1071, 462) = 21.

Tabelina olid sammud järgmised:

Rakendused

Laiendatud Eukleidese algoritm ja Bezouti seos

Valemid jaoks r i (\displaystyle r_(i)) saab ümber kirjutada nii:

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) (\kuvastiil 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 (\kuvastiil (a,b)=r_(n)=as+bt)

Siin s Ja t terve. Seda suurima ühise jagaja esitust nimetatakse Bezouti seoseks ja arvudeks s Ja t- koefitsiendid Bezu . Bezouti seos on võtmeks Eukleidese lemma tõestuses ja aritmeetika põhiteoreemis.

Jätkuvad murded

Eukleidese algoritm on jätkuvate murdudega üsna tihedalt seotud. Suhtumine a/b lubab jätkuvat murdosa esitust:

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

Sel juhul on jätkuv murd ilma viimase liikmeta võrdne Bezouti koefitsientide suhtega t/s miinusmärgiga võetud:

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

Eukleidese algoritmi defineerivate võrdsuste jada saab ümber kirjutada järgmisel kujul:

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(joonatud)(\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(joondatud)))

Viimane liige võrrandi paremal küljel on alati võrdne järgmise võrrandi vasaku külje pöördarvuga. Seetõttu saab kaks esimest võrrandit ühendada järgmisel kujul:

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))))))

Kolmandat võrdsust saab kasutada avaldise nimetaja asendamiseks r 1 /r 0, saame:

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)))))))

Viimase jäägi suhe r k /r k−1 saab alati asendada jada järgmise võrrandiga ja nii edasi kuni viimase võrrandini. Tulemuseks on jätkuv murdosa:

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)))))))))=)

Üldistatud Eukleidese algoritm polünoomide jaoks

Eukleidese algoritm ja laiendatud Eukleidese algoritm loomulikultüldistab polünoomide ringiks k[x] ühest muutujast suvalise välja kohal k, kuna selliste polünoomide jaoks on defineeritud jäägiga jagamise tehe. Eukleidese polünoomide algoritmi täitmisel saadakse sarnaselt Eukleidese täisarvude algoritmiga polünoomijääkide jada (PRS).

Rõnga näide Z[x]

Olgu cont(f) definitsiooni järgi polünoomi f(x) koefitsientide gcd väärtusest Z[x] - sisu polünoom. Nimetatakse jagatis f(x) jagamiseks cont(f)-ga primitiivne osa polünoom f(x) ja seda tähistatakse primpart(f(x)). Neid määratlusi on vaja kahe polünoomi gcd leidmiseks lk 1 (x) Ja lk 2 (x) ringis Z[x]. Täisarvudest ületavate polünoomide puhul kehtib järgmine:

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

P r i m p a r t ((\displaystyle primpart() GCD ( p 1 (x) , p 2 (x) )) = (\kuvastiil \(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))\).)

Seega taandub kahe suvalise polünoomi gcd leidmise probleem primitiivsete polünoomide gcd leidmise probleemiks.

Olgu Z[x]-st kaks primitiivset polünoomi p 1 (x) ja p 2 (x), mille astmete seos on täidetud: deg(p 1 (x)) = m ja deg(p 2 (x) ) = n, m > n. Polünoomide jagamine jäägiga eeldab dividendi kõrgeima koefitsiendi täpset jaguvust jagaja kõrgeima koefitsiendiga; jäägiga jagamist üldjuhul teha ei saa. Seetõttu võetakse kasutusele pseudojaotusalgoritm, mis võimaldab siiski saada pseudojagatise ja pseudojäägi (prem), mis ise kuuluvad täisarvude kohal olevate polünoomide hulka.

Pseudojaotuse all peame silmas seda, et jagamisele endale eelneb polünoomi korrutamine p 1 (x) (\displaystyle p_(1) (x)) peal (l c (p 2 (x))) m − n + 1 (\displaystyle (lc(p_(2)(x)))^(m-n+1)), see on

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)),}

Kus q (x) (\displaystyle q(x)) Ja r (x) (\displaystyle r(x))- vastavalt pseudoosaline ja pseudojääk.

Niisiis, p 1 (x) , p 2 (x) ∈ Z [ x ] (\displaystyle p_(1) (x), p_(2) (x)\in Z[x]), enamgi veel kraad ⁡ (p 1) = n 1 ≥ kraad ⁡ (p 2) = n 2 (\displaystyle \deg(p_(1))=n_(1)\geq \deg(p_(2))=n_(2) ). Seejärel koosneb Eukleidese algoritm järgmistest sammudest:

1. GCD sisu arvutamine:

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

2. Primitiivsete osade arvutamine:

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. Polünoomijääkide jada koostamine:

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

Suurim ühine jagaja

2. definitsioon

Kui naturaalarv a jagub naturaalarvuga $b$, siis $b$ nimetatakse arvu $a$ jagajaks ja arvu $a$ arvu $b$ kordseks.

Olgu $a$ ja $b$ naturaalarvud. Arvu $c$ nimetatakse nii $a$ kui ka $b$ ühiseks jagajaks.

Arvude $a$ ja $b$ ühisjagajate hulk on lõplik, kuna ükski neist jagajatest ei saa olla suurem kui $a$. See tähendab, et nende jagajate hulgas on suurim, mida nimetatakse arvude $a$ ja $b$ suurimaks ühisjagajaks ning selle tähistamiseks kasutatakse tähistust:

$gcd \ (a; b) \ ​​või \ D \ (a; b) $

Kahe arvu suurima ühisjagaja leidmiseks:

1. Leidke sammus 2 leitud arvude korrutis. Saadud arv on soovitud suurim ühisjagaja.

Näide 1

Leidke numbrite $121$ ja $132.$ gcd

$242=2\cdot 11\cdot 11$

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

Valige numbrid, mis sisalduvad nende numbrite laienduses

$242=2\cdot 11\cdot 11$

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

Leidke sammus 2 leitud arvude korrutis. Saadud arv on soovitud suurim ühisjagaja.

$gcd=2\cdot 11=22$

Näide 2

Leidke monomialide GCD $ 63 $ ja $ 81 $.

Leiame vastavalt esitatud algoritmile. Selle jaoks:

Jagame arvud algteguriteks

63 $=3\cdot 3\cdot 7$

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

Valime numbrid, mis sisalduvad nende numbrite laienduses

63 $=3\cdot 3\cdot 7$

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

Leiame sammus 2 leitud arvude korrutise. Saadud arv on soovitud suurim ühisjagaja.

$gcd=3\cdot 3=9$

Kahe arvu GCD saate leida muul viisil, kasutades arvude jagajate komplekti.

Näide 3

Leidke numbrite $48$ ja $60$ gcd.

Lahendus:

Leidke $48$ jagajate komplekt: $\left\((\rm 1,2,3.4.6,8,12,16,24,48)\right\)$

Nüüd leiame jagajate komplekti $60$:$\ \left\((\rm 1,2,3,4,5,6,10,12,15,20,30,60)\right\)$

Leiame nende hulkade ristumiskoha: $\left\((\rm 1,2,3,4,6,12)\right\)$ – see hulk määrab arvude $48$ ja $60 ühisjagajate hulga $. Selle komplekti suurim element on number 12 $. Seega on $48$ ja $60$ suurim ühine jagaja $12$.

NOC määratlus

3. määratlus

naturaalarvude ühiskordne$a$ ja $b$ on naturaalarv, mis on arvude $a$ ja $b$ kordne.

Arvude ühiskordsed on arvud, mis jaguvad algarvuga ilma jäägita. Näiteks arvude $25$ ja $50$ puhul on ühiskordseteks numbrid $50,100,150,200$ jne.

Väiksemat ühiskordset nimetatakse vähimaks ühiskordseks ja seda tähistatakse LCM$(a;b)$ või K$(a;b).$

Kahe numbri LCM-i leidmiseks vajate:

1. Jagage arvud algteguriteks
2. Kirjutage välja tegurid, mis on osa esimesest arvust ja lisage neile tegurid, mis on osa teisest ja ei lähe esimesele

Näide 4

Leidke numbrite 99 $ ja 77 $ LCM.

Leiame vastavalt esitatud algoritmile. Selle jaoks

Jagage arvud algteguriteks

99 $=3\cdot 3\cdot 11$

Kirjutage üles esimeses sisalduvad tegurid

lisada neile tegurid, mis on osa teisest ja ei lähe esimese juurde

Leidke sammus 2 leitud arvude korrutis. Saadud arv on soovitud vähim ühiskordne

$LCC=3\cdot 3\cdot 11\cdot 7=693 $

Arvude jagajate loendite koostamine on sageli väga aeganõudev. GCD leidmiseks on võimalus, mida nimetatakse Eukleidese algoritmiks.

Väited, millel Eukleidese algoritm põhineb:

Kui $a$ ja $b$ on naturaalarvud ja $a\vdots b$, siis $D(a;b)=b$

Kui $a$ ja $b$ on naturaalarvud, nii et $b

Kasutades $D(a;b)= D(a-b;b)$, saame vaadeldavaid arve järjest vähendada, kuni jõuame sellise arvupaarini, et üks neist jagub teisega. Siis neist arvudest väiksem on arvude $a$ ja $b$ soovitud suurim ühisjagaja.

GCD ja LCM omadused

1. $a$ ja $b$ mis tahes ühiskordne jagub K$(a;b)$-ga
2. Kui $a\vdots b$ , siis K$(a;b)=a$

Kui K$(a;b)=k$ ja $m$-loodusarv, siis K$(am;bm)=km$

Kui $d$ on väärtuste $a$ ja $b$ ühine jagaja, siis K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d ) $

Kui $a\vdots c$ ja $b\vdots c$ , siis on $\frac(ab)(c)$ väärtuste $a$ ja $b$ ühiskordne

Mis tahes naturaalarvude $a$ ja $b$ korral on võrdsus

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

$a$ ja $b$ mis tahes ühisjagaja on $D(a;b)$ jagaja

Eukleidese algoritm on viis kahe täisarvu suurima ühisjagaja (gcd) leidmiseks. Algoritmi algversiooni, kui GCD leitakse lahutamise teel, avastas Euclid (3. sajand eKr). Praegu kasutatakse jagamist sagedamini GCD arvutamisel Eukleidese algoritmi järgi, kuna see meetod on tõhusam.

Gcd arvutamine jagamise teel

Arvupaari suurim ühisjagaja on suurim arv, mis jagab selle paari mõlemad arvud. Olgu, et tuleb arvutada GCD arvude 108 ja 72 jaoks. Jagamise arvutamise algoritm on järgmine:

1. Jagage suurem arv (jagaja) väiksemaga (jagaja): 108 / 72 = 1, jääk 36.
2. Kuna jääk ei olnud võrdne nulliga, teeme jagaja jagatavaks ja jääk jagajaks: 72 / 36 = 2, jääk on 0.
3. Kui jääk on null, on jagajaks antud arvude paari soovitud gcd. See tähendab, et gcd(108, 72) = 36. Tõepoolest, 108/36 = 3 ja 72/36 = 2.

Selles algoritmis jagamist korratakse, kuni jääk on null. Kui temast saab GCD on viimase jaotuse jagaja. Näiteks soovite leida GCD(106, 16):

1. 106/16 = 6, ülejäänud 10
2. 16/10 = 1, ülejäänud 6
3. 10/6 = 1, ülejäänud 4
4. 6/4 = 1, ülejäänud 2
5. 4/2 = 2, ülejäänud 0
6. gcd(106, 16) = 2

GCD arvutamine lahutamise teel

GCD leidmisel lahutamise teel on vaja ka jõuda nullini. Algoritm on sarnane jagamismeetodiga, ainult siin lahutatakse ja vähendatakse igal järgmisel etapil alamosa ja erinevus eelmisest etapist. Väiksem arv lahutatakse alati suuremast arvust. Selline algoritm sobib ainult positiivsete täisarvude jaoks.

Olgu GCD(108, 72) leidmiseks nõutav:

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

Leidke 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

Seda algoritmi kirjeldatakse mõnikord erinevalt. Lahutamine lõpeb varem, sammuga, mil üks arv jagab teise. See tähendab, et nad ühendavad lahutamise jagatavuse testimisega. Siis näeb GCD leidmine 44 ja 60 jaoks välja järgmine:

1. Kas 44 jagab võrdselt 60-ga? Ei. 60–44 = 16.
2. Kas 16 jagab võrdselt 44-ga? Ei. 44-16 = 28.
3. Kas 16 jagab võrdselt 28-ga? Ei. 28-16 = 12.
4. Kas 12 jagab võrdselt 16-ga? Ei. 16-12 = 4.
5. Kas 4 jagab võrdselt 12-ga? Jah. Seega gcd(44, 60) = 4.

Märge, GCD ei ole jagatis, vaid jagaja. Kui näites jagame 12 4-ga, saame jagatise 3. Kuid see pole GCD.

Eukleidese algoritmi tõestus

Võtame arvesse asjaolu, et kui paarist üks naturaalarv jagab teise, siis on nende gcd võrdne neist väiksemaga. Võite selle kirjutada nii:

kui a / b on täisarv, siis gcd(a, b) = b. Näiteks gcd(15, 5) = 5.

Seega, kui lõpuks jõuame arvupaarini, millest üks jagab teise, siis väiksem on mõlema suurim ühine jagaja. Just sellist arvupaari otsitakse Eukleidese algoritmi järgi: üks arv jagab teise täielikult.

Teine fakt. On vaja tõestada, et kui üks arv on suurem kui teine, siis on nende suurim ühisjagaja võrdne paari väiksema arvu suurima ühisjagajaga ning suuremate ja väiksemate arvude erinevusega. Selle saab kirjutada nii:

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

Seda, et gcd(a, b) = gcd(a, b - a) saame tõestada järgmiselt. Olgu b - a = c. Kui suvaline arv x jagab a ja b, jagab see ka c. Lõppude lõpuks, kui a ja b on erinevad, siis jagaja mahub neisse täisarvu, kuid erinev arv kordi. Ja kui lahutada üks teisest, siis peab ka jagaja mahtuma saadud vahe hulka täisarv korda.

Kui vähendame järjestikku a ja b, siis varem või hiljem jõuame neist väiksema väärtuseni, mis jagab suurema täielikult ära. Sellisest paarist väiksem on algse naturaalarvude paari suurim ühine jagaja. See on Eukleidese algoritmi sisu.

Vaatleme kahte peamist meetodit GCD leidmiseks kahel peamisel viisil: kasutades Eukleidese algoritmi ja faktoringut. Kasutame mõlemat meetodit kahe, kolme ja enama arvu puhul.

Eukleidese algoritm GCD leidmiseks

Eukleidese algoritmi abil on lihtne arvutada kahe positiivse arvu suurimat ühisjagajat. Oleme esitanud Eukleidese algoritmi sõnastused ja tõendid jaotises Suurim ühine jagaja: determinant, näited.

Algoritmi põhiolemus on järjepidevalt jagamine jäägiga, mille käigus saadakse vormi võrdsuste jada:

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

Saame jaotuse lõpetada millal rk + 1 = 0, kus r k = gcd (a , b).

Näide 1

64 Ja 48 .

Lahendus

Tutvustame tähistust: a = 64 , b = 48 .

Eukleidese algoritmi alusel viime läbi jagamise 64 peal 48 .

Saame 1 ja ülejäänud 16 . Selgub, et q 1 = 1, r 1 = 16.

Teine samm on jagamine 48 kella 16-ks saame 3 . See on q2 = 3, A r2 = 0. Seega on arv 16 tingimusest tulenevate arvude suurim ühine jagaja.

Vastus: gcd(64, 48) = 16.

Näide 2

Mis on numbrite GCD 111 Ja 432 ?

Lahendus

Jaga 432 peal 111 . Eukleidese algoritmi järgi saame võrduste ahela 432 = 111 3 + 99 , 111 = 99 1 + 12 , 99 = 12 8 + 3 , 12 = 3 4 .

Seega arvude suurim ühisjagaja 111 Ja 432 on 3.

Vastus: gcd(111, 432) = 3.

Näide 3

Leidke 661 ja 113 suurim ühisjagaja.

Lahendus

Jagame arvud järjestikku ja saame GCD (661 , 113) = 1 . See tähendab, et 661 ja 113 on suhteliselt algarvud. Võiksime selle välja mõelda enne arvutuste alustamist, kui vaataksime algarvude tabelit.

Vastus: gcd(661, 113) = 1.

GCD leidmine arvude algteguriteks faktoriseerimise teel

Faktooringuga kahe arvu suurima ühisjagaja leidmiseks on vaja korrutada kõik nende kahe arvu lahutamisel saadud algtegurid, mis on neile ühised.

Näide 4

Kui jagame arvud 220 ja 600 algteguriteks, saame kaks korrutist: 220 = 2 2 5 11 Ja 600 = 2 2 2 3 5 5. Nende kahe toote ühised tegurid on 2, 2 ja 5. See tähendab, et NOD (220, 600) = 2 2 5 = 20.

Näide 5

Leidke arvude suurim ühisjagaja 72 Ja 96 .

Lahendus

Leia kõik arvude algtegurid 72 Ja 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

Kahe arvu ühised algtegurid: 2 , 2 , 2 ja 3 . See tähendab, et NOD (72, 96) = 2 2 2 3 = 24.

Vastus: gcd(72, 96) = 24.

Kahe arvu suurima ühisjagaja leidmise reegel põhineb suurima ühisjagaja omadustel, mille kohaselt gcd (m a 1 , m b 1) = m gcd (a 1 , b 1) , kus m on mis tahes positiivne täisarv .

Kolme või enama numbri GCD leidmine

Olenemata arvude arvust, mille jaoks peame leidma GCD, järgime sama algoritmi, mis seisneb kahe järjestikuse arvu GCD leidmises. See algoritm põhineb järgmise teoreemi rakendamisel: Mitme arvu GCD a 1 , a 2 , … , a k on võrdne arvuga dk, mis leitakse gcd järjestikuses arvutuses (a 1, a 2) = d 2, GCD (d2, a3) = d3, GCD (d3, a4) = d4, …, GCD (dk-1, a k) = dk.

Näide 6

Leidke nelja arvu 78, 294, 570 ja suurim ühisjagaja 36 .

Lahendus

Tutvustame tähistust: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

Alustame arvude 78 ja 294 GCD leidmisega: d2= GCD (78 , 294) = 6 .

Nüüd hakkame otsima d 3 \u003d GCD (d 2, a 3) \u003d GCD (6, 570) . Eukleidese algoritmi järgi 570 = 6 95 . See tähendab et d 3 = GCD (6 , 570) = 6 .

Leidke d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36) . 36 jagub 6-ga ilma jäägita. See võimaldab meil saada d4= GCD (6 , 36) = 6 .

d4 = 6, see tähendab GCD (78 , 294 , 570 , 36) = 6 .

Vastus:

Ja nüüd vaatame veel ühte võimalust nende ja muude numbrite jaoks GCD arvutamiseks. Leiame gcd, korrutades kõik arvude tavalised algtegurid.

Näide 7

Arvutage arvude 78 , 294 , 570 ja gcd 36 .

Lahendus

Jagame need arvud algteguriteks: 78 = 2 3 13 , 294 = 2 3 7 7 , 570 = 2 3 5 19 , 36 = 2 2 3 3 .

Kõigi nelja numbri puhul on ühised algtegurid arvud 2 ja 3.

Selgub, et NOD (78, 294, 570, 36) = 2 3 = 6.

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

Negatiivsete arvude gcd leidmine

Kui peame tegelema negatiivsete arvudega, siis saame kasutada nende arvude mooduleid suurima ühisjagaja leidmiseks. Seda saame teha, teades vastandmärgiga numbrite omadust: arvud n Ja -n neil on samad jagajad.

Näide 8

Leidke negatiivsete täisarvude gcd − 231 Ja − 140 .

Lahendus

Arvutuste tegemiseks võtame tingimuses antud arvude moodulid. Need on numbrid 231 ja 140. Ütleme lühidalt: GCD (− 231 , − 140) = GCD (231, 140). Nüüd rakendame kahe arvu algtegurite leidmiseks Eukleidese algoritmi: 231 = 140 1 + 91 ; 140 = 91 1 + 49; 91 = 49 1 + 42; 49 = 42 1 + 7 ja 42 = 7 6. Saame, et gcd (231, 140) = 7 .

Ja alates NOD-st (− 231 , − 140) = GCD (231 , 140) , siis numbrite gcd − 231 Ja − 140 võrdub 7 .

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

Näide 9

Määrake kolme arvu gcd - 585, 81 ja − 189 .

Lahendus

Asendame ülaltoodud loendis olevad negatiivsed arvud nende absoluutväärtustega, saame GCD (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . Seejärel jagame kõik antud arvud algteguriteks: 585 = 3 3 5 13, 81 = 3 3 3 3 ja 189 = 3 3 3 7. Algtegurid 3 ja 3 on kolmele arvule ühised. Selgub, et gcd (585 , 81 , 189) = gcd (- 585 , 81 , - 189) = 9 .

Vastus: GCD (− 585 , 81 , − 189) = 9 .

Kui märkate tekstis viga, tõstke see esile ja vajutage Ctrl+Enter

Eukleidese algoritm

Suurim ühine jagaja

Mõelge järgmisele probleemile: kahe naturaalarvu suurima ühisjagaja (GCD) määramiseks on vaja kirjutada programm.

Meenutagem matemaatikat. Kahe naturaalarvu suurim ühisjagaja on suurim naturaalarv, millega need on võrdselt jagatavad. Näiteks arvudel 12 ja 18 on ühised jagajad: 2, 3, 6. Suurim ühine jagaja on 6. See on kirjutatud järgmiselt:

gcd(12, 18) = 6.

Tähistage lähteandmeid kui M u N. Probleemi avaldus on järgmine:
Arvestades: M, N
Leia: GCD (M, N).

Sel juhul ei ole vaja täiendavat matemaatilist vormistamist. Ülesande püstitus ise on formaalset matemaatilist laadi. Puudub valem GCD(M, N) arvutamiseks M ja N väärtustest. Kuid teisest küljest, üsna kaua aega tagasi, ammu enne arvutite tulekut, oli selle probleemi lahendamiseks tuntud algoritmiline meetod. . Seda nimetatakse Eukleidese algoritm .

Eukleidese algoritmi idee

Selle algoritmi idee põhineb omadusel, et kui M>N, siis

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

Teisisõnu, kahe naturaalarvu gcd on võrdne nende positiivse erinevuse gcd-ga (nende erinevuse moodul) ja väiksema arvuga.

Seda omadust on lihtne tõestada. Olgu K ühisjagaja M u N (M > N). See tähendab, et M \u003d mK, N \u003d nK, kus m, n on naturaalarvud ja m > n. Siis M - N \u003d K (m - n), mis tähendab, et K on arvu M - N jagaja. Seega on kõik arvude M ja N tavalised jagajad nende erinevuse M - N jagajad, sealhulgas suurim ühine jagaja.

Teine ilmne omadus:

GCD(M, M) = M.

"Käsitsi" loendamise jaoks näeb Eukleidese algoritm välja järgmine:

1) kui arvud on võrdsed, siis võta vastuseks ükskõik milline neist, vastasel juhul jätkake algoritmi;

2) asendada suurem arv suurema ja väiksema arvu vahega;

3) pöörduda tagasi lõike 1 rakendamise juurde.

Mõelge sellele algoritmile näitel M = 32, N = 24:

Algoritmi struktuur on pesastatud hargnemisega while-tsükkel. Tsükkel kordub, kuni M ja N väärtused on üksteisega võrdsed. Hargnemisel asendatakse kahest väärtusest suurem nende erinevusega.

Nüüd vaadake algväärtuste M = 32, N = 24 algoritmi jälgimistabelit.

Samm	Operatsioon	M	N	Seisund
1	sisend M	32
2	sisend N		24
3	M¹N			32 ¹ 24, jah
4	M>N			32>24, jah
5	M: = M-N	8
6	M¹N			8 ¹ 24, jah
7	M>N			8>24, nr
8	N:=N-M		16
9	M¹N			8 ¹ 16, jah
10	M>N			8>16, nr
11	N:=N-M		8
12	M¹N			8 ¹ 8, nr
13	terminal M	8
14	lõpp

Lõpptulemus on õige.

Programm AZ ja Pascal keeles

Algoritmi kirjutame AI-s ja programmi Pascalis.

Küsimused ja ülesanded

1. Käivitage arvutis programm Evklid. Katsetage M=32, N=24; M = 696, N = 234.

2. Kirjutage programm, mis leiab järgmise valemi abil kolme arvu suurima ühisjagaja:

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

3. Kirjutage programm kahe arvu vähima ühiskordse (LCM) leidmiseks, kasutades valemit:

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