Ero sivun ”Eukleideen algoritmi” versioiden välillä

79 merkkiä poistettu ,  13 vuotta sitten
 
==Esimerkkejä==
Määritetään lukujen 112 ja 408 suurin yhteinen tekijä eli syt(112, 408).
 
EtsitäänMääritetään lukujen 31 ja 56 suurin yhteinen tekijä.<p> Eukleideen algoritmin avulla:
:<math>408=112\times\,3+72</math>
 
Ensin jaetaan 56 31:llä: <math>56 112= 72\times\,1*31+25.40</math> <br />
Sitten 31 25:llä: 31 = <math>72=40\times\,1*25+6.32</math> <br />
Sitten 25 6:lla: <math>25 40= 4*632\times\,1+1.8</math> <br />
Sitten 6 1:llä: <math>6 32= 6*18\times\,4+0.</math> <br />
Lukujen 112 ja 408 suurin yhteinen tekijä on siis kahdeksan eli syt(112, 408)=8.
<p>
Viimeinen nollasta eroava on lukujen 31 ja 56 suurin yhteinen tekijä eli syt(31,56)=(31,56)=1. Tämä nähdään myös lukujen alkutekijähajotelmien avulla selvästi: 31 on alkuluku ja 56 = 2<sup>3</sup> * 7, joten suurin yhteinen tekijä on 1.<p>
 
=== Kiinalaisten käyttämä algoritmi ===
Kiinalaiset suorittivat saman algoritmin [[helmitaulu]]ssa seuraavasti:<p>
 
20 551

muokkausta