Jakoyhtälö ja suurin yhteinen tekijä – Eukleideen algoritmi

Jakoyhtälö on perusyhtälö lukuteoriassa, joka kuvaa, miten luku voidaan jakaa toisella luvulla. Jakoyhtälön avulla voidaan löytää kahden luvun suurin yhteinen tekijä (syt) Eukleideen algoritmilla. Tämä aihe kuuluu lukion pitkän matematiikan opetussuunnitelmaan (LOPS21) ja käsitellään erityisesti kurssissa MAA11: Algoritmit ja lukuteoria. Tällä sivulla opit jakoyhtälön, suurimman yhteisen tekijän ja Eukleideen algoritmin.

Määritelmä

Jakoyhtälö: Jos ja ovat kokonaislukuja ja , niin on olemassa yksikäsitteiset kokonaisluvut (osamäärä) ja (jakojäännös), joille pätee: , missä . Suurin yhteinen tekijä on suurin positiivinen kokonaisluku, joka jakaa sekä :n että :n.

Kaavat

, missä (jakoyhtälö)

(Eukleideen algoritmin perusominaisuus)

(Eukleideen algoritmin peruslause)

(kommutatiivisuus)

kaikilla

Säännöt

Jakoyhtälö

Jos ja ovat kokonaislukuja ja , niin , missä

Eukleideen algoritmi

Suurin yhteinen tekijä

on suurin positiivinen kokonaisluku, joka jakaa sekä :n että :n

Bézoutin identiteetti

Jos , niin on olemassa kokonaisluvut ja , joille

Esimerkit

Esimerkki 1: Yksinkertainen Eukleideen algoritmi

Helppo

Löydä Eukleideen algoritmilla.

Alku: , .
Algoritmi alkaa kahdella luvulla, joille halutaan löytää suurin yhteinen tekijä.
Laske jakojäännös: , joten .
Jakoyhtälön avulla lasketaan jakojäännös: jaetaan :lla, jolloin osamäärä on ja jakojäännös on .
Aseta , .
Eukleideen algoritmin mukaan .
Laske jakojäännös: , joten .
Jatketaan algoritmia: jaetaan :lla, jolloin jakojäännös on .
Koska , niin .
Kun jakojäännös on , algoritmi päättyy ja suurin yhteinen tekijä on .

Esimerkki 2: Suuremmat luvut

Keskitaso

Löydä Eukleideen algoritmilla.

Alku: , .
Algoritmi alkaa kahdella luvulla, joille halutaan löytää suurin yhteinen tekijä.
Laske jakojäännös: , joten .
Jakoyhtälön avulla lasketaan jakojäännös: jaetaan :lla, jolloin osamäärä on ja jakojäännös on .
Aseta , .
Eukleideen algoritmin mukaan .
Laske jakojäännös: , joten .
Jatketaan algoritmia: jaetaan :llä, jolloin osamäärä on ja jakojäännös on .
Aseta , .
Eukleideen algoritmin mukaan .
Laske jakojäännös: , joten .
Jatketaan algoritmia: jaetaan :llä, jolloin jakojäännös on .
Koska , niin .
Kun jakojäännös on , algoritmi päättyy ja suurin yhteinen tekijä on .

Esimerkki 3: Alkuluvut (suurin yhteinen tekijä on 1)

Keskitaso

Löydä Eukleideen algoritmilla.

Alku: , .
Algoritmi alkaa kahdella luvulla, joille halutaan löytää suurin yhteinen tekijä.
Laske jakojäännös: , joten .
Jakoyhtälön avulla lasketaan jakojäännös: jaetaan :llä, jolloin osamäärä on ja jakojäännös on .
Aseta , .
Eukleideen algoritmin mukaan .
Laske jakojäännös: , joten .
Jatketaan algoritmia: jaetaan :lla, jolloin osamäärä on ja jakojäännös on .
Aseta , .
Eukleideen algoritmin mukaan .
Laske jakojäännös: , joten .
Jatketaan algoritmia: jaetaan :llä, jolloin osamäärä on ja jakojäännös on .
Aseta , .
Eukleideen algoritmin mukaan .
Laske jakojäännös: , joten .
Jatketaan algoritmia: jaetaan :llä, jolloin jakojäännös on .
Koska , niin .
Kun jakojäännös on , algoritmi päättyy ja suurin yhteinen tekijä on . Tämä tarkoittaa, että luvut ovat keskenään jaottomia (relatiivisesti alkulukuja).

Esimerkki 4: Jakoyhtälön kirjoittaminen

Helppo

Kirjoita jakoyhtälö luvuille ja .

Jaa luvulla : .
Jakoyhtälön avulla lasketaan osamäärä ja jakojäännös: jaetaan :lla, jolloin osamäärä on ja jakojäännös on .
Tarkista: .
Jakoyhtälön ehto täyttyy: jakojäännös on välillä .
Jakoyhtälö on: , missä (osamäärä) ja (jakojäännös).
Jakoyhtälö on muodossa , missä , , ja .

Esimerkki 5: Negatiivinen luku

Keskitaso

Löydä Eukleideen algoritmilla.

Käytä itseisarvoja: .
Suurin yhteinen tekijä on aina positiivinen, joten voidaan käyttää lukujen itseisarvoja.
Alku: , .
Algoritmi alkaa kahdella positiivisella luvulla.
Laske jakojäännös: , joten .
Jakoyhtälön avulla lasketaan jakojäännös: jaetaan :lla, jolloin osamäärä on ja jakojäännös on .
Aseta , .
Eukleideen algoritmin mukaan .
Laske jakojäännös: , joten .
Jatketaan algoritmia: jaetaan :lla, jolloin jakojäännös on .
Koska , niin .
Kun jakojäännös on , algoritmi päättyy ja suurin yhteinen tekijä on .

Esimerkki

Löydä Eukleideen algoritmilla.

Alku: , .
Laske jakojäännös: , joten .
Aseta , .
Laske jakojäännös: , joten .
Aseta , .
Laske jakojäännös: , joten .
Koska , niin .

Sovellukset

Kryptografiassa Eukleideen algoritmia käytetään RSA-salauksessa ja muissa salausmenetelmissä. Suurin yhteinen tekijä on tärkeä, kun valitaan salausavaimet.
Murtolukujen yksinkertaistamisessa suurin yhteinen tekijä auttaa supistamaan murtoluvun pienimpään muotoonsa. Esimerkiksi , koska .
Modulaariaritmetiikassa suurin yhteinen tekijä määrittää, onko kongruenssiyhtälöllä ratkaisu. Yhtälöllä on ratkaisu, jos ja vain jos jakaa :n.
Algoritmien tehokkuusanalyysissä Eukleideen algoritmi on erittäin tehokas, koska sen aikakompleksisuus on .

Yleisiä virheitä

Jakojäännöksen väärä laskeminen

Monet unohtavat, että jakojäännös on aina positiivinen ja pienempi kuin jakaja. Esimerkiksi, jos ja , jakojäännös ei ole , vaan (koska ).

Oikein: Muista, että jakojäännös täyttää aina ehdon . Jos laskeminen antaa negatiivisen jakojäännöksen, korjaa se lisäämällä jakaja.

Eukleideen algoritmin väärä toteutus

Monet unohtavat vaihtaa lukujen järjestystä algoritmissa. Eukleideen algoritmin mukaan , joten ja vaihdetaan jokaisella kierroksella.

Oikein: Varmista, että jokaisella kierroksella asetat ja (jakojäännös). Tämä on olennaista algoritmin oikealle toiminnalle.

Negatiivisten lukujen käsittely

Monet unohtavat, että suurin yhteinen tekijä on aina positiivinen. Jos toinen luvuista on negatiivinen, käytä itseisarvoja.

Oikein: Muista: . Suurin yhteinen tekijä on aina positiivinen kokonaisluku.

Algoritmin lopettamisen unohtaminen

Monet unohtavat tarkistaa, milloin algoritmi päättyy. Algoritmi päättyy, kun , jolloin vastaus on .

Oikein: Varmista aina, että algoritmi päättyy. Tarkista jokaisella kierroksella, onko . Jos on, niin vastaus on .

Usein kysyttyä

Mikä on jakoyhtälö?: Jakoyhtälö on yhtälö muodossa , missä ja ovat kokonaislukuja, , on osamäärä ja on jakojäännös, jolle pätee . Jakoyhtälö kuvaa, miten luku voidaan jakaa toisella luvulla.
Mikä on suurin yhteinen tekijä?: Suurin yhteinen tekijä on suurin positiivinen kokonaisluku, joka jakaa sekä :n että :n. Esimerkiksi , koska on suurin luku, joka jakaa sekä :n että :n.
Miten Eukleideen algoritmi toimii?: Eukleideen algoritmi perustuu siihen, että . Algoritmi toistetaan, kunnes , jolloin vastaus on . Algoritmi on erittäin tehokas, koska sen aikakompleksisuus on .
Miksi Eukleideen algoritmi päättyy?: Eukleideen algoritmi päättyy, koska jakojäännös on aina pienempi kuin , joten pienenee jokaisella kierroksella. Koska on positiivinen kokonaisluku, se saavuttaa lopulta arvon , jolloin algoritmi päättyy.
Mitä tarkoittaa, että luvut ovat keskenään jaottomia?: Luvut ja ovat keskenään jaottomia (relatiivisesti alkulukuja), jos . Tämä tarkoittaa, että luvuilla ei ole muita yhteisiä tekijöitä kuin .
Miten löydän , jos toinen luvuista on negatiivinen?: Suurin yhteinen tekijä on aina positiivinen, joten voidaan käyttää lukujen itseisarvoja: . Esimerkiksi .
Mikä on Bézoutin identiteetti?: Bézoutin identiteetti sanoo, että jos , niin on olemassa kokonaisluvut ja , joille . Tämä voidaan löytää laajennetulla Eukleideen algoritmilla.
Miten käytän Eukleideen algoritmia murtolukujen supistamiseen?: Etsi ensin suurin yhteinen tekijä osoittajalle ja nimittäjälle. Sitten jaa sekä osoittaja että nimittäjä tällä luvulla. Esimerkiksi: , joten .
Mikä on Eukleideen algoritmin aikakompleksisuus?: Eukleideen algoritmin aikakompleksisuus on , mikä tarkoittaa, että algoritmi on erittäin tehokas. Tämä johtuu siitä, että jakojäännös pienenee nopeasti jokaisella kierroksella.
Miten tarkistan, onko Eukleideen algoritmi oikein?: Tarkista, että löytämäsi suurin yhteinen tekijä todella jakaa molemmat luvut. Esimerkiksi, jos , tarkista, että jakaa sekä :n että :n. Lisäksi tarkista, että mikään suurempi luku ei jaa molempia lukuja.

Lähteet ja lisämateriaali

LOPS21: MAA11 Algoritmit ja lukuteoria
Lukion pitkän matematiikan kurssi (LOPS21), joka käsittelee jakoyhtälöä, suurinta yhteistä tekijää ja Eukleideen algoritmia. Tämä kurssi on osa lukion opetussuunnitelmaa.
Ylioppilaskokeiden tehtävät
Aiemmat ylioppilaskokeiden tehtävät ja malliratkaisut jakoyhtälöstä ja suurimmasta yhteisestä tekijästä.
TIM - Pitkän matematiikan kertauskurssi
Jyväskylän yliopiston kertauskurssi, joka sisältää harjoitustehtäviä ja teoriaa jakoyhtälöstä ja Eukleideen algoritmista.

Jakoyhtälö ja suurin yhteinen tekijä – Eukleideen algoritmi

Esimerkit

Esimerkki 1: Yksinkertainen Eukleideen algoritmi

Helppo

Löydä Eukleideen algoritmilla.

Alku: , .
Algoritmi alkaa kahdella luvulla, joille halutaan löytää suurin yhteinen tekijä.
Laske jakojäännös: , joten .
Jakoyhtälön avulla lasketaan jakojäännös: jaetaan :lla, jolloin osamäärä on ja jakojäännös on .
Aseta , .
Eukleideen algoritmin mukaan .
Laske jakojäännös: , joten .
Jatketaan algoritmia: jaetaan :lla, jolloin jakojäännös on .
Koska , niin .
Kun jakojäännös on , algoritmi päättyy ja suurin yhteinen tekijä on .

Esimerkki 2: Suuremmat luvut

Keskitaso

Löydä Eukleideen algoritmilla.

Alku: , .
Algoritmi alkaa kahdella luvulla, joille halutaan löytää suurin yhteinen tekijä.
Laske jakojäännös: , joten .
Jakoyhtälön avulla lasketaan jakojäännös: jaetaan :lla, jolloin osamäärä on ja jakojäännös on .
Aseta , .
Eukleideen algoritmin mukaan .
Laske jakojäännös: , joten .
Jatketaan algoritmia: jaetaan :llä, jolloin osamäärä on ja jakojäännös on .
Aseta , .
Eukleideen algoritmin mukaan .
Laske jakojäännös: , joten .
Jatketaan algoritmia: jaetaan :llä, jolloin jakojäännös on .
Koska , niin .
Kun jakojäännös on , algoritmi päättyy ja suurin yhteinen tekijä on .

Esimerkki 3: Alkuluvut (suurin yhteinen tekijä on 1)

Keskitaso

Löydä Eukleideen algoritmilla.

Alku: , .
Algoritmi alkaa kahdella luvulla, joille halutaan löytää suurin yhteinen tekijä.
Laske jakojäännös: , joten .
Jakoyhtälön avulla lasketaan jakojäännös: jaetaan :llä, jolloin osamäärä on ja jakojäännös on .
Aseta , .
Eukleideen algoritmin mukaan .
Laske jakojäännös: , joten .
Jatketaan algoritmia: jaetaan :lla, jolloin osamäärä on ja jakojäännös on .
Aseta , .
Eukleideen algoritmin mukaan .
Laske jakojäännös: , joten .
Jatketaan algoritmia: jaetaan :llä, jolloin osamäärä on ja jakojäännös on .
Aseta , .
Eukleideen algoritmin mukaan .
Laske jakojäännös: , joten .
Jatketaan algoritmia: jaetaan :llä, jolloin jakojäännös on .
Koska , niin .
Kun jakojäännös on , algoritmi päättyy ja suurin yhteinen tekijä on . Tämä tarkoittaa, että luvut ovat keskenään jaottomia (relatiivisesti alkulukuja).

Esimerkki 4: Jakoyhtälön kirjoittaminen

Helppo

Kirjoita jakoyhtälö luvuille ja .

Jaa luvulla : .
Jakoyhtälön avulla lasketaan osamäärä ja jakojäännös: jaetaan :lla, jolloin osamäärä on ja jakojäännös on .
Tarkista: .
Jakoyhtälön ehto täyttyy: jakojäännös on välillä .
Jakoyhtälö on: , missä (osamäärä) ja (jakojäännös).
Jakoyhtälö on muodossa , missä , , ja .

Esimerkki 5: Negatiivinen luku

Keskitaso

Löydä Eukleideen algoritmilla.

Käytä itseisarvoja: .
Suurin yhteinen tekijä on aina positiivinen, joten voidaan käyttää lukujen itseisarvoja.
Alku: , .
Algoritmi alkaa kahdella positiivisella luvulla.
Laske jakojäännös: , joten .
Jakoyhtälön avulla lasketaan jakojäännös: jaetaan :lla, jolloin osamäärä on ja jakojäännös on .
Aseta , .
Eukleideen algoritmin mukaan .
Laske jakojäännös: , joten .
Jatketaan algoritmia: jaetaan :lla, jolloin jakojäännös on .
Koska , niin .
Kun jakojäännös on , algoritmi päättyy ja suurin yhteinen tekijä on .

Sovellukset

Kryptografiassa Eukleideen algoritmia käytetään RSA-salauksessa ja muissa salausmenetelmissä. Suurin yhteinen tekijä on tärkeä, kun valitaan salausavaimet.

Murtolukujen yksinkertaistamisessa suurin yhteinen tekijä auttaa supistamaan murtoluvun pienimpään muotoonsa. Esimerkiksi , koska .

Modulaariaritmetiikassa suurin yhteinen tekijä määrittää, onko kongruenssiyhtälöllä ratkaisu. Yhtälöllä on ratkaisu, jos ja vain jos jakaa :n.

Algoritmien tehokkuusanalyysissä Eukleideen algoritmi on erittäin tehokas, koska sen aikakompleksisuus on .

Yleisiä virheitä

Jakojäännöksen väärä laskeminen

Monet unohtavat, että jakojäännös on aina positiivinen ja pienempi kuin jakaja. Esimerkiksi, jos ja , jakojäännös ei ole , vaan (koska ).

Oikein: Muista, että jakojäännös täyttää aina ehdon . Jos laskeminen antaa negatiivisen jakojäännöksen, korjaa se lisäämällä jakaja.

Eukleideen algoritmin väärä toteutus

Monet unohtavat vaihtaa lukujen järjestystä algoritmissa. Eukleideen algoritmin mukaan , joten ja vaihdetaan jokaisella kierroksella.

Oikein: Varmista, että jokaisella kierroksella asetat ja (jakojäännös). Tämä on olennaista algoritmin oikealle toiminnalle.

Negatiivisten lukujen käsittely

Monet unohtavat, että suurin yhteinen tekijä on aina positiivinen. Jos toinen luvuista on negatiivinen, käytä itseisarvoja.

Oikein: Muista: . Suurin yhteinen tekijä on aina positiivinen kokonaisluku.

Algoritmin lopettamisen unohtaminen

Monet unohtavat tarkistaa, milloin algoritmi päättyy. Algoritmi päättyy, kun , jolloin vastaus on .

Oikein: Varmista aina, että algoritmi päättyy. Tarkista jokaisella kierroksella, onko . Jos on, niin vastaus on .

Usein kysyttyä

Mikä on jakoyhtälö?

Jakoyhtälö on yhtälö muodossa , missä ja ovat kokonaislukuja, , on osamäärä ja on jakojäännös, jolle pätee . Jakoyhtälö kuvaa, miten luku voidaan jakaa toisella luvulla.

Mikä on suurin yhteinen tekijä?

Suurin yhteinen tekijä on suurin positiivinen kokonaisluku, joka jakaa sekä :n että :n. Esimerkiksi , koska on suurin luku, joka jakaa sekä :n että :n.

Miten Eukleideen algoritmi toimii?

Eukleideen algoritmi perustuu siihen, että . Algoritmi toistetaan, kunnes , jolloin vastaus on . Algoritmi on erittäin tehokas, koska sen aikakompleksisuus on .

Miksi Eukleideen algoritmi päättyy?

Eukleideen algoritmi päättyy, koska jakojäännös on aina pienempi kuin , joten pienenee jokaisella kierroksella. Koska on positiivinen kokonaisluku, se saavuttaa lopulta arvon , jolloin algoritmi päättyy.

Mitä tarkoittaa, että luvut ovat keskenään jaottomia?

Luvut ja ovat keskenään jaottomia (relatiivisesti alkulukuja), jos . Tämä tarkoittaa, että luvuilla ei ole muita yhteisiä tekijöitä kuin .

Miten löydän , jos toinen luvuista on negatiivinen?

Suurin yhteinen tekijä on aina positiivinen, joten voidaan käyttää lukujen itseisarvoja: . Esimerkiksi .

Mikä on Bézoutin identiteetti?

Bézoutin identiteetti sanoo, että jos , niin on olemassa kokonaisluvut ja , joille . Tämä voidaan löytää laajennetulla Eukleideen algoritmilla.

Miten käytän Eukleideen algoritmia murtolukujen supistamiseen?

Etsi ensin suurin yhteinen tekijä osoittajalle ja nimittäjälle. Sitten jaa sekä osoittaja että nimittäjä tällä luvulla. Esimerkiksi: , joten .

Mikä on Eukleideen algoritmin aikakompleksisuus?

Eukleideen algoritmin aikakompleksisuus on , mikä tarkoittaa, että algoritmi on erittäin tehokas. Tämä johtuu siitä, että jakojäännös pienenee nopeasti jokaisella kierroksella.

Miten tarkistan, onko Eukleideen algoritmi oikein?

Tarkista, että löytämäsi suurin yhteinen tekijä todella jakaa molemmat luvut. Esimerkiksi, jos , tarkista, että jakaa sekä :n että :n. Lisäksi tarkista, että mikään suurempi luku ei jaa molempia lukuja.

Lähteet ja lisämateriaali

LOPS21: MAA11 Algoritmit ja lukuteoria

Lukion pitkän matematiikan kurssi (LOPS21), joka käsittelee jakoyhtälöä, suurinta yhteistä tekijää ja Eukleideen algoritmia. Tämä kurssi on osa lukion opetussuunnitelmaa.

Ylioppilaskokeiden tehtävät

Aiemmat ylioppilaskokeiden tehtävät ja malliratkaisut jakoyhtälöstä ja suurimmasta yhteisestä tekijästä.

TIM - Pitkän matematiikan kertauskurssi

Jyväskylän yliopiston kertauskurssi, joka sisältää harjoitustehtäviä ja teoriaa jakoyhtälöstä ja Eukleideen algoritmista.