Patunay ng Euclidean algorithm para sa paghahanap ng mga node. Euclidean algorithm para sa paghahanap ng GCD (pinakamahusay na karaniwang divisor). Application ng Euclidean algorithm
Euclidean algorithm para sa paghahanap ng GCD (pinakamahusay na karaniwang divisor)
Ibinigay ang dalawang di-negatibong integer at . Ito ay kinakailangan upang mahanap ang kanilang pinakamalaking karaniwang divisor, i.e. ang pinakamalaking bilang na isang divisor ng pareho , at . Naka-on wikang Ingles Ang "greatest common divisor" ay nakasulat na "greatest common divisor", at ang karaniwang designation nito ay:
(dito ang simbolo na "" ay nagpapahiwatig ng divisibility, ibig sabihin, "" ay nagsasaad ng "divides")
Kapag ang isa sa mga numero ay katumbas ng zero, at ang isa ay iba sa zero, ang kanilang pinakamalaking karaniwang divisor, ayon sa kahulugan, ay ang pangalawang numerong ito. Kapag ang parehong mga numero ay katumbas ng zero, ang resulta ay hindi natukoy (anumang walang katapusang malaking bilang ang gagawin), ilalagay namin ang pinakamalaking karaniwang divisor sa kasong ito katumbas ng zero. Samakatuwid, maaari nating pag-usapan ang sumusunod na panuntunan: kung ang isa sa mga numero ay katumbas ng zero, kung gayon ang kanilang pinakamalaking karaniwang divisor ay katumbas ng pangalawang numero.
Ang algorithm ni Euclid, na tinalakay sa ibaba, ay malulutas ang problema sa paghahanap ng pinakamalaking karaniwang divisor ng dalawang numero at para sa .
Ang algorithm na ito ay unang inilarawan sa Euclid's Elements (circa 300 BC), bagaman ito ay lubos na posible na ang algorithm na ito ay may mas naunang mga pinagmulan.
Algorithm
Ang algorithm mismo ay napaka-simple at inilalarawan ng sumusunod na formula:
Pagpapatupad
int gcd (int a, int b) ( if (b == 0 ) return a; else return gcd (b, a % b) ; )Gamit ang C++ ternary conditional operator, ang algorithm ay maaaring maisulat nang mas maikli:
int gcd (int a, int b) ( return b ? gcd (b, a % b): a; )Sa wakas, ipinakita namin ang hindi recursive na anyo ng algorithm:
int gcd (int a, int b) ( habang (b) ( a % = b; swap (a, b) ; ) return a; )Patunay ng Katumpakan
Una, tandaan na sa bawat pag-ulit ng Euclidean algorithm, ang pangalawang argumento nito ay mahigpit na bumababa, samakatuwid, dahil ito ay hindi negatibo, pagkatapos ay ang Euclidean algorithm laging kumpleto.
Para sa patunay ng kawastuhan kailangan nating ipakita iyon para sa anumang >.
Ipakita natin na ang dami sa kaliwang bahagi ng equation ay nahahati sa tunay na nasa kanan, at ang dami sa kanan ay nahahati sa isa sa kaliwa. Malinaw, ito ay mangangahulugan na ang kaliwa at kanang bahagi ay magkasabay, na magpapatunay sa kawastuhan ng Euclidean algorithm.
Tukuyin natin . Pagkatapos, sa pamamagitan ng kahulugan, at .
Ngunit pagkatapos ay sumusunod mula dito:
Kaya, ang pag-alala sa pahayag, nakukuha namin ang sistema:
Gamitin natin ngayon ang sumusunod na simpleng katotohanan: kung para sa ilan tatlong numero natupad: at , pagkatapos ay natupad at: . Sa ating sitwasyon, nakukuha natin:
O, pinapalitan ang kahulugan nito bilang , nakukuha natin ang:
Kaya, nagawa namin ang kalahati ng patunay: ipinakita namin na ang kaliwang bahagi ay naghahati sa kanan. Ang ikalawang kalahati ng patunay ay ginagawa sa katulad na paraan.
Oras ng trabaho
Tinatantya ang oras ng pagpapatakbo ng algorithm Ang teorama ni Lamé, na nagtatatag ng nakakagulat na koneksyon sa pagitan ng Euclidean algorithm at ng Fibonacci sequence:
Kung > at para sa ilan , ang Euclidean algorithm ay hindi na gagawa ng mga recursive na tawag.
1.1 Paglalapat ng Euclidean algorithm
Tulad ng anumang trabahong mahusay na nagawa, ang Euclidean algorithm ay gumagawa ng higit pa kaysa sa orihinal na inaasahan. Mula sa kanyang pagsusuri ay malinaw, halimbawa, na ang hanay ng mga divisors a at b ay tumutugma sa set ng divisors (a, b). Nagbibigay din siya praktikal na paraan paghahanap ng mga numero u at v mula sa Z (o, kung gusto mo, mula sa theorem ng talata 2) upang
r n = au + bv = (a, b).
Sa katunayan, mula sa chain of equalities mayroon tayo:
r n = r n -2 - r n -1 q n = r n -2 - (r n -3 - r n -2 q n -1) q n =...
(pumupunta kami sa kadena ng mga pagkakapantay-pantay mula sa ibaba hanggang sa itaas, na nagpapahayag ng natitira mula sa bawat susunod na pagkakapantay-pantay at pinapalitan ito sa ekspresyong nakuha sa sandaling ito)
Au + bv = (a, b).
Walang alinlangan, ang pamamaraang inilarawan ni Euclid para sa pagtukoy ng pangkalahatang sukat ng dalawang dami na may kaugnayan sa mga numero (at ang pangkalahatang sukat ng dalawang natural na mga numero, malinaw naman, ang kanilang pinakadakilang karaniwang divisor) ay naimbento nang matagal bago ang Euclid. Ang mga sinaunang Chinese mathematician ay natagpuan din ang GCD sa parehong paraan. At tanging ang katotohanan na ang pamamaraang ito ay naging kilala sa Renaissance mula sa "Mga Prinsipyo" ang nagbigay sa kanya ng pangalang "Euclidean algorithm"
Malamang, ito ay lumitaw mula sa komersyal na kasanayan ng mga sinaunang mangangalakal, kapag kailangan nilang ihambing ang iba't ibang mga ratio ng mga integer. Paano, halimbawa, maihahambing ang mga ratio ng mga numerong 3703700 at 1234567 at ang mga numerong 22962965 at 7654321? Natural lang na subukang alamin kung gaano karaming beses ang mas maliit na numero ay umaangkop sa mas malaki. Madaling suriin na ang 3703700 = 2 1234567 + 1234566, at 22962965 = 3 7654321 + 2. Malinaw na ngayon na ang ratio ng 3703700 hanggang 1234567 ay mas mababa kaysa sa ratio ng 229629 na ngayon ay isinulat natin ngayon.
2,99999919 <= 3, 000000261,
Ipinaliwanag ng mga sinaunang calculator sa isang mahabang parirala.
Kung kailangan nating ihambing ang mas malapit na mga ratio ng mga numero, halimbawa, at, kung gayon ang mga kalkulasyon ay magiging mas kumplikado:
71755875 = 61735500 + 10020375;
61735500 = 6 10020375 + 1613250;
10020375 = 6 1613250 + 340875;
1613250 = 4 340875 + 249750;
340875 = 249750 + 91125;
249750 = 2 91125 + 67500;
91125 = 67500 + 23625;
67500 = 2 23625 + 20250;
23625 = 20250 + 3375;
20250 = 6 3375.
Ang Euclidean algorithm dito ay nagpapahintulot sa amin na matukoy ang gcd ng mga numerong 71755875 at 61735500, na katumbas ng 3375 at tumutugma sa pagpapalawak ng ratio na 71755875 hanggang 61735500 sa isang patuloy na bahagi:
Ang Euclid algorithm ay lumalabas na katumbas ng modernong pamamaraan para sa pag-decomposing ng isang numero sa isang patuloy na fraction at, bukod dito, pinapayagan kang "i-round off" ang mga ratio ng mga numero, i.e. palitan ang isang fraction na may malaking denominator ng isang napakalapit na fraction na may mas maliit na denominator. Sa katunayan, ang expression
katumbas ng isang fraction, sa modernong matematika ay tinatawag na "angkop na fraction" ng agnas ng kaugnayan b = sa isang patuloy (o patuloy) na bahagi.
Malinaw na
b=1+< 1 + и б=1 + > 1+ = ,
dahil ang
Ang paghahambing sa itaas ay ginawa noong ika-3 siglo. BC. Aristarchus ng Samos sa kanyang treatise "Sa layo at laki ng Buwan at Araw."
Alam na ngayon na ang mga angkop na praksyon ng patuloy na pagpapalawak ng praksyon ng anumang (makatuwiran o hindi makatwiran) na numero ay ang pinakamahusay na makatwirang pagtatantya ng numerong iyon.
Algorithm na may polynomials
Ang algorithm ng Euclid ay isang paraan para sa paghahanap ng pinakamalaking karaniwang divisor ng dalawang integer, pati na rin ang dalawang polynomial ng parehong variable...
Ang isa sa mga pinakalumang mathematical algorithm ay ang Euclid algorithm para sa paghahanap ng pinakamalaking karaniwang divisor ng dalawang positibong numero. Narito ang pinakasimpleng anyo nito. Hayaang maibigay ang dalawang integer. Kung pantay sila...
Pagsusuri ng Euclidean algorithm sa Euclidean rings
Bago natin simulan ang pagsusuri sa Euclidean algorithm, tingnan natin ang mga numero ng Fibonacci. Ang kakanyahan ng Fibonacci sequence ay simula sa 1.1, ang susunod na numero ay makukuha sa pamamagitan ng pagdaragdag ng dalawang nauna. 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ......
Ang kasaysayan ng pagbuo ng konsepto ng "algorithm". Ang pinakasikat na mga algorithm sa kasaysayan ng matematika
Ang Euclidean algorithm ay isang unibersal na paraan na nagbibigay-daan sa iyong kalkulahin ang pinakamalaking karaniwang divisor ng dalawang positibong integer. Paglalarawan ng algorithm para sa paghahanap ng GCD ayon sa dibisyon: 1. Mas malaking numero hatiin sa mas maliit 2. Kung ito ay hinati nang walang nalalabi...
Gaussian integer ring
Ginagamit namin ang karaniwang kahulugan ng pinakamalaking karaniwang divisor para sa mga singsing. Ang GCD ng dalawang Gaussian na numero ay ang kanilang karaniwang divisor na nahahati ng anumang iba pang karaniwang divisor. Tulad ng sa maraming integer...
Mga pundasyon ng matematika ng natitirang sistema ng klase
Tingnan natin ang isang halimbawa. Hayaan ang p = 6. Pagkatapos ay mayroon kaming anim na klase ng partition ng set ng integers modulo 6: r = 0; r = 1; r = 2; r = 3; r = 4; r = 5; kung saan ang r ay nagsasaad ng natitira kapag hinahati ang isang integer sa 6...
Mga pamamaraan para sa pag-aaral ng polynomial sa mga elektibong klase sa mataas na paaralan sekondaryang paaralan
Hayaang matapos ang singsing ng mga polynomial. Depinisyon 1: Hayaan at, kung mayroong isang polynomial, kung gayon ang natitira sa dibisyon ay zero, kung gayon ito ay tinatawag na divisor ng polynomial at ipinapahiwatig: ()...
Mga pangunahing yugto ng pagbuo at istraktura modernong matematika
Noong ika-3 siglo BC, isang libro ng Euclid na may parehong pangalan ang lumitaw sa Alexandria, sa pagsasalin ng Ruso ng "Mga Prinsipyo". Mula sa Latin na pangalan Ang "Nagsimula" ay nagmula sa terminong "elementarya na geometry". Sa kabila ng...
Sa teritoryo ng isang tiyak na lungsod N mayroong mga pabrika at tindahan kung saan ibinibigay ang mga produkto mula sa mga pabrika na ito. Bilang resulta ng pag-unlad, ang mga posibleng ruta para sa pagtula ng mga komunikasyon ay natukoy at ang halaga ng kanilang paglikha para sa bawat ruta ay tinatantya...
Paglalapat ng mga pamamaraan ng discrete mathematics sa ekonomiya
Ang isang kumpanya na nakikibahagi sa transportasyon ng mga nabubulok na kalakal ay kailangang maghatid ng mga kalakal mula Suifenhe hanggang Khabarovsk, at mayroong ilang mga ruta kung saan maaaring gawin ang paghahatid. Ang distansya sa pagitan ng Suifenhe at City 2 ay 15 km...
Pagbuo ng konsepto ng "Space" at non-Euclidean geometry
Mga espesyal na pamamaraan integrasyon ng mga makatwirang ekspresyon
Hayaang kailanganin upang mahanap ang gcd ng polynomials at. Nang walang pagkawala ng pangkalahatan, ipagpalagay natin na ang antas ay hindi mas mataas kaysa sa antas. Katawanin natin ang polynomial sa anyo: saan ang natitira sa paghahati ni. Kung gayon ang antas ay mas mababa kaysa sa antas ng divisor. Dagdag pa...
Teorya ng nalalabi
Teorya ng nalalabi
Kahulugan. Ang numerong d??Z, na sabay-sabay na naghahati sa mga numerong a, b, c, ..., k??Z, ay tinatawag na karaniwang divisor ng mga numerong ito. Ang pinakamalaking d na may ganitong ari-arian ay tinatawag na pinakamalaking karaniwang divisor. Pagtatalaga: d = (a, b, c, ..., k). Teorama. Kung (a , b) = d...
Teorya ng nalalabi
Hayaang kailangang lutasin ang isang linear na Diophantine equation: ax + by = c, kung saan a, b, c ??Z; a at b ay hindi mga zero. Subukan nating mangatwiran sa pamamagitan ng pagtingin sa equation na ito. Hayaan ang (a, b) = d. Pagkatapos a = a 1 d ; b = b 1 d at ang equation ay ganito ang hitsura: a 1 d x + b 1 d y = c, i.e. d· (a 1 x + b 1 y) = c...
Malawakang ginagamit sa e-commerce. Ginagamit din ang algorithm sa paglutas ng mga linear na Diophantine equation, sa pagbuo ng mga patuloy na fraction, at sa Sturm method. Ang algorithm ni Euclid ay ang pangunahing kasangkapan para sa pagpapatunay ng mga teorema sa modernong teorya ng numero, tulad ng teorama ni Lagrange sa kabuuan ng apat na parisukat at ang pangunahing teorama ng arithmetic.
Encyclopedic YouTube
1 / 5
✪ Matematika. Mga natural na numero: Euclid's algorithm. Foxford Online Learning Center
✪Euclidean algorithm
✪ Euclidean algorithm, mabilis na paraan hanapin ang gcd
✪ Math 71. Pinakamahusay na karaniwang divisor. Euclid's algorithm - Academy of Entertaining Sciences
✪ 20 while loop Python Euclidean algorithm
Mga subtitle
Kwento
Tinawag ng mga sinaunang Greek mathematician ang algorithm na ito ἀνθυφαίρεσις o ἀνταναίρεσις - "mutual subtraction". Ang algorithm na ito ay hindi natuklasan ni Euclid, dahil nabanggit na ito sa Topeka Aristotle. Sa Euclid's Elements ito ay inilarawan nang dalawang beses - sa Book VII para sa paghahanap ng pinakamalaking karaniwang divisor ng dalawang natural na numero at sa Book X para sa paghahanap ng pinakamalaking karaniwang sukat ng dalawang homogenous na dami. Sa parehong mga kaso, ang isang geometric na paglalarawan ng algorithm ay ibinigay para sa paghahanap ng "karaniwang sukat" ng dalawang mga segment.
Paglalarawan
Euclid's algorithm para sa mga integer
Hayaan a (\displaystyle a) At b (\displaystyle b)- mga integer na hindi katumbas ng zero sa parehong oras, at isang pagkakasunod-sunod ng mga numero
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))tinutukoy ng katotohanan na ang bawat isa r k (\displaystyle r_(k))- ito ang natitira mula sa paghahati ng nakaraang numero sa nauna, at ang penultimate ay nahahati sa huli, iyon ay:
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).)Pagkatapos GCD( a, b), pinakamalaking karaniwang divisor a At b, ay katumbas r n, ang huling di-zero na termino ng sequence na ito.
Pag-iral ganyan r 1 , r 2 , ..., r n, iyon ay, ang posibilidad ng paghahati sa isang natitira m sa n para sa anumang integer m at ang kabuuan n≠ 0, mapapatunayan sa pamamagitan ng induction on m.
Katumpakan Ang algorithm na ito ay sumusunod mula sa sumusunod na dalawang pahayag:
- Hayaan a = b⋅q + r, pagkatapos ay gcd (a, b) = gcd (b, r).
Patunay
- GCD( r, 0) = r para sa anumang hindi zero r(dahil ang 0 ay nahahati sa anumang integer maliban sa zero).
Geometric Euclidean algorithm
Hayaang ibigay ang dalawang bahagi ng haba a At b. Ibawas ang mas maliit na segment mula sa mas malaking segment at palitan ang mas malaking segment ng resultang pagkakaiba. Ulitin namin ang operasyong ito hanggang sa magkapantay ang mga segment. Kung mangyari ito, kung gayon ang mga orihinal na mga segment ay katumbas ng halaga, at ang huling nagreresultang segment ay ang kanilang pinakamalaking karaniwang sukat. Kung walang pangkalahatang panukala, kung gayon ang proseso ay walang katapusan. Sa form na ito, ang algorithm ay inilarawan ni Euclid at ipinatupad gamit ang isang compass at ruler.
Halimbawa
Upang ilarawan, ang Euclidean algorithm ay gagamitin upang mahanap ang GCD a= 1071 at b= 462. Una, ibawas ang isang multiple ng 462 mula sa 1071 hanggang sa makakuha tayo ng pagkakaibang mas mababa sa 462. Dapat nating ibawas ang 462 nang dalawang beses, ( q 0 = 2), na nag-iiwan ng natitirang 147:
1071 = 2 × 462 + 147.
Pagkatapos ay ibawas ang mga multiple ng 147 mula sa 462 hanggang sa makakuha tayo ng pagkakaibang mas mababa sa 147. Dapat nating ibawas ang 147 nang tatlong beses ( q 1 = 3), na nag-iiwan ng natitirang 21:
462 = 3 × 147 + 21.
Pagkatapos ay ibawas ang mga multiple ng 21 mula sa 147 hanggang ang pagkakaiba ay mas mababa sa 21. Dapat nating ibawas ng 21 pitong beses ( q 2 = 7), walang natitira:
147 = 7 × 21 + 0.
Kaya ang sequence a > b > r 1 > r 2 > r 3 > … > r n sa partikular na kaso na ito ay magiging ganito:
1071 > 462 > 147 > 21.
Dahil zero ang huling natitira, nagtatapos ang algorithm sa numerong 21 at gcd(1071, 462) = 21.
Sa anyong tabular, ang mga hakbang ay ang mga sumusunod:
Mga aplikasyon
Pinalawak na Euclidean algorithm at ugnayan ni Bezout
Mga formula para sa r i (\displaystyle r_(i)) maaaring muling isulat tulad ng sumusunod:
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)Dito s At t buo. Ang representasyong ito ng pinakamalaking karaniwang divisor ay tinatawag na Bezout relation, at ang mga numero s At t- Mga coefficient ng Bezout. Ang kaugnayan ni Bezout ay susi sa patunay ng lemma ni Euclid at ang pangunahing teorama ng arithmetic.
Patuloy na mga fraction
Ang algorithm ng Euclid ay medyo malapit na nauugnay sa patuloy na mga fraction. Saloobin a/b ay maaaring katawanin bilang isang patuloy na fraction:
a b = [ q 0 ; q 1 , q 2 , ⋯ , q n ] (\displaystyle (\frac (a)(b))=).Sa kasong ito, ang patuloy na fraction na walang huling termino ay katumbas ng ratio ng Bezout coefficients t/s, kinuha gamit ang isang minus sign:
[q 0 ; q 1 , q 2 , ⋯ , q n − 1 ] = − t s (\displaystyle =-(\frac (t)(s))).Ang pagkakasunud-sunod ng mga pagkakapantay-pantay na tumutukoy sa Euclidean algorithm ay maaaring muling isulat sa anyo:
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(aligned)(\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(aligned)))Ang huling termino sa kanang bahagi ng equation ay palaging katumbas ng kabaligtaran ng kaliwang bahagi ng sumusunod na equation. Samakatuwid ang unang dalawang equation ay maaaring pagsamahin sa anyo:
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))))))Ang ikatlong pagkakapantay-pantay ay maaaring gamitin upang palitan ang denominator ng expression r 1 /r 0 , nakukuha namin ang:
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))))))))Huling Residual Ratio r k /r k Ang −1 ay maaaring palaging palitan gamit ang susunod na equation sa sequence, at iba pa hanggang sa huling equation. Ang resulta ay isang patuloy na bahagi:
a b = q 0 + 1 q 1 + 1 q 2 + 1 ayos + 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))))))))=)Pangkalahatang Euclidean algorithm para sa mga polynomial
Ang Euclidean algorithm at ang extended na Euclidean algorithm ay natural na nag-generalize sa ring ng polynomials k[x] mula sa isang variable sa isang arbitrary na field k, dahil para sa gayong mga polynomial ang operasyon ng dibisyon na may natitira ay tinukoy. Ang pagpapatakbo ng Euclidean algorithm para sa mga polynomial sa katulad na paraan sa Euclidean algorithm para sa mga integer ay gumagawa ng polynomial remainder sequence (PRS).
Halimbawa para sa singsing Z[x]
Hayaang ang cont(f) ayon sa kahulugan ay ang gcd ng mga coefficient ng polynomial f(x) mula sa Z[x] - nilalaman polinomyal. Ang quotient ng f(x) na hinati sa cont(f) ay tinatawag primitive na bahagi polynomial f(x) at ipinapahiwatig ng primpart(f(x)). Kakailanganin ang mga kahulugang ito upang mahanap ang gcd ng dalawang polynomial p1(x) At p2(x) sa ring Z[x]. Para sa mga polynomial sa mga integer ang sumusunod ay totoo:
K 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) )) = (\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))\).)
Kaya, ang problema ng paghahanap ng GCD ng dalawang arbitrary na polynomial ay nabawasan sa problema ng paghahanap ng GCD ng primitive polynomial.
Hayaang magkaroon ng dalawang primitive polynomial p 1 (x) at p 2 (x) mula sa Z[x], kung saan ang ugnayan sa pagitan ng kanilang mga kapangyarihan ay nagtataglay: deg(p 1 (x)) = m at deg(p 2 (x) ) = n, m > n. Ang dibisyon ng mga polynomial na may natitira ay ipinapalagay ang eksaktong divisibility ng pinakamataas na koepisyent ng dibidendo sa pamamagitan ng pinakamataas na koepisyent ng divisor sa pangkalahatang kaso, ang paghahati na may natitira ay hindi maaaring maisagawa. Samakatuwid, ang isang pseudo-division algorithm ay ipinakilala, na nagpapahintulot pa rin sa isa na makakuha ng isang pseudo-quotient at isang pseudo-remainder (prem), na sila mismo ay kabilang sa hanay ng mga polynomial sa mga integer.
Ang ibig sabihin ng pseudo-division ay ang dibisyon mismo ay nauuna sa pagpaparami ng isang polynomial p 1 (x) (\displaystyle p_(1)(x)) sa (l c (p 2 (x))) m − n + 1 (\displaystyle (lc(p_(2)(x)))^(m-n+1)), yan ay
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)),}
saan q (x) (\displaystyle q(x)) At r (x) (\displaystyle r(x))- pseudo-quotient at pseudo-remainder, ayon sa pagkakabanggit.
Kaya, p 1 (x) , p 2 (x) ∈ Z [ x ] (\displaystyle p_(1)(x),p_(2)(x)\in Z[x]), at deg (p 1) = n 1 ≥ deg (p 2) = n 2 (\displaystyle \deg(p_(1))=n_(1)\geq \deg(p_(2))=n_(2) ). Pagkatapos ang Euclidean algorithm ay binubuo ng mga sumusunod na hakbang:
1. Pagkalkula ng mga nilalaman ng GCD:
C:= (\displaystyle c:=) GCD ( c o n t (p 1) , c o n t (p 2) ) (\displaystyle \(cont(p_(1)),cont(p_(2))\)).
2. Pagkalkula ng mga primitive na bahagi:
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. Pagbubuo ng isang pagkakasunud-sunod ng mga polynomial na natitira:
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)).)
Isaalang-alang natin ang dalawang pangunahing paraan ng paghahanap ng GCD sa dalawang pangunahing paraan: gamit ang Euclidean algorithm at sa pamamagitan ng decomposing sa prime factors. Ilapat natin ang parehong pamamaraan para sa dalawa, tatlo o higit pang mga numero.
Euclidean algorithm para sa paghahanap ng GCD
Pinapadali ng Euclidean algorithm na kalkulahin ang pinakamalaking karaniwang salik ng dalawang positibong numero. Iniharap namin ang mga pormulasyon at patunay ng Euclid algorithm sa seksyong "Pinakamahusay na karaniwang divisor: determinant, mga halimbawa."
Ang kakanyahan ng algorithm ay ang sunud-sunod na pagsasagawa ng paghahati sa isang natitira, kung saan ang isang serye ng mga pagkakapantay-pantay ng form ay nakuha:
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
Matatapos natin ang division kapag r k + 1 = 0, kung saan r k = gcd (a , b).
Halimbawa 1
64 At 48 .
Solusyon
Ipakilala natin ang mga sumusunod na notasyon: a = 64, b = 48.
Batay sa Euclidean algorithm, magsasagawa kami ng paghahati 64 sa 48 .
Nakukuha namin ang 1 at ang natitira ay 16. Lumalabas na q 1 = 1, r 1 = 16.
Ang ikalawang hakbang ay ang hatiin 48 sa 16, makakakuha tayo ng 3. Yan ay q 2 = 3, A r 2 = 0 . Kaya, ang numero 16 ay ang pinakamalaking karaniwang divisor para sa mga numero mula sa kundisyon.
Sagot: GCD (64, 48) = 16.
Halimbawa 2
Ano ang GCD ng mga numero? 111 At 432 ?
Solusyon
hati tayo 432 sa 111 . Ayon sa Euclidean algorithm, nakukuha natin ang chain of equalities 432 = 111 · 3 + 99, 111 = 99 · 1 + 12, 99 = 12 · 8 + 3, 12 = 3 · 4.
Kaya, ang pinakamalaking karaniwang divisor ng mga numero ay 111 At 432 - ito ay 3.
Sagot: GCD (111, 432) = 3.
Halimbawa 3
Hanapin ang pinakamalaking karaniwang divisor ng mga numerong 661 at 113.
Solusyon
Hatiin natin nang sunud-sunod ang mga numero at kunin ang GCD (661 , 113) = 1 . Nangangahulugan ito na ang 661 at 113 ay medyo prime number. Maaari naming malaman ito bago simulan ang pagkalkula kung kumunsulta kami sa isang talahanayan ng mga prime number.
Sagot: GCD (661, 113) = 1.
Paghahanap ng GCD sa pamamagitan ng pag-factor ng mga numero sa prime factor
Upang mahanap ang pinakadakilang karaniwang divisor ng dalawang numero gamit ang paraan ng factorization, kinakailangan na i-multiply ang lahat ng prime factor na nakuha sa pamamagitan ng factoring ng dalawang numerong ito at karaniwan sa kanila.
Halimbawa 4
Kung isasaalang-alang natin ang mga numerong 220 at 600 sa mga pangunahing kadahilanan, makakakuha tayo ng dalawang produkto: 220 = 2 2 5 11 At 600 = 2 2 2 3 5 5. Ang karaniwang mga kadahilanan sa dalawang produktong ito ay 2, 2 at 5. Ibig sabihin, ang GCD (220, 600) = 2 2 5 = 20.
Halimbawa 5
Hanapin ang pinakamalaking karaniwang divisor ng mga numero 72 At 96 .
Solusyon
Hanapin ang lahat ng prime factor ng mga numero 72 At 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
Ang karaniwang prime factor para sa dalawang numero ay 2, 2, 2 at 3. Ibig sabihin, ang GCD (72, 96) = 2 2 2 3 = 24.
Sagot: GCD (72, 96) = 24.
Ang panuntunan para sa paghahanap ng pinakamalaking karaniwang divisor ng dalawang numero ay batay sa mga katangian ng pinakamalaking karaniwang divisor, ayon sa kung aling gcd (m a 1, m b 1) = m gcd (a 1, b 1), kung saan ang m ay anumang positibong integer .
Paghahanap ng gcd ng tatlo o higit pang mga numero
Anuman ang bilang ng mga numero kung saan kailangan nating hanapin ang GCD, susundin natin ang parehong algorithm, na binubuo ng sunud-sunod na paghahanap ng GCD ng dalawang numero. Ang algorithm na ito ay batay sa aplikasyon ng sumusunod na theorem: GCD ng ilang numero a 1 , a 2 , … , a k katumbas ng bilang dk, na matatagpuan sa pamamagitan ng sunud-sunod na pagkalkula ng 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 .
Halimbawa 6
Hanapin ang pinakamalaking karaniwang divisor ng apat na numero 78, 294, 570 at 36 .
Solusyon
Ipakilala natin ang notasyon: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.
Magsimula tayo sa paghahanap ng gcd ng mga numero 78 at 294: d 2 = GCD (78 , 294) = 6 .
Ngayon simulan natin ang paghahanap ng d 3 = GCD (d 2 , a 3) = GCD (6, 570). Ayon sa Euclid algorithm 570 = 6 95. Ibig sabihin nito ay d 3 = GCD (6 , 570) = 6 .
Hanapin natin ang d 4 = GCD (d 3 , a 4) = GCD (6, 36). 36 nahahati sa 6 na walang natitira. Ito ay nagpapahintulot sa amin na makakuha d 4 = GCD (6 , 36) = 6 .
d4 = 6, iyon ay, GCD (78 , 294 , 570 , 36) = 6 .
Sagot:
Ngayon tingnan natin ang isa pang paraan upang kalkulahin ang GCD para sa mga iyon at higit pang mga numero. Mahahanap natin ang gcd sa pamamagitan ng pagpaparami ng lahat ng karaniwang prime factor ng mga numero.
Halimbawa 7
Kalkulahin ang GCD ng mga numerong 78, 294, 570 at 36 .
Solusyon
I-decompose ang mga numerong ito sa prime factor: 78 = 2 3 13, 294 = 2 3 7 7, 570 = 2 3 5 19, 36 = 2 2 3 3.
Para sa lahat ng apat na numero, ang karaniwang prime factor ay ang mga numero 2 at 3.
GCD na pala (78, 294, 570, 36) = 2 3 = 6.
Sagot: GCD (78, 294, 570, 36) = 6.
Paghahanap ng gcd ng mga negatibong numero
Kung kailangan nating harapin ang mga negatibong numero, maaari nating gamitin ang moduli ng mga numerong ito upang mahanap ang pinakamalaking karaniwang divisor. Magagawa natin ito, alam ang pag-aari ng mga numero na may kabaligtaran na mga palatandaan: mga numero n At - n may parehong divisors.
Halimbawa 8
Hanapin ang gcd ng mga negatibong integer − 231 At − 140 .
Solusyon
Upang magsagawa ng mga kalkulasyon, kinukuha namin ang mga module ng mga numero na ibinigay sa kondisyon. Ito ang magiging mga numerong 231 at 140. Isulat natin ito nang maikli: GCD (− 231 , − 140) = GCD (231, 140) . Ngayon ay inilalapat namin ang Euclidean algorithm upang mahanap ang mga pangunahing kadahilanan ng dalawang numero: 231 = 140 · 1 + 91 ; 140 = 91 · 1 + 49 ; 91 = 49 · 1 + 42 ; 49 = 42 1 + 7 at 42 = 7 6. Nakukuha namin na GCD (231, 140) = 7 .
At dahil GCD (− 231 , − 140) = GCD (231 , 140) , pagkatapos ay gcd ng mga numero − 231 At − 140 katumbas 7 .
Sagot: GCD (− 231, − 140) = 7.
Halimbawa 9
Tukuyin ang gcd ng tatlong numero − 585, 81 at − 189 .
Solusyon
Palitan natin ang mga negatibong numero sa listahan sa itaas ng kanilang mga ganap na halaga, makakakuha tayo ng GCD (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . Pagkatapos ay isasaalang-alang namin ang lahat ng mga numerong ito sa mga pangunahing kadahilanan: 585 = 3 3 5 13, 81 = 3 3 3 3 at 189 = 3 3 3 7. Karaniwan sa tatlong numero ay ang prime factor 3 at 3. Lumalabas na GCD (585, 81, 189) = GCD (− 585, 81, − 189) = 9.
Sagot: GCD (− 585, 81, − 189) = 9.
Kung may napansin kang error sa text, paki-highlight ito at pindutin ang Ctrl+Enter
Ang algorithm ni Euclid ay isang algorithm para sa paghahanap ng greatest common divisor (GCD) ng isang pares ng integer.
Greatest Common Divisor (GCD) ay isang numero na naghahati ng dalawang numero nang walang nalalabi at mismong nahahati nang walang nalalabi sa anumang iba pang divisor ng ibinigay na dalawang numero. Sa madaling salita, ito ang pinakamalaking bilang kung saan maaaring hatiin ang dalawang numero kung saan hinahanap ang gcd nang walang natitira.
Algorithm para sa paghahanap ng GCD sa pamamagitan ng dibisyon
- Hatiin ang mas malaking bilang sa mas maliit na bilang.
- Kung ito ay hinati nang walang natitira, kung gayon ang mas maliit na bilang ay GCD (dapat kang lumabas sa cycle).
- Kung mayroong natitira, pagkatapos ay palitan ang mas malaking numero ng natitira sa dibisyon.
- Pumunta tayo sa point 1.
Halimbawa:
Maghanap ng gcd para sa 30 at 18.
30 / 18 = 1 (natitira 12)
18 / 12 = 1 (natitira 6)
12 / 6 = 2 (natitira 0)
Katapusan: Ang GCD ay isang divisor ng 6.
GCD(30, 18) = 6
a = 50 b = 130 habang a != 0 at b != 0 : kung a > b: a = a % b iba pa : b = b % isang print (a + b)
Sa loop, ang natitira sa dibisyon ay nakasulat sa variable na a o b. Ang loop ay nagtatapos kapag ang hindi bababa sa isa sa mga variable ay zero. Nangangahulugan ito na ang isa pa ay naglalaman ng isang gcd. Gayunpaman, hindi namin alam kung alin ang eksaktong. Samakatuwid, para sa GCD, makikita natin ang kabuuan ng mga variable na ito. Dahil ang isa sa mga variable ay zero, wala itong epekto sa resulta.
Algorithm para sa paghahanap ng GCD sa pamamagitan ng pagbabawas
- Ibawas ang mas maliit na bilang sa mas malaking bilang.
- Kung ang resulta ay 0, nangangahulugan ito na ang mga numero ay pantay sa isa't isa at GCD (dapat kang lumabas sa loop).
- Kung ang resulta ng pagbabawas ay hindi katumbas ng 0, pagkatapos ay palitan ang mas malaking bilang ng resulta ng pagbabawas.
- Pumunta tayo sa point 1.
Halimbawa:
Maghanap ng gcd para sa 30 at 18.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
Katapusan: Ang GCD ay isang minuend o subtrahend.
GCD(30, 18) = 6
a = 50 b = 130 habang a != b: kung a > b: a = a - b iba pa : b = b - isang print (a)