Lyhyt MathCheck-ohje (uuteen välilehteen)
Tässä tehtävässä tarkastellaan kuuluisan Eukleideen algoritmin nykyversiota. Se löytää tehokkaasti kahden luonnollisen luvun suurimman yhteisen tekijän. Luonnolliset luvut ovat ℕ = {0, 1, 2, …}. Tässä tehtävässä kaikki luvut ovat luonnollisia lukuja.
Tekijän määritelmä on seuraava.
Määritelmä 1 Luonnollinen luku h on luonnollisen luvun I tekijä jos ja vain jos on olemassa sellainen luonnollinen luku i, että I = hi.
Määritelmä 2 Luonnollinen luku s on luonnollisten lukujen n ja m suurin yhteinen tekijä jos ja vain jos s on n:n ja m:n tekijä, eikä mikään suurempi luonnollinen luku ole sekä n:n että m:n tekijä.
SYT-algoritmi voidaan esittää pseudokoodina seuraavasti:
1 while m ≠ 0 do
2 k := n mod m
3 n := m
4 m := k
Koska 0 = 7 ⋅ 0 ja 0 = 123 ⋅ 0, ovat sekä 7 että 123 nollan tekijöitä. Itse asiassa jokainen luonnollinen luku on nollan tekijä, sillä 0 = h ⋅ 0 pätee jokaisella h. Siksi, jos alussa n = m = 0, niin suurinta yhteistä tekijää ei ole olemassa.
Niillä on vain rajallisesti yhteisiä tekijöitä, miksi? Mieti ensin itse, ja katso sitten opettajan selitys tästäJos n ≠ 0, niin mikään n:ää suurempi luku ei ole n:n tekijä. Samanlainen väite pätee m:lle..
Eräässä Muumipeikko-piirretyssä Muumipappa sanoi ”mamma, pidä aina käsillä kattilallinen kiehuvaa vettä”. Kun ratkaiset lukujen jaollisuutta käsitteleviä tehtäviä, pidä aina käsillä jakoyhtälö. Tällä kertaa kätevintä on, jos se on kirjoitettu siten, että jakajana on J ja jaettavana I. Etsi jakoyhtälö jostakin ja laita johonkin kätevään paikkaan. Jos hyvin käy, niin sitä ei tarvitse etsiä kovin kaukaa.
Tulemme tarvitsemaan viisi aputulosta. Todistamme ne tässä.
Mitä toisen näistä aputuloksista käyttö edellyttää? VastausB edellyttää I ≥ J. Nyt I:n paikalla on I ja J:n paikalla on J(I div J), eli on oltava I ≥ J(I div J). Miksi se pätee? VastausJakoyhtälön mukaan 0 ≤ I mod J < | J|, joten I mod J ≥ 0. Koska I mod J = I − J(I div J), saamme I − J(I div J) ≥ 0 eli I ≥ J(I div J).
Tässä osassa osoitamme, että jos alussa n ≠ 0 tai m ≠ 0 niin SYT-algoritmin vastaus on oikea. Tärkeintä ei ole lopputulos vaan päättelyn harjoitteleminen, tai ainakin päättelyn ymmärtämisen harjoitteleminen. Tapauksessa n = m = 0 suurinta yhteistä tekijää ei ole olemassa, joten jätämme sen tutkimatta.
Jotta alkuperäisten n:n ja m:n suurimmasta yhteisestä tekijästä olisi helpompi puhua, annamme sille nimeksi s. Tavoitteemme on osoittaa, että n:n lopullinen arvo on s.
SYT-algoritmi koostuu yhdestä silmukasta. Käytämme silmukoiden todistamisessa hyvin yleistä päättelytapaa, jossa on viisi vaihetta:
Tämä menettely on pätevä seuraavasta syystä. Käytämme SYT-algoritmin rivejä esimerkkinä.
Käytämme tätä menetelmää todistaaksemme, että SYT-algoritmin silmukka lopettaa ja silloin n = s.
Jokainen n:n ja m:n yhteinen tekijä on myös N:n tekijä, koska …n:n ja m:n yhteinen tekijä on m:n tekijä ja N = m.
Näistä yhteensä seuraa, että n:n ja m:n suurin yhteinen tekijä on myös N:n ja M:n yhteinen tekijä. Vielä tarvitsee osoittaa, että se on N:n ja M:n yhteisistä tekijöistä suurin. Teemme sen osoittamalla, että jokainen N:n ja M:n yhteinen tekijä on myös n:n ja m:n tekijä. Kun saamme sen tehtyä, on osoitettu, että n:n ja m:n yhteiset tekijät ovat samat kuin N:n ja M:n yhteiset tekijät, jolloin toisen parin suurin on myös toisen parin suurin.
Jokainen N:n ja M:n yhteinen tekijä on myös m:n tekijä, koska …N:n ja M:n yhteinen tekijä on N:n tekijä ja N = m.
Jokainen N:n ja M:n yhteinen tekijä on myös n:n tekijä, koska …Edellä osoitettu E antaa väitteen, koska N = m ja M = n mod m.
Tarvittiinko tietoa m ≠ 0 mihinkään? VastausKyllä. Aputulokset D ja E vaativat, että J ≠ 0. Koska J:n roolissa oli m, tarvittiin m ≠ 0.
Se tarkoittaa, että m:n arvo pienenee silmukan jokaisella kierroksella, kuitenkin pysyen vähintään nollana. Koska m:n arvo on luonnollinen luku, se voi pienentyä enintään niin monta kertaa kuin m:n arvo oli SYT-algoritmin suorituksen alussa. Silmukka lopettaa kierrettyään korkeintaan niin monta kertaa.
Eukleideen versio oli tällainen:
while m ≠ 0 do
k := maksimi(n, m)
n := minimi(n, m)
m := k − n
Siis modulo-operaatio oli korvattu sillä, että suuremmasta vähennettiin pienempi.
Miten se käyttäytyy, kun aluksi n = 49 ja m = 70?
Miten se käyttäytyy, kun aluksi n = 1000 ja m = 1? Tutkimme vain jonkin matkaa alkua.
Eukleideen versio toimii joillakin syötteillä nopeasti (kokeile vaikka m = n = 1000), mutta on olemassa loputtomasti syötteitä, joilla se toimii hitaasti (esimerkiksi aina kun n on iso ja m = 1). Moderni SYT-algoritmi ei ole millään syötteellä todella hidas. Sen nopeuden tutkiminen on oman tehtävänsä arvoinen asia.