Sanna Ranto, LUKUTEORIA JA ALGEBRA
Versio 1, 1.11.2003 		LUKUTEORIA
 

Eukleideen algoritmi

Kahden kokonaisluvun a ja b, joista molemmat eivät ole nollia, suurin yhteinen tekijä syt(a,b) saadaan lasketuksi Eukleideen algoritmilla. Siinä sovelletaan jakoalgoritmia toistuvasti. Oletetaan nyt, että b/=0.

a = q1b + r1, 0 < r1 < |b| b = q2r1 + r2, 0 < r2 < |r1| r1 = q3r2 + r3, 0 < r3 < |r2| . . .. .. rn-2 = qnrn-1 + rn, 0 < rn < |rn-1| rn-1 = qn+1rn(+0).

Jakaminen päättyy, koska jakojäännökset muodostavat aidosti vähenevän jonon positiivisia kokonaislukuja. Osoitetaan, että viimeinen jakojäännös rn (> 0) on haettu suurin yhteinen tekijä:

rn = syt(a,b).

Koska rn | rn-1, niin viimeistä edellisen yhtälön mukaan myös rn | rn-2. Jatkamalla yhtälöketjussa ylöspäin nähdään, että rn | a ja rn | b. Jos luvuilla a ja b on yhteinen tekijä c, niin ensimmäisen yhtälön mukaan c | r1, vastaavasti toisen yhtälön mukaan c | r2. Jatkamalla näin loppuun saakka nähdään, että c | rn. Täten luku rn on lukujen a ja b yhteisistä tekijöistä suurin.

Eukleideen algoritmi antaa myös eräät sellaiset luvut u ja v, joilla rn = ua + vb. Näiden lukujen löytämiseksi käydään yhtälöketjua lävitse alhaalta ylöspäin samalla sijoittaen eliminoiden luvut rn-1, rn-2,..., r2, r1.

Linkit:
Jaollisuus ja alkuluvut
Jakoalgoritmi
Suurin yhteinen tekijä