Jotta voit oppia löytämään kahden tai useamman luvun suurimman yhteisen jakajan, sinun on ymmärrettävä, mitä luonnolliset, alkuluvut ja kompleksiluvut ovat.
Luonnollinen luku on mikä tahansa luku, jota käytetään kokonaislukujen laskemiseen.
Jos luonnollinen luku voidaan jakaa vain itsellään ja yhdellä, sitä kutsutaan alkuluvuksi.
Kaikki luonnolliset luvut voidaan jakaa itsellään ja yhdellä, mutta ainoa parillinen alkuluku on 2, kaikki muut alkuluvut voidaan jakaa kahdella. Siksi vain parittomat luvut voivat olla alkulukuja.
Alkulukuja on paljon, niistä ei ole täydellistä luetteloa. GCD:n löytämiseksi on kätevää käyttää erityisiä taulukoita tällaisilla numeroilla.
Useimmat luonnolliset luvut voidaan jakaa ei vain yhdellä, vaan myös muilla luvuilla. Joten esimerkiksi luku 15 voidaan jakaa 3:lla ja 5:llä. Kaikkia niitä kutsutaan luvun 15 jakajiksi.
Siten minkä tahansa A:n jakaja on luku, jolla se voidaan jakaa ilman jäännöstä. Jos luvulla on enemmän kuin kaksi luonnollista jakajaa, sitä kutsutaan yhdistelmäksi.
Numerolla 30 on jakajia kuten 1, 3, 5, 6, 15, 30.
Voit nähdä, että luvuilla 15 ja 30 on samat jakajat 1, 3, 5, 15. Näiden kahden luvun suurin yhteinen jakaja on 15.
Näin ollen lukujen A ja B yhteinen jakaja on luku, jolla voit jakaa ne kokonaan. Maksimi voidaan katsoa enimmäismääräksi, jolla ne voidaan jakaa.
Ongelmien ratkaisemiseksi käytetään seuraavaa lyhennettyä merkintää:
GCD (A; B).
Esimerkiksi GCD (15; 30) = 30.
Luonnollisen luvun kaikkien jakajien kirjoittamiseen käytetään merkintää:
D(15) = (1, 3, 5, 15)
gcd (9; 15) = 1
Tässä esimerkissä luonnollisilla luvuilla on vain yksi yhteinen jakaja. Niitä kutsutaan vastaavasti koprimeiksi, yksikkö on niiden suurin yhteinen jakaja.
Kuinka löytää lukujen suurin yhteinen jakaja
Useiden numeroiden GCD:n löytämiseksi tarvitset:
Etsi jokaisen luonnollisen luvun kaikki jakajat erikseen, eli jaa ne tekijöiksi (alkuluvuiksi);
Valitse kaikki samat tekijät annetuille numeroille;
Kerro ne yhteen.
Esimerkiksi lukujen 30 ja 56 suurimman yhteisen jakajan laskemiseksi kirjoitat seuraavaa:
Jotta et joutuisi sekaannukseen , on kätevää kirjoittaa kertoimet pystysarakkeilla. Viivan vasemmalle puolelle sinun on asetettava osinko ja oikealle - jakaja. Osingon alle tulee ilmoittaa tuloksena oleva osamäärä.
Oikeassa sarakkeessa on siis kaikki ratkaisuun tarvittavat tekijät.
Identtiset jakajat (löytyneet tekijät) voidaan alleviivata mukavuuden vuoksi. Ne tulee kirjoittaa uudelleen ja kertoa ja suurin yhteinen jakaja kirjoittaa ylös.
GCD (30; 56) = 2 * 5 = 10
On todella helppoa löytää lukujen suurin yhteinen jakaja. Pienellä harjoittelulla voit tehdä sen lähes automaattisesti.
Kutsutaan suurinta luonnollista lukua, jolla luvut a ja b ovat jaollisia ilman jäännöstä suurin yhteinen jakaja nämä numerot. Merkitse GCD(a, b).
Harkitse GCD:n löytämistä kahden luonnollisen luvun 18 ja 60 esimerkin avulla:
18 = 2×3×3
60 = 2×2×3×5
18 = 2×3×3
60 = 2×2×3×5
324 , 111 ja 432
Jaetaan luvut alkutekijöiksi:
324 = 2×2×3×3×3×3
111 = 3×37
432 = 2×2×2×2×3×3×3
Poista ensimmäisestä numerosta, jonka tekijät eivät ole toisessa ja kolmannessa numerossa, saamme:
2 x 2 x 2 x 2 x 3 x 3 x 3 = 3
GCD( 324 , 111 , 432 )=3
GCD:n etsiminen Euklidesin algoritmilla
Toinen tapa löytää suurin yhteinen jakaja käyttämällä Eukleideen algoritmi. Euklidesin algoritmi on tehokkain tapa löytää GCD, sen avulla sinun on jatkuvasti löydettävä loput numerojaosta ja käytettävä sitä toistuva kaava.
Toistuva kaava GCD:lle, gcd(a, b)=gcd(b, a mod b), jossa a mod b on jakojäännös a:lla b:llä.
Eukleideen algoritmi
Esimerkki: Etsi numeroiden suurin yhteinen jakaja 7920 ja 594
Etsitään GCD( 7920 , 594 ) Euclid-algoritmin avulla laskemme jaon loppuosan laskimen avulla.
- 7920 mod 594 = 7920 - 13 × 594 = 198
- 594 mod 198 = 594 - 3 × 198 = 0
Tuloksena saamme GCD( 7920 , 594 ) = 198
Vähiten yhteinen kerrannainen
Löytääksesi yhteisen nimittäjän, kun lisäät ja vähennät murtolukuja eri nimittäjillä, sinun on tiedettävä ja osattava laskea vähiten yhteinen kerrannainen(NOC).
Luvun "a" kerrannainen on luku, joka itse on jaollinen luvulla "a" ilman jäännöstä.
Numerot, jotka ovat 8:n kerrannaisia (eli nämä luvut jaetaan 8:lla ilman jäännöstä): nämä ovat luvut 16, 24, 32 ...
9:n kerrannaiset: 18, 27, 36, 45…
Tietyllä luvulla a on äärettömän monta kertaa, toisin kuin saman luvun jakajat. Jakajat - äärellinen luku.
Kahden luonnollisen luvun yhteinen kerrannainen on luku, joka on tasan jaollinen molemmilla näillä luvuilla..
Vähiten yhteinen kerrannainen Kahden tai useamman luonnollisen luvun (LCM) on pienin luonnollinen luku, joka on itse jaollinen kullakin näistä luvuista.
Kuinka löytää NOC
LCM voidaan löytää ja kirjoittaa kahdella tavalla.
Ensimmäinen tapa löytää LCM
Tätä menetelmää käytetään yleensä pienille määrille.
- Kirjoitamme jokaisen numeron kerrannaiset riville, kunnes on kerrannainen, joka on sama molemmille numeroille.
- Numeron "a" kerrannainen on merkitty isolla kirjaimella "K".
Esimerkki. Etsi LCM 6 ja 8.
Toinen tapa löytää LCM
Tätä menetelmää on kätevä käyttää kolmen tai useamman numeron LCM:n etsimiseen.
Identtisten tekijöiden lukumäärä lukujen laajennuksissa voi olla erilainen.
LCM (24, 60) = 2 2 3 5 2
Vastaus: LCM (24, 60) = 120
Voit myös formalisoida pienimmän yhteiskerran (LCM) löytämisen seuraavasti. Etsitään LCM (12, 16, 24) .
24 = 2 2 2 3
Kuten lukujen laajennuksesta näkyy, kaikki 12:n tekijät sisältyvät luvun 24 laajennukseen (suurin luvuista), joten lisäämme vain yhden 2:n luvun 16 laajennuksesta LCM:ään.
LCM (12, 16, 24) = 2 2 2 3 2 = 48
Vastaus: LCM (12, 16, 24) = 48
Erityistapaukset NOC:iden löytämiseksi
Esimerkiksi LCM(60, 15) = 60
Koska koprime-luvuilla ei ole yhteisiä alkujakajia, niiden pienin yhteinen kerrannainen on yhtä suuri kuin näiden lukujen tulo.
Sivustollamme voit myös käyttää erityistä laskinta löytääksesi vähiten yleisimmän kerran verkosta ja tarkistaaksesi laskelmasi.
Jos luonnollinen luku on jaollinen vain 1:llä ja itsellään, sitä kutsutaan alkuluvuksi.
Mikä tahansa luonnollinen luku on aina jaollinen 1:llä ja itsellään.
Luku 2 on pienin alkuluku. Tämä on ainoa parillinen alkuluku, loput alkuluvut ovat parittomia.
Alkulukuja on monia, ja ensimmäinen niistä on luku 2. Viimeistä alkulukua ei kuitenkaan ole. "Opiskelua varten" -osiossa voit ladata alkulukutaulukon aina 997 asti.
Mutta monet luonnolliset luvut ovat tasan jaollisia muilla luonnollisilla luvuilla.
- luku 12 on jaollinen 1:llä, 2:lla, 3:lla, 4:llä, 6:lla, 12:lla;
- 36 on jaollinen 1:llä, 2:lla, 3:lla, 4:llä, 6:lla, 12:lla, 18:lla, 36:lla.
- hajottaa lukujen jakajat alkutekijöiksi;
Lukuja, joilla luku on tasan jaollinen (12:lle nämä ovat 1, 2, 3, 4, 6 ja 12), kutsutaan luvun jakajiksi.
Luonnollisen luvun a jakaja on sellainen luonnollinen luku, joka jakaa annetun luvun "a" ilman jäännöstä.
Luonnollista lukua, jossa on enemmän kuin kaksi tekijää, kutsutaan yhdistelmäluvuksi.
Huomaa, että numeroilla 12 ja 36 on yhteiset jakajat. Nämä ovat numeroita: 1, 2, 3, 4, 6, 12. Näiden lukujen suurin jakaja on 12.
Kahden annetun luvun "a" ja "b" yhteinen jakaja on luku, jolla molemmat annetut luvut "a" ja "b" jaetaan ilman jäännöstä.
Suurin yhteinen jakaja(GCD) kahdesta annetusta luvusta "a" ja "b" on suurin luku, jolla molemmat luvut "a" ja "b" ovat jaollisia ilman jäännöstä.
Lyhyesti sanottuna lukujen "a" ja "b" suurin yhteinen jakaja kirjoitetaan seuraavasti:
Esimerkki: gcd (12; 36) = 12 .
Ratkaisutietueen lukujen jakajat on merkitty isolla kirjaimella "D".
Numeroilla 7 ja 9 on vain yksi yhteinen jakaja - numero 1. Tällaisia numeroita kutsutaan koprimilukuja.
Koprime-luvut ovat luonnollisia lukuja, joilla on vain yksi yhteinen jakaja - luku 1. Niiden GCD on 1.
Kuinka löytää suurin yhteinen jakaja
Kahden tai useamman luonnollisen luvun gcd:n löytämiseksi tarvitset:
Laskelmat kirjoitetaan kätevästi pystypalkilla. Kirjoita rivin vasemmalle puolelle ensin osinko, oikealle - jakaja. Edelleen vasemmassa sarakkeessa kirjoitamme ylös yksityisen arvot.
Selitetäänpä heti esimerkillä. Otetaan luvut 28 ja 64 alkutekijöiksi.
- Alleviivaa samat alkutekijät molemmissa luvuissa.
28 = 2 2 7
64 = 2 2 2 2 2 2
Etsimme identtisten alkutekijöiden tulon ja kirjoitamme vastauksen muistiin;
GCD (28; 64) = 2 2 = 4
Vastaus: GCD (28; 64) = 4
Voit järjestää GCD:n sijainnin kahdella tavalla: sarakkeessa (kuten yllä) tai "riville".
Ensimmäinen tapa kirjoittaa GCD
Etsi GCD 48 ja 36.
GCD (48; 36) = 2 2 3 = 12
Toinen tapa kirjoittaa GCD
Nyt kirjoitetaan GCD-hakuratkaisu riville. Etsi GCD 10 ja 15.
Tietosivultamme löydät myös suurimman yhteisen jakajan verkosta käyttämällä apuohjelmaa laskelmien tarkistamiseen.
Vähimmän yhteisen kerrannaisen löytäminen, menetelmät, esimerkit LCM:n löytämisestä.
Alla esitetty materiaali on loogista jatkoa teorialle artikkelista otsikon LCM - Vähiten yleinen moninkertainen, määritelmä, esimerkit, LCM:n ja GCD:n välinen suhde. Täällä puhutaan pienimmän yhteisen kerrannaisen (LCM) löytäminen, ja kiinnitä erityistä huomiota esimerkkien ratkaisemiseen. Osoitetaan ensin, kuinka kahden luvun LCM lasketaan näiden numeroiden GCD:nä. Harkitse seuraavaksi pienimmän yhteisen kerrannaisen löytämistä laskemalla luvut alkutekijöiksi. Sen jälkeen keskitymme kolmen tai useamman luvun LCM:n löytämiseen ja kiinnitämme huomiota myös negatiivisten lukujen LCM:n laskemiseen.
Sivulla navigointi.
Pienimmän yhteiskerran (LCM) laskenta gcd:n kautta
Yksi tapa löytää pienin yhteinen kerrannainen perustuu LCM:n ja GCD:n väliseen suhteeseen. LCM:n ja GCD:n välinen suhde mahdollistaa kahden positiivisen kokonaisluvun pienimmän yhteisen kerrannaisen laskemisen tunnetun suurimman yhteisen jakajan kautta. Vastaavalla kaavalla on muoto LCM(a, b)=a b: GCD(a, b). Harkitse esimerkkejä LCM:n löytämisestä yllä olevan kaavan mukaan.
Etsi kahdesta luvusta 126 ja 70 pienin yhteinen kerrannainen.
Tässä esimerkissä a=126 , b=70 . Käytetään LCM:n linkkiä GCD:hen, joka ilmaistaan kaavalla LCM(a, b)=a b: GCM(a, b) . Eli ensin on löydettävä lukujen 70 ja 126 suurin yhteinen jakaja, jonka jälkeen voidaan laskea näiden lukujen LCM kirjoitetun kaavan mukaan.
Etsi gcd(126, 70) käyttämällä Euklidin algoritmia: 126=70 1+56 , 70=56 1+14 , 56=14 4 , joten gcd(126, 70)=14 .
Nyt löydämme vaaditun pienimmän yhteiskerran: LCM(126, 70)=126 70:GCD(126, 70)= 126 70:14=630 .
Mikä on LCM(68, 34)?
Koska 68 on tasan jaollinen luvulla 34 , niin gcd(68, 34)=34 . Nyt lasketaan pienin yhteinen kerrannainen: LCM(68, 34)=68 34:GCD(68, 34)= 68 34:34=68 .
Huomaa, että edellinen esimerkki sopii seuraavaan sääntöön LCM:n löytämiseksi positiivisille kokonaisluvuille a ja b: jos luku a on jaollinen b:llä, niin näiden lukujen pienin yhteinen kerrannainen on a .
LCM:n löytäminen laskemalla luvut alkutekijöiksi
Toinen tapa löytää pienin yhteinen kerrannainen perustuu lukujen laskemiseen alkutekijöiksi. Jos teemme näiden lukujen kaikkien alkutekijöiden tulon, jonka jälkeen jätämme tästä tulosta pois kaikki yleiset alkutekijät, jotka esiintyvät näiden lukujen laajennuksissa, niin tuloksena oleva tulo on yhtä suuri kuin näiden lukujen pienin yhteinen kerrannainen.
Ilmoitettu sääntö LCM:n löytämiseksi seuraa yhtälöstä LCM(a, b)=a b: GCD(a, b) . Todellakin, lukujen a ja b tulo on yhtä suuri kuin kaikkien lukujen a ja b laajennuksiin osallistuvien tekijöiden tulo. Gcd(a, b) on puolestaan yhtä kuin kaikkien lukujen a ja b laajennuksissa samanaikaisesti esiintyvien alkutekijöiden tulo (joka on kuvattu osiossa gcd:n löytäminen käyttämällä lukujen alkutekijöitä jakamista ).
Otetaan esimerkki. Kerro meille, että 75=3 5 5 ja 210=2 3 5 7 . Laske näiden laajennusten kaikkien tekijöiden tulo: 2 3 3 5 5 5 7 . Nyt jätetään tästä tuotteesta pois kaikki tekijät, jotka ovat läsnä sekä luvun 75 laajennuksessa että luvun 210 laajennuksessa (sellaiset tekijät ovat 3 ja 5), jolloin tuote saa muotoa 2 3 5 5 7 . Tämän tuotteen arvo on yhtä suuri kuin lukujen 75 ja 210 pienin yhteinen kerrannainen, eli LCM(75, 210)= 2 3 5 5 7=1 050 .
Kun olet laskenut luvut 441 ja 700 alkutekijöiksi, etsi näiden lukujen pienin yhteinen kerrannainen.
Jaetaan luvut 441 ja 700 alkutekijöiksi: 
Saamme 441=3 3 7 7 ja 700=2 2 5 5 7 .
Tehdään nyt tulo kaikista tekijöistä, jotka vaikuttavat näiden lukujen laajentumiseen: 2 2 3 3 5 5 7 7 7 . Jätetään tästä tuotteesta pois kaikki tekijät, jotka ovat samanaikaisesti läsnä molemmissa laajennuksissa (tällaista tekijää on vain yksi - tämä on luku 7): 2 2 3 3 5 5 7 7 . Joten LCM(441; 700) = 2 2 3 3 5 5 7 7 = 44 100 .
LCM(441; 700) = 44 100.
Sääntö LCM:n löytämiseksi käyttämällä lukujen hajottamista alkutekijöiksi voidaan muotoilla hieman eri tavalla. Jos luvun b laajennuksesta puuttuvat tekijät lisätään luvun a laajennuksen tekijöihin, niin tuloksena olevan tuotteen arvo on yhtä suuri kuin lukujen a ja b pienin yhteinen kerrannainen.
Otetaan esimerkiksi kaikki samat luvut 75 ja 210, niiden laajennukset alkutekijöiksi ovat seuraavat: 75=3 5 5 ja 210=2 3 5 7 . Tekijöihin 3, 5 ja 5 luvun 75 laajennuksesta lisätään puuttuvat tekijät 2 ja 7 luvun 210 laajennuksesta, saadaan tulo 2 3 5 5 7 , jonka arvo on LCM(75 , 210) .
Etsi lukujen 84 ja 648 pienin yhteinen kerrannainen.
Ensin saadaan lukujen 84 ja 648 hajotus alkutekijöiksi. Ne näyttävät tältä 84=2 2 3 7 ja 648=2 2 2 3 3 3 3 . Tekijöihin 2 , 2 , 3 ja 7 luvun 84 laajennuksesta lisätään puuttuvat tekijät 2 , 3 , 3 ja 3 luvun 648 laajennuksesta , saadaan tulo 2 2 2 3 3 3 3 7 , joka on yhtä suuri kuin 4 536 . Siten lukujen 84 ja 648 haluttu pienin yhteinen kerrannainen on 4536.
Kolmen tai useamman luvun LCM:n löytäminen
Kolmen tai useamman luvun pienin yhteinen kerrannainen voidaan löytää etsimällä peräkkäin kahden luvun LCM. Muista vastaava lause, joka antaa tavan löytää kolmen tai useamman luvun LCM.
Olkoon positiiviset kokonaisluvut a 1 , a 2 , …, a k, näiden lukujen pienin yhteinen kerrannainen m k löytyy peräkkäisestä laskelmasta m 2 = LCM (a 1 , a 2) , m 3 = LCM (m 2 , a 3) , … , m k =LCM(m k−1, a k) .
Harkitse tämän lauseen soveltamista esimerkissä, jossa löydetään neljän luvun pienin yhteinen kerrannainen.
Etsi neljän luvun 140, 9, 54 ja 250 LCM.
Ensin löydämme m 2 = LCM (a 1 , a 2) = LCM (140, 9) . Tätä varten määritämme euklidisen algoritmin avulla gcd(140, 9) , meillä on 140=9 15+5 , 9=5 1+4 , 5=4 1+1 , 4=1 4 , joten gcd( 140, 9) = 1, josta LCM(140, 9) = 140 9: GCD(140, 9) = 140 9:1 = 1 260 . Eli m 2 = 1 260 .
Nyt löydämme m 3 = LCM (m 2, a 3) = LCM (1 260, 54) . Lasketaan se gcd(1 260, 54) :n avulla, joka myös määräytyy Euklidisen algoritmin avulla: 1 260=54 23+18 , 54=18 3 . Sitten gcd(1 260, 54) = 18, josta LCM(1 260, 54) = 1 260 54:gcd(1 260, 54) = 1 260 54:18 = 3 780. Eli m 3 \u003d 3 780.
Jäljelle jää löytää m 4 = LCM (m 3, a 4) = LCM (3 780, 250). Tätä varten löydämme GCD(3 780, 250) käyttämällä Euklidin algoritmia: 3 780=250 15+30 , 250=30 8+10 , 30=10 3 . Siksi gcd(3 780, 250) = 10, joten LCM(3 780, 250) = 3 780 250:gcd(3 780, 250) = 3 780 250:10 = 94 500. Eli m 4 \u003d 94 500.
Joten alkuperäisen neljän luvun pienin yhteinen kerrannainen on 94 500.
LCM(140; 9; 54; 250) = 94500.
Monissa tapauksissa kolmen tai useamman luvun pienin yhteinen kerrannainen löydetään kätevästi käyttämällä annettujen lukujen alkutekijöitä. Tässä tapauksessa on noudatettava seuraavaa sääntöä. Usean luvun pienin yhteinen kerrannainen on yhtä suuri kuin tulo, joka muodostuu seuraavasti: toisen luvun laajennuksesta puuttuvat tekijät lisätään kaikkiin ensimmäisen luvun laajennuksesta peräisin oleviin tekijöihin, puuttuvat tekijät ensimmäisen luvun laajennuksesta. kolmas luku lisätään saatuihin tekijöihin ja niin edelleen.
Harkitse esimerkkiä pienimmän yhteiskerran löytämisestä käyttämällä lukujen hajottamista alkutekijöiksi.
Etsi viiden luvun 84, 6, 48, 7, 143 pienin yhteinen kerrannainen.
Ensin saadaan näiden lukujen hajotukset alkutekijöiksi: 84=2 2 3 7 , 6=2 3 , 48=2 2 2 2 3 , 7 (7 on alkuluku, se osuu yhteen sen hajoamisen kanssa alkutekijöiksi) ja 143=11 13 .
Löytääksesi näiden lukujen LCM, ensimmäisen luvun 84 tekijöihin (ne ovat 2 , 2 , 3 ja 7) sinun on lisättävä puuttuvat tekijät toisen luvun 6 laajennuksesta. Luvun 6 laajennus ei sisällä puuttuvia tekijöitä, koska ensimmäisen luvun 84 laajennuksessa ovat jo mukana sekä 2 että 3 . Lisätään tekijöihin 2, 2, 3 ja 7 puuttuvat tekijät 2 ja 2 kolmannen luvun 48 laajennuksesta, saadaan joukko kertoimia 2, 2, 2, 2, 3 ja 7. Tähän joukkoon ei tarvitse lisätä tekijöitä seuraavassa vaiheessa, koska se sisältää jo 7. Lopuksi tekijöihin 2 , 2 , 2 , 2 , 3 ja 7 lisätään puuttuvat tekijät 11 ja 13 luvun 143 laajennuksesta. Saamme tuotteen 2 2 2 2 3 7 11 13, joka on yhtä suuri kuin 48 048.
Siksi LCM(84, 6, 48, 7, 143)=48048 .
LCM(84; 6; 48; 7; 143) = 48048.
Vähiten yhteisen negatiivisten lukujen löytäminen
Joskus on tehtäviä, joissa sinun on löydettävä lukujen pienin yhteinen kerrannainen, joista yksi, useita tai kaikki luvut ovat negatiivisia. Näissä tapauksissa kaikki negatiiviset luvut on korvattava niiden vastakkaisilla luvuilla, minkä jälkeen tulee löytää positiivisten lukujen LCM. Tämä on tapa löytää negatiivisten lukujen LCM. Esimerkiksi LCM(54, -34)=LCM(54, 34) ja LCM(-622, -46, -54, -888)= LCM(622, 46, 54, 888) .
Voimme tehdä tämän, koska a:n kerrannaisten joukko on sama kuin −a:n kerrannaisten joukko (a ja −a ovat vastakkaisia lukuja). Todellakin, olkoon b jokin a:n kerrannainen, silloin b on jaollinen a:lla, ja jaollisuuden käsite väittää sellaisen kokonaisluvun q olemassaolon, että b=a q . Mutta yhtälö b=(−a)·(−q) on myös totta, mikä saman jaollisuuskäsitteen nojalla tarkoittaa, että b on jaollinen −a:lla, eli b on −a:n kerrannainen. Myös käänteinen väite on totta: jos b on jokin −a:n kerrannainen, niin b on myös a:n kerrannainen.
Etsi negatiivisten lukujen −145 ja −45 pienin yhteinen kerrannainen.
Korvataan negatiiviset luvut −145 ja −45 niiden vastakkaisilla luvuilla 145 ja 45 . Meillä on LCM(−145, −45)=LCM(145, 45) . Kun olet määrittänyt gcd(145, 45)=5 (esimerkiksi Euclid-algoritmia käyttämällä), laskemme LCM(145, 45)=145 45:gcd(145, 45)= 145 45:5=1 305 . Siten negatiivisten kokonaislukujen −145 ja −45 pienin yhteinen kerrannainen on 1,305 .
www.cleverstudents.ru
Jatkamme divisioonan opiskelua. Tällä oppitunnilla tarkastelemme käsitteitä, kuten GCD ja NOC.
GCD on suurin yhteinen jakaja.
NOC on pienin yhteinen kerrannainen.
Aihe on melko tylsä, mutta se on ymmärrettävä. Ilman tämän aiheen ymmärtämistä et pysty työskentelemään tehokkaasti murtolukujen kanssa, jotka ovat todellinen este matematiikassa.
Suurin yhteinen jakaja
Määritelmä. Suurin yhteinen numeroiden jakaja a ja b a ja b jaettu ilman jäännöstä.
Ymmärtääksemme tämän määritelmän hyvin, korvaamme muuttujien sijaan a ja b mikä tahansa kaksi numeroa esimerkiksi muuttujan sijaan a korvaa luku 12 ja muuttujan sijaan b numero 9. Yritetään nyt lukea tämä määritelmä:
Suurin yhteinen numeroiden jakaja 12 ja 9 on suurin luku, jolla 12 ja 9 jaettu ilman jäännöstä.
Määritelmästä käy selvästi ilmi, että puhumme numeroiden 12 ja 9 yhteisestä jakajasta, ja tämä jakaja on suurin kaikista olemassa olevista jakajista. Tämä suurin yhteinen jakaja (gcd) on löydettävä.
Kahden luvun suurimman yhteisen jakajan löytämiseksi käytetään kolmea menetelmää. Ensimmäinen menetelmä on melko aikaa vievä, mutta sen avulla voit ymmärtää aiheen olemuksen hyvin ja tuntea sen koko merkityksen.
Toinen ja kolmas menetelmä ovat melko yksinkertaisia ja mahdollistavat GCD:n nopean löytämisen. Harkitsemme kaikkia kolmea menetelmää. Ja mitä soveltaa käytännössä - sinä valitset.
Ensimmäinen tapa on löytää kaikki mahdolliset kahden luvun jakajat ja valita niistä suurin. Tarkastellaan tätä menetelmää seuraavassa esimerkissä: Etsi lukujen 12 ja 9 suurin yhteinen jakaja.
Ensin etsitään kaikki mahdolliset luvun 12 jakajat. Tätä varten jaamme 12 kaikkiin jakajiin välillä 1-12. Jos jakaja antaa meille mahdollisuuden jakaa 12 ilman jäännöstä, korostamme sen sinisellä ja tee sopiva selitys suluissa.
12: 1 = 12
(12 jaettuna 1:llä ilman jäännöstä, joten 1 on luvun 12 jakaja)
12: 2 = 6
(12 jaettuna 2:lla ilman jäännöstä, joten 2 on luvun 12 jakaja)
12: 3 = 4
(12 jaettuna 3:lla ilman jäännöstä, joten 3 on luvun 12 jakaja)
12: 4 = 3
(12 jaettuna 4:llä ilman jäännöstä, joten 4 on luvun 12 jakaja)
12:5 = 2 (2 jäljellä)
(12:ta ei jaeta viidellä ilman jäännöstä, joten 5 ei ole luvun 12 jakaja)
12: 6 = 2
(12 jaettuna 6:lla ilman jäännöstä, joten 6 on luvun 12 jakaja)
12: 7 = 1 (5 jäljellä)
(12:ta ei jaeta 7:llä ilman jäännöstä, joten 7 ei ole luvun 12 jakaja)
12: 8 = 1 (4 jäljellä)
(12:ta ei jaeta 8:lla ilman jäännöstä, joten 8 ei ole luvun 12 jakaja)
12:9 = 1 (3 jäljellä)
(12:ta ei jaeta 9:llä ilman jäännöstä, joten 9 ei ole luvun 12 jakaja)
12: 10 = 1 (2 jäljellä)
(12:ta ei jaeta 10:llä ilman jäännöstä, joten 10 ei ole luvun 12 jakaja)
12:11 = 1 (1 jäljellä)
(12:ta ei jaeta luvulla 11 ilman jäännöstä, joten 11 ei ole luvun 12 jakaja)
12: 12 = 1
(12 jaettuna 12:lla ilman jäännöstä, joten 12 on luvun 12 jakaja)
Etsitään nyt luvun 9 jakajat. Voit tehdä tämän tarkistamalla kaikki jakajat välillä 1 - 9
9: 1 = 9
(9 jaettuna 1:llä ilman jäännöstä, joten 1 on luvun 9 jakaja)
9: 2 = 4 (1 jäljellä)
(9 ei ole jaettu kahdella ilman jäännöstä, joten 2 ei ole 9:n jakaja)
9: 3 = 3
(9 jaettuna 3:lla ilman jäännöstä, joten 3 on 9:n jakaja)
9: 4 = 2 (1 jäljellä)
(9 ei ole jaettu 4:llä ilman jäännöstä, joten 4 ei ole 9:n jakaja)
9:5 = 1 (4 jäljellä)
(9 ei ole jaettu viidellä ilman jäännöstä, joten 5 ei ole 9:n jakaja)
9: 6 = 1 (3 jäljellä)
(9 ei jakanut 6:lla ilman jäännöstä, joten 6 ei ole 9:n jakaja)
9:7 = 1 (2 jäljellä)
(9 ei ole jaettu luvulla 7 ilman jäännöstä, joten 7 ei ole 9:n jakaja)
9:8 = 1 (1 jäljellä)
(9 ei ole jaettu luvulla 8 ilman jäännöstä, joten 8 ei ole 9:n jakaja)
9: 9 = 1
(9 jaettuna 9:llä ilman jäännöstä, joten 9 on luvun 9 jakaja)
Kirjoita nyt molempien lukujen jakajat. Sinisellä korostetut numerot ovat jakajia. Kirjoitetaan ne ulos:
Kun olet kirjoittanut jakajat, voit heti määrittää, mikä niistä on suurin ja yleisin.
Määritelmän mukaan lukujen 12 ja 9 suurin yhteinen jakaja on luku, jolla 12 ja 9 ovat tasan jaollisia. Suurin ja yhteinen lukujen 12 ja 9 jakaja on luku 3
Sekä luku 12 että numero 9 ovat jaollisia kolmella ilman jäännöstä:
Joten gcd (12 ja 9) = 3
Toinen tapa löytää GCD
Harkitse nyt toista tapaa löytää suurin yhteinen jakaja. Tämän menetelmän ydin on hajottaa molemmat luvut alkutekijöiksi ja kertoa yhteiset luvut.
Esimerkki 1. Etsi GCD numeroista 24 ja 18
Laitetaan ensin molemmat luvut alkutekijöiksi:
Nyt kerromme niiden yhteiset tekijät. Yhteisiä tekijöitä voidaan alleviivata, jotta se ei menisi hämmentymään.
Tarkastellaan luvun 24 hajotusta. Sen ensimmäinen tekijä on 2. Etsimme samaa tekijää luvun 18 hajottelusta ja näemme, että se on myös siellä. Korostamme molemmat:
Jälleen tarkastellaan luvun 24 hajotusta. Sen toinen tekijä on myös 2. Etsimme samaa tekijää luvun 18 hajotuksesta ja näemme, että se ei ole siellä toista kertaa. Silloin emme korosta mitään.
Numeron 24 laajennuksen kaksi seuraavaa puuttuu myös luvun 18 laajennuksesta.
Siirrymme viimeiseen tekijään luvun 24 hajotuksessa. Tämä on tekijä 3. Etsimme samaa tekijää luvun 18 hajotuksessa ja näemme, että se on myös siellä. Korostamme molempia kolmea:
Joten lukujen 24 ja 18 yhteiset tekijät ovat tekijät 2 ja 3. GCD:n saamiseksi nämä tekijät on kerrottava:
Joten gcd (24 ja 18) = 6
Kolmas tapa löytää GCD
Harkitse nyt kolmatta tapaa löytää suurin yhteinen jakaja. Tämän menetelmän ydin on siinä, että suurimman yhteisen jakajan etsittävät luvut jaetaan alkutekijöiksi. Sitten ensimmäisen luvun hajotuksesta poistetaan tekijät, jotka eivät sisälly toisen luvun hajotukseen. Ensimmäisen laajennuksen loput luvut kerrotaan ja saavat GCD:n.
Etsitään esimerkiksi GCD numeroille 28 ja 16 tällä tavalla. Ensinnäkin jaamme nämä luvut alkutekijöiksi:
Saimme kaksi laajennusta: ja
Nyt poistamme ensimmäisen luvun laajennuksesta tekijät, jotka eivät sisälly toisen luvun laajennukseen. Toisen numeron laajennus ei sisällä seitsemää. Poistamme sen ensimmäisestä laajennuksesta:
Nyt kerrotaan loput tekijät ja saadaan GCD:
Luku 4 on lukujen 28 ja 16 suurin yhteinen jakaja. Molemmat luvut ovat jaollisia 4:llä ilman jäännöstä:
Esimerkki 2 Etsi GCD numeroista 100 ja 40
Lasketaan luku 100
Lasketaan luku 40
Meillä on kaksi laajennusta:
Nyt poistamme ensimmäisen luvun laajennuksesta tekijät, jotka eivät sisälly toisen luvun laajennukseen. Toisen numeron laajennus ei sisällä yhtä viitestä (on vain yksi viisi). Poistamme sen ensimmäisestä hajotuksesta
Kerro loput luvut:
Saimme vastauksen 20. Luku 20 on siis lukujen 100 ja 40 suurin yhteinen jakaja. Nämä kaksi lukua ovat jaollisia 20:llä ilman jäännöstä:
GCD (100 ja 40) = 20.
Esimerkki 3 Etsi lukujen 72 ja 128 gcd
Lasketaan luku 72
Lasketaan luku 128
2×2×2×2×2×2×2
Nyt poistamme ensimmäisen luvun laajennuksesta tekijät, jotka eivät sisälly toisen luvun laajennukseen. Toisen luvun laajennus ei sisällä kahta triplettiä (ei ole ollenkaan). Poistamme ne ensimmäisestä hajotuksesta:
Saimme vastauksen 8. Luku 8 on siis lukujen 72 ja 128 suurin yhteinen jakaja. Nämä kaksi lukua ovat jaollisia 8:lla ilman jäännöstä:
GCD (72 ja 128) = 8
GCD:n etsiminen useille numeroille
Suurin yhteinen jakaja löytyy useille luvuille, ei vain kahdelle. Tätä varten suurimmalle yhteiselle jakajalle löydettävät luvut jaetaan alkutekijöiksi, jolloin saadaan näiden lukujen yhteisten alkutekijöiden tulo.
Etsitään esimerkiksi GCD numeroille 18, 24 ja 36
Lasketaan numero 18
Lasketaan numero 24
Lasketaan numero 36
Meillä on kolme laajennusta:
Nyt valitsemme ja alleviivaamme näiden numeroiden yhteiset tekijät. Yhteiset tekijät on sisällytettävä kaikkiin kolmeen numeroon:
Näemme, että yhteiset tekijät numeroille 18, 24 ja 36 ovat tekijät 2 ja 3. Kerromalla nämä tekijät saadaan etsimämme GCD:
Saimme vastauksen 6. Luku 6 on siis lukujen 18, 24 ja 36 suurin yhteinen jakaja. Nämä kolme lukua ovat jaollisia 6:lla ilman jäännöstä:
GCD (18, 24 ja 36) = 6
Esimerkki 2 Etsi gcd numeroille 12, 24, 36 ja 42
Lasketaan jokainen luku kertoimella. Sitten löydämme näiden lukujen yhteisten tekijöiden tulon.
Lasketaan numero 12
Lasketaan numero 42
Meillä on neljä laajennusta:
Nyt valitsemme ja alleviivaamme näiden numeroiden yhteiset tekijät. Yhteiset tekijät on sisällytettävä kaikkiin neljään numeroon:
Näemme, että yhteiset tekijät luvuille 12, 24, 36 ja 42 ovat tekijät 2 ja 3. Kerromalla nämä tekijät saadaan etsimämme GCD:
Saimme vastauksen 6. Luku 6 on siis lukujen 12, 24, 36 ja 42 suurin yhteinen jakaja. Nämä luvut ovat jaollisia 6:lla ilman jäännöstä:
gcd(12, 24, 36 ja 42) = 6
Edellisestä oppitunnista tiedämme, että jos jokin luku jaetaan toisella ilman jäännöstä, sitä kutsutaan tämän luvun kerrannaiseksi.
Osoittautuu, että kerrannainen voi olla yhteinen useille luvuille. Ja nyt olemme kiinnostuneita kahden luvun kerrannaisesta, vaikka sen tulisi olla mahdollisimman pieni.
Määritelmä. Lukujen vähiten yhteinen kerrannainen (LCM). a ja b- a ja b a ja numero b.
Määritelmä sisältää kaksi muuttujaa a ja b. Korvataan nämä muuttujat millä tahansa kahdella numerolla. Esimerkiksi muuttujan sijaan a korvaa numero 9 ja muuttujan sijaan b korvataan luku 12. Yritetään nyt lukea määritelmä:
Lukujen vähiten yhteinen kerrannainen (LCM). 9 ja 12 - on pienin luku, joka on luvun kerrannainen 9 ja 12 . Toisin sanoen se on niin pieni luku, joka on jaollinen luvulla ilman jäännöstä 9 ja numerossa 12 .
Määritelmästä on selvää, että LCM on pienin luku, joka on jaollinen ilman jäännöstä 9:llä ja 12:lla. Tämä LCM on löydettävä.
On kaksi tapaa löytää pienin yhteinen monikerta (LCM). Ensimmäinen tapa on kirjoittaa muistiin kahden luvun ensimmäiset kerrannaiset ja sitten valita näistä kerrannaisista sellainen luku, joka on yhteinen sekä luvuille että pienille. Sovelletaan tätä menetelmää.
Ensinnäkin, etsitään luvun 9 ensimmäiset kerrannaiset. Löytääksesi luvun 9 kerrannaiset, sinun on kerrottava tämä yhdeksän vuorotellen luvuilla 1-9. Saat vastaukset luvun 9 kerrannaisina. , aloitetaan. Useita korostetaan punaisella:
Nyt löydämme luvun 12 kerrannaiset. Tätä varten kerromme 12 vuorotellen kaikilla luvuilla 1-12.
Harkitse kahta tapaa löytää suurin yhteinen jakaja.
Löytö Factoringin avulla
Ensimmäinen tapa on löytää suurin yhteinen jakaja laskemalla annetut luvut alkutekijöiksi.
Useiden lukujen GCD:n löytämiseksi riittää, että ne hajotetaan alkutekijöiksi ja kerrotaan keskenään ne, jotka ovat yhteisiä kaikille annetuille luvuille.
Esimerkki 1 Etsitään GCD (84, 90).
Jaamme luvut 84 ja 90 alkutekijöiksi:
Joten olemme alleviivaaneet kaikki yleiset alkutekijät, on vielä kerrottava ne keskenään: 1 2 3 = 6.
Joten gcd(84, 90) = 6.
Esimerkki 2 Etsitään GCD (15, 28).
Jaamme luvut 15 ja 28 alkutekijöiksi:
Numerot 15 ja 28 ovat alkulukuja, koska niiden suurin yhteinen jakaja on yksi.
gcd (15, 28) = 1.
Eukleideen algoritmi
Toinen menetelmä (jota kutsutaan myös Euklid-menetelmäksi) on löytää GCD peräkkäisellä jaolla.
Ensin tarkastellaan tätä menetelmää sovellettuina vain kahteen annettuun numeroon, ja sitten selvitetään, kuinka sitä sovelletaan kolmeen tai useampaan numeroon.
Jos kahdesta annetusta luvusta suurempi on jaollinen pienemmällä, niin pienempi luku on niiden suurin yhteinen jakaja.
Esimerkki 1 Otetaan kaksi lukua 27 ja 9. Koska 27 on jaollinen 9:llä ja 9 on jaollinen 9:llä, niin 9 on lukujen 27 ja 9 yhteinen jakaja. Tämä jakaja on myös suurin, koska 9 ei voi olla jaollinen millään luvulla, suurempi kuin 9. Siksi gcd (27, 9) = 9.
Muissa tapauksissa kahden luvun suurimman yhteisen jakajan löytämiseksi käytetään seuraavaa menettelyä:
- Kahdesta annetusta luvusta suurempi luku jaetaan pienemmällä.
- Sitten pienempi luku jaetaan jäännöksellä, joka saadaan jakamalla suurempi luku pienemmällä.
- Lisäksi ensimmäinen jäännös jaetaan toisella jäännöksellä, joka saadaan jakamalla pienempi luku ensimmäisellä jäännöksellä.
- Toinen jäännös jaetaan kolmannella, joka saadaan jakamalla ensimmäinen jäännös toisella ja niin edelleen.
- Näin ollen jako jatkuu, kunnes jäännös on nolla. Viimeinen jakaja on suurin yhteinen jakaja.
Esimerkki 2 Etsitään lukujen 140 ja 96 suurin yhteinen jakaja:
1) 140: 96 = 1 (loput 44)
2) 96: 44 = 2 (loput 8)
3) 44: 8 = 5 (loput 4)
Viimeinen jakaja on 4, mikä tarkoittaa gcd(140, 96) = 4.
Jaksottainen jako voidaan kirjoittaa myös sarakkeeseen:
Voit löytää kolmen tai useamman annetun luvun suurimman yhteisen jakajan seuraavasti:
- Etsi ensin minkä tahansa kahden luvun suurin yhteinen jakaja useista tietojoukoista.
- Sitten löydämme löydetyn jakajan GCD:n ja jonkin kolmannen annetun luvun.
- Sitten löydämme viimeksi löydetyn jakajan GCD:n ja neljännen annetun luvun ja niin edelleen.
Esimerkki 3 Etsitään lukujen 140, 96 ja 48 suurin yhteinen jakaja. Löysimme jo edellisessä esimerkissä lukujen 140 ja 96 GCD:n (tämä on luku 4). On vielä löydettävä luvun 4 ja kolmannen annetun luvun suurin yhteinen jakaja - 48:
48 on jaollinen 4:llä ilman jäännöstä. Joten gcd(140, 96, 48) = 4.
Muistaa!
Jos luonnollinen luku on jaollinen vain 1:llä ja itsellään, sitä kutsutaan alkuluvuksi.
Mikä tahansa luonnollinen luku on aina jaollinen 1:llä ja itsellään.
Luku 2 on pienin alkuluku. Tämä on ainoa parillinen alkuluku, loput alkuluvut ovat parittomia.
Alkulukuja on monia, ja ensimmäinen niistä on luku 2. Viimeistä alkulukua ei kuitenkaan ole. "Opiskelua varten" -osiossa voit ladata alkulukutaulukon aina 997 asti.
Mutta monet luonnolliset luvut ovat tasan jaollisia muilla luonnollisilla luvuilla.
Esimerkiksi:
- luku 12 on jaollinen 1:llä, 2:lla, 3:lla, 4:llä, 6:lla, 12:lla;
- 36 on jaollinen 1:llä, 2:lla, 3:lla, 4:llä, 6:lla, 12:lla, 18:lla, 36:lla.
Lukuja, joilla luku on tasan jaollinen (12:lle nämä ovat 1, 2, 3, 4, 6 ja 12), kutsutaan luvun jakajiksi.
Muistaa!
Luonnollisen luvun a jakaja on sellainen luonnollinen luku, joka jakaa annetun luvun "a" ilman jäännöstä.
Luonnollista lukua, jossa on enemmän kuin kaksi tekijää, kutsutaan yhdistelmäluvuksi.
Huomaa, että numeroilla 12 ja 36 on yhteiset jakajat. Nämä ovat numeroita: 1, 2, 3, 4, 6, 12. Näiden lukujen suurin jakaja on 12.
Kahden annetun luvun "a" ja "b" yhteinen jakaja on luku, jolla molemmat annetut luvut "a" ja "b" jaetaan ilman jäännöstä.
Muistaa!
Suurin yhteinen jakaja(GCD) kahdesta tietystä luvusta "a" ja "b" - tämä on suurin luku, jolla molemmat luvut "a" ja "b" jaetaan ilman jäännöstä.
Lyhyesti sanottuna lukujen "a" ja "b" suurin yhteinen jakaja kirjoitetaan seuraavasti:
gcd (a; b) .
Esimerkki: gcd (12; 36) = 12 .
Ratkaisutietueen lukujen jakajat on merkitty isolla kirjaimella "D".
D(7) = (1, 7)
D(9) = (1, 9)
gcd (7; 9) = 1
Numeroilla 7 ja 9 on vain yksi yhteinen jakaja - numero 1. Tällaisia numeroita kutsutaan koprimilukuja.
Muistaa!
Koprime-luvut ovat luonnollisia lukuja, joilla on vain yksi yhteinen jakaja - luku 1. Niiden GCD on 1.
Kuinka löytää suurin yhteinen jakaja
Kahden tai useamman luonnollisen luvun gcd:n löytämiseksi tarvitset:
- hajottaa lukujen jakajat alkutekijöiksi;
Laskelmat kirjoitetaan kätevästi pystypalkilla. Kirjoita rivin vasemmalle puolelle ensin osinko, oikealle - jakaja. Edelleen vasemmassa sarakkeessa kirjoitamme ylös yksityisen arvot.
Selitetäänpä heti esimerkillä. Otetaan luvut 28 ja 64 alkutekijöiksi.
- Alleviivaa samat alkutekijät molemmissa luvuissa.
28 = 2 2 764 = 2 2 2 2 2 2
- Etsimme identtisten alkutekijöiden tulon ja kirjoitamme vastauksen muistiin;
GCD (28; 64) = 2 2 = 4Vastaus: GCD (28; 64) = 4
Voit järjestää GCD:n sijainnin kahdella tavalla: sarakkeessa (kuten yllä) tai "riville".
Nyt ja seuraavassa oletetaan, että ainakin yksi näistä luvuista on eri kuin nolla. Jos kaikki annetut luvut ovat yhtä suuria kuin nolla, niin niiden yhteinen jakaja on mikä tahansa kokonaisluku, ja koska kokonaislukuja on äärettömän monta, emme voi puhua niistä suurimmasta. Siksi ei voida puhua lukujen suurimmasta yhteisestä jakajasta, joista jokainen on yhtä suuri kuin nolla.
Nyt voimme antaa löytää suurin yhteinen jakaja kaksi numeroa.
Määritelmä.
Suurin yhteinen jakaja kahdesta kokonaisluvusta on suurin kokonaisluku, joka jakaa kaksi annettua kokonaislukua.
Lyhennettä GCD käytetään usein lyhentämään suurinta yhteistä jakajaa - Greatest Common Divisor. Myös kahden luvun a ja b suurin yhteinen jakaja on usein merkitty gcd(a, b) .
Tuodaan Greatest Common Divisor (gcd) esimerkki kaksi kokonaislukua. Lukujen 6 ja −15 suurin yhteinen jakaja on 3 . Perustellaan tämä. Kirjataan ylös kaikki luvun kuuden jakajat: ±6, ±3, ±1 ja luvun −15 jakajat ovat luvut ±15, ±5, ±3 ja ±1. Nyt löydät kaikki lukujen 6 ja −15 yhteiset jakajat, nämä ovat luvut −3, −1, 1 ja 3. Alkaen -3<−1<1<3 , то 3 – это наибольший общий делитель чисел 6 и −15 . То есть, НОД(6, −15)=3 .
Kolmen tai useamman kokonaisluvun suurimman yhteisen jakajan määritelmä on samanlainen kuin kahden luvun gcd:n määritelmä.
Määritelmä.
Suurin yhteinen jakaja kolme tai useampi kokonaisluku on suurin kokonaisluku, joka jakaa samanaikaisesti kaikki annetut luvut.
N:n kokonaisluvun suurin yhteinen jakaja a 1 , a 2 , …, a n merkitään gcd(a 1 , a 2 , …, a n) . Jos näiden lukujen suurimman yhteisen jakajan arvo b löytyy, voimme kirjoittaa GCD(a1, a2, …, an)=b.
Esimerkkinä annettuna neljän kokonaisluvun −8 , 52 , 16 ja −12 gcd, se on yhtä suuri kuin 4, eli gcd(−8, 52, 16, −12)=4 . Tämä voidaan tarkistaa kirjoittamalla muistiin annettujen lukujen kaikki jakajat, valitsemalla niistä yhteiset jakajat ja määrittämällä suurin yhteinen jakaja.
Huomaa, että kokonaislukujen suurin yhteinen jakaja voi olla yhtä suuri kuin jokin näistä luvuista. Tämä väite on totta, jos kaikki annetut luvut ovat jaollisia yhdellä niistä (todiste on tämän artikkelin seuraavassa kappaleessa). Esimerkiksi gcd(15, 60, -45)=15 . Tämä pitää paikkansa, koska 15 jakaa luvut 15 , 60 ja -45, eikä luvuilla 15, 60 ja -45 ole yhteistä jakajaa, joka olisi suurempi kuin 15 .
Erityisen kiinnostavia ovat niin sanotut suhteellisen alkuluvut, - sellaiset kokonaisluvut, joiden suurin yhteinen jakaja on yksi.
Suurimmat yhteiset jakajaominaisuudet, Euklidin algoritmi
Suurimmalla yhteisellä jakajalla on useita tunnusomaisia tuloksia, toisin sanoen useita ominaisuuksia. Listaamme nyt tärkeimmät suurimman yhteisen jakajan (gcd) ominaisuudet, muotoilemme ne lauseiden muodossa ja annamme heti todisteet.
Muotoilemme kaikki suurimman yhteisen jakajan ominaisuudet positiivisille kokonaisluvuille, kun taas otamme huomioon vain näiden lukujen positiiviset jakajat.
A:n ja b:n suurin yhteinen jakaja on yhtä suuri kuin b:n ja a:n suurin yhteinen jakaja, eli gcd(a, b)=gcd(a, b) .
Tämä GCD-ominaisuus seuraa suoraan suurimman yhteisen jakajan määritelmästä.
Jos a on jaollinen b:llä, niin a:n ja b:n yhteisten jakajien joukko on sama kuin b:n jakajien joukko, erityisesti gcd(a, b)=b .
Todiste.
Mikä tahansa lukujen a ja b yhteinen jakaja on jokaisen näiden luvun jakaja, mukaan lukien luku b. Toisaalta, koska a on b:n kerrannainen, niin mikä tahansa luvun b jakaja on myös luvun a jakaja johtuen siitä, että jaollisuudella on transitiivisuusominaisuus, joten mikä tahansa luvun b jakaja on a lukujen a ja b yhteinen jakaja. Tämä osoittaa, että jos a on jaollinen b:llä, niin lukujen a ja b jakajien joukko osuu yhteen yhden luvun b jakajien joukon kanssa. Ja koska luvun b suurin jakaja on itse luku b, niin lukujen a ja b suurin yhteinen jakaja on myös b , eli gcd(a, b)=b .
Erityisesti, jos luvut a ja b ovat yhtä suuret, niin gcd(a, b)=gcd(a, a)=gcd(b, b)=a=b. Esimerkiksi gcd(132, 132)=132 .
Todistettu suurin jakajaominaisuus antaa meille mahdollisuuden löytää kahden luvun gcd, kun toinen niistä on jaollinen toisella. Tässä tapauksessa GCD on yhtä suuri kuin yksi näistä luvuista, jolla toinen luku on jaollinen. Esimerkiksi gcd(8, 24)=8, koska 24 on kahdeksan kerrannainen.
Jos a=b q+c , missä a , b , c ja q ovat kokonaislukuja, niin lukujen a ja b yhteisten jakajien joukko osuu yhteen lukujen b ja c yhteisten jakajien joukon kanssa, erityisesti gcd( a, b) = gcd (b, c).
Perustelkaamme tämä GCD:n ominaisuus.
Koska yhtälö a=b·q+c pätee, niin mikä tahansa lukujen a ja b yhteinen jakaja jakaa myös c:n (tämä seuraa jaollisuuden ominaisuuksista). Samasta syystä jokainen b:n ja c:n yhteinen jakaja jakaa a:n. Siksi lukujen a ja b yhteisten jakajien joukko on sama kuin lukujen b ja c yhteisten jakajien joukko. Erityisesti suurimman näistä yhteisistä jakajista on myös vastattava, eli seuraavan yhtälön on oltava voimassa gcd(a, b)=gcd(b, c) .
Nyt muotoillaan ja todistetaan lause, joka on Eukleideen algoritmi. Euklides-algoritmin avulla voit löytää kahden luvun GCD:n (katso GCD:n löytäminen Euklidin algoritmilla). Lisäksi Euklidesin algoritmi antaa meille mahdollisuuden todistaa seuraavat suurimman yhteisen jakajan ominaisuudet.
Ennen lauseen lausunnon antamista suosittelemme virkistämään lauseen muistin teoriaosasta, jossa todetaan, että osinko a voidaan esittää muodossa b q + r, missä b on jakaja, q on jokin kokonaisluku, jota kutsutaan osittaisosamääräksi, ja r on kokonaisluku, joka täyttää ehdon, jota kutsutaan jäännökseksi.
Olkoon siis kahdelle nollasta poikkeavalle positiiviselle kokonaisluvulle a ja b sarja yhtäläisyyksiä totta 
päättyy kun r k+1 =0 (mikä on väistämätöntä, koska b>r 1 >r 2 >r 3 , … on sarja pieneneviä kokonaislukuja, ja tämä sarja ei voi sisältää enempää kuin äärellisen määrän positiivisia lukuja), silloin r k – on a:n ja b:n suurin yhteinen jakaja, eli r k =gcd(a, b) .
Todiste.
Osoitetaan ensin, että r k on lukujen a ja b yhteinen jakaja, minkä jälkeen osoitetaan, että r k ei ole vain jakaja, vaan lukujen a ja b suurin yhteinen jakaja.
Siirrymme kirjoitettuja yhtäläisyyksiä pitkin alhaalta ylös. Viimeisestä yhtälöstä voidaan sanoa, että r k−1 on jaollinen r k:llä. Ottaen huomioon tämä tosiasia, samoin kuin edellinen GCD-ominaisuus, toiseksi viimeinen yhtälö r k−2 =r k−1 q k +r k antaa meille mahdollisuuden väittää, että r k−2 on jaollinen r k:llä, koska r k−1 on jaollinen r k:llä ja r k on jaollinen kirjoittanut r k . Analogisesti, kolmannesta yhtälöstä alhaalta päättelemme, että r k−3 on jaollinen r k:llä. Jne. Toisesta yhtälöstä saadaan, että b on jaollinen r k:llä ja ensimmäisestä yhtälöstä, että a on jaollinen r k:llä. Siksi r k on a:n ja b:n yhteinen jakaja.
On vielä todistettava, että r k =gcd(a, b) . Sillä riittää osoittamaan, että mikä tahansa lukujen a ja b yhteinen jakaja (merkitsimme sitä r 0 :lla) jakaa r k:n.
Siirrymme alkuperäisiä tasa-arvoja pitkin ylhäältä alas. Edellisen ominaisuuden perusteella ensimmäisestä yhtälöstä seuraa, että r 1 on jaollinen r 0:lla. Sitten toisesta yhtälöstä saadaan, että r 2 on jaollinen r 0:lla. Jne. Viimeisestä yhtälöstä saadaan, että r k on jaollinen r 0:lla. Siten r k =gcd(a, b) .
Suurimman yhteisen jakajan tarkastelusta ominaisuudesta seuraa, että lukujen a ja b yhteisten jakajien joukko on sama kuin näiden lukujen suurimman yhteisen jakajan joukko. Tämä Euklidesin algoritmin seuraus mahdollistaa kaikkien kahden luvun yhteisten jakajien löytämisen näiden lukujen gcd:n jakajiksi.
Olkoot a ja b kokonaislukuja, jotka eivät ole samanaikaisesti yhtä kuin nolla, silloin on sellaisia kokonaislukuja u 0 ja v 0 , jolloin yhtälö gcd(a, b)=a u 0 +b v 0 on tosi. Viimeinen yhtälö on lineaarinen esitys lukujen a ja b suurimmasta yhteisestä jakajasta, tätä yhtälöä kutsutaan Bezout-suhteeksi ja luvut u 0 ja v 0 ovat Bezout-kertoimia.
Todiste.
Eukleideen algoritmin mukaan voidaan kirjoittaa seuraavat yhtälöt
Ensimmäisestä yhtälöstä saamme r 1 =a−b q 1 , ja merkitseen 1=s 1 ja −q 1 =t 1, tämä yhtälö saa muotoa r 1 =s 1 a+t 1 b ja luvut s 1 ja t 1 ovat kokonaislukuja. Sitten toisesta yhtälöstä saadaan r 2 =b−r 1 q 2 = b−(s 1 a+t 1 b) q 2 =−s 1 q 2 a+(1−t 1 q 2) b. Merkitään −s 1 q 2 =s 2 ja 1−t 1 q 2 =t 2, viimeinen yhtälö voidaan kirjoittaa muodossa r 2 =s 2 a+t 2 b, ja s 2 ja t 2 ovat kokonaislukuja (koska summa , erotus ja kokonaislukujen tulo on kokonaisluku). Vastaavasti kolmannesta yhtälöstä saadaan r 3 =s 3 ·a+t 3 ·b, neljännestä r 4 =s 4 ·a+t 4 ·b ja niin edelleen. Lopuksi r k =s k ·a+t k ·b , missä s k ja t k ovat kokonaislukuja. Koska r k =gcd(a, b) , ja merkitsee s k =u 0 ja t k =v 0, saadaan gcd:n lineaarinen esitys vaaditussa muodossa: gcd(a, b)=a u 0 +b v 0 .
Jos m on mikä tahansa luonnollinen luku, niin gcd(m a, m b)=m gcd(a, b).
Syy tälle suurimman yhteisen jakajan ominaisuudelle on seuraava. Jos kerromme m:llä Euklides-algoritmin jokaisen yhtälön molemmilla puolilla, saadaan, että gcd(m a, m b)=m r k ja r k on gcd(a, b) . Siten, gcd(m a, m b)=m gcd(a, b).
Tämä suurimman yhteisen jakajan ominaisuus on perusta menetelmälle GCD:n löytämiseksi alkutekijöiden jakamista käyttäen.
Olkoon p mikä tahansa lukujen a ja b yhteinen jakaja gcd(a:p, b:p)=gcd(a, b):p, erityisesti jos p=gcd(a, b) meillä on gcd(a:gcd(a, b), b:gcd(a, b))=1, eli luvut a:gcd(a, b) ja b:gcd(a, b) ovat koprime.
Koska a=p (a:p) ja b=p (b:p) , ja edellisestä ominaisuudesta johtuen, voidaan kirjoittaa muotoisia yhtäläisyyksiä gcd(a, b)=gcd(p(a:p), p(b:p))= p·gcd(a:p, b:p) , josta seuraa todistettava yhtäläisyys.
Suurin yhteinen jakaja -ominaisuus osoittautui juuri taustaksi.
Esitetään nyt GCD-ominaisuus, joka vähentää kolmen tai useamman luvun suurimman yhteisen jakajan löytämisen ongelman kahden luvun GCD:n peräkkäiseen löytämiseen.
Lukujen a 1 , a 2 , ..., a k suurin yhteinen jakaja on yhtä suuri kuin luku d k, joka löytyy GCD(a 1 , a 2)=d 2 , GCD(d 2 , a) peräkkäisestä laskennasta. 3)=d3, GCD(d3, a4)=d4, …, GCD(dk-1, ak)=dk.
Todistus perustuu Euklidesin algoritmin johtopäätökseen. Lukujen a 1 ja a 2 yhteiset jakajat ovat samat kuin d 2:n jakajat. Silloin lukujen a 1, a 2 ja a 3 yhteiset jakajat osuvat yhteen lukujen d 2 ja a 3 yhteisten jakajien kanssa, joten ne ovat yhtäpitäviä d 3:n jakajien kanssa. Lukujen a 1 , a 2 , a 3 ja a 4 yhteiset jakajat ovat samat kuin d 3:n ja a 4:n yhteiset jakajat, eli samat kuin d 4:n jakajat. Jne. Lopuksi lukujen a 1 , a 2 , …, a k yhteiset jakajat osuvat yhteen d k:n jakajien kanssa. Ja koska luvun d k suurin jakaja on itse luku d k, niin GCD(a 1 , a 2 , …, a k) = d k.
Tämä päättää suurimman yhteisen jakajan pääominaisuuksien tarkastelun.
Bibliografia.
- Vilenkin N.Ya. jne. Matematiikka. Luokka 6: oppikirja oppilaitoksille.
- Vinogradov I.M. Lukuteorian perusteet.
- Mikhelovich Sh.Kh. Numeroteoria.
- Kulikov L.Ya. ja muut Algebran ja lukuteorian tehtäväkokoelma: Oppikirja fiz.-matin opiskelijoille. pedagogisten laitosten erikoisaloja.
