CINXE.COM

<!DOCTYPE html> <html class="client-nojs" lang="fi" dir="ltr"> <head> <meta charset="UTF-8"> <title>Eukleideen algoritmi – Wikipedia</title> <script>(function(){var className="client-js";var cookie=document.cookie.match(/(?:^|; )fiwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":[",\t."," \t,"],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"fi normal","wgMonthNames":["","tammikuu","helmikuu","maaliskuu","huhtikuu","toukokuu","kesäkuu","heinäkuu","elokuu","syyskuu","lokakuu","marraskuu","joulukuu"],"wgRequestId":"8b619cfd-560f-4ffd-a4e8-f33c3a2ace97","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Eukleideen_algoritmi","wgTitle":"Eukleideen algoritmi","wgCurRevisionId":22774615,"wgRevisionId":22774615,"wgArticleId":14171,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName": null,"wgUserGroups":["*"],"wgCategories":["Sivut, joiden viitemallineissa on virheitä","Julkaisija-parametri puuttuu","Sivut, joissa on virheellinen ISBN-tunniste","Sivut, jotka käyttävät ISBN-taikalinkkejä","Käännetyt artikkelit","Seulonnan keskeiset artikkelit","Lukuteoria","Algoritmit"],"wgPageViewLanguage":"fi","wgPageContentLanguage":"fi","wgPageContentModel":"wikitext","wgRelevantPageName":"Eukleideen_algoritmi","wgRelevantArticleId":14171,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":true,"wgFlaggedRevsParams":{"tags":{"accuracy":{"levels":3}}},"wgStableRevisionId":22774615,"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"fi","pageLanguageDir":"ltr","pageVariantFallbacks":"fi"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":true,"nearby":true}, "wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":20000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":true,"wgVector2022LanguageInHeader":false,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q230848","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.gadget.hidePersonalSandboxEdits":"ready","ext.gadget.fiwiki_flaggedrevs_css_rcfix":"ready","ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.styles.legacy":"ready", "ext.flaggedRevs.basic":"ready","mediawiki.codex.messagebox.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","codex-search-styles":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","site","mediawiki.page.ready","mediawiki.toc","skins.vector.legacy.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.flaggedRevs.advanced","ext.gadget.publicarttablesort","ext.gadget.ViikonKilpailu","ext.gadget.WikiLovesMonunmets","ext.gadget.ProtectionIndicator","ext.gadget.frwiki_infobox_v3","ext.gadget.linkeddata","ext.gadget.perustiedotwikidatassa","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.compactlinks","ext.uls.interface", "ext.cx.eventlogging.campaigns","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","oojs-ui.styles.icons-media","oojs-ui-core.icons","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=fi&modules=codex-search-styles%7Cext.cite.styles%7Cext.flaggedRevs.basic%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cmediawiki.codex.messagebox.styles%7Cskins.vector.styles.legacy%7Cwikibase.client.init&only=styles&skin=vector"> <script async="" src="/w/load.php?lang=fi&modules=startup&only=scripts&raw=1&skin=vector"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=fi&modules=ext.gadget.fiwiki_flaggedrevs_css_rcfix%2ChidePersonalSandboxEdits&only=styles&skin=vector"> <link rel="stylesheet" href="/w/load.php?lang=fi&modules=site.styles&only=styles&skin=vector"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Eukleideen algoritmi – Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//fi.m.wikipedia.org/wiki/Eukleideen_algoritmi"> <link rel="alternate" type="application/x-wiki" title="Muokkaa" href="/w/index.php?title=Eukleideen_algoritmi&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (fi)"> <link rel="EditURI" type="application/rsd+xml" href="//fi.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://fi.wikipedia.org/wiki/Eukleideen_algoritmi"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.fi"> <link rel="alternate" type="application/atom+xml" title="Wikipedia-Atom-syöte" href="/w/index.php?title=Toiminnot:Tuoreet_muutokset&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin-vector-legacy mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Eukleideen_algoritmi rootpage-Eukleideen_algoritmi skin-vector action-view"><div id="mw-page-base" class="noprint"></div> <div id="mw-head-base" class="noprint"></div> <div id="content" class="mw-body" role="main"> <a id="top"></a> <div id="siteNotice"></div> <div class="mw-indicators"> </div> <h1 id="firstHeading" class="firstHeading mw-first-heading">Eukleideen algoritmi</h1> <div id="bodyContent" class="vector-body"> <div id="siteSub" class="noprint">Wikipediasta</div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="contentSub2"></div> <div id="jump-to-nav"></div> <a class="mw-jump-link" href="#mw-head">Siirry navigaatioon</a> <a class="mw-jump-link" href="#searchInput">Siirry hakuun</a> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="fi" dir="ltr">Eukleideen algoritmi on <a href="/wiki/Eukleides" title="Eukleides">Eukleideen</a> mukaan nimetty menetelmä, jonka avulla voidaan selvittää kahden <a href="/wiki/Kokonaisluku" title="Kokonaisluku">kokonaisluvun</a> <a href="/wiki/Suurin_yhteinen_tekij%C3%A4" title="Suurin yhteinen tekijä">suurin yhteinen tekijä</a> (syt). Algoritmi perustuu <a href="/wiki/Jakoyht%C3%A4l%C3%B6" title="Jakoyhtälö">jakoyhtälön</a> perättäiseen käyttöön.<a href="#cite_note-m1-1">[1]</a> Eukleideen algoritmi etenee seuraavasti: <ul><li>Ensin kirjoitetaan jakoyhtälö luvuilla a ja b</li> <li>Seuraavaksi kirjoitetaan jakoyhtälö luvulle b ja edellisen jakoyhtälön <a href="/wiki/Jakoj%C3%A4%C3%A4nn%C3%B6s" title="Jakojäännös">jakojäännökselle</a></li> <li>Aiempi jakojäännös jaetaan uudella jakojäännöksellä</li> <li>Toistetaan niin usein, että jakojäännökseksi saadaan nolla.</li> <li>Lukujen a ja b suurin yhteinen tekijä on viimeisin nollasta eroava jakojäännös</li></ul> <div id="toc" class="toc" role="navigation" aria-labelledby="mw-toc-heading"><input type="checkbox" role="button" id="toctogglecheckbox" class="toctogglecheckbox" style="display:none" /><div class="toctitle" lang="fi" dir="ltr"><h2 id="mw-toc-heading">Sisällys</h2><label class="toctogglelabel" for="toctogglecheckbox"></label></div> <ul> <li class="toclevel-1 tocsection-1"><a href="#Esimerkkejä">1 Esimerkkejä</a> <ul> <li class="toclevel-2 tocsection-2"><a href="#Suoritus_peräkkäisten_jakokulmien_avulla">1.1 Suoritus peräkkäisten jakokulmien avulla</a></li> <li class="toclevel-2 tocsection-3"><a href="#Yleinen_tapaus">1.2 Yleinen tapaus</a></li> </ul> </li> <li class="toclevel-1 tocsection-4"><a href="#Kiinalaisten_käyttämä_algoritmi">2 Kiinalaisten käyttämä algoritmi</a></li> <li class="toclevel-1 tocsection-5"><a href="#Todistus">3 Todistus</a></li> <li class="toclevel-1 tocsection-6"><a href="#Sovelluksia">4 Sovelluksia</a></li> <li class="toclevel-1 tocsection-7"><a href="#Historia">5 Historia</a></li> <li class="toclevel-1 tocsection-8"><a href="#Lähteet">6 Lähteet</a></li> <li class="toclevel-1 tocsection-9"><a href="#Kirjallisuutta">7 Kirjallisuutta</a></li> <li class="toclevel-1 tocsection-10"><a href="#Aiheesta_muualla">8 Aiheesta muualla</a></li> </ul> </div> <div class="mw-heading mw-heading2"><h2 id="Esimerkkejä">Esimerkkejä</h2>[<a href="/w/index.php?title=Eukleideen_algoritmi&veaction=edit&section=1" title="Muokkaa osiota Esimerkkejä" class="mw-editsection-visualeditor">muokkaa</a> | <a href="/w/index.php?title=Eukleideen_algoritmi&action=edit&section=1" title="Muokkaa osion lähdekoodia: Esimerkkejä">muokkaa wikitekstiä</a>]</div> Alla kaksi esimerkkiä. 1. Määritetään lukujen 48 ja 18 suurin yhteinen tekijä eli syt(48,18). Toisin sanoen a = 48 ja b = 18 a : b = 2 kokonaista ja jakojäännös on 12 (48:18 on 2 kokonaista ja 12 on <a href="/wiki/Jakoj%C3%A4%C3%A4nn%C3%B6s" title="Jakojäännös">jakojäännös</a>) b : 12 = 1 kokonainen ja jakojäännös on 6 12 : 6 = 2 ja jakojäännös on 0. Suurin yhteinen tekijä luvuilla 48 ja 18 on siis 6 eli viimeinen luku, jolla esimerkissä jaettiin. 2. Määritetään lukujen 112 ja 408 suurin yhteinen tekijä eli syt(112, 408). Määritetään lukujen suurin yhteinen tekijä Eukleideen algoritmin avulla: <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 408=112\cdot \,3+72}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>408</mn> <mo>=</mo> <mn>112</mn> <mo>⋅</mo> <mspace width="thinmathspace" /> <mn>3</mn> <mo>+</mo> <mn>72</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 408=112\cdot \,3+72}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/30061133923701cd2162ea3d06cc5a4cb155b0e6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:18.467ex; height:2.343ex;" alt="{\displaystyle 408=112\cdot \,3+72}"></dd> <dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 112=72\cdot \,1+40}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>112</mn> <mo>=</mo> <mn>72</mn> <mo>⋅</mo> <mspace width="thinmathspace" /> <mn>1</mn> <mo>+</mo> <mn>40</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 112=72\cdot \,1+40}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/14c2c92dd8d28d6ab4688680e806d028d5f7dc5b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:17.305ex; height:2.343ex;" alt="{\displaystyle 112=72\cdot \,1+40}"></dd> <dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 72=40\cdot \,1+32}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>72</mn> <mo>=</mo> <mn>40</mn> <mo>⋅</mo> <mspace width="thinmathspace" /> <mn>1</mn> <mo>+</mo> <mn>32</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 72=40\cdot \,1+32}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6574b82090c898cacba506b6050e1df50c145937" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:16.142ex; height:2.343ex;" alt="{\displaystyle 72=40\cdot \,1+32}"></dd> <dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 40=32\cdot \,1+8}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>40</mn> <mo>=</mo> <mn>32</mn> <mo>⋅</mo> <mspace width="thinmathspace" /> <mn>1</mn> <mo>+</mo> <mn>8</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 40=32\cdot \,1+8}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f9711f41cd8a7b63bd28fafe36f47f9c591a6739" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:14.98ex; height:2.343ex;" alt="{\displaystyle 40=32\cdot \,1+8}"></dd> <dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 32=8\cdot \,4+0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>32</mn> <mo>=</mo> <mn>8</mn> <mo>⋅</mo> <mspace width="thinmathspace" /> <mn>4</mn> <mo>+</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 32=8\cdot \,4+0}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f05b06ccb64543af0ef16a9cba3e7736a4a38140" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:13.817ex; height:2.343ex;" alt="{\displaystyle 32=8\cdot \,4+0}"></dd></dl> Lukujen 112 ja 408 suurin yhteinen tekijä on siis kahdeksan eli syt(112, 408)=8. <div class="mw-heading mw-heading3"><h3 id="Suoritus_peräkkäisten_jakokulmien_avulla">Suoritus peräkkäisten jakokulmien avulla</h3>[<a href="/w/index.php?title=Eukleideen_algoritmi&veaction=edit&section=2" title="Muokkaa osiota Suoritus peräkkäisten jakokulmien avulla" class="mw-editsection-visualeditor">muokkaa</a> | <a href="/w/index.php?title=Eukleideen_algoritmi&action=edit&section=2" title="Muokkaa osion lähdekoodia: Suoritus peräkkäisten jakokulmien avulla">muokkaa wikitekstiä</a>]</div> Edellä johdetut laskutoimitukset voidaan kynällä ja paperilla laskettaessa suorittaa myös peräkkäisten <a href="/wiki/Jakokulma" title="Jakokulma">jakokulmien</a> avulla seuraavalla tavalla: <pre> 48|18 -36| 2 18| 12 -12| 1 12| 6 -12| 2 0 </pre> <pre> 408|112 -336| 3 112| 72 -72| 1 72| 40 -40| 1 40| 32 -32| 1 32| 8 -32| 4 0 </pre> Tässä käytetyt ja toisiinsa yhdistetyt jakokulmat ovat ns. <a href="/wiki/Jakokulma#muita_merkintätapoja" title="Jakokulma">italialaisia jakokulmia</a>, joissa jaettava, jakaja ja osamäärä sijoitetaan seuraavasti: <pre> jaettava | jakaja | osamäärä. </pre> Ensimmäisessä jakolaskussa on suurempi alkuperäisistä luvuista jaettavana, pienempi jakajana. Kussakin jakokulmassa on ylävasemmalla jaettava ja yläoikealla jakaja. Osamäärän kokonaisosa merkitään alaoikealle, kun taas alavasemmalla suoritetaan vähennyslasku, josta saadaan jakojäännös. Kun jakolasku on suoritettu, jaetaan edellisen jakolaskun jakaja saadulla jakojäännöksellä, mikä suoritetaan merkitsemällä se jakojäännöksen vasemmalle puolelle ja suorittamalla jakolasku tavalliseen tapaan. Näin jatketaan, kunnes jakojäännös on nolla, jolloin viimeinen sitä edeltänyt jakaja (tässä esimerkissä 8) on alkuperäisten lukujen suurin yhteinen tekijä. <div class="mw-heading mw-heading3"><h3 id="Yleinen_tapaus">Yleinen tapaus</h3>[<a href="/w/index.php?title=Eukleideen_algoritmi&veaction=edit&section=3" title="Muokkaa osiota Yleinen tapaus" class="mw-editsection-visualeditor">muokkaa</a> | <a href="/w/index.php?title=Eukleideen_algoritmi&action=edit&section=3" title="Muokkaa osion lähdekoodia: Yleinen tapaus">muokkaa wikitekstiä</a>]</div> Olkoot luvut a ja b <a href="/wiki/Kokonaisluku" title="Kokonaisluku">kokonaislukuja</a> ja b erisuuri kuin nolla. Käyttämällä toistuvasti jakoyhtälöä saadaan: <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a=q_{0}b+r_{0},\ 0<r_{0}<|b|}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mo>=</mo> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mi>b</mi> <mo>+</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>,</mo> <mtext> </mtext> <mn>0</mn> <mo><</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo><</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a=q_{0}b+r_{0},\ 0<r_{0}<|b|}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ebc3966bbf02b7f41f2f44a8779e3408321b5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.728ex; height:2.843ex;" alt="{\displaystyle a=q_{0}b+r_{0},\ 0<r_{0}<|b|}"></dd> <dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b=q_{1}r_{0}+r_{1},\ 0<r_{1}<|r_{0}|}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>b</mi> <mo>=</mo> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <mtext> </mtext> <mn>0</mn> <mo><</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo><</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b=q_{1}r_{0}+r_{1},\ 0<r_{1}<|r_{0}|}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fe7fb54b3aab7a07963b0169579f6f201f1c0a2d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.707ex; height:2.843ex;" alt="{\displaystyle b=q_{1}r_{0}+r_{1},\ 0<r_{1}<|r_{0}|}"></dd> <dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{0}=q_{2}r_{1}+r_{2},\ 0<r_{2}<|r_{1}|}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mtext> </mtext> <mn>0</mn> <mo><</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo><</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r_{0}=q_{2}r_{1}+r_{2},\ 0<r_{2}<|r_{1}|}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b7eb196ef3fd3e5194babb3f5003d90505bba1d7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.812ex; height:2.843ex;" alt="{\displaystyle r_{0}=q_{2}r_{1}+r_{2},\ 0<r_{2}<|r_{1}|}"></dd> <dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{1}=q_{3}r_{2}+r_{3},\ 0<r_{3}<|r_{2}|}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>,</mo> <mtext> </mtext> <mn>0</mn> <mo><</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo><</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r_{1}=q_{3}r_{2}+r_{3},\ 0<r_{3}<|r_{2}|}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/597f25e807d5fffae0909ccb627a1a2c9c7cbcbc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.812ex; height:2.843ex;" alt="{\displaystyle r_{1}=q_{3}r_{2}+r_{3},\ 0<r_{3}<|r_{2}|}"></dd> <dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{2}=q_{4}r_{3}+r_{4},\ 0<r_{4}<|r_{3}|}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo>,</mo> <mtext> </mtext> <mn>0</mn> <mo><</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo><</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r_{2}=q_{4}r_{3}+r_{4},\ 0<r_{4}<|r_{3}|}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aea0602e8d54970dc0cd3d26251bd57126085d24" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.812ex; height:2.843ex;" alt="{\displaystyle r_{2}=q_{4}r_{3}+r_{4},\ 0<r_{4}<|r_{3}|}"></dd> <dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{3}=q_{5}r_{4}+r_{5},\ 0<r_{5}<|r_{4}|}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>5</mn> </mrow> </msub> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>5</mn> </mrow> </msub> <mo>,</mo> <mtext> </mtext> <mn>0</mn> <mo><</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>5</mn> </mrow> </msub> <mo><</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>4</mn> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r_{3}=q_{5}r_{4}+r_{5},\ 0<r_{5}<|r_{4}|}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9f8ce9c9106f97fb8b8f5a380e6a46e3b45a1665" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.812ex; height:2.843ex;" alt="{\displaystyle r_{3}=q_{5}r_{4}+r_{5},\ 0<r_{5}<|r_{4}|}"></dd></dl> ... <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{n-2}=q_{n}r_{n-1}+r_{n},\ 0<r_{n}<|r_{n-1}|}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>2</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>,</mo> <mtext> </mtext> <mn>0</mn> <mo><</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo><</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r_{n-2}=q_{n}r_{n-1}+r_{n},\ 0<r_{n}<|r_{n-1}|}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f56d51808d92705636d31acf116cb233e8cb0065" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:36.099ex; height:2.843ex;" alt="{\displaystyle r_{n-2}=q_{n}r_{n-1}+r_{n},\ 0<r_{n}<|r_{n-1}|}"></dd> <dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{n-1}=q_{n+1}r_{n}+0\ }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>+</mo> <mn>0</mn> <mtext> </mtext> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r_{n-1}=q_{n+1}r_{n}+0\ }</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/93502f497d606c4ce330a1c3d6887049efbfe7a8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.673ex; height:2.509ex;" alt="{\displaystyle r_{n-1}=q_{n+1}r_{n}+0\ }">.</dd></dl> Algoritmi päättyy, koska luvut r0, r1, ...,rn muodostavat aidosti <a href="/w/index.php?title=V%C3%A4henev%C3%A4&action=edit&redlink=1" class="new" title="Vähenevä (sivua ei ole)">vähenevän</a> <a href="/wiki/Lukujono" title="Lukujono">jonon</a> <a href="/w/index.php?title=Positiivinen&action=edit&redlink=1" class="new" title="Positiivinen (sivua ei ole)">positiivisia</a> <a href="/wiki/Kokonaisluku" title="Kokonaisluku">kokonaislukuja</a>. Viimeinen <a href="/wiki/Jakoj%C3%A4%C3%A4nn%C3%B6s" title="Jakojäännös">jakojäännös</a> rn jakaa (tasan) luvut a ja b: Alimmasta yhtälöstä rn jakaa luvun rn-1. Koska <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{n-2}=q_{n}r_{n-1}+r_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>2</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r_{n-2}=q_{n}r_{n-1}+r_{n}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bcb0f95c9136e0e150ba8dc59df0f48254a17991" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:19.197ex; height:2.343ex;" alt="{\displaystyle r_{n-2}=q_{n}r_{n-1}+r_{n}}">, 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 <a href="/wiki/Jaollisuus" title="Jaollisuus">jaollisia</a> 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. <div class="mw-heading mw-heading2"><h2 id="Kiinalaisten_käyttämä_algoritmi">Kiinalaisten käyttämä algoritmi</h2>[<a href="/w/index.php?title=Eukleideen_algoritmi&veaction=edit&section=4" title="Muokkaa osiota Kiinalaisten käyttämä algoritmi" class="mw-editsection-visualeditor">muokkaa</a> | <a href="/w/index.php?title=Eukleideen_algoritmi&action=edit&section=4" title="Muokkaa osion lähdekoodia: Kiinalaisten käyttämä algoritmi">muokkaa wikitekstiä</a>]</div> <a href="/wiki/Kiina" title="Kiina">Kiinalaiset</a> suorittivat saman algoritmin <a href="/wiki/Helmitaulu" title="Helmitaulu">helmitaulussa</a> seuraavasti: Vähennä toistuvasti pienempi luku suuremmasta. Kun luvut ovat keskenään yhtä suuret, algoritmi päättyy ja kyseinen luku on suurin yhteinen tekijä. Esimerkki etsitään syt(15,25). 25 = 1 * 15 + 10. 15 = 1 * 10 + 5. 10 = 2 * 5 + 0. eli syt(15,25) = 5. "Kiinalaisittain": <table border="1" width="200"> <tbody><tr align="right"> <td>25</td> <td>10</td> <td>10</td> <td>5 </td></tr> <tr align="right"> <td>15</td> <td>15</td> <td>5</td> <td>5 </td></tr></tbody></table> <div class="mw-heading mw-heading2"><h2 id="Todistus">Todistus</h2>[<a href="/w/index.php?title=Eukleideen_algoritmi&veaction=edit&section=5" title="Muokkaa osiota Todistus" class="mw-editsection-visualeditor">muokkaa</a> | <a href="/w/index.php?title=Eukleideen_algoritmi&action=edit&section=5" title="Muokkaa osion lähdekoodia: Todistus">muokkaa wikitekstiä</a>]</div> Että Eukleideen algoritmi antaa tuloksena lukujen suurimman yhteisen tekijän, voidaan osoittaa kaksivaiheisella todistuksella.<a href="#cite_note-2">[2]</a> Ensin osoitetaan, että viimeinen nollasta poikkeava jakojäännös rN−1 on sekä a:n että b:n tekijä eli sekä a että b ovat sillä jaollisia. Koska se on niiden yhteinen tekijä, on se on joko pienempi tai yhtä suuri kuin niiden suurin yhteinen tekijä g, toisin sanoen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{N-1}\leq g}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>N</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>≤</mo> <mi>g</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r_{N-1}\leq g}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5b1965fadcda313bb77d04056bbd7b4cc305a91b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.055ex; height:2.343ex;" alt="{\displaystyle r_{N-1}\leq g}"> Toisessa vaiheessa osoitetaan, että rN−1 on jaollinen jokaisella a:n ja b:n yhteisellä tekijällä, siis myös niiden suurimmalla yhteisellä tekijällä g, mistä seuraa, että <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{N-1}\geq g}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>N</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>≥</mo> <mi>g</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r_{N-1}\geq g}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/055c6a7fd26a9ce0f944e559c2ce456679756092" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.055ex; height:2.343ex;" alt="{\displaystyle r_{N-1}\geq g}">. Näistä kahdesta epäyhtälöstä seuraa, että <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{N-1}=g}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>N</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mi>g</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r_{N-1}=g}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ffa9b533e92f9fef4efb6b59b9de298e0f80abbe" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.055ex; height:2.009ex;" alt="{\displaystyle r_{N-1}=g}"> Ensimmäisessä vaiheessa siis osoitetaan, että sekä a että b ovat jaollisia luvulla rN−1. Edellinen jakojäännös rN−2 on jaollinen rN−1:llä, <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{N-2}=q_{n}r_{N-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>N</mi> <mo>−</mo> <mn>2</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>N</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r_{N-2}=q_{n}r_{N-1}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/77c7a62d08bd907e92bb5bdc083d46a676d6895d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.035ex; height:2.009ex;" alt="{\displaystyle r_{N-2}=q_{n}r_{N-1}}"></dd></dl> koska viimeinen jakojäännös rN on nolla. Myös sitä edeltävä jakojäännös rN−3 on jaollinen rN−1:llä <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{N-3}=q_{N-1}r_{N-2}+r_{N-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>N</mi> <mo>−</mo> <mn>3</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>N</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>N</mi> <mo>−</mo> <mn>2</mn> </mrow> </msub> <mo>+</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>N</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r_{N-3}=q_{N-1}r_{N-2}+r_{N-1}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/badf1091e4891cbcdda834dbe27beda8093728d5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:25.29ex; height:2.343ex;" alt="{\displaystyle r_{N-3}=q_{N-1}r_{N-2}+r_{N-1}}"></dd></dl> koska molemmat yhtälön oikealla puolella olevat termit ovat sillä jaollisia. Samaa päättelyä toistamalla todetaan, että kaikki edeltävät jakojäännökset sekä lopulta myös alkuperäiset luvut a ja b oat jaollisia luvulla rN−1. Mikään aikaisemmista jakojäännöksistä, rN−2, rN−3 jne. ei ole a:n ja b:n tekijä, koska jäljelle jäi jakojäännös. Koska rNrN−1 on a:n ja b:n yhteinen tekijä, on rN−1 ≤ g. Toisessa vaiheessa osoitetaan, että jokainen <a href="/wiki/Luonnolliset_luvut" class="mw-redirect" title="Luonnolliset luvut">luonnollinen luku</a> c, jolla sekä a että b ovat jaollisia (toisin sanoen jokainen a:n ja b:n yhteinen tekijä) on myös rk:n tekijä (eli rk on jaollinen c:llä). Määritelmän mukaan a ja b voidaan esittää c:n monikertoina: a = mc and b = nc, missä m and n ovat luonnollisia lukuja. Näin ollen ensimmäinen jakojäännös, r0, on jaollinen c:llä, koska r0 = a − q0b = mc − q0nc = (m − q0n)c. Vastaavalla tavalla osoittautuu, että c on myös jaollinen kaikilla myöhemmillä jakojäännöksillä r1, r2, jne. Siksi suurimman yhteisen tekijän g on oltava myös rN−1:n tekijä, mistä seuraa, että g ≤ rN−1. Koska todistuksen ensimmäisessä vaiheessa osoitettiin, että kääntäen (rN−1 ≤ g), seuraa tästä, että g = rN−1. Näin ollen g on lukujen a ja b sekä samalla kaikkien ketjussa peräkkäisten lukujen suurin yhteinen tekijä:<a href="#cite_note-Lovasz_2003-3">[3]</a> <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g={\text{syt}}(a,b)={\text{syt}}(b,r_{0})={\text{syt}}(r_{0},r_{1})={\text{syt}}(R_{N-2},R_{N-1})=r_{N-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>g</mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext>syt</mtext> </mrow> <mo stretchy="false">(</mo> <mi>a</mi> <mo>,</mo> <mi>b</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext>syt</mtext> </mrow> <mo stretchy="false">(</mo> <mi>b</mi> <mo>,</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext>syt</mtext> </mrow> <mo stretchy="false">(</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mtext>syt</mtext> </mrow> <mo stretchy="false">(</mo> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>N</mi> <mo>−</mo> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>N</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>N</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g={\text{syt}}(a,b)={\text{syt}}(b,r_{0})={\text{syt}}(r_{0},r_{1})={\text{syt}}(R_{N-2},R_{N-1})=r_{N-1}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/19e31c5aa81f6b25e05777a1e3a7744d5cccc244" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:65.661ex; height:2.843ex;" alt="{\displaystyle g={\text{syt}}(a,b)={\text{syt}}(b,r_{0})={\text{syt}}(r_{0},r_{1})={\text{syt}}(R_{N-2},R_{N-1})=r_{N-1}}">.</dd></dl> <div class="mw-heading mw-heading2"><h2 id="Sovelluksia">Sovelluksia</h2>[<a href="/w/index.php?title=Eukleideen_algoritmi&veaction=edit&section=6" title="Muokkaa osiota Sovelluksia" class="mw-editsection-visualeditor">muokkaa</a> | <a href="/w/index.php?title=Eukleideen_algoritmi&action=edit&section=6" title="Muokkaa osion lähdekoodia: Sovelluksia">muokkaa wikitekstiä</a>]</div> Eukleideen algoritmilla on monia teoreettisia ja käytännöllisiä sovelluksia. Ensinnäkin sen avulla voidaan <a href="/w/index.php?title=Sievent%C3%A4minen&action=edit&redlink=1" class="new" title="Sieventäminen (sivua ei ole)">sieventää</a> <a href="/wiki/Murtoluku" title="Murtoluku">murtolukuja</a>, sillä osoittajan ja nimittäjän suurin yhteinen tekijä on suurin luku, jolla murtoluku voidaan <a href="/wiki/Supistaminen" title="Supistaminen">supistaa</a>. Sen avulla voidaan myös suorittaa jakolaskuja <a href="/wiki/Modulaariaritmetiikka" class="mw-redirect" title="Modulaariaritmetiikka">modulaariaritmetiikassa</a>. Tähän algoritmiin perustuvat laskutoimitukset muodostavat myös osan <a href="/wiki/Salausprotokolla" title="Salausprotokolla">salausprotollista</a>, joiden avulla varmistetaan Internet-yhteyksien turvallisuus, mutta myös keinoissa, joilla tämä salaus puretaan jakamalla suuret luvut alkutekijöihin. Eukleideen algoritmilla voidaan myös ratkaista <a href="/wiki/Diofantoksen_yht%C3%A4l%C3%B6" title="Diofantoksen yhtälö">Diofantoksen yhtälöitä</a>, esimerkiksi sellaisten lukujen etsimiseksi, jotka <a href="/wiki/Kiinalainen_j%C3%A4%C3%A4nn%C3%B6slause" title="Kiinalainen jäännöslause">kiinalaisen jäännöslauseen</a> mukaisesti toteuttavat moninkertaisia <a href="/wiki/Kongruenssi_(lukuteoria)" title="Kongruenssi (lukuteoria)">kongruensseja</a>. Sitä käytetään myös <a href="/wiki/Ketjumurtoluku" title="Ketjumurtoluku">ketjumurtolukujen</a> konstruointiin sekä rationaalisten likiarvojen määrittämiseksi reaaliluvuilla. Sen avulla voidaan myös todistaa monia <a href="/wiki/Lukuteoria" title="Lukuteoria">lukuteorian</a> keskeisiä tuloksia, esimerkiksi <a href="/wiki/Lagrangen_nelj%C3%A4n_neli%C3%B6n_lause" title="Lagrangen neljän neliön lause">Lagrangen neljän neliön lause</a> sekä <a href="/wiki/Aritmetiikan_peruslause" title="Aritmetiikan peruslause">aritmetiikan peruslause</a>, jonka mukaan jokainen yhtä suurempi kokonaisluku voidaan yhdellä ja vain yhdellä esittää <a href="/wiki/Alkuluku" title="Alkuluku">alkulukujen</a> tulona. <div class="mw-heading mw-heading2"><h2 id="Historia">Historia</h2>[<a href="/w/index.php?title=Eukleideen_algoritmi&veaction=edit&section=7" title="Muokkaa osiota Historia" class="mw-editsection-visualeditor">muokkaa</a> | <a href="/w/index.php?title=Eukleideen_algoritmi&action=edit&section=7" title="Muokkaa osion lähdekoodia: Historia">muokkaa wikitekstiä</a>]</div> <div class="noprint noviewer" style="background-color: var( --background-color-neutral-subtle, #f8f9fa ); color: var( --color-emphasized, #101418 ); font-size: 90%; padding-left: 1em; padding-right: 1em; padding-top: 0.2em; padding-bottom: 0.5em; margin-top: 1em; margin-bottom: 0.5em; border: 1px solid var( --border-color-subtle, #c8ccd1 ); clear: both;"><figure class="mw-halign-left" typeof="mw:File"><a href="/wiki/Tiedosto:Translation_Latin_Alphabet.svg" class="mw-file-description" title="Käännös suomeksi"><img alt="Käännös suomeksi" src="//upload.wikimedia.org/wikipedia/commons/thumb/2/2a/Translation_Latin_Alphabet.svg/60px-Translation_Latin_Alphabet.svg.png" decoding="async" width="60" height="19" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/2/2a/Translation_Latin_Alphabet.svg/90px-Translation_Latin_Alphabet.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/2/2a/Translation_Latin_Alphabet.svg/120px-Translation_Latin_Alphabet.svg.png 2x" data-file-width="475" data-file-height="150" /></a><figcaption>Käännös suomeksi</figcaption></figure> <div style="text-align: center; font-style:italic;">Tämä artikkeli tai sen osa on käännetty tai siihen on haettu tietoja muunkielisen Wikipedian artikkelista. Alkuperäinen artikkeli: <a href="https://en.wikipedia.org/wiki/Euclidean_algorithm" class="extiw" title="en:Euclidean algorithm">en:Euclidean algorithm</a> </div></div> <figure class="mw-default-size mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/Tiedosto:Euclid%27s_algorithm_Book_VII_Proposition_2_3.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/9/96/Euclid%27s_algorithm_Book_VII_Proposition_2_3.svg/300px-Euclid%27s_algorithm_Book_VII_Proposition_2_3.svg.png" decoding="async" width="300" height="408" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/9/96/Euclid%27s_algorithm_Book_VII_Proposition_2_3.svg/450px-Euclid%27s_algorithm_Book_VII_Proposition_2_3.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/9/96/Euclid%27s_algorithm_Book_VII_Proposition_2_3.svg/600px-Euclid%27s_algorithm_Book_VII_Proposition_2_3.svg.png 2x" data-file-width="1098" data-file-height="1495" /></a><figcaption>Eukleideen menetelmä kahden janan, BA ja DC, pituuksien suurimman yhteisen tekijän määrittämiseksi, kun molempien pituudet ovat saman "yksikköjanan" pituuden monikertoja. Kun DC on lyhempi, sitä käytetään BA:n "mittaamiseen", mutta vain kerran, koska jäljelle jäävä osa EA on lyhyempi kuin DC. EA mittaa nyt kahteen kertaan pienemmän alkuperäisistä janoista DC, jolloin jäljelle jäävä osa FC on pienempi kuin EA. Tämän jälkeen EA mittaa (kolmeen kertaan) pituuden EA. Koska jako nyt menee tasan, voidaan lopettaa tähän ja todeta, että suurin yhteinen tekijä on FC. Oikealla <a href="/wiki/Nikomakhos" class="mw-disambig" title="Nikomakhos">Nikomakhoksen</a> esimerkki luvuilla 49 ja 21, joiden suurimmaksi yhteiseksi tekijäksi osoittautuu 7.</figcaption></figure> Eukleideen algoritmi on yksi vanhimmista yhä käytössä olevista algoritmeista.<a href="#cite_note-Knuth-4">[4]</a> Se esitellään Eukleideen Alkeet -teoksen 10. kirjassa lauseena 2<a href="#cite_note-5">[5]</a> sekä eri pituisia janoja koskevana <a href="/wiki/Geometria" title="Geometria">geometrisena</a> lauseena myös 10. kirjassa lauseena 3.<a href="#cite_note-6">[6]</a> Jälkimmäinen todistus osoittaa, miten kahden janan ollessa yhteismitalliset löydetään jana, jonka pituus sisältyy tasan kummankin janan pituuteen. Todennäköisesti Eukleides ei itse keksinyt algoritmia, vaan se tunnettiin jo ennen hänen aikaansa.<a href="#cite_note-Weil_1983-7">[7]</a><a href="#cite_note-Jones_1994-8">[8]</a> Matemaatikko ja historioitsija <a href="/w/index.php?title=Bartel_Leendert_van_der_Waerden&action=edit&redlink=1" class="new" title="Bartel Leendert van der Waerden (sivua ei ole)">B. L. van der Waerden</a> arvelee, että Eukleideen 7. kirja on alkujaan ollut <a href="/wiki/Pythagoras" title="Pythagoras">Pythagoraan</a> koulukunnassa käytetty <a href="/wiki/Lukuteoria" title="Lukuteoria">lukuteoriaa</a> käsittelevä oppikirja.<a href="#cite_note-van_der_Waerden_1954-9">[9]</a> Todennäköisesti algoritmin tunsi ainakin jo <a href="/wiki/Eudoksos" title="Eudoksos">Eudoksos Knidolainen</a> noin vuonna 375 eKr, mutta mahdollisesti se oli tunnettu jo ennen häntäkin,<a href="#cite_note-10">[10]</a> mihin viittaa se seikka, että Eukleides ja <a href="/wiki/Aristoteles" title="Aristoteles">Aristoteles</a> käyttivät teknistä termiä ἀνθυφαίρεσις (anthyphairesis, "käänteinen vähennyslasku".<a href="#cite_note-11">[11]</a> Satoja vuosia myöhemmin Eukleideen algoritmi keksittiin kreikkalaisista riippumatta sekä <a href="/wiki/Intia" title="Intia">Intiassa</a> että <a href="/wiki/Kiina" title="Kiina">Kiinassa</a>,<a href="#cite_note-Stillwell,_p._31-12">[12]</a> joissa sitä käytettiin lähinnä tähtitieteessä ja tarkkojen kalenterien laskennassa tarvittavien <a href="/wiki/Diofantoksen_yht%C3%A4l%C3%B6" title="Diofantoksen yhtälö">Diofantoksen yhtälöiden</a> ratkaisemisessa. Intialainen matemaatikko ja tähtitieteilijä <a href="/wiki/Aryabhata" title="Aryabhata">Aryabhata</a> 400-luvun lopulla nimitti erästä algoritmin yleistystä "pulverisoijaksi" (Kuttaka)<a href="#cite_note-13">[13]</a>, luultavasti sen vuoksi, koska se tarjosi niin tehokkaan keinon yhtälöiden ratkaisemiseksi.<a href="#cite_note-14">[14]</a> Vaikka jo <a href="/w/index.php?title=Sun_Zu&action=edit&redlink=1" class="new" title="Sun Zu (sivua ei ole)">Sun Zu</a> kolmannella vuosisadalla esitti erään erikoistapauksen <a href="/wiki/Kiinalainen_j%C3%A4%C3%A4nn%C3%B6slause" title="Kiinalainen jäännöslause">kiinalaisesta jäännöslauseesta</a><a href="#cite_note-15">[15]</a>, yleisen ratkaisun esitti <a href="/w/index.php?title=Qin_Jiushao&action=edit&redlink=1" class="new" title="Qin Jiushao (sivua ei ole)">Qin Jiushao</a> vuonna 1247 teoksessaan Shushu Jiuzhang (數書九章 Yhdeksänosainen matemaattinen tutkielma)<a href="#cite_note-16">[16]</a> Euroopassa Eukleideen algoritmin esitteli ensimmäisenä numeerisesti ja teki yleisesti tunnetuksi <a href="/w/index.php?title=Claude_Gaspard_Bachet_de_M%C3%A9ziriac&action=edit&redlink=1" class="new" title="Claude Gaspard Bachet de Méziriac (sivua ei ole)">Bachet'n</a> teoksen Problèmes plaisants et délectables (Hauskoja ja huvittavia probleemoja) toinen painos vuodelta 1624.<a href="#cite_note-17">[17]</a> Euroopassakin sitä käytettiin Diofantoksen yhälöiden ratkaisemiseen sekä myös <a href="/wiki/Ketjumurtoluku" title="Ketjumurtoluku">ketjumurtolukujen</a> kehittämiseen. <a href="/w/index.php?title=Yleistetty_Eukleideen_algoritmi&action=edit&redlink=1" class="new" title="Yleistetty Eukleideen algoritmi (sivua ei ole)">Yleistetyn Eukleideen algoritmin</a> julkaisi englantilainen matemaatikko <a href="/w/index.php?title=Nicholas_Saunderson&action=edit&redlink=1" class="new" title="Nicholas Saunderson (sivua ei ole)">Nicholas Saunderson</a><a href="#cite_note-18">[18]</a> joka väitti <a href="/wiki/Roger_Cotes" title="Roger Cotes">Roger Cotesin</a> jo aikaisemmin kehittäneen sen menetelmäksi ketjumurtolukujen tehokkaaseen käsittelyyn.<a href="#cite_note-19">[19]</a> 1800-luvulla Eukleideen algoritmi johti uusien lukualueiden kuten <a href="/wiki/Gaussin_kokonaisluku" title="Gaussin kokonaisluku">Gaussin kokonaislukujen</a> ja <a href="/wiki/Eisensteinin_kokonaisluku" title="Eisensteinin kokonaisluku">Eisensteinin kokonaislukujen</a> keksimi]]seen. Vuonna 1815 <a href="/wiki/Carl_Friedrich_Gauss" title="Carl Friedrich Gauss">Carl Friedrich Gauss</a> osoitti Eukleideen algoritmin avulla, että Gaussin kokonaisluvut voidaan yksikäsitteisellä tavalla jakaa alkutekijöihin, joskin todistus julkaistiin vasta vuonna 1832.<a href="#cite_note-20">[20]</a> Gauss mainitsi algoritmin jo vuonna 1801 julkaisemassaan teoksessa Disquisitiones Arithmeticae, mutta vain <a href="/wiki/Ketjumurtoluku" title="Ketjumurtoluku">ketjumurtolukujen</a> käsittelyyn liittyvänä keinona.<a href="#cite_note-Stillwell,_p._31-12">[12]</a> <a href="/wiki/Peter_Gustav_Dirichlet" class="mw-redirect" title="Peter Gustav Dirichlet">Peter Dirichlet</a> näyttää olleen ensimmäinen, joka osoitti Eukleideen algoritmin merkityksen perustana suurelle osalle lukuteoriaa.<a href="#cite_note-Stillwell,_p._31-12">[12]</a> Hän osoitti, että monet lukuteorian tulokset, kuten yksikäsitteinen alkutekijöihin jako, pätevät jokaisessa lukualueessa, johon Eukleideen algoritmia voidaan soveltaa.<a href="#cite_note-21">[21]</a> Hänen lukuteoriaa käsittelevää tutkielmaansa muokkasi ja laajensi <a href="/wiki/Richard_Dedekind" title="Richard Dedekind">Richard Dedekind</a>, joka tutki Eukleideen algoritmin avulla uutta yleistä lukualuetta, <a href="/wiki/Algebrallinen_kokonaisluku" title="Algebrallinen kokonaisluku">algebrallisia kokonaislukuja</a>. Dedekind muun muassa todisti ensimmäisenä <a href="/w/index.php?title=Fermat%27n_kahden_neli%C3%B6n_lause&action=edit&redlink=1" class="new" title="Fermat'n kahden neliön lause (sivua ei ole)">Fermat'n kahden neliön lauseen</a>, jonka pariton alkuluku p voidaan esittää kahden kokonaisluvun neliöiden summana, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p=x^{2}+y^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <mo>=</mo> <msup> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>+</mo> <msup> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p=x^{2}+y^{2}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fe433e9ba9c42efe1bc9fd51bb439c698b8f6843" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:11.796ex; height:3.009ex;" alt="{\displaystyle p=x^{2}+y^{2}}">, <a href="/wiki/Jos_ja_vain_jos" title="Jos ja vain jos">jos ja vain jos</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p\equiv 1{\pmod {4}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> <mo>≡</mo> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mspace width="1em" /> <mo stretchy="false">(</mo> <mi>mod</mi> <mspace width="0.333em" /> <mn>4</mn> <mo stretchy="false">)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p\equiv 1{\pmod {4}}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/125d70c2c8848e96954eddfc7f9283ec4f676ed7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:16.366ex; height:2.843ex;" alt="{\displaystyle p\equiv 1{\pmod {4}}}">. Dedekind määritteli myös <a href="/w/index.php?title=Euklidinen_alue&action=edit&redlink=1" class="new" title="Euklidinen alue (sivua ei ole)">euklidisen alueen</a> käsitteen. Sillä tarkoitetaan lukualuetta, jossa yleistetty versio Eukleideen algoritmista voidaan määritellä. 1800-luvun lopuolla Eukleideen algoritmi kuitenkin jäi vähitellen Dedekindin yleisemmän <a href="/wiki/Ideaali_(rengasteoria)" title="Ideaali (rengasteoria)">ideaalien</a> teorian varjoon.<a href="#cite_note-Stillwell,_p._31-12">[12]</a> 1800-luvulla Eukleideen algoritmille keksittiin muitakin sovelluksia. Vuonna 1829 <a href="/wiki/Jacques_Charles_Fran%C3%A7ois_Sturm" title="Jacques Charles François Sturm">Charles Sturm</a> osoitti sen käyttökelpoisuuden määritettäessä <a href="/w/index.php?title=Sturmin_lause&action=edit&redlink=1" class="new" title="Sturmin lause (sivua ei ole)">Sturmin ketjun</a> avulla annetun polynomin niiden tietyllä välillä olevia nollakohtia.<a href="#cite_note-22">[22]</a> Eukleideen algoritmi on vanhin tunnettu keino, jonka avulla yhteismitallisille reaaliluvuille voidaan löytää kokonaislukusuhteita. Nykyaikana on keksitty muitakin kokonaislukujen suhteisiin perustuvia algoritmeja kuten <a href="/w/index.php?title=Helaman_Ferguson&action=edit&redlink=1" class="new" title="Helaman Ferguson (sivua ei ole)">Helaman Fergusonin</a> ja R.W. Forcaden algoritmi (1979)<a href="#cite_note-23">[23]</a> ja <a href="/w/index.php?title=Lenstran%E2%80%93Lenstran%E2%80%93Lov%C3%A1szin_algoritmi&action=edit&redlink=1" class="new" title="Lenstran–Lenstran–Lovászin algoritmi (sivua ei ole)">Lenstran–Lenstran–Lovászin algoritmi</a> (LLL-algoritmi)<a href="#cite_note-24">[24]</a><a href="#cite_note-25">[25]</a> Vuonna 1969 Cole ja Davie kehittivät Eukleideen algoritmiin perustuvan kahden henkilön pelin nimeltä ääThe Game of Euclid In 1969, Cole and Davie developed a two-player game based on the Euclidean algorithm, called The Game of Euclid,<a href="#cite_note-26">[26]</a> which has an optimal strategy.<a href="#cite_note-27">[27]</a> Pelin alussa kummallakin pelaajalla on kasa kiviä, toisella a ja toisella b kappaletta. Sitten pelaajat vuorotellen poistavat suuremmasta kasasta m kertaa pienemmässä kasassa olevien kivien lukumäärän. Jos siis pinoissa jollakin hetkellä on x ja y kiveä ja x on suurempi kuin y, vuorossa oleva pelaaja poistaa suuremmasta kasasta my kiveä, jolloinisen kasan tyhjennetyksi kokonaan.<a href="#cite_note-28">[28]</a> <a href="/wiki/Donald_Knuth" title="Donald Knuth">Donald Knuth</a> on nimittänyt Eukleideen algoritmia "kaikkien algoritmien isoisäksi", koska se on vanhin ei-triviaali algoritmi, joka on pysynyt käytössä nykyaikaan saakka.<a href="#cite_note-Knuth-4">[4]</a> <div class="mw-heading mw-heading2"><h2 id="Lähteet">Lähteet</h2>[<a href="/w/index.php?title=Eukleideen_algoritmi&veaction=edit&section=8" title="Muokkaa osiota Lähteet" class="mw-editsection-visualeditor">muokkaa</a> | <a href="/w/index.php?title=Eukleideen_algoritmi&action=edit&section=8" title="Muokkaa osion lähdekoodia: Lähteet">muokkaa wikitekstiä</a>]</div> <div id="viitteet-malline" class="viitteet-malline" style="list-style-type:decimal;"><ol class="references"> <li id="cite_note-m1-1"><a href="#cite_ref-m1_1-0">↑</a> Thompson, Jan & Martinsson, Thomas: Matematiikan käsikirja, s. 92. Helsinki: Tammi, 1994. <a href="/wiki/Toiminnot:Kirjal%C3%A4hteet/951-31-0471-0" title="Toiminnot:Kirjalähteet/951-31-0471-0">ISBN 951-31-0471-0</a> </li> <li id="cite_note-2"><a href="#cite_ref-2">↑</a> H. Stark: An Introduction to Number Theory, s. 16–20. MIT Press, 1978. <a href="/wiki/Toiminnot:Kirjal%C3%A4hteet/0-262-69060-8" title="Toiminnot:Kirjalähteet/0-262-69060-8">ISBN 0-262-69060-8</a> </li> <li id="cite_note-Lovasz_2003-3"><a href="#cite_ref-Lovasz_2003_3-0">↑</a> László Lovász: Discrete Mathematics: Elementary and Beyond, s. 100–101. New York: Springer-Verlag, 2003. <a href="/wiki/Toiminnot:Kirjal%C3%A4hteet/0-387-95584-4" title="Toiminnot:Kirjalähteet/0-387-95584-4">ISBN 0-387-95584-4</a> </li> <li id="cite_note-Knuth-4">↑ <a href="#cite_ref-Knuth_4-0">a</a> <a href="#cite_ref-Knuth_4-1">b</a> D. E. Knuth: The Art of Computer Programming, Vol 2: Seminumerical Algorithms (3rd ed.), s. 318. Addison-Wesley, 1997. <a href="/wiki/Toiminnot:Kirjal%C3%A4hteet/0-387-94777-9" title="Toiminnot:Kirjalähteet/0-387-94777-9">ISBN 0-387-94777-9</a> </li> <li id="cite_note-5"><a href="#cite_ref-5">↑</a> Eukleides: ”Book VII (Fundamentals of Number Theory), Proposition 2 Julkaisija = aleph0.clarku.edu”, Euclid's Elements. Määritä julkaisija! <a rel="nofollow" class="external text" href="http://aleph0.clarku.edu/~djoyce/java/elements/bookVII/bookVII.html#props">Teoksen verkkoversio</a>. </li> <li id="cite_note-6"><a href="#cite_ref-6">↑</a> Eukleides: ”Book 10 (Classification of Incommensurables), Proporision 3”, Euclid's Elements. aleph0.clarku.edu. <a rel="nofollow" class="external text" href="http://aleph0.clarku.edu/~djoyce/java/elements/bookX/propX3.html">Teoksen verkkoversio</a>. </li> <li id="cite_note-Weil_1983-7"><a href="#cite_ref-Weil_1983_7-0">↑</a> André Weil: Number Theory, s. 4–6. Birkhäuser, 1983. <a href="/wiki/Toiminnot:Kirjal%C3%A4hteet/0-8176-3141-0" title="Toiminnot:Kirjalähteet/0-8176-3141-0">ISBN 0-8176-3141-0</a> </li> <li id="cite_note-Jones_1994-8"><a href="#cite_ref-Jones_1994_8-0">↑</a> A. Jones: ”Greek mathematics to AD 300”, Companion encyclopedia of the history and philosophy of the mathematical sciences, s. 46–48. New York: Routledge, 1994. <a href="/wiki/Toiminnot:Kirjal%C3%A4hteet/0-415-09238-8" title="Toiminnot:Kirjalähteet/0-415-09238-8">ISBN 0-415-09238-8</a> </li> <li id="cite_note-van_der_Waerden_1954-9"><a href="#cite_ref-van_der_Waerden_1954_9-0">↑</a> Bartel Leendert van der Waerden: Science Awakening, s. 114–. (englanniksi kääntänyt Arnold Dresden) Groningen: P. Noordhoff Ltd. <a rel="nofollow" class="external text" href="https://archive.org/details/scienceawakening00waer/page/114">Teoksen verkkoversio</a>. </li> <li id="cite_note-10"><a href="#cite_ref-10">↑</a> <a rel="nofollow" class="external text" href="https://www.uvm.edu/~cbcafier/cs1210/book/11_loops/euclids_gcd.html">Euclid’s Algorithm (GCD)</a> ((Footnote 1)) uvm.edu. </li> <li id="cite_note-11"><a href="#cite_ref-11">↑</a> O. Becker: Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid. Quellen und Studien zur Geschichte der Mathematik B, 1933, nro 2, s. 311–333. </li> <li id="cite_note-Stillwell,_p._31-12">↑ <a href="#cite_ref-Stillwell,_p._31_12-0">a</a> <a href="#cite_ref-Stillwell,_p._31_12-1">b</a> <a href="#cite_ref-Stillwell,_p._31_12-2">c</a> <a href="#cite_ref-Stillwell,_p._31_12-3">d</a> John Stillwell: Numbers and Geometry, s. 31–32. Springer-Verlag, 1997. <a href="/wiki/Toiminnot:Kirjal%C3%A4hteet/0-387-98289-2" title="Toiminnot:Kirjalähteet/0-387-98289-2">ISBN 0-387-98289-2</a> </li> <li id="cite_note-13"><a href="#cite_ref-13">↑</a> <a rel="nofollow" class="external text" href="https://arxiv.org/pdf/cs/0604012">The Aryabhata Algorithm Using Least Absolute Remainders</a> arxiv.org. Viitattu 7.6.2024. </li> <li id="cite_note-14"><a href="#cite_ref-14">↑</a> K. H. Rosen: Elementary Number Theory and its Applications (4th ed.). Reading, Massachusetts: Addison-Wesley, 2000. <a href="/wiki/Toiminnot:Kirjal%C3%A4hteet/0-201-87073-8" title="Toiminnot:Kirjalähteet/0-201-87073-8">ISBN 0-201-87073-8</a> </li> <li id="cite_note-15"><a href="#cite_ref-15">↑</a> O. Ore: Number Theory and Its History, s. 247–248. New York: McGraw-Hill, 1948. </li> <li id="cite_note-16"><a href="#cite_ref-16">↑</a> J. J. Tattersall: Elementary Number Theory in Nine Chapters, s. 72, 184–185. Cambridge: Cambridge University Press, 2005 <a href="/wiki/Toiminnot:Kirjal%C3%A4hteet/9780521850148" class="internal mw-magiclink-isbn">ISBN 978-0-521-85014-8</a>. </li> <li id="cite_note-17"><a href="#cite_ref-17">↑</a> J. J. Tattersall: Elementary Number Theory in Nine Chapters, s. 70. Cambdidge: Cambridge University Press, 2005. <a href="/wiki/Toiminnot:Kirjal%C3%A4hteet/978-0-521-85014-8" title="Toiminnot:Kirjalähteet/978-0-521-85014-8">ISBN 978-0-521-85014-8</a> <a rel="nofollow" class="external text" href="https://www.loc.gov/resource/rbc0001.2009gen48833/">Teoksen verkkoversio</a>. </li> <li id="cite_note-18"><a href="#cite_ref-18">↑</a> Nicholas Saunderson: The Elements of Algebra in Ten Books. University of Cambridge Press, 1740. <a rel="nofollow" class="external text" href="http://www.e-rara.ch/zut/content/structure/2440626">Teoksen verkkoversio</a>. </li> <li id="cite_note-19"><a href="#cite_ref-19">↑</a> J. J. Tattersall: Elementary Number Theory in Nine Chapters, s. 72–76. Cambdidge: Cambridge University Press, 2005 <a href="/wiki/Toiminnot:Kirjal%C3%A4hteet/9780521850148" class="internal mw-magiclink-isbn">ISBN 978-0-521-85014-8</a>. </li> <li id="cite_note-20"><a href="#cite_ref-20">↑</a> C. F. Gauss: Theoria residuorum biquadraticorum. Comm. Soc. Reg. Sci. Gött. Rec, 1832, nro 4. <a rel="nofollow" class="external text" href="https://www.cambridge.org/core/books/abs/werke/theoria-residuorum-biquadraticorum-commentatio-prima/608AB610CDE568B47FC8EDDC59C944EF">Artikkelin verkkoversio</a>. </li> <li id="cite_note-21"><a href="#cite_ref-21">↑</a> Richard Dedekind (toim.); P. G. Lejeune Dirichlet: Vorlesungen über Zahlentheorie, s. 29–31. Braunschweig: Vieweg, 1894. (saksaksi) </li> <li id="cite_note-22"><a href="#cite_ref-22">↑</a> Charles Sturm: Mémoire sur la résolution des équations numériques. Bull. Des sciences de Férussac, 1829, nro 11, s. 419–422. (ranskaksi) </li> <li id="cite_note-23"><a href="#cite_ref-23">↑</a> Helaman Ferguson, R. W. Forcade: Generalization of the Euclidean algorithm for real numbers to all dimensions higher than two. Bulletin of the American Mathematical Society, New Series, 1979, 1. vsk, nro 6, s. 912–914. <a href="/wiki/Digital_object_identifier" class="mw-redirect" title="Digital object identifier">doi</a>:<a rel="nofollow" class="external text" href="https://dx.doi.org/10.1090%2FS0273-0979-1979-14691-3">10.1090/S0273-0979-1979-14691-3</a> <a href="/w/index.php?title=Mathematical_Reviews&action=edit&redlink=1" class="new" title="Mathematical Reviews (sivua ei ole)">MR</a>:<a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=546316">546316</a> </li> <li id="cite_note-24"><a href="#cite_ref-24">↑</a> I. Peterson: Jazzing Up Euclid's Algorithm. ScienceNews, 12.8.2002. <a rel="nofollow" class="external text" href="https://www.sciencenews.org/article/jazzing-euclids-algorithm">Artikkelin verkkoversio</a>. </li> <li id="cite_note-25"><a href="#cite_ref-25">↑</a> Barry Arthur Cipra: The Best of the 20th Century: Editors Name Top 10 Algorithms. SIAM News, 16.5.2000, 33. vsk, nro 4. Society for Industrial and Applied Mathematics. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160922144038/https://www.siam.org/pdf/news/637.pdf">Artikkelin verkkoversio</a>. </li> <li id="cite_note-26"><a href="#cite_ref-26">↑</a> A. J. Cole; A. J. T. Davie: A game based on the Euclidean algorithm and a winning strategy for it. Math. Gaz., 1969, 53. vsk, nro 386, s. = 354–357. <a href="/wiki/Digital_object_identifier" class="mw-redirect" title="Digital object identifier">doi</a>:<a rel="nofollow" class="external text" href="https://dx.doi.org/10.2307%2F3612461">10.2307/3612461</a> <a href="/wiki/JSTOR" title="JSTOR">JSTOR</a>:<a rel="nofollow" class="external text" href="http://www.jstor.org/stable/3612461">3612461</a> S2CID:<a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:125164797">125164797</a> </li> <li id="cite_note-27"><a href="#cite_ref-27">↑</a> E. L. Spitznagel: Properties of a game based on Euclid's algorithm. Math. Mag., 1973, 46. vsk, nro 2, s. 87–92. <a href="/wiki/Digital_object_identifier" class="mw-redirect" title="Digital object identifier">doi</a>:<a rel="nofollow" class="external text" href="https://dx.doi.org/10.2307%2F2689037">10.2307/2689037</a> <a href="/wiki/JSTOR" title="JSTOR">JSTOR</a>:<a rel="nofollow" class="external text" href="http://www.jstor.org/stable/2689037">2689037</a> </li> <li id="cite_note-28"><a href="#cite_ref-28">↑</a> J. Roberts: Elementary Number Theory: A Problem Oriented Approach, s. 1–8. Cambridge, Massachusetts: <a href="/w/index.php?title=MIT_Press&action=edit&redlink=1" class="new" title="MIT Press (sivua ei ole)">MIT Press</a>, 1977. Virhe: Virheellinen ISBN-tunniste <a rel="nofollow" class="external text" href="https://archive.org/details/Elementary_00_Robe/page/1">Teoksen verkkoversio</a>. </li> </ol> </div> <div class="mw-heading mw-heading2"><h2 id="Kirjallisuutta">Kirjallisuutta</h2>[<a href="/w/index.php?title=Eukleideen_algoritmi&veaction=edit&section=9" title="Muokkaa osiota Kirjallisuutta" class="mw-editsection-visualeditor">muokkaa</a> | <a href="/w/index.php?title=Eukleideen_algoritmi&action=edit&section=9" title="Muokkaa osion lähdekoodia: Kirjallisuutta">muokkaa wikitekstiä</a>]</div> <ul><li>Kaleva, Osmo: Numeerinen analyysi. (Opintomoniste 163) Tampere: TTKK, 1993. <a href="/wiki/Toiminnot:Kirjal%C3%A4hteet/951-721-941-5" title="Toiminnot:Kirjalähteet/951-721-941-5">ISBN 951-721-941-5</a> </li> <li>Häsä, Jokke & Rämö, Johanna: <a href="/wiki/Johdatus_abstraktiin_algebraan" class="mw-redirect" title="Johdatus abstraktiin algebraan">Johdatus abstraktiin algebraan</a>. Helsinki: Gaudeamus, 2015. <a href="/wiki/Toiminnot:Kirjal%C3%A4hteet/978-952-495-361-0" title="Toiminnot:Kirjalähteet/978-952-495-361-0">ISBN 978-952-495-361-0</a> </li></ul> <div class="mw-heading mw-heading2"><h2 id="Aiheesta_muualla">Aiheesta muualla</h2>[<a href="/w/index.php?title=Eukleideen_algoritmi&veaction=edit&section=10" title="Muokkaa osiota Aiheesta muualla" class="mw-editsection-visualeditor">muokkaa</a> | <a href="/w/index.php?title=Eukleideen_algoritmi&action=edit&section=10" title="Muokkaa osion lähdekoodia: Aiheesta muualla">muokkaa wikitekstiä</a>]</div> <style data-mw-deduplicate="TemplateStyles:r22431496">.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:#f9f9f9;display:flow-root}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}</style><div class="side-box side-box-right plainlinks sistersitebox"> <div class="side-box-flex"> <div class="side-box-image"><a href="/wiki/Tiedosto:Commons-logo.svg" class="mw-file-description"><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png" decoding="async" width="30" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/45px-Commons-logo.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/59px-Commons-logo.svg.png 2x" data-file-width="1024" data-file-height="1376" /></a></div> <div class="side-box-text plainlist"><a href="/wiki/Wikimedia_Commons" title="Wikimedia Commons">Wikimedia Commonsissa</a> on kuvia tai muita tiedostoja aiheesta <a href="https://commons.wikimedia.org/wiki/Category:Euclidean_algorithm" class="extiw" title="commons:Category:Euclidean algorithm">Eukleideen algoritmi</a>.</div></div> </div> <ul><li><a rel="nofollow" class="external text" href="http://opiskelu.org/2010/03/eukleideen-algoritmi/">Eukleideen algoritmi, online sovellus</a></li></ul></div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Noudettu kohteesta ”<a dir="ltr" href="https://fi.wikipedia.org/w/index.php?title=Eukleideen_algoritmi&oldid=22774615">https://fi.wikipedia.org/w/index.php?title=Eukleideen_algoritmi&oldid=22774615</a>”</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Toiminnot:Luokat" title="Toiminnot:Luokat">Luokat</a>: <ul><li><a href="/wiki/Luokka:Lukuteoria" title="Luokka:Lukuteoria">Lukuteoria</a></li><li><a href="/wiki/Luokka:Algoritmit" title="Luokka:Algoritmit">Algoritmit</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Piilotetut luokat: <ul><li><a href="/wiki/Luokka:Sivut,_joiden_viitemallineissa_on_virheit%C3%A4" title="Luokka:Sivut, joiden viitemallineissa on virheitä">Sivut, joiden viitemallineissa on virheitä</a></li><li><a href="/wiki/Luokka:Julkaisija-parametri_puuttuu" title="Luokka:Julkaisija-parametri puuttuu">Julkaisija-parametri puuttuu</a></li><li><a href="/wiki/Luokka:Sivut,_joissa_on_virheellinen_ISBN-tunniste" title="Luokka:Sivut, joissa on virheellinen ISBN-tunniste">Sivut, joissa on virheellinen ISBN-tunniste</a></li><li><a href="/wiki/Luokka:Sivut,_jotka_k%C3%A4ytt%C3%A4v%C3%A4t_ISBN-taikalinkkej%C3%A4" title="Luokka:Sivut, jotka käyttävät ISBN-taikalinkkejä">Sivut, jotka käyttävät ISBN-taikalinkkejä</a></li><li><a href="/wiki/Luokka:K%C3%A4%C3%A4nnetyt_artikkelit" title="Luokka:Käännetyt artikkelit">Käännetyt artikkelit</a></li><li><a href="/wiki/Luokka:Seulonnan_keskeiset_artikkelit" title="Luokka:Seulonnan keskeiset artikkelit">Seulonnan keskeiset artikkelit</a></li></ul></div></div> </div> </div> <div id="mw-navigation"> <h2>Navigointivalikko</h2> <div id="mw-head"> <nav id="p-personal" class="mw-portlet mw-portlet-personal vector-user-menu-legacy vector-menu" aria-labelledby="p-personal-label" > <h3 id="p-personal-label" class="vector-menu-heading " > Henkilökohtaiset työkalut </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anonuserpage" class="mw-list-item">Et ole kirjautunut</li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Toiminnot:Oma_keskustelu" title="Keskustelu tämän IP-osoitteen muokkauksista [n]" accesskey="n">Keskustelu</a></li><li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Toiminnot:Omat_muokkaukset" title="Luettelo tästä IP-osoitteesta tehdyistä muokkauksista [y]" accesskey="y">Muokkaukset</a></li><li id="pt-createaccount" class="mw-list-item"><a href="/w/index.php?title=Toiminnot:Luo_tunnus&returnto=Eukleideen+algoritmi" title="On suositeltavaa luoda käyttäjätunnus ja kirjautua sisään. Se ei kuitenkaan ole pakollista.">Luo tunnus</a></li><li id="pt-login" class="mw-list-item"><a href="/w/index.php?title=Toiminnot:Kirjaudu_sis%C3%A4%C3%A4n&returnto=Eukleideen+algoritmi" title="On suositeltavaa kirjautua sisään. Se ei kuitenkaan ole pakollista. [o]" accesskey="o">Kirjaudu sisään</a></li> </ul> </div> </nav> <div id="left-navigation"> <nav id="p-namespaces" class="mw-portlet mw-portlet-namespaces vector-menu-tabs vector-menu-tabs-legacy vector-menu" aria-labelledby="p-namespaces-label" > <h3 id="p-namespaces-label" class="vector-menu-heading " > Nimiavaruudet </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected mw-list-item"><a href="/wiki/Eukleideen_algoritmi" title="Näytä sisältösivu [c]" accesskey="c">Artikkeli</a></li><li id="ca-talk" class="new mw-list-item"><a href="/w/index.php?title=Keskustelu:Eukleideen_algoritmi&action=edit&redlink=1" rel="discussion" class="new" title="Keskustele sisällöstä (sivua ei ole) [t]" accesskey="t">Keskustelu</a></li> </ul> </div> </nav> <nav id="p-variants" class="mw-portlet mw-portlet-variants emptyPortlet vector-menu-dropdown vector-menu" aria-labelledby="p-variants-label" > <input type="checkbox" id="p-variants-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-variants" class="vector-menu-checkbox" aria-labelledby="p-variants-label" > <label id="p-variants-label" class="vector-menu-heading " > suomi </label> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </nav> </div> <div id="right-navigation"> <nav id="p-views" class="mw-portlet mw-portlet-views vector-menu-tabs vector-menu-tabs-legacy vector-menu" aria-labelledby="p-views-label" > <h3 id="p-views-label" class="vector-menu-heading " > Näkymät </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected mw-list-item"><a href="/wiki/Eukleideen_algoritmi">Lue</a></li><li id="ca-ve-edit" class="mw-list-item"><a href="/w/index.php?title=Eukleideen_algoritmi&veaction=edit" title="Muokkaa tätä sivua [v]" accesskey="v">Muokkaa</a></li><li id="ca-edit" class="collapsible mw-list-item"><a href="/w/index.php?title=Eukleideen_algoritmi&action=edit" title="Muokkaa tämän sivun lähdekoodia [e]" accesskey="e">Muokkaa wikitekstiä</a></li><li id="ca-history" class="mw-list-item"><a href="/w/index.php?title=Eukleideen_algoritmi&action=history" title="Sivun aikaisemmat versiot [h]" accesskey="h">Näytä historia</a></li> </ul> </div> </nav> <nav id="p-cactions" class="mw-portlet mw-portlet-cactions emptyPortlet vector-menu-dropdown vector-menu" aria-labelledby="p-cactions-label" title="Lisää valintoja" > <input type="checkbox" id="p-cactions-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-cactions" class="vector-menu-checkbox" aria-labelledby="p-cactions-label" > <label id="p-cactions-label" class="vector-menu-heading " > Muut </label> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </nav> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <h3 >Haku</h3> <form action="/w/index.php" id="searchform" class="vector-search-box-form"> <div id="simpleSearch" class="vector-search-box-inner" data-search-loc="header-navigation"> <input class="vector-search-box-input" type="search" name="search" placeholder="Hae Wikipediasta" aria-label="Hae Wikipediasta" autocapitalize="sentences" title="Hae Wikipediasta [f]" accesskey="f" id="searchInput" > <input type="hidden" name="title" value="Toiminnot:Haku"> <input id="mw-searchButton" class="searchButton mw-fallbackSearchButton" type="submit" name="fulltext" title="Hae sivuilta tätä tekstiä" value="Hae"> <input id="searchButton" class="searchButton" type="submit" name="go" title="Siirry sivulle, joka on tarkalleen tällä nimellä" value="Siirry"> </div> </form> </div> </div> </div> <div id="mw-panel" class="vector-legacy-sidebar"> <div id="p-logo" role="banner"> <a class="mw-wiki-logo" href="/wiki/Wikipedia:Etusivu" title="Etusivu"></a> </div> <nav id="p-navigation" class="mw-portlet mw-portlet-navigation vector-menu-portal portal vector-menu" aria-labelledby="p-navigation-label" > <h3 id="p-navigation-label" class="vector-menu-heading " > Valikko </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Wikipedia:Etusivu" title="Siirry etusivulle [z]" accesskey="z">Etusivu</a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:Tietoja">Tietoja Wikipediasta</a></li><li id="n-allarticles" class="mw-list-item"><a href="/wiki/Wikipedia:Selaa_luokittain">Kaikki sivut</a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Toiminnot:Satunnainen_sivu" title="Avaa satunnainen sivu [x]" accesskey="x">Satunnainen artikkeli</a></li> </ul> </div> </nav> <nav id="p-interaction" class="mw-portlet mw-portlet-interaction vector-menu-portal portal vector-menu" aria-labelledby="p-interaction-label" > <h3 id="p-interaction-label" class="vector-menu-heading " > Osallistuminen </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Ohje:Sis%C3%A4llys" title="Ohjeita">Ohje</a></li><li id="n-Kahvihuone" class="mw-list-item"><a href="/wiki/Wikipedia:Kahvihuone">Kahvihuone</a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Wikipedia:Ajankohtaista" title="Taustatietoa tämänhetkisistä tapahtumista">Ajankohtaista</a></li><li id="n-Tuoreet-odottavat-muutokset" class="mw-list-item"><a href="//fi.wikipedia.org/wiki/Toiminnot:Tuoreet_muutokset?damaging=&goodfaith=&hideliu=0&hideanons=0&userExpLevel=&hidemyself=0&hidebyothers=0&hidebots=1&hidehumans=0&hidepatrolled=1&hideunpatrolled=0&hideminor=0&hidemajor=0&hidepageedits=0&hidenewpages=0&hidecategorization=1&hideWikibase=1&hidelog=0&highlight=1&goodfaith__verylikelybad_color=c5&goodfaith__likelybad_color=c4&goodfaith__maybebad_color=c3&damaging__verylikelybad_color=c5&damaging__likelybad_color=c4&damaging__maybebad_color=c3">Tuoreet odottavat muutokset</a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Toiminnot:Tuoreet_muutokset" title="Luettelo tuoreista muutoksista [r]" accesskey="r">Tuoreet muutokset</a></li><li id="n-sitesupport" class="mw-list-item"><a href="//donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_fi.wikipedia.org&uselang=fi" title="Tue meitä">Lahjoitukset</a></li> </ul> </div> </nav> <nav id="p-tb" class="mw-portlet mw-portlet-tb vector-menu-portal portal vector-menu" aria-labelledby="p-tb-label" > <h3 id="p-tb-label" class="vector-menu-heading " > Työkalut </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Toiminnot:T%C3%A4nne_viittaavat_sivut/Eukleideen_algoritmi" title="Lista sivuista, jotka viittaavat tänne [j]" accesskey="j">Tänne viittaavat sivut</a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Toiminnot:Linkitetyt_muutokset/Eukleideen_algoritmi" rel="nofollow" title="Viimeisimmät muokkaukset sivuissa, joille viitataan tältä sivulta [k]" accesskey="k">Linkitettyjen sivujen muutokset</a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Toiminnot:Toimintosivut" title="Näytä toimintosivut [q]" accesskey="q">Toimintosivut</a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Eukleideen_algoritmi&oldid=22774615" title="Ikilinkki tämän sivun tähän versioon">Ikilinkki</a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Eukleideen_algoritmi&action=info" title="Enemmän tietoa tästä sivusta">Sivun tiedot</a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Toiminnot:Viittaus&page=Eukleideen_algoritmi&id=22774615&wpFormIdentifier=titleform" title="Tietoa tämän sivun lainaamisesta">Viitetiedot</a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Toiminnot:UrlShortener&url=https%3A%2F%2Ffi.wikipedia.org%2Fwiki%2FEukleideen_algoritmi">Lyhennä URL-osoite</a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Toiminnot:QrCode&url=https%3A%2F%2Ffi.wikipedia.org%2Fwiki%2FEukleideen_algoritmi">Lataa QR-koodi</a></li> </ul> </div> </nav> <nav id="p-coll-print_export" class="mw-portlet mw-portlet-coll-print_export vector-menu-portal portal vector-menu" aria-labelledby="p-coll-print_export-label" > <h3 id="p-coll-print_export-label" class="vector-menu-heading " > Tulosta/vie </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Toiminnot:DownloadAsPdf&page=Eukleideen_algoritmi&action=show-download-screen">Lataa PDF-tiedostona</a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Eukleideen_algoritmi&printable=yes" title="Tulostettava versio [p]" accesskey="p">Tulostettava versio</a></li> </ul> </div> </nav> <nav id="p-wikibase-otherprojects" class="mw-portlet mw-portlet-wikibase-otherprojects vector-menu-portal portal vector-menu" aria-labelledby="p-wikibase-otherprojects-label" > <h3 id="p-wikibase-otherprojects-label" class="vector-menu-heading " > Muissa hankkeissa </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Euclidean_algorithm" hreflang="en">Wikimedia Commons</a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q230848" title="Linkki yhdistettyyn keskustietovaraston kohteeseen [g]" accesskey="g">Wikidata-kohde</a></li> </ul> </div> </nav> <nav id="p-lang" class="mw-portlet mw-portlet-lang vector-menu-portal portal vector-menu" aria-labelledby="p-lang-label" > <h3 id="p-lang-label" class="vector-menu-heading " > Muilla kielillä </h3> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9_%D8%A3%D9%82%D9%84%D9%8A%D8%AF%D8%B3" title="خوارزمية أقليدس — arabia" lang="ar" hreflang="ar" data-title="خوارزمية أقليدس" data-language-autonym="العربية" data-language-local-name="arabia" class="interlanguage-link-target">العربية</a></li><li class="interlanguage-link interwiki-ast mw-list-item"><a href="https://ast.wikipedia.org/wiki/Algoritmu_d%27Euclides" title="Algoritmu d'Euclides — asturia" lang="ast" hreflang="ast" data-title="Algoritmu d'Euclides" data-language-autonym="Asturianu" data-language-local-name="asturia" class="interlanguage-link-target">Asturianu</a></li><li class="interlanguage-link interwiki-az mw-list-item"><a href="https://az.wikipedia.org/wiki/Evklid_alqoritmi" title="Evklid alqoritmi — azeri" lang="az" hreflang="az" data-title="Evklid alqoritmi" data-language-autonym="Azərbaycanca" data-language-local-name="azeri" class="interlanguage-link-target">Azərbaycanca</a></li><li class="interlanguage-link interwiki-id mw-list-item"><a href="https://id.wikipedia.org/wiki/Algoritma_Euklides" title="Algoritma Euklides — indonesia" lang="id" hreflang="id" data-title="Algoritma Euklides" data-language-autonym="Bahasa Indonesia" data-language-local-name="indonesia" class="interlanguage-link-target">Bahasa Indonesia</a></li><li class="interlanguage-link interwiki-bn mw-list-item"><a href="https://bn.wikipedia.org/wiki/%E0%A6%87%E0%A6%89%E0%A6%95%E0%A7%8D%E0%A6%B2%E0%A6%BF%E0%A6%A1%E0%A7%80%E0%A6%AF%E0%A6%BC_%E0%A6%8F%E0%A6%B2%E0%A6%97%E0%A6%B0%E0%A6%BF%E0%A6%A6%E0%A6%AE" title="ইউক্লিডীয় এলগরিদম — bengali" lang="bn" hreflang="bn" data-title="ইউক্লিডীয় এলগরিদম" data-language-autonym="বাংলা" data-language-local-name="bengali" class="interlanguage-link-target">বাংলা</a></li><li class="interlanguage-link interwiki-ba mw-list-item"><a href="https://ba.wikipedia.org/wiki/%D0%95%D0%B2%D0%BA%D0%BB%D0%B8%D0%B4_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B" title="Евклид алгоритмы — baškiiri" lang="ba" hreflang="ba" data-title="Евклид алгоритмы" data-language-autonym="Башҡортса" data-language-local-name="baškiiri" class="interlanguage-link-target">Башҡортса</a></li><li class="interlanguage-link interwiki-be mw-list-item"><a href="https://be.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%B0%D1%80%D1%8B%D1%82%D0%BC_%D0%AD%D1%9E%D0%BA%D0%BB%D1%96%D0%B4%D0%B0" title="Алгарытм Эўкліда — valkovenäjä" lang="be" hreflang="be" data-title="Алгарытм Эўкліда" data-language-autonym="Беларуская" data-language-local-name="valkovenäjä" class="interlanguage-link-target">Беларуская</a></li><li class="interlanguage-link interwiki-bg mw-list-item"><a href="https://bg.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D1%8A%D0%BC_%D0%BD%D0%B0_%D0%95%D0%B2%D0%BA%D0%BB%D0%B8%D0%B4" title="Алгоритъм на Евклид — bulgaria" lang="bg" hreflang="bg" data-title="Алгоритъм на Евклид" data-language-autonym="Български" data-language-local-name="bulgaria" class="interlanguage-link-target">Български</a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Algorisme_d%27Euclides" title="Algorisme d'Euclides — katalaani" lang="ca" hreflang="ca" data-title="Algorisme d'Euclides" data-language-autonym="Català" data-language-local-name="katalaani" class="interlanguage-link-target">Català</a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Eukleid%C5%AFv_algoritmus" title="Eukleidův algoritmus — tšekki" lang="cs" hreflang="cs" data-title="Eukleidův algoritmus" data-language-autonym="Čeština" data-language-local-name="tšekki" class="interlanguage-link-target">Čeština</a></li><li class="interlanguage-link interwiki-cy mw-list-item"><a href="https://cy.wikipedia.org/wiki/Algorithm_Ewclidaidd" title="Algorithm Ewclidaidd — kymri" lang="cy" hreflang="cy" data-title="Algorithm Ewclidaidd" data-language-autonym="Cymraeg" data-language-local-name="kymri" class="interlanguage-link-target">Cymraeg</a></li><li class="interlanguage-link interwiki-da mw-list-item"><a href="https://da.wikipedia.org/wiki/Euklids_algoritme" title="Euklids algoritme — tanska" lang="da" hreflang="da" data-title="Euklids algoritme" data-language-autonym="Dansk" data-language-local-name="tanska" class="interlanguage-link-target">Dansk</a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Euklidischer_Algorithmus" title="Euklidischer Algorithmus — saksa" lang="de" hreflang="de" data-title="Euklidischer Algorithmus" data-language-autonym="Deutsch" data-language-local-name="saksa" class="interlanguage-link-target">Deutsch</a></li><li class="interlanguage-link interwiki-el mw-list-item"><a href="https://el.wikipedia.org/wiki/%CE%91%CE%BB%CE%B3%CF%8C%CF%81%CE%B9%CE%B8%CE%BC%CE%BF%CF%82_%CF%84%CE%BF%CF%85_%CE%95%CF%85%CE%BA%CE%BB%CE%B5%CE%AF%CE%B4%CE%B7" title="Αλγόριθμος του Ευκλείδη — kreikka" lang="el" hreflang="el" data-title="Αλγόριθμος του Ευκλείδη" data-language-autonym="Ελληνικά" data-language-local-name="kreikka" class="interlanguage-link-target">Ελληνικά</a></li><li class="interlanguage-link interwiki-en badge-Q17437796 badge-featuredarticle mw-list-item" title="suositeltu artikkeli"><a href="https://en.wikipedia.org/wiki/Euclidean_algorithm" title="Euclidean algorithm — englanti" lang="en" hreflang="en" data-title="Euclidean algorithm" data-language-autonym="English" data-language-local-name="englanti" class="interlanguage-link-target">English</a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Algoritmo_de_Euclides" title="Algoritmo de Euclides — espanja" lang="es" hreflang="es" data-title="Algoritmo de Euclides" data-language-autonym="Español" data-language-local-name="espanja" class="interlanguage-link-target">Español</a></li><li class="interlanguage-link interwiki-eo mw-list-item"><a href="https://eo.wikipedia.org/wiki/E%C5%ADklida_algoritmo" title="Eŭklida algoritmo — esperanto" lang="eo" hreflang="eo" data-title="Eŭklida algoritmo" data-language-autonym="Esperanto" data-language-local-name="esperanto" class="interlanguage-link-target">Esperanto</a></li><li class="interlanguage-link interwiki-eu mw-list-item"><a href="https://eu.wikipedia.org/wiki/Euklidesen_algoritmo" title="Euklidesen algoritmo — baski" lang="eu" hreflang="eu" data-title="Euklidesen algoritmo" data-language-autonym="Euskara" data-language-local-name="baski" class="interlanguage-link-target">Euskara</a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%D8%A7%D9%82%D9%84%DB%8C%D8%AF%D8%B3" title="الگوریتم اقلیدس — persia" lang="fa" hreflang="fa" data-title="الگوریتم اقلیدس" data-language-autonym="فارسی" data-language-local-name="persia" class="interlanguage-link-target">فارسی</a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Algorithme_d%27Euclide" title="Algorithme d'Euclide — ranska" lang="fr" hreflang="fr" data-title="Algorithme d'Euclide" data-language-autonym="Français" data-language-local-name="ranska" class="interlanguage-link-target">Français</a></li><li class="interlanguage-link interwiki-gl mw-list-item"><a href="https://gl.wikipedia.org/wiki/Algoritmo_de_Euclides" title="Algoritmo de Euclides — galicia" lang="gl" hreflang="gl" data-title="Algoritmo de Euclides" data-language-autonym="Galego" data-language-local-name="galicia" class="interlanguage-link-target">Galego</a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95" title="유클리드 호제법 — korea" lang="ko" hreflang="ko" data-title="유클리드 호제법" data-language-autonym="한국어" data-language-local-name="korea" class="interlanguage-link-target">한국어</a></li><li class="interlanguage-link interwiki-hy mw-list-item"><a href="https://hy.wikipedia.org/wiki/%D4%B7%D5%BE%D5%AF%D5%AC%D5%AB%D5%A4%D5%A5%D5%BD%D5%AB_%D5%A1%D5%AC%D5%A3%D5%B8%D6%80%D5%AB%D5%A9%D5%B4" title="Էվկլիդեսի ալգորիթմ — armenia" lang="hy" hreflang="hy" data-title="Էվկլիդեսի ալգորիթմ" data-language-autonym="Հայերեն" data-language-local-name="armenia" class="interlanguage-link-target">Հայերեն</a></li><li class="interlanguage-link interwiki-hr mw-list-item"><a href="https://hr.wikipedia.org/wiki/Euklidov_algoritam" title="Euklidov algoritam — kroatia" lang="hr" hreflang="hr" data-title="Euklidov algoritam" data-language-autonym="Hrvatski" data-language-local-name="kroatia" class="interlanguage-link-target">Hrvatski</a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Algoritmo_di_Euclide" title="Algoritmo di Euclide — italia" lang="it" hreflang="it" data-title="Algoritmo di Euclide" data-language-autonym="Italiano" data-language-local-name="italia" class="interlanguage-link-target">Italiano</a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%90%D7%9C%D7%92%D7%95%D7%A8%D7%99%D7%AA%D7%9D_%D7%90%D7%95%D7%A7%D7%9C%D7%99%D7%93%D7%A1" title="אלגוריתם אוקלידס — heprea" lang="he" hreflang="he" data-title="אלגוריתם אוקלידס" data-language-autonym="עברית" data-language-local-name="heprea" class="interlanguage-link-target">עברית</a></li><li class="interlanguage-link interwiki-la mw-list-item"><a href="https://la.wikipedia.org/wiki/Algorithmus_Euclidis" title="Algorithmus Euclidis — latina" lang="la" hreflang="la" data-title="Algorithmus Euclidis" data-language-autonym="Latina" data-language-local-name="latina" class="interlanguage-link-target">Latina</a></li><li class="interlanguage-link interwiki-lv mw-list-item"><a href="https://lv.wikipedia.org/wiki/Eikl%C4%ABda_algoritms" title="Eiklīda algoritms — latvia" lang="lv" hreflang="lv" data-title="Eiklīda algoritms" data-language-autonym="Latviešu" data-language-local-name="latvia" class="interlanguage-link-target">Latviešu</a></li><li class="interlanguage-link interwiki-lt mw-list-item"><a href="https://lt.wikipedia.org/wiki/Euklido_algoritmas" title="Euklido algoritmas — liettua" lang="lt" hreflang="lt" data-title="Euklido algoritmas" data-language-autonym="Lietuvių" data-language-local-name="liettua" class="interlanguage-link-target">Lietuvių</a></li><li class="interlanguage-link interwiki-hu badge-Q17437796 badge-featuredarticle mw-list-item" title="suositeltu artikkeli"><a href="https://hu.wikipedia.org/wiki/Euklideszi_algoritmus" title="Euklideszi algoritmus — unkari" lang="hu" hreflang="hu" data-title="Euklideszi algoritmus" data-language-autonym="Magyar" data-language-local-name="unkari" class="interlanguage-link-target">Magyar</a></li><li class="interlanguage-link interwiki-mk mw-list-item"><a href="https://mk.wikipedia.org/wiki/%D0%95%D0%B2%D0%BA%D0%BB%D0%B8%D0%B4%D0%BE%D0%B2_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%B0%D0%BC" title="Евклидов алгоритам — makedonia" lang="mk" hreflang="mk" data-title="Евклидов алгоритам" data-language-autonym="Македонски" data-language-local-name="makedonia" class="interlanguage-link-target">Македонски</a></li><li class="interlanguage-link interwiki-ml mw-list-item"><a href="https://ml.wikipedia.org/wiki/%E0%B4%AF%E0%B5%82%E0%B4%95%E0%B5%8D%E0%B4%B2%E0%B4%BF%E0%B4%A1%E0%B4%BF%E0%B4%A8%E0%B5%8D%E0%B4%B1%E0%B5%86_%E0%B4%85%E0%B5%BD%E0%B4%97%E0%B5%8A%E0%B4%B0%E0%B4%BF%E0%B4%A4%E0%B4%82" title="യൂക്ലിഡിന്റെ അൽഗൊരിതം — malajalam" lang="ml" hreflang="ml" data-title="യൂക്ലിഡിന്റെ അൽഗൊരിതം" data-language-autonym="മലയാളം" data-language-local-name="malajalam" class="interlanguage-link-target">മലയാളം</a></li><li class="interlanguage-link interwiki-mn mw-list-item"><a href="https://mn.wikipedia.org/wiki/%D0%95%D0%B2%D0%BA%D0%BB%D0%B8%D0%B4%D0%B8%D0%B9%D0%BD_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC" title="Евклидийн алгоритм — mongoli" lang="mn" hreflang="mn" data-title="Евклидийн алгоритм" data-language-autonym="Монгол" data-language-local-name="mongoli" class="interlanguage-link-target">Монгол</a></li><li class="interlanguage-link interwiki-nl mw-list-item"><a href="https://nl.wikipedia.org/wiki/Algoritme_van_Euclides" title="Algoritme van Euclides — hollanti" lang="nl" hreflang="nl" data-title="Algoritme van Euclides" data-language-autonym="Nederlands" data-language-local-name="hollanti" class="interlanguage-link-target">Nederlands</a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95" title="ユークリッドの互除法 — japani" lang="ja" hreflang="ja" data-title="ユークリッドの互除法" data-language-autonym="日本語" data-language-local-name="japani" class="interlanguage-link-target">日本語</a></li><li class="interlanguage-link interwiki-no mw-list-item"><a href="https://no.wikipedia.org/wiki/Euklids_algoritme" title="Euklids algoritme — norjan bokmål" lang="nb" hreflang="nb" data-title="Euklids algoritme" data-language-autonym="Norsk bokmål" data-language-local-name="norjan bokmål" class="interlanguage-link-target">Norsk bokmål</a></li><li class="interlanguage-link interwiki-nn mw-list-item"><a href="https://nn.wikipedia.org/wiki/Euklidsk_algoritme" title="Euklidsk algoritme — norjan nynorsk" lang="nn" hreflang="nn" data-title="Euklidsk algoritme" data-language-autonym="Norsk nynorsk" data-language-local-name="norjan nynorsk" class="interlanguage-link-target">Norsk nynorsk</a></li><li class="interlanguage-link interwiki-pms mw-list-item"><a href="https://pms.wikipedia.org/wiki/Algoritm_d%27Euclid" title="Algoritm d'Euclid — piemonte" lang="pms" hreflang="pms" data-title="Algoritm d'Euclid" data-language-autonym="Piemontèis" data-language-local-name="piemonte" class="interlanguage-link-target">Piemontèis</a></li><li class="interlanguage-link interwiki-nds mw-list-item"><a href="https://nds.wikipedia.org/wiki/Euklidsch_Algorithmus" title="Euklidsch Algorithmus — alasaksa" lang="nds" hreflang="nds" data-title="Euklidsch Algorithmus" data-language-autonym="Plattdüütsch" data-language-local-name="alasaksa" class="interlanguage-link-target">Plattdüütsch</a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Algorytm_Euklidesa" title="Algorytm Euklidesa — puola" lang="pl" hreflang="pl" data-title="Algorytm Euklidesa" data-language-autonym="Polski" data-language-local-name="puola" class="interlanguage-link-target">Polski</a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Algoritmo_de_Euclides" title="Algoritmo de Euclides — portugali" lang="pt" hreflang="pt" data-title="Algoritmo de Euclides" data-language-autonym="Português" data-language-local-name="portugali" class="interlanguage-link-target">Português</a></li><li class="interlanguage-link interwiki-ro badge-Q17437796 badge-featuredarticle mw-list-item" title="suositeltu artikkeli"><a href="https://ro.wikipedia.org/wiki/Algoritmul_lui_Euclid" title="Algoritmul lui Euclid — romania" lang="ro" hreflang="ro" data-title="Algoritmul lui Euclid" data-language-autonym="Română" data-language-local-name="romania" class="interlanguage-link-target">Română</a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%95%D0%B2%D0%BA%D0%BB%D0%B8%D0%B4%D0%B0" title="Алгоритм Евклида — venäjä" lang="ru" hreflang="ru" data-title="Алгоритм Евклида" data-language-autonym="Русский" data-language-local-name="venäjä" class="interlanguage-link-target">Русский</a></li><li class="interlanguage-link interwiki-simple mw-list-item"><a href="https://simple.wikipedia.org/wiki/Euclidean_algorithm" title="Euclidean algorithm — Simple English" lang="en-simple" hreflang="en-simple" data-title="Euclidean algorithm" data-language-autonym="Simple English" data-language-local-name="Simple English" class="interlanguage-link-target">Simple English</a></li><li class="interlanguage-link interwiki-sk mw-list-item"><a href="https://sk.wikipedia.org/wiki/Euklidov_algoritmus" title="Euklidov algoritmus — slovakki" lang="sk" hreflang="sk" data-title="Euklidov algoritmus" data-language-autonym="Slovenčina" data-language-local-name="slovakki" class="interlanguage-link-target">Slovenčina</a></li><li class="interlanguage-link interwiki-sl mw-list-item"><a href="https://sl.wikipedia.org/wiki/Evklidov_algoritem" title="Evklidov algoritem — sloveeni" lang="sl" hreflang="sl" data-title="Evklidov algoritem" data-language-autonym="Slovenščina" data-language-local-name="sloveeni" class="interlanguage-link-target">Slovenščina</a></li><li class="interlanguage-link interwiki-ckb mw-list-item"><a href="https://ckb.wikipedia.org/wiki/%D8%A6%DB%95%D9%84%DA%AF%DB%86%D8%B1%DB%8C%D8%AA%D9%85%DB%8C_%D8%A6%DB%8C%D9%82%D9%84%DB%8C%D8%AF%D8%B3" title="ئەلگۆریتمی ئیقلیدس — soranî" lang="ckb" hreflang="ckb" data-title="ئەلگۆریتمی ئیقلیدس" data-language-autonym="کوردی" data-language-local-name="soranî" class="interlanguage-link-target">کوردی</a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%95%D1%83%D0%BA%D0%BB%D0%B8%D0%B4%D0%BE%D0%B2_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%B0%D0%BC" title="Еуклидов алгоритам — serbia" lang="sr" hreflang="sr" data-title="Еуклидов алгоритам" data-language-autonym="Српски / srpski" data-language-local-name="serbia" class="interlanguage-link-target">Српски / srpski</a></li><li class="interlanguage-link interwiki-sh mw-list-item"><a href="https://sh.wikipedia.org/wiki/Euklidov_algoritam" title="Euklidov algoritam — serbokroaatti" lang="sh" hreflang="sh" data-title="Euklidov algoritam" data-language-autonym="Srpskohrvatski / српскохрватски" data-language-local-name="serbokroaatti" class="interlanguage-link-target">Srpskohrvatski / српскохрватски</a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/Euklides_algoritm" title="Euklides algoritm — ruotsi" lang="sv" hreflang="sv" data-title="Euklides algoritm" data-language-autonym="Svenska" data-language-local-name="ruotsi" class="interlanguage-link-target">Svenska</a></li><li class="interlanguage-link interwiki-ta mw-list-item"><a href="https://ta.wikipedia.org/wiki/%E0%AE%AF%E0%AF%82%E0%AE%95%E0%AF%8D%E0%AE%B3%E0%AE%BF%E0%AE%9F%E0%AE%BF%E0%AE%AF_%E0%AE%AA%E0%AE%9F%E0%AE%BF%E0%AE%AE%E0%AF%81%E0%AE%B1%E0%AF%88%E0%AE%A4%E0%AF%8D%E0%AE%A4%E0%AF%80%E0%AE%B0%E0%AF%8D%E0%AE%B5%E0%AF%81" title="யூக்ளிடிய படிமுறைத்தீர்வு — tamili" lang="ta" hreflang="ta" data-title="யூக்ளிடிய படிமுறைத்தீர்வு" data-language-autonym="தமிழ்" data-language-local-name="tamili" class="interlanguage-link-target">தமிழ்</a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B8%82%E0%B8%B1%E0%B9%89%E0%B8%99%E0%B8%95%E0%B8%AD%E0%B8%99%E0%B8%A7%E0%B8%B4%E0%B8%98%E0%B8%B5%E0%B9%81%E0%B8%9A%E0%B8%9A%E0%B8%A2%E0%B8%B8%E0%B8%84%E0%B8%A5%E0%B8%B4%E0%B8%94" title="ขั้นตอนวิธีแบบยุคลิด — thai" lang="th" hreflang="th" data-title="ขั้นตอนวิธีแบบยุคลิด" data-language-autonym="ไทย" data-language-local-name="thai" class="interlanguage-link-target">ไทย</a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/Gi%E1%BA%A3i_thu%E1%BA%ADt_Euclid" title="Giải thuật Euclid — vietnam" lang="vi" hreflang="vi" data-title="Giải thuật Euclid" data-language-autonym="Tiếng Việt" data-language-local-name="vietnam" class="interlanguage-link-target">Tiếng Việt</a></li><li class="interlanguage-link interwiki-tr mw-list-item"><a href="https://tr.wikipedia.org/wiki/%C3%96klid_algoritmas%C4%B1" title="Öklid algoritması — turkki" lang="tr" hreflang="tr" data-title="Öklid algoritması" data-language-autonym="Türkçe" data-language-local-name="turkki" class="interlanguage-link-target">Türkçe</a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%95%D0%B2%D0%BA%D0%BB%D1%96%D0%B4%D0%B0" title="Алгоритм Евкліда — ukraina" lang="uk" hreflang="uk" data-title="Алгоритм Евкліда" data-language-autonym="Українська" data-language-local-name="ukraina" class="interlanguage-link-target">Українська</a></li><li class="interlanguage-link interwiki-wuu mw-list-item"><a href="https://wuu.wikipedia.org/wiki/%E8%BE%97%E8%BD%AC%E7%9B%B8%E9%99%A4%E6%B3%95" title="辗转相除法 — wu-kiina" lang="wuu" hreflang="wuu" data-title="辗转相除法" data-language-autonym="吴语" data-language-local-name="wu-kiina" class="interlanguage-link-target">吴语</a></li><li class="interlanguage-link interwiki-zh-yue mw-list-item"><a href="https://zh-yue.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95" title="輾轉相除法 — kantoninkiina" lang="yue" hreflang="yue" data-title="輾轉相除法" data-language-autonym="粵語" data-language-local-name="kantoninkiina" class="interlanguage-link-target">粵語</a></li><li class="interlanguage-link interwiki-zh badge-Q17437798 badge-goodarticle mw-list-item" title="hyvä artikkeli"><a href="https://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95" title="輾轉相除法 — kiina" lang="zh" hreflang="zh" data-title="輾轉相除法" data-language-autonym="中文" data-language-local-name="kiina" class="interlanguage-link-target">中文</a></li> </ul> <div class="after-portlet after-portlet-lang"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q230848#sitelinks-wikipedia" title="Muokkaa kieltenvälisiä linkkejä" class="wbc-editpage">Muokkaa linkkejä</a></div> </div> </nav> </div> </div> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> Sivua on viimeksi muutettu 12. marraskuuta 2024 kello 15.25.</li> <li id="footer-info-copyright">Teksti on saatavilla <a rel="nofollow" class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.fi">Creative Commons Attribution/Share-Alike</a> -lisenssillä; lisäehtoja voi sisältyä. Katso <a class="external text" href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use/fi">käyttöehdot</a>. Wikipedia® on <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundationin</a> rekisteröimä tavaramerkki. <a href="/wiki/Wikipedia:Artikkelien_ongelmat" title="Wikipedia:Artikkelien ongelmat">Ongelma artikkelissa?</a></li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Tietosuojakäytäntö</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:Tietoja">Tietoja Wikipediasta</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:Vastuuvapaus">Vastuuvapaus</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Käytössäännöstö</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Kehittäjät</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/fi.wikipedia.org">Tilastot</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Evästekäytäntö</a></li> <li id="footer-places-mobileview"><a href="//fi.m.wikipedia.org/w/index.php?title=Eukleideen_algoritmi&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobiilinäkymä</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> <script>(RLQ=window.RLQ||[]).push(function(){mw.log.warn("This page is using the deprecated ResourceLoader module \"codex-search-styles\".\n[1.43] Use a CodexModule with codexComponents to set your specific components used: https://www.mediawiki.org/wiki/Codex#Using_a_limited_subset_of_components");mw.config.set({"wgHostname":"mw-web.codfw.main-f69cdc8f6-gzbbg","wgBackendResponseTime":168,"wgPageParseReport":{"limitreport":{"cputime":"0.189","walltime":"0.316","ppvisitednodes":{"value":1399,"limit":1000000},"postexpandincludesize":{"value":21317,"limit":2097152},"templateargumentsize":{"value":450,"limit":2097152},"expansiondepth":{"value":18,"limit":100},"expensivefunctioncount":{"value":0,"limit":500},"unstrip-depth":{"value":0,"limit":20},"unstrip-size":{"value":20787,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 145.223 1 -total"," 52.01% 75.537 1 Malline:Viitteet"," 35.09% 50.952 1 Malline:Commonscat"," 33.44% 48.561 1 Malline:Commons"," 31.90% 46.324 1 Malline:Sister_project"," 30.25% 43.933 1 Malline:Side_box"," 25.81% 37.483 20 Malline:Kirjaviite"," 24.16% 35.086 4 Malline:Wikidata"," 8.98% 13.038 8 Malline:Lehtiviite"," 4.36% 6.339 2 Malline:Verkkoviite"]},"scribunto":{"limitreport-timeusage":{"value":"0.035","limit":"10.000"},"limitreport-memusage":{"value":1381108,"limit":52428800}},"cachereport":{"origin":"mw-web.eqiad.main-745f94f9f8-w7sdn","timestamp":"20241120024759","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Eukleideen algoritmi","url":"https:\/\/fi.wikipedia.org\/wiki\/Eukleideen_algoritmi","sameAs":"http:\/\/www.wikidata.org\/entity\/Q230848","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q230848","author":{"@type":"Organization","name":"Wikimedia-hankkeiden muokkaajat"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2004-07-26T09:59:38Z","headline":"algoritmi suurimman yhteisen tekij\u00e4n laskemiseen"}</script> </body> </html>