Paghahanap ng mga node gamit ang Euclidean algorithm at gamit ang prime factorization. Paghahanap ng nok sa pamamagitan ng pag-factor ng mga numero sa prime factor na algorithm ni Euclid para sa paghahanap ng gcd

Isaalang-alang ang dalawang paraan upang mahanap ang pinakamalaking karaniwang divisor.

Paghahanap sa pamamagitan ng Factoring

Ang unang paraan ay upang mahanap ang pinakamalaking karaniwang divisor sa pamamagitan ng pagsasakatuparan ng mga ibinigay na numero sa mga pangunahing kadahilanan.

Upang mahanap ang GCD ng ilang mga numero, sapat na upang mabulok ang mga ito sa mga pangunahing kadahilanan at i-multiply sa kanilang mga sarili ang mga ito na karaniwan sa lahat ng ibinigay na mga numero.

Halimbawa 1 Hanapin natin ang GCD (84, 90).

Binubulok namin ang mga numero 84 at 90 sa pangunahing mga kadahilanan:

Kaya, sinalungguhitan namin ang lahat ng mga karaniwang pangunahing kadahilanan, nananatili itong paramihin ang mga ito sa kanilang sarili: 1 2 3 = 6.

Kaya gcd(84, 90) = 6.

Halimbawa 2 Hanapin natin ang GCD (15, 28).

Binubulok namin ang 15 at 28 sa pangunahing mga kadahilanan:

Ang mga numero 15 at 28 ay coprime dahil ang kanilang pinakamalaking karaniwang divisor ay isa.

gcd (15, 28) = 1.

Ang algorithm ni Euclid

Ang pangalawang paraan (kung hindi man ay tinatawag na Euclid method) ay ang paghahanap ng GCD sa pamamagitan ng sunud-sunod na dibisyon.

Una, titingnan natin ang pamamaraang ito bilang inilapat sa dalawang ibinigay na numero, at pagkatapos ay malalaman natin kung paano ito ilalapat sa tatlo o higit pang mga numero.

Kung ang mas malaki sa dalawang ibinigay na numero ay nahahati sa mas maliit, kung gayon ang bilang na mas maliit ay ang kanilang pinakamalaking karaniwang divisor.

Halimbawa 1 Kunin ang dalawang numero 27 at 9. Dahil ang 27 ay nahahati ng 9 at ang 9 ay nahahati ng 9, kung gayon ang 9 ay isang karaniwang divisor ng mga numerong 27 at 9. Ang divisor na ito ay din ang pinakamalaking, dahil ang 9 ay hindi maaaring mahahati ng anumang numero, mas malaki. kaysa sa 9. Samakatuwid, gcd (27, 9) = 9.

Sa ibang mga kaso, upang mahanap ang pinakamalaking karaniwang divisor ng dalawang numero, ang sumusunod na pamamaraan ay ginagamit:

1. Sa dalawang ibinigay na numero, ang mas malaking bilang ay hinati sa mas maliit.
2. Pagkatapos, ang mas maliit na bilang ay hinati sa natitira na nagreresulta mula sa paghahati ng mas malaking bilang sa mas maliit.
3. Dagdag pa, ang unang natitira ay nahahati sa pangalawang natitira, na nakukuha sa pamamagitan ng paghahati ng mas maliit na bilang sa unang natitira.
4. Ang pangalawang natitira ay nahahati sa pangatlo, na nakuha sa pamamagitan ng paghahati ng unang natitira sa pangalawa, at iba pa.
5. Kaya, ang paghahati ay nagpapatuloy hanggang ang natitira ay zero. Ang huling divisor ang magiging pinakamalaking common divisor.

Halimbawa 2 Hanapin natin ang pinakamalaking karaniwang divisor ng mga numero 140 at 96:

1) 140: 96 = 1 (natitira 44)

2) 96: 44 = 2 (natitira 8)

3) 44: 8 = 5 (natitira 4)

Ang huling divisor ay 4, na nangangahulugang gcd(140, 96) = 4.

Ang sequential division ay maaari ding isulat sa isang column:

Upang mahanap ang pinakamalaking karaniwang divisor ng tatlo o higit pang ibinigay na mga numero, gamitin ang sumusunod na pamamaraan:

1. Una, hanapin ang pinakamalaking karaniwang divisor ng alinmang dalawang numero mula sa maraming dataset.
2. Pagkatapos ay makikita natin ang GCD ng nahanap na divisor at ilang ikatlong ibinigay na numero.
3. Pagkatapos ay makikita natin ang GCD ng huling nahanap na divisor at ang ikaapat na ibinigay na numero, at iba pa.

Halimbawa 3 Hanapin natin ang pinakamalaking karaniwang divisor ng mga numero 140, 96 at 48. Nahanap na natin ang GCD ng mga numero 140 at 96 sa nakaraang halimbawa (ito ang numero 4). Ito ay nananatili upang mahanap ang pinakadakilang karaniwang divisor ng numero 4 at ang ikatlong ibinigay na numero - 48:

Ang 48 ay nahahati sa 4 na walang nalalabi. Kaya gcd(140, 96, 48) = 4.

Ang kumakatawan sa isang numero bilang isang produkto ng mga prime number ay tinatawag nabubulok ang bilang na ito sa mga pangunahing kadahilanan.

Halimbawa, ang entry na 110 = 2 5 11 ay nagpapahiwatig na ang bilang 110 ay nabulok sa prime factor 2, 5 at 11.

Sa pangkalahatan, ang anumang pinagsama-samang numero ay maaaring mabulok sa mga pangunahing kadahilanan, at sa anumang paraan, ang parehong agnas ay nakuha, kung ang pagkakasunud-sunod ng mga kadahilanan ay hindi isinasaalang-alang. Samakatuwid, ang mga representasyon ng numerong 110 bilang isang produkto ng 2 · 5 · 11 o ang produkto ng 5 · 2 · 11 ay, sa esensya, ang parehong pagkabulok ng numero 110 sa pangunahing mga kadahilanan.

Kapag nabubulok ang mga numero sa mga pangunahing kadahilanan, gamit ang mga palatandaan ng paghahati sa pamamagitan ng 2, 3, 5, atbp., alalahanin natin ang paraan upang isulat ang agnas ng isang numero sa mga pangunahing kadahilanan. I-decompose natin, halimbawa, ang numerong 720 sa prime factor. Ang numero 720 ay nahahati sa 2. Kaya, ang 2 ay isa sa mga pangunahing salik sa decomposition ng numerong 720. Hatiin ang 720 sa 2. Ang numero 2 ay isinusulat sa ang kanan ng pantay na tanda, at ang quotient 360 ay nakasulat sa ilalim ng numerong 720. Ang numerong 360 na hinati ng 2, nakakakuha tayo ng 180. Hatiin ang 180 sa 2, nakuha natin ang 90, hatiin ang 90 sa 2, nakuha natin ang 45, hatiin ang 45 sa pamamagitan ng 3, makakakuha tayo ng 15, hatiin ang 15 sa 3, makuha natin ang 5. Ang numero 5 ay prime, kapag hinati sa 5 makakakuha tayo ng 1. Nakumpleto ang factorization.

720 = 2 2 2 2 3 3 5

Nakaugalian na palitan ang produkto ng magkaparehong mga kadahilanan na may kapangyarihan: 720 = 5. Ang nasabing representasyon ng bilang na 720 ay tinatawag canonical view itong numero.

Ang pag-factor ng isang numero sa prime factor ay ginagamit upang mahanap ang kanilang pinakamalaking common divisor at least common multiple.

Hanapin, halimbawa, ang pinakamalaking common divisor at least common multiple ng mga numerong 3600 at 288.

Katawanin natin ang bawat isa sa mga numerong ito sa canonical form.

3600 = 2 2 2 2 3 3 5 5 = ; 288 = 2 2 2 2 2 3 3 =

Sa prime factorization ng pinakamalaking karaniwang divisor ng mga numerong 3600 at 288, lahat karaniwang simpleng multiply, na nakapaloob sa mga pagpapalawak ng ibinigay na mga numero, at ang bawat isa sa kanila ay dapat kunin mula sa ang pinakamababang tagapagpahiwatig kung saan pumapasok ito sa parehong mga pagpapalawak. Samakatuwid, ang pagpapalawak ng pinakamalaking karaniwang divisor ng mga numerong 3600 at 288 ay magsasama ng mga salik at . Kaya D (3600? 288) = · = 144.

Ang prime factorization ng least common multiple ng 3600 at 288 ay dapat isama ang lahat ng prime factor na nilalaman sa kahit isa mula sa mga pagpapalawak ng mga numerong 3600 at 288, at dapat kunin ang bawat isa sa kanila may pinakamataas na marka, kasama sa parehong pagpapalawak ng mga numerong ito. Samakatuwid, ang pagpapalawak ng hindi bababa sa karaniwang multiple ng 3600 at 288 ay magsasama ng mga salik , , 5. Samakatuwid,

K (3600, 288) = 5 = 7200.

Sa pangkalahatan, upang mahanap ang pinakamalaking karaniwang divisor ng mga ibinigay na numero:

2) Bumubuo kami ng isang produkto ng mga pangunahing kadahilanan na karaniwan sa lahat ng ibinigay na mga numero, at ang bawat isa sa kanila ay kinuha gamit ang pinakamaliit na exponent kung saan ito pumapasok sa lahat ng pagpapalawak ng mga numerong ito;

3) Nalaman namin ang halaga ng produktong ito - ito ang magiging pinakamalaking karaniwang divisor ng mga numerong ito.

Upang mahanap ang hindi bababa sa karaniwang multiple ng mga ibinigay na numero:

1) Kinakatawan namin ang bawat ibinigay na numero sa canonical form;

2) Bumubuo kami ng isang produkto mula sa lahat ng pangunahing mga kadahilanan na nasa pagpapalawak ng mga numerong ito, at ang bawat isa ay kinuha na may pinakamalaking exponent kung saan ito pumapasok sa lahat ng pagpapalawak ng mga numerong ito;

3) Nahanap namin ang halaga ng produktong ito - ito ang magiging pinakamaliit na karaniwang multiple ng mga numerong ito.

Numero ng tiket 45. Ang hindi bababa sa karaniwang multiple ng mga numero. Mga katangian at paraan ng paghahanap nito. Mga halimbawa.

Kinakalkula ang least common multiple (LCM) sa pamamagitan ng gcd(least common divisor)

Ang isang paraan upang mahanap ang least common multiple ay batay sa relasyon sa pagitan ng LCM at GCD. Ang umiiral na ugnayan sa pagitan ng LCM at GCD ay nagbibigay-daan sa iyong kalkulahin ang hindi bababa sa karaniwang multiple ng dalawang positive integer sa pamamagitan ng kilalang pinakadakilang karaniwang divisor. Ang kaukulang formula ay may anyo LCM(a, b)=a b: GCD(a, b) . Isaalang-alang ang mga halimbawa ng paghahanap ng LCM ayon sa formula sa itaas.

Halimbawa.

Hanapin ang hindi bababa sa karaniwang multiple ng dalawang numero 126 at 70 .

Desisyon.

Sa halimbawang ito a=126, b=70. Gamitin natin ang kaugnayan sa pagitan ng LCM at GCD na ipinahayag ng formula LCM(a, b)=a b: GCD(a, b). Iyon ay, kailangan muna nating hanapin ang pinakamalaking karaniwang divisor ng mga numero 70 at 126 , pagkatapos nito ay maaari nating kalkulahin ang LCM ng mga numerong ito ayon sa nakasulat na formula.

Hanapin natin GCD(126, 70), gamit ang Euclid algorithm: 126=70 1+56, 70=56 1+14, 56=14 4, samakatuwid, gcd(126, 70)=14.

Ngayon nakita namin ang kinakailangang hindi bababa sa karaniwang maramihang: LCM(126, 70)=126 70: GCM(126, 70)=126 70:14=630.

Sagot:

LCM(126, 70)=630.

Halimbawa.

Ano ang katumbas ng NOC(68, 34)?

Desisyon.

Bilang 68 ganap na nahahati sa 34 , pagkatapos GCD(68, 34)=34. Ngayon kinakalkula namin ang hindi bababa sa karaniwang maramihang: LCM(68, 34)=68 34:GCM(68, 34)=68 34:34=68.

Sagot:

LCM(68, 34)=68.

Tandaan na ang nakaraang halimbawa ay umaangkop sa sumusunod na panuntunan para sa paghahanap ng LCM para sa positive integer a at b: kung numero a hinati ng b, kung gayon ang hindi bababa sa karaniwang multiple ng mga numerong ito ay a.

Paghahanap ng LCM sa pamamagitan ng Factoring Numbers into Prime Factors

Ang isa pang paraan upang mahanap ang hindi bababa sa karaniwang maramihang ay batay sa mga numero ng factoring sa prime factor. Kung gagawin namin ang isang produkto ng lahat ng prime factor ng mga numerong ito, pagkatapos nito ay ibubukod namin mula sa produktong ito ang lahat ng karaniwang prime factor na naroroon sa mga pagpapalawak ng mga numerong ito, ang resultang produkto ay magiging katumbas ng hindi bababa sa common multiple ng mga numerong ito.

Ang inihayag na panuntunan para sa paghahanap ng LCM ay sumusunod sa pagkakapantay-pantay LCM(a, b)=a b: GCD(a, b). Sa katunayan, ang produkto ng mga numero a at b ay katumbas ng produkto ng lahat ng mga salik na kasangkot sa pagpapalawak ng mga numero a at b. Sa turn nito gcd(a, b) ay katumbas ng produkto ng lahat ng mga pangunahing kadahilanan na sabay-sabay na naroroon sa mga pagpapalawak ng mga numero a at b(na inilalarawan sa seksyon sa paghahanap ng GCD sa pamamagitan ng pag-factor ng mga numero sa prime factor).

Kumuha tayo ng isang halimbawa. Ipaalam sa amin iyon 75=3 5 5 at 210=2 3 5 7. Buuin ang produkto ng lahat ng mga salik ng mga pagpapalawak na ito: 2 3 3 5 5 5 7. Ngayon ay ibinubukod namin mula sa produktong ito ang lahat ng mga kadahilanan na naroroon din sa pagpapalawak ng numero 75 at sa pagpapalawak ng bilang 210 (ang mga ganitong salik ay 3 at 5 ), pagkatapos ay kukuha ng anyo ang produkto 2 3 5 5 7. Ang halaga ng produktong ito ay katumbas ng hindi bababa sa karaniwang multiple ng mga numero 75 at 210 , ibig sabihin, LCM(75, 210)= 2 3 5 5 7=1 050.

Halimbawa.

Pagpapalawak ng mga numero 441 at 700 sa prime factor, hanapin ang least common multiple ng mga numerong ito.

Desisyon.

I-decompose natin ang mga numero 441 at 700 para sa mga pangunahing kadahilanan:

Nakukuha namin 441=3 3 7 7 at 700=2 2 5 5 7.

Ngayon, gumawa tayo ng produkto ng lahat ng mga salik na kasangkot sa pagpapalawak ng mga numerong ito: 2 2 3 3 5 5 7 7 7. Ibinubukod namin mula sa produktong ito ang lahat ng mga salik na sabay-sabay na naroroon sa parehong mga pagpapalawak (mayroong isa lamang na kadahilanan - ito ang numero 7 ): 2 2 3 3 5 5 7 7. kaya, LCM(441, 700)=2 2 3 3 5 5 7 7=44 100.

Sagot:

LCM(441, 700)= 44 100.

Ang panuntunan para sa paghahanap ng LCM gamit ang decomposition ng mga numero sa prime factor ay maaaring mabuo nang medyo naiiba. Kung sa mga salik mula sa pagpapalawak ng bilang a idagdag ang mga nawawalang salik mula sa pagpapalawak ng bilang b, kung gayon ang halaga ng magreresultang produkto ay magiging katumbas ng hindi bababa sa karaniwang multiple ng mga numero a at b .

Halimbawa, kunin natin ang lahat ng parehong numero 75 at 210 , ang kanilang mga factorization ay ang mga sumusunod: 75=3 5 5 at 210=2 3 5 7. Sa multipliers 3 , 5 at 5 mula sa agnas ng numero 75 2 at 7 mula sa agnas ng numero 210 , nakukuha namin ang produkto 2 3 5 5 7, na ang halaga ay NOC(75, 210).

Halimbawa.

Hanapin ang hindi bababa sa karaniwang maramihang mga numero 84 at 648 .

Desisyon.

Una naming makuha ang agnas ng mga numero 84 at 648 sa mga pangunahing kadahilanan. Magkamukha sila 84=2 2 3 7 at 648=2 2 2 3 3 3 3. Sa multipliers 2 , 2 , 3 at 7 mula sa agnas ng numero 84 pagdaragdag ng nawawalang mga kadahilanan 2 , 3 , 3 at 3 mula sa agnas ng numero 648 , nakukuha namin ang produkto 2 2 2 3 3 3 3 7, na katumbas ng 4 536 . Kaya, ang nais na hindi bababa sa karaniwang maramihang ng mga numero 84 at 648 katumbas 4 536 .

Sagot:

LCM(84, 648)=4536.

Isaalang-alang natin ang dalawang pangunahing pamamaraan para sa paghahanap ng GCD sa dalawang pangunahing paraan: gamit ang Euclid algorithm at sa pamamagitan ng factoring. Ilapat natin ang parehong pamamaraan para sa dalawa, tatlo at higit pang mga numero.

Yandex.RTB R-A-339285-1

Euclid's algorithm para sa paghahanap ng GCD

Pinapadali ng algorithm ng Euclid na kalkulahin ang pinakamalaking karaniwang divisor ng dalawang positibong numero. Ibinigay namin ang mga formulasyon at patunay ng algorithm ni Euclid sa Greatest Common Divisor: Determinant, Examples section.

Ang kakanyahan ng algorithm ay ang patuloy 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 rk + 1 = 0, kung saan r k = gcd (a , b).

Halimbawa 1

64 at 48 .

Desisyon

Ipakilala natin ang notasyon: a = 64 , b = 48 .

Batay sa Euclid algorithm, isasagawa namin ang 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 pamamagitan ng 16 , makakakuha tayo ng 3 . I.e q2 = 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 ?

Desisyon

hatiin 432 sa 111 . Ayon sa algorithm ni Euclid, 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 111 at 432 ay 3.

Sagot: gcd(111, 432) = 3.

Halimbawa 3

Hanapin ang pinakamalaking karaniwang divisor ng 661 at 113 .

Desisyon

Hahatiin namin ang mga numero nang sunud-sunod at kunin ang GCD (661 , 113) = 1 . Nangangahulugan ito na ang 661 at 113 ay medyo prime number. Maaari nating malaman ito bago natin simulan ang mga kalkulasyon kung titingnan natin ang talahanayan ng mga primes.

Sagot: gcd(661, 113) = 1.

Paghahanap ng GCD sa pamamagitan ng Factoring Numbers into Prime Factors

Upang mahanap ang pinakamalaking karaniwang divisor ng dalawang numero sa pamamagitan ng factoring, kinakailangan na i-multiply ang lahat ng prime factor na nakukuha sa pamamagitan ng pag-decompose ng dalawang numerong ito at karaniwan sa kanila.

Halimbawa 4

Kung i-decompose 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 mga karaniwang salik sa dalawang produktong ito ay 2, 2 at 5. Ibig sabihin, NOD (220, 600) = 2 2 5 = 20.

Halimbawa 5

Hanapin ang pinakamalaking karaniwang divisor ng mga numero 72 at 96 .

Desisyon

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

Mga karaniwang prime factor para sa dalawang numero: 2 , 2 , 2 at 3 . Ibig sabihin, NOD (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, kikilos tayo ayon sa parehong algorithm, na binubuo sa paghahanap ng GCD ng dalawang numero na magkakasunod. Ang algorithm na ito ay batay sa aplikasyon ng sumusunod na theorem: GCD ng ilang numero a 1 , a 2 , … , a k ay katumbas ng bilang dk, na makikita sa sequential 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 .

Desisyon

Ipakilala natin ang notasyon: a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36.

Magsimula tayo sa paghahanap ng GCD ng mga numerong 78 at 294: d2= GCD (78 , 294) = 6 .

Ngayon simulan natin ang paghahanap ng d 3 \u003d GCD (d 2, a 3) \u003d GCD (6, 570) . Ayon sa Euclid algorithm 570 = 6 95 . Ibig sabihin nito ay d 3 = GCD (6 , 570) = 6 .

Hanapin ang d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36) . 36 ay nahahati sa 6 na walang nalalabi. Ito ay nagpapahintulot sa amin na makakuha d4= GCD (6 , 36) = 6 .

d4 = 6, iyon ay, GCD (78 , 294 , 570 , 36) = 6 .

Sagot:

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

Desisyon

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.

NOD 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 mga module ng mga numerong ito upang mahanap ang pinakamalaking karaniwang divisor. Magagawa natin ito, alam ang pag-aari ng mga numero na may magkasalungat na mga palatandaan: mga numero n at -n may parehong divisors.

Halimbawa 8

Hanapin ang gcd ng mga negatibong integer − 231 at − 140 .

Desisyon

Upang magsagawa ng mga kalkulasyon, kunin natin ang mga module ng mga numero na ibinigay sa kundisyon. Ito ang magiging mga numerong 231 at 140. Ilagay natin ito nang maikli: GCD (− 231 , − 140) = GCD (231 , 140) . Ngayon ay ilapat natin ang algorithm ni Euclid upang mahanap ang mga pangunahing salik 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 NOD (− 231 , − 140) = GCD (231 , 140) , pagkatapos ay ang 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 .

Desisyon

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 nabubulok namin ang lahat ng ibinigay na numero sa mga pangunahing kadahilanan: 585 = 3 3 5 13, 81 = 3 3 3 3 at 189 = 3 3 3 7. Ang prime factor 3 at 3 ay karaniwan sa tatlong numero. Lumalabas na gcd (585 , 81 , 189) = gcd (- 585 , 81 , - 189) = 9 .

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

Kung may napansin kang pagkakamali sa text, mangyaring i-highlight ito at pindutin ang Ctrl+Enter