Ero sivun ”Eukleideen algoritmi” versioiden välillä
| [arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
pEi muokkausyhteenvetoa |
|||
Rivi 8:
*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ä==
Rivi 74 ⟶ 96:
</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]]
| |||