Ero sivun ”Eukleideen algoritmi” versioiden välillä

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