Suurima ühisteguri

Teised tööriistad

Pindalakalkulaator{$ ',' | translate $}
Ümbermõõdukalkulaator{$ ',' | translate $}
Ruumala kalkulaator{$ ',' | translate $}
Korrutustabel{$ ',' | translate $}
Mendelejevi tabel{$ ',' | translate $}
Matrix kalkulaator{$ ',' | translate $}
Vähima ühiskordse{$ ',' | translate $}
Siinus, koosinus, puutuja{$ ',' | translate $}

Suurima ühisteguri kalkulaator

Enne suurima ühisjagaja (GCD) mõiste määratlemise juurde asumist on vaja mõista, mis on ühine jagaja üldiselt.

On teada, et täisarvul võib olla mitu jagajat. Oleme huvitatud mitme täisarvu samaaegsest juurdepääsust neile. Mitme täisarvu ühiseks jagajaks loeme arvu, mis võib toimida määratud seeria iga arvu jagajana.

Näiteks arvudel 8 ja 12 on järgmised ühised jagajad: 1 ja 4. Seda saab hõlpsasti kontrollida, kirjutades matemaatilisi avaldisi: 8 = 4 ⋅ 2; 12 = 3 ⋅ 4.

Tuleb märkida, et igal arvul on esialgu vähemalt kaks ühist jagajat: iga arv jagub iseendaga ilma jäägita ja jagub ka 1-ga.

Suurima ühise jagaja määramine

Kahe naturaalarvu suurim ühine jagaja (GCD) on suurim naturaalarvudest, millega saame oma kahte arvu jagada. Kui kahe naturaalarvu suurima ühisjagaja väärtus on 1, siis nimetame neid numbreid koprime.

Kahe arvu a ja b puhul on suurim ühisjagaja arv, millega a ja b saab jagada ilma jäägita. See avaldis on kirjutatud järgmiselt: gcd (a, b) = c.

Teine viis GCD kirjutamiseks: (a, b) = c. Enamasti kasutatakse siiski esimest võimalust.

Nii näiteks on arvude 4 ja 16 suurim ühisjagaja 4. Kirjutame: gcd (4, 16) = 4.

Kirjeldame, kuidas me selle tulemuseni jõudsime:

Kirjutasime välja kõik arvu 4 jagajad. Saime: 4, 2, 1.
Järgmisena värvisime kõik 16 jagajad. Saime: 16, 8, 4, 2, 1.
Valisime jagajad, mis on ühised nii 4 kui 16 jaoks. Saime: 4, 2, 1.
Saadud ühisjagajate hulgast valiti suurim. See on 4.
Saame vastuse: numbrite 4 ja 16 puhul on GCD 4.

Samamoodi leiate GCD kolme või enama täisarvu jaoks. Sel juhul on see suurim täisarv, millega saate kõik pakutud seeria numbrid jagada.

Nii näiteks on täisarvude 6, 12, 18, 42 suurim jagaja arv 6, st gcd (6, 12, 18, 42) = 6. Vastus saadi algoritmi abil sarnaselt ülalkirjeldatule – seeria numbrite puhul kirjutati järjest välja kõik jagajad, misjärel valiti neist suurim.

GCD omadused

Suurimal ühisel jagajal on mitmeid omadusi, mis on olulised nullist suuremate jagajate positiivsete täisarvude GCD puhul.

Atribuut 1

Numbrite kohtade muutmisel GCD lõplik väärtus ei muutu. Saate selle avalduse kirjutada järgmiselt:

gcd(a, b) = gcd(b, a).

Atribuut 2

Kui a jagab b-ga, siis on a ja b ühisjagajate hulk sama, mis b jagajate hulk. Kirjutatud nii:

gcd(a, b) = b.

Tõestatud suurimat jagaja omadust saab kasutada kahe arvu gcd leidmiseks, kui üks neist jagub teisega. Sel juhul on GCD võrdne ühega neist arvudest, millega teine arv jagub.

Näiteks:

gcd(12, 4) = 4.

Sarnane:

gcd(10, 1) = 1.

Atribuut 3

Kui a = bq + c, kus a, b, c ja q on täisarvud, siis on a ja b ühisjagajate hulk sama, mis b ja c ühisjagajate hulk.

Võrdsus gcd (a, b) = gcd (b, c) hakkab kehtima.

Atribuut 4

Avaldis gcd(ma, mb) = m ⋅ gcd(a, b) on tõene tingimusel, et m on mis tahes naturaalarv.

Atribuut 5

Oletame, et p on a ja b mis tahes ühine jagaja.

Siis:

gcd(a / p, b / p) = gcd(a, b) / p.

Kui p = gcd(a, b), saame:

gcd (a / gcd (a, b), b / gcd (a, b)) = 1,

Seega on arvud a / gcd (a, b) ja b / gcd (a, b) koaprima.

Atribuut 6

Igal kahel arvul on vähemalt üks ühine jagaja – see on arv 1.

Tavamurdudega töötamiseks on vajalikud teadmised GCD kontseptsiooni teoreetiliste aluste kohta, samuti praktilised oskused selle määratlemisel. Lisaks on GCD tihedalt seotud teise matemaatilise ühikuga – kõige vähem levinud jagajaga. Mõlemat määratlust uuritakse tavaliselt kooli standardõppekava osana.

Kuidas leida suurim ühine tegur

Suurima ühisjagaja (gcd) leidmine on üsna populaarne ülesanne. See toiming aitab meil teha arvutusi, milles esinevad tavalised murrud.

GCD leidmise meetodid

Suurima ühise jagaja leidmiseks on mitu nippi. Vaatleme neist kõige populaarsemat.

GCD leidmine arvude algteguriteks jaotamisega

See meetod on üks kõige sagedamini kasutatavaid matemaatikaülesannete lahendamisel.

Algoritm GCD määramiseks algteguriteks jaotamisega koosneb järgmistest sammudest.

Esitame algteguritena numbreid. Näiteks arvu 20 saab esitada arvu 2 ⋅ 2 ⋅ 5 korrutisena.
Valige tegurid, mis esinevad mõlemas laienduses.
Leidke nende tegurite korrutis.

Vaatleme mõnda näidet selle algoritmi praktikas rakendamisest:

Määrake numbrite 12 ja 8 GCD.

Jagage 12 ja 8 algteguriteks:

12 = 2 ⋅ 2 ⋅ 3.
8 = 2 ⋅ 2 ⋅ 2.

Vaatame, millised tegurid esinevad mõlemas laienduses. Leia: 2 ja 2.

Korrutame tegurid ja saame:

2 ⋅ 2 = 4.

Vastus: gcd (12, 8) = 4.

Määrake arvude 75 ja 150 GCD.

Lahendusjärjestus on sarnane eelmisele näitele.

Esitame algteguritena 75 ja 150:

75 = 3 ⋅ 5 ⋅ 5.
150 = 2 ⋅ 3 ⋅ 5 ⋅ 5.

Määrake mõlemas laienduses korduvad tegurid: 3, 5 ja 5.

Korrutame saadud arvud kokku: 3 ⋅ 5 ⋅ 5 = 75.

Vastus: gcd (75, 150) = 75.

Määrake arvude 9 ja 5 GCD.

Selles näites kasutatakse algarve, mille kordaja saab olla ainult 1.

Kui arvestame 9 ja 5 algteguriteks, näeme, et neil ei ole samu tegureid:

5 = 5.
9 = 3 ⋅ 3.

Tuleb meeles pidada, et see juhtum on eriline. Sellised arvud on kaasalgarvud ja nende ühine jagaja on üks.

Eukleidese algoritm

See algoritm sai nime Vana-Kreeka matemaatiku Eukleidese järgi, kes kirjeldas seda esimest korda oma kirjutistes ("Alguste" 7. ja 10. raamat). On teada, et Euclid ei olnud selle algoritmi autor. Sellest hoolimata peetakse seda üheks vanimaks tänapäeval kasutatavaks algoritmiks.

Eukleidese algoritm muudab kahe positiivse arvu suurima ühisjagaja arvutamise lihtsaks.

GCD (a, b) leidmiseks näeb see algoritm välja järgmine:

Kui a = 0, siis gcd(a, b) = b, sest gcd(0, b) = b ja algoritm peatub.
Kui b = 0, siis gcd(a, b) = a, sest gcd(a, 0) = a ja algoritm peatub.
Jagage a b-ga jäägiga (a = b ⋅ q + r)
Leia gcd(b, r), kasutades Eukleidese algoritmi, sest gcd(a, b) = gcd(b, r).

Meetodi tõhususe praktikas kontrollimiseks vaadake näidet.

Tuleb määrata numbrite 270 ja 192 GCD.

a = 270, b = 192.
a ≠ 0.
b ≠ 0.

Jagades a b-ga, saame:

270/192 = 1 (ülejäänu on 78).

Saate kirjutada tulemuse järgmiselt: 270 = 192 ⋅ 1 + 78.

Järgmisena arvutame gcd (192, 78), kuna gcd (270, 192) = gcd (192, 78).

Lähme edasi.

a = 192, b = 78.
a ≠ 0.
b ≠ 0.

Jagades a b-ga, saame:

192/78 = 2 (ülejäänu on 36).

Võib kirjutada järgmiselt:

192 = 78 ⋅ 2 + 36.

Arvutage gcd(78, 36), kuna gcd(192, 78) = gcd(78, 36).

a = 78, b = 36.
a ≠ 0.
b ≠ 0.

Jagades a b-ga, saame:

78/36 = 2 (ülejäänu on 0).

Kirjutame tulemuse järgmiselt:

78 = 36 ⋅ 2 + 6.

Arvutage gcd(36, 6), kuna gcd(78, 36) = gcd(36, 6).

a = 36, b = 6.
a ≠ 0.
b ≠ 0.

Jagage A B-ga, saame 36/6 = 6 (ülejäänu on 0).

Kirjutage tulemus järgmisel kujul:

36 = 6 ⋅ 6 + 0.

Järgmisena leiame gcd(6, 0), kuna gcd(36, 6) = gcd(6, 0).

a = 6, b = 0.
a ≠ 0.
b = 0.

Selle tulemusel on meil:

gcd(6, 0) = 6.

Seega on meil järgmine arvutuste jada:

gcd(270, 192) = gcd(192, 78) = gcd(78, 36) = gcd(36, 6) = gcd(6, 0) = 6.

Selle tulemusena on meil vastus:

gcd(270, 192) = 6.

Igal ülalkirjeldatud otsingumeetodil on oma eelised ja puudused. Esimene meetod sobib suurepäraselt suhteliselt lihtsate näidetega töötamiseks, erinevalt teisest, mida saab kasutada keerukamate matemaatiliste ülesannete lahendamiseks.