Ero sivun ”Eukleideen algoritmi” versioiden välillä

p
ei muokkausyhteenvetoa
p
*Lukujen a ja b suurin yhteinen tekijä on viimeisin nollasta eroava jakojäännös
 
== Algoritmi ==
 
Olkoot luvut a ja b [[kokonaisluku]]ja ja b erisuuri kuin nolla. Käyttämällä toistuvasti jakoyhtälöä, saadaan:
 
:<math> a = q_0 b + r_0, \ 0 < r_0 < |b|</math>
:<math> b = q_1 r_0 + r_1, \ 0 < r_1 < |r_0|</math>
:<math> r_0 = q_2 r_1 + r_2, \ 0 < r_2 < |r_1|</math>
:<math> r_1 = q_3 r_2 + r_3, \ 0 < r_3 < |r_2|</math>
:<math> r_2 = q_4 r_3 + r_4, \ 0 < r_4 < |r_3|</math>
:<math> r_3 = q_5 r_4 + r_5, \ 0 < r_5 < |r_4|</math>
...
:<math> r_{n-2} = q_n r_{n-1} + r_n, \ 0 < r_n < |r_{n-1}|</math>
:<math> r_{n-1} = q_{n+1} r_n + 0 \ </math>.
 
Algoritmi päättyy, koska luvut r<sub>0</sub>, r<sub>1</sub>, ...,r<sub>n</sub> muodostavat aidosti [[vähenevä]]n [[lukujono|jonon]] [[positiivinen|positiivisia]] [[kokonaisluku]]ja.
 
Viimeinen [[jakojäännös]] r<sub>n</sub> jakaa (tasan) luvut a ja b:<p>
Alimmasta yhtälöstä r<sub>n</sub> jakaa luvun r<sub>n-1</sub>.<br />
Koska <math> r_{n-2} = q_n r_{n-1} + r_n</math>, niin r<sub>n</sub> jakaa luvun r<sub>n-2</sub><br />
Näin jatkamalla saadaan lopulta, että r<sub>n</sub> jakaa b:n ja a:n.<p>
 
Jos luvuilla a ja b on yhteinen tekijä c, ts. sanoen a ja b ovat tasan [[jaollisuus|jaollisia]] luvulla c, c jakaa luvun r<sub>0</sub>, r<sub>1</sub>, ... yllä olevien yhtälöiden nojalla. Näin siis c jakaa luvun r<sub>n</sub>, joka on siten yhteisistä tekijöistä suurin.
 
==Esimerkkejä==
</tr>
</table>
 
== Algoritmi ==
 
Olkoot luvut a ja b [[kokonaisluku]]ja ja b erisuuri kuin nolla. Käyttämällä toistuvasti jakoyhtälöä, saadaan:
 
:<math> a = q_0 b + r_0, \ 0 < r_0 < |b|</math>
:<math> b = q_1 r_0 + r_1, \ 0 < r_1 < |r_0|</math>
:<math> r_0 = q_2 r_1 + r_2, \ 0 < r_2 < |r_1|</math>
:<math> r_1 = q_3 r_2 + r_3, \ 0 < r_3 < |r_2|</math>
:<math> r_2 = q_4 r_3 + r_4, \ 0 < r_4 < |r_3|</math>
:<math> r_3 = q_5 r_4 + r_5, \ 0 < r_5 < |r_4|</math>
...
:<math> r_{n-2} = q_n r_{n-1} + r_n, \ 0 < r_n < |r_{n-1}|</math>
:<math> r_{n-1} = q_{n+1} r_n + 0 \ </math>.
 
Algoritmi päättyy, koska luvut r<sub>0</sub>, r<sub>1</sub>, ...,r<sub>n</sub> muodostavat aidosti [[vähenevä]]n [[lukujono|jonon]] [[positiivinen|positiivisia]] [[kokonaisluku]]ja.
 
Viimeinen [[jakojäännös]] r<sub>n</sub> jakaa (tasan) luvut a ja b:<p>
Alimmasta yhtälöstä r<sub>n</sub> jakaa luvun r<sub>n-1</sub>.<br />
Koska <math> r_{n-2} = q_n r_{n-1} + r_n</math>, niin r<sub>n</sub> jakaa luvun r<sub>n-2</sub><br />
Näin jatkamalla saadaan lopulta, että r<sub>n</sub> jakaa b:n ja a:n.<p>
 
Jos luvuilla a ja b on yhteinen tekijä c, ts. sanoen a ja b ovat tasan [[jaollisuus|jaollisia]] luvulla c, c jakaa luvun r<sub>0</sub>, r<sub>1</sub>, ... yllä olevien yhtälöiden nojalla. Näin siis c jakaa luvun r<sub>n</sub>, joka on siten yhteisistä tekijöistä suurin.
 
[[Luokka:Lukuteoria]]
20 551

muokkausta