Eukleideen algoritmi

Suurin yhteinen tekijä

Olkoon a ja b positiivisia kokonaislukuja. Lukujen a ja b yhteisistä tekijöistä suurinta lukua d kutsutaan lukujen a ja b suurimmaksi yhteiseksi tekijäksi. Suurinta yhteistä tekijää merkitään

syt(a, b) = d.

Esimerkin 1 tapauksessa merkitään syt(84, 66)=6.

Lukujen a ja b suurin yhteinen tekijä on jaollinen jokaisella lukujen a ja b yhteisellä tekijällä.

Esimerkin 1 tapauksessa

syt(84, 66) = 6 = 1 · 2 · 3.

Luvun 6 tekijät ovat 1, 2, 3 ja 6 eli samat luvut kuin lukujen 84 ja 66 yhteiset tekijät.

Kahden luvun suurinta yhteistä tekijää voidaan etsiä tekijöitä luettelemalla kun tarkastelemme suhteellisen pieniä lukuja. Tämä menettelytapa käy kuitenkin hyvin työlääksi suurten lukujen kohdalla, jolloin on mielekästä hyödyntää niin kutsuttua Eukleideen algoritmia. Yksinkertaisen algoritmin kahden luvun suurimman yhteisen tekijän määrittämiseksi esitti aikoinaan kreikkalainen matemaatikko Eukleides (n. 300 eaa.) teoksessaan Stoikheia (suom. Alkeet). Eukleideen algoritmi perustuu seuraavaan lauseeseen:

Todistus

Todistetaan väite molempiin suuntiin.

→

Oletetaan, että luku d on lukujen a ja b yhteinen tekijä. Tällöin luvut a ja b ovat muotoa a = αd ja b = βd, missä α, β ∈ ℕ. Todistetaan, että luku d on myös lukujen b ja r yhteinen tekijä.

Koska

niin luku d on myös lukujen b ja r yhteinen tekijä.

←

Oletetaan, että luku d on lukujen b ja r yhteinen tekijä. Tällöin luvut b ja r ovat muotoa b = αd ja r = βd, missä α, β ∈ ℤ. Todistetaan, että luku d on myös lukujen a ja b yhteinen tekijä.

Koska

niin luku d on myös lukujen a ja b yhteinen tekijä.

Jaollisuuden peruslauseesta seuraa:

Seurauslause

Olkoon a ja b positiivisia kokonaislukuja. Oletetaan, että b∤a eli

a = tb + r,

missä t ja r ovat kokonaislukuja sekä 0 < r < b. Tällöin syt(a, b) = syt(b, r).

Todistus

Jaollisuuden peruslauseen nojalla lukujen a ja b yhteiset tekijät ovat samat kuin lukujen b ja r yhteiset tekijät. Tästä seuraa, että lukujen a ja b suurin yhteinen tekijä on sama kuin lukujen b ja r suurin yhteinen tekijä.

Eukleideen algoritmi

Sovelletaan algoritmia positiivisten kokonaislukujen a ja b tapauksessa, missä a ≥ b.

(1) Esitetään jakolasku a/b jakoyhtälönä

missä 0 ≤ r₁ < b. Jos jakojäännös r₁ = 0, niin b|a ja syt(a, b) = b. Jos r₁ ≠ 0, niin siirrytään seuraavaan askeleeseen.

(2) Esitetään b/r₁ jakoyhtälönä

missä 0 ≤ r₂ < r₁. Jos jakojäännös r₂ = 0, niin r₁|b ja syt(a, b) = r₁. Jos r₂ ≠ 0, niin siirrytään seuraavaan askeleeseen.

(3) Esitetään b/r₁ jakoyhtälönä

missä 0 ≤ r₃ < r₂. Jos jakojäännös r₃ = 0, niin r₂|b ja syt(a, b) = r₂. Jos r₃ ≠ 0, niin siirrytään seuraavaan askeleeseen.

...

Algoritmia jatkamalla päädytään lopulta jakolaskuun, joka menee tasan. Viimeinen nollasta eroava jakojäännös on lukujen a ja b suurin yhteinen tekijä. Koska algoritmissa esiintyy laskeva kokonaislukujen jono b>r₁>r₂>...>rₙ≥0, niin algoritmin suorittamiseen tarvitaan enintään b askelta.

Esimerkki 2

Määritä lukujen 8745439 ja 859 suurin yhteinen tekijä

Ratkaisu

Suoritetaan Eukleideen algoritmi luvuilla 8745439 ja 859.

Saadaan syt(8745439, 859) = 1.

Pienin yhteinen moninkerta

Olkoon a ja b positiivisia kokonaislukuja. Lukujen a ja b pienin yhteinen moninkerta/pienin yhteinen jaettava on pienin mahdollinen kokonaisluku, joka on jaollinen molemmilla luvuilla a ja b. Pienintä yhteistä moninkertaa merkitään pym(a, b) tai pyj(a, b).

Pienimmälle yhteiselle monikerralle pätee seuraava kaava:

Kaavan todistus perustuu lukujen alkulukuhajotelmiin, johon tutustutaan seuraavassa kappaleessa. Todistus sivuutetaan toistaiseksi.

Esimerkki 3

Määritä lukujen 7293 ja 1386 pienin yhteinen moninkerta.

Ratkaisu

Määritetään ensin syt(7293, 1386) Eukleideen algoritmilla:

Saadaan syt(7293, 1386) = 33. Pienimmän yhteisen moninkerran kaavalla saadaan

Diofantoksen yhtälöt

Diofantoksen yhtälöksi kutsutaan muotoa

ax + by = c,

olevia yhtälöitä, missä muuttujat x, y ∈ ℤ, vakiot a, b, c ∈ ℤ sekä vähintään toinen luvuista a ja b on nollasta poikkeava. Diofantoksen yhtölöllä voi olla monia tai ei yhtään ratkaisua.

Esimerkki 4

Onko olemassa sellaiset x, y ∈ ℤ,että

a) 11x + 7y = 1

b) 11x + 7y = 5

c) 8x + 2y = 3

Ratkaisu

a) Huomataan, että 11·2 + 7·(-3) = 22 – 21 = 1. Siispä yhtälöllä 11x + 7y = 1 on ratkaisu x = 2 ja y = -3.

b) Hyödynnetään a-kohdan havaintoa 11·2 + 7·(-3) = 22 – 21 = 1 ja saadaan

Siispä yhtälöllä 11x + 7y = 5 on ratkaisu x = 10 ja y = -15.

c) Koska 8x + 2y = 2(4x + y) on parillinen, niin se ei voi saada arvoksi lukua 3.

Ei ratkaisua.

Jos Diofantoksen yhtälössä c = syt(a, b), niin on olemassa sellaiset x, y ∈ ℤ, että ax + by = c.

Todistus saadaan kulkemalla Eukleideen algoritmi lopusta alkuun.

Esimerkki 5

Palataan esimerkin 3 tapaukseen, jossa määritettiin syt(7293, 1386) Eukleideen algoritmilla:

ja saatiin syt(7293, 1386) = 33.

Ratkaistaan jakoyhtälöistä nyt jakojäännökset:

Kuljetaan Eukleideen algoritmia lopusta alkuun. Aloitetaan viimeisestä jakojäännöksestä eli luvun syt(7293, 1386) = 33 esityksestä ja sijoitetaan aina edellisen rivin jakojäännöksen lauseke seuraavaksi tulevan rivin lausekkeeseen seuraavasti:

Täten

syt(7293, 1386) = 7293x + 1386y, kun x = -19 ja y = 100.

Diofantoksen yhtälöllä

ax + by = c,

on ratkaisu, jos ja vain jos luku c on on jaollinen lukujen a ja b suurimmalla yhteisellä tekijällä eli syt(a, b)|c.

Todistetaan väite molempiin suuntiin.

→

Oletetaan, että yhtälöllä

ax + by = c,

on ratkaisu eli yhtälö on tosi joillakin x, y ∈ ℤ. Todistetaan, että syt(a, b)|c.

Merkitään d = syt(a, b). Luvut a ja b voidaan ilmaista niiden suurimman yhteisen moninkerran avulla muodossa a = αd ja b = βd, misssä α, β ∈ ℤ.

Tällöin

eli luku c = d(αx+βd) on luvun d moninkertana jaollinen luvulla d.

←

Oletetaan, että syt(a, b)|c. Todistetaan että yhtälöllä

ax + by = c,

on jokin ratkaisu x, y ∈ ℤ.

Merkitään yhä d = syt(a, b). Luku c voidaan ilmaista suurimman yhteisen tekijän avulla muodossa c = φd, missä φ ∈ ℤ.

Kuten aikaisemmin todettiin: jos Diofantoksen yhtälössä d = syt(a, b), niin on olemassa sellaiset x₁, y₁ ∈ ℤ, että ax₁ + by₁ = d.

Täten

Siispä yhtälöllä ax + by = c on ratkaisu arvoilla x = φx₁ ja y = φy₁.​

Erityisesti, jos yhtälö ax + by = c toteutuu joillakin kokonaisluvuilla x = x₀ ja y = y₀, niin yhtälön kaikki ratkaisut saadaan kaavoista

missä n ∈ ℤ ja d = syt(a, b).

Todistaminen jätetään harjoitustehtäväksi (tehtävä 5).

Ratkeavalla Diofantoksen yhtälöllä on siis äärettömän monta ratkaisua. Kertoimet x ja y saattavat saada myös negatiivisia arvoja.

Jokainen kokonaisluku voidaan ilmaista lukujen Diofantoksen yhtälönä muodossa ax + by, jos ja vain jos syt(a, b) = 1.

Harjoituksia