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ä b∤a 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
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
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.