Eukleideen algoritmi

Kokonaisluvun tekijät

Olkoon a positiivinen kokonaisluku. Positiivinen kokonaisluku b on luvun a tekijä, jos ja vain jos on olemassa jokin kokonaisluku c siten että a = c · b.


Esimerkki 1

a) Määritä lukujen 84 ja 66 kaikki tekijät.

b) Määritä lukujen 84 ja 66 kaikki yhteiset tekijät. Mikä on lukujen 84 ja 66 suurin yhteinen tekijä?

Ratkaisu

a) Koska

84 = 1 · 2 · 2 · 3 · 7,

niin luvun 84 tekijät ovat

1, 2, 3, 4, 6, 7, 12, 14, 21, 28 ja 84.


Koska

66 = 1 · 2 · 3 · 11,

niin luvun 66 tekijät ovat

1, 2, 3, 6, 22, 33 ja 66.


b) Lukujen 84 ja 66 yhteiset tekijät ovat 1, 2, 3 ja 6. Suurin yhteinen tekijä on luku 6.

By Photograph taken by Mark A. Wilson (Wilson44691, Department of Geology, The College of Wooster).[1] - Oma teos, Public Domain

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:

Jaollisuuden peruslause

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

a = tb + r,

missä t ja r ovat kokonaislukuja sekä 0 < r < b. Tällöin luku d on lukujen a ja b yhteinen tekijä, jos ja vain jos se on lukujen b ja r yhteinen tekijä.

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

r = α – tb = αd – tβd = d(α – βd)

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ä ba 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/rjakoyhtä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

1. Määritä lukujen suurin yhteinen tekijä ja pienin yhteinen moninkerta jakamalla luvut tekijöihin.

a) 78 ja 42

b) 495 ja 102

Vihje

Esimerkki 1

2. Määritä Eukleideen algoritmilla lukujen suurin yhteinen tekijä.

a) 31269 ja 2338

b) 95191 ja 364

Vihje

Esimerkki 2

3. Määritä Eukleideen algoritmilla lukujen 836 ja 268 pienin yhteinen moninkerta.

Vihje

Esimerkki 3

4. a) Jos murtoluku a supistuu, niin millä luvulla se supistuu?

b) Osoita, että murtoluku b ei supistu.

Vihje

Murtoluku supistuu, jos ja vain jos nimittäjän ja osoittajan suurin yhteinen tekijä on suurempi kuin luku 1.

5. Todista, että jos yhtälö ax +by = c toteutuu joillakin kokonaisluvuilla x = x₀ ja y = y₀, niin yhtälö toteutuu kaikilla ratkaisuilla

missä n∈ℤ ja d = syt(a, b). Voidaan osoittaa, että näin saadaan kaikki yhtälön ax + by = c kokonaislukuratkaisut.

Vihje

Aloita oletuksesta ja sijoita arvot x= x₀+nb/d sekä y=y₀-na/d yhtälöön ax+by=c.

6. Oppilas osti 45 sentin tikkareita ja 1,32 euron suklaapatukoita. Kassalla myyjä laski ostokset ja ilmoitti loppusummaksi 4,9 euroa. Oppilas arvasi heti loppusumman kuultuaan, että myyjälle oli sattunut laskuvirhe. Mistä oppilas saattoi päätellä tämän?

Vihje

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.

7. Määritä kolme yhtälön kokonaislukuratkaisua

a) 5x + 2y = 1

b) 12x + 16y = 4, kun 3 ≤ |x + y| ≤ 4

Vihje

Hyödynnä tehtävän 5 lausetta.

8. Olkoon n∈ℕ. Tutki mitä arvoja syt(n, n+2) voi saada?

Vihje

Seurauslause

9. Yhtiön kauppavoitto 150 mk on jaettava tasan osakkaille. Jos osakkaita olisi ollut 5 enemmän, olisi jokainen saanut 5 mk vähemmän. Montako osakasta oli yhtiössä?

YO 1874

Vihje

Muodosta yhtälöryhmä ja palaa tarvittaessa tekijöihin jakoon.

10. Kolmessa kylässä on yhteensä 43 taloa; näihin majoltetaan 360 sotamiestä siten, että ensimäisen kylän taloihin jokaiseen sijoitetaan 6, toisen kylän taloihin kuhunkin 10 ja kolmannen kylän taloihin kuhunkin 12 miestä. Ensimäisessä kylässä majailevien sotamiesten luku on yhtä paljon suurempi toisessa kylässä majailevien miesten lukua, kuin tämä jälkimäinen on kolmanteen kylään majoitettujen miesten lukua suurempi. Montako taloa kussakin kylässä on?

Vihje

Muodosta yhtälöryhmä, jossa muuttujina ovat kylien kyläkohtaiset talomäärät.

Osion perustehtävät