Ero sivun ”Eukleideen algoritmi” versioiden välillä

Wikipediasta
Siirry navigaatioon Siirry hakuun
[arvioimaton versio][arvioimaton versio]
Poistettu sisältö Lisätty sisältö
Thijs!bot (keskustelu | muokkaukset)
p Botti lisäsi: no:Euklids algoritme
QWerk (keskustelu | muokkaukset)
Ei muokkausyhteenvetoa
Rivi 1: Rivi 1:
[[Eukleides|Eukleideen]] [[algoritmi]]n avulla löydetään kahden [[kokonaisluku|kokonaisluvun]] [[syt|suurin yhteinen tekijä (s.y.t.)]]. Algoritmi perustuu ns. [[jakoyhtälö]]n perättäiseen käyttöön.<br />
'''Eukleideen algoritmin''' on keino, jonka avulla voidaan selvittää kahden [[kokonaisluku|kokonaisluvun]] [[suurin yhteinen tekijä]] (syt). Algoritmi perustuu [[jakoyhtälö]]n perättäiseen käyttöön.

Eukleideen algorimi etenee seuraavasti:

*Ensin kirjoitetaan jakoyhtälö luvuilla a ja b
*Seuraavaksi kirjoitetaan jakoyhtälö luvulle b ja edellisen jakoyhtälön jakojäännökselle
*Toistetaan niin usein, että jakojäännökseksi saadaan nolla.
*Lukujen a ja b suurin yhteinen tekijä on viimeisin nollasta eroava jakojäännös



==Esimerkkejä==
==Esimerkkejä==

Versio 12. marraskuuta 2007 kello 17.08

Eukleideen algoritmin on keino, jonka avulla voidaan selvittää kahden kokonaisluvun suurin yhteinen tekijä (syt). Algoritmi perustuu jakoyhtälön perättäiseen käyttöön.

Eukleideen algorimi etenee seuraavasti:

  • Ensin kirjoitetaan jakoyhtälö luvuilla a ja b
  • Seuraavaksi kirjoitetaan jakoyhtälö luvulle b ja edellisen jakoyhtälön jakojäännökselle
  • Toistetaan niin usein, että jakojäännökseksi saadaan nolla.
  • Lukujen a ja b suurin yhteinen tekijä on viimeisin nollasta eroava jakojäännös


Esimerkkejä

Etsitään lukujen 31 ja 56 suurin yhteinen tekijä.

Ensin jaetaan 56 31:llä:
Sitten 31 25:llä: 31 = Jäsentäminen epäonnistui (MathML, sekä SVG tai PNG varalla (suositeltu nykyaikaisille selaimille ja helppokäyttötyökaluille): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/fi.wikipedia.org/v1/":): {\displaystyle 1*25+6.}
Sitten 25 6:lla: Jäsentäminen epäonnistui (MathML, sekä SVG tai PNG varalla (suositeltu nykyaikaisille selaimille ja helppokäyttötyökaluille): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/fi.wikipedia.org/v1/":): {\displaystyle 25 = 4*6+1.}
Sitten 6 1:llä: Jäsentäminen epäonnistui (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. upstream connect error or disconnect/reset before headers. reset reason: connection termination"): {\displaystyle 6=6*1+0.}

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 = 23 * 7, joten suurin yhteinen tekijä on 1.

Kiinalaiset suorittivat saman algoritmin helmitaulussa seuraavasti:

Vähennä toistuvasti pienempää suuremmasta. Kun luvut ovat samat, algoritmi päättyy ja ko. luku on suurin yhteinen tekijä.

31 31 6 6 6 6 6 ... 1
56 25 25 19 13 7 1 ... 1


Etsitään syt(15,25).

25 = 1 * 15 + 10.
15 = 1 * 10 + 5.
10 = 2 * 5 + 0.

eli syt(15,25) = 5.

Kiinalaisittain:

25 10 10 5
15 15 5 5

Algoritmi

Olkoot luvut a ja b kokonaislukuja ja b erisuuri kuin nolla. Käyttämällä toistuvasti jakoyhtälöä, saadaan:

...

.

Algoritmi päättyy, koska luvut r0, r1, ...,rn muodostavat aidosti vähenevän jonon positiivisia kokonaislukuja.

Viimeinen jakojäännös rn jakaa (tasan) luvut a ja b:

Alimmasta yhtälöstä rn jakaa luvun rn-1.
Koska , niin rn jakaa luvun rn-2
Näin jatkamalla saadaan lopulta, että rn jakaa b:n ja a:n.

Jos luvuilla a ja b on yhteinen tekijä c, ts. sanoen a ja b ovat tasan jaollisia luvulla c, c jakaa luvun r0, r1, ... yllä olevien yhtälöiden nojalla. Näin siis c jakaa luvun rn, joka on siten yhteisistä tekijöistä suurin.