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ä