Ero sivun ”Eukleideen algoritmi” versioiden välillä
[arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
p Botti lisäsi: ro:Algoritmul lui Euclid |
p <p> on tarpeeton |
||
Rivi 24:
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:
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.
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.
Rivi 43 ⟶ 44:
=== Kiinalaisten käyttämä algoritmi ===
Kiinalaiset suorittivat saman algoritmin [[helmitaulu]]ssa seuraavasti:
Vähennä toistuvasti pienempää suuremmasta. Kun luvut ovat samat, algoritmi päättyy ja ko. luku on suurin yhteinen tekijä.
<table border=1 width="40%">
Rivi 73 ⟶ 74:
Etsitään syt(15,25).
25 = 1 * 15 + 10.<br />
15 = 1 * 10 + 5.<br />
10 = 2 * 5 + 0.
eli syt(15,25) = 5.
Kiinalaisittain:
<table border=1 width="20%">
|