CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-disabled skin-theme-clientpref-day vector-toc-available" lang="it" dir="ltr"> <head> <meta charset="UTF-8"> <title>Algoritmo di Euclide - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-disabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )itwikimwclientpreferences=([^;]+)/);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":"dmy","wgMonthNames":["","gennaio","febbraio","marzo","aprile","maggio","giugno","luglio","agosto","settembre","ottobre","novembre","dicembre"],"wgRequestId":"68819dd9-ea72-4df7-ad14-b42173f89619","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Algoritmo_di_Euclide","wgTitle":"Algoritmo di Euclide","wgCurRevisionId":141009238,"wgRevisionId":141009238,"wgArticleId":131343,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Controllare - informatica","Controllare - giugno 2015","P6706 letta da Wikidata","P9621 letta da Wikidata","P1417 letta da Wikidata","P3847 letta da Wikidata","P2812 letta da Wikidata","P7554 letta da Wikidata","Voci con codice GND","Voci non biografiche con codici di controllo di autorità","Pagine che utilizzano collegamenti magici ISBN","Algoritmi aritmetici","Euclide"],"wgPageViewLanguage":"it","wgPageContentLanguage":"it", "wgPageContentModel":"wikitext","wgRelevantPageName":"Algoritmo_di_Euclide","wgRelevantArticleId":131343,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"it","pageLanguageDir":"ltr","pageVariantFallbacks":"it"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":true,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":10000,"wgRelatedArticlesCompat":[],"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q230848","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform", "platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.gadget.coloriDarkMode-default":"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","ext.pygments":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","ext.pygments.view","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP", "ext.centralNotice.startUp","ext.gadget.MainPageWikiList","ext.gadget.stru-commonsupload","ext.gadget.HiddenCat","ext.gadget.ReferenceTooltips","ext.gadget.TitoloErrato","ext.gadget.NewSection","ext.gadget.RichiediRevisioneBozza","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.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","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=it&modules=ext.cite.styles%7Cext.math.styles%7Cext.pygments%2CwikimediaBadges%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=it&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=it&modules=ext.gadget.coloriDarkMode-default&only=styles&skin=vector-2022"> <link rel="stylesheet" href="/w/load.php?lang=it&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.5"> <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="Algoritmo di Euclide - 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="//it.m.wikipedia.org/wiki/Algoritmo_di_Euclide"> <link rel="alternate" type="application/x-wiki" title="Modifica" href="/w/index.php?title=Algoritmo_di_Euclide&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 (it)"> <link rel="EditURI" type="application/rsd+xml" href="//it.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://it.wikipedia.org/wiki/Algoritmo_di_Euclide"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.it"> <link rel="alternate" type="application/atom+xml" title="Feed Atom di Wikipedia" href="/w/index.php?title=Speciale:UltimeModifiche&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Algoritmo_di_Euclide rootpage-Algoritmo_di_Euclide skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Vai al contenuto</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Sito"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Menu principale" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" > Menu principale </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Menu principale</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">sposta nella barra laterale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">nascondi</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigazione </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Pagina_principale" title="Visita la pagina principale [z]" accesskey="z">Pagina principale</a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Speciale:UltimeModifiche" title="Elenco delle ultime modifiche del sito [r]" accesskey="r">Ultime modifiche</a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Speciale:PaginaCasuale" title="Mostra una pagina a caso [x]" accesskey="x">Una voce a caso</a></li><li id="n-nearby-pages-title" class="mw-list-item"><a href="/wiki/Speciale:NelleVicinanze">Nelle vicinanze</a></li><li id="n-vetrina" class="mw-list-item"><a href="/wiki/Wikipedia:Vetrina">Vetrina</a></li><li id="n-help" class="mw-list-item"><a href="/wiki/Aiuto:Aiuto" title="Pagine di aiuto">Aiuto</a></li><li id="n-Sportello-informazioni" class="mw-list-item"><a href="/wiki/Aiuto:Sportello_informazioni">Sportello informazioni</a></li> </ul> </div> </div> <div id="p-Comunità" class="vector-menu mw-portlet mw-portlet-Comunità" > <div class="vector-menu-heading"> Comunità </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-portal" class="mw-list-item"><a href="/wiki/Portale:Comunit%C3%A0" title="Descrizione del progetto, cosa puoi fare, dove trovare le cose">Portale Comunità</a></li><li id="n-villagepump" class="mw-list-item"><a href="/wiki/Wikipedia:Bar">Bar</a></li><li id="n-wikipediano" class="mw-list-item"><a href="/wiki/Wikipedia:Wikipediano">Il Wikipediano</a></li><li id="n-contactpage" class="mw-list-item"><a href="/wiki/Wikipedia:Contatti">Contatti</a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Pagina_principale" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="L'enciclopedia libera" src="/static/images/mobile/copyright/wikipedia-tagline-it.svg" width="120" height="13" style="width: 7.5em; height: 0.8125em;"> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Speciale:Ricerca" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Cerca in Wikipedia [f]" accesskey="f"> Ricerca </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Cerca in Wikipedia" aria-label="Cerca in Wikipedia" autocapitalize="sentences" title="Cerca in Wikipedia [f]" accesskey="f" id="searchInput" > </div> <input type="hidden" name="title" value="Speciale:Ricerca"> </div> <button class="cdx-button cdx-search-input__end-button">Ricerca</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Strumenti personali"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Aspetto"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Modifica la dimensione, la larghezza e il colore del testo" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Aspetto" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" > Aspetto </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="//donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_it.wikipedia.org&uselang=it" class="">Fai una donazione</a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Speciale:CreaUtenza&returnto=Algoritmo+di+Euclide" title="Si consiglia di registrarsi e di effettuare l'accesso, anche se non è obbligatorio" class="">registrati</a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Speciale:Entra&returnto=Algoritmo+di+Euclide" title="Si consiglia di effettuare l'accesso, anche se non è obbligatorio [o]" accesskey="o" class="">entra</a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Altre opzioni" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Strumenti personali" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" > Strumenti personali </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="Menu utente" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="//donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_it.wikipedia.org&uselang=it">Fai una donazione</a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Speciale:CreaUtenza&returnto=Algoritmo+di+Euclide" title="Si consiglia di registrarsi e di effettuare l'accesso, anche se non è obbligatorio"> registrati</a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Speciale:Entra&returnto=Algoritmo+di+Euclide" title="Si consiglia di effettuare l'accesso, anche se non è obbligatorio [o]" accesskey="o"> entra</a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pagine per utenti anonimi <a href="/wiki/Aiuto:Benvenuto" aria-label="Ulteriori informazioni sulla contribuzione">ulteriori informazioni</a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Speciale:MieiContributi" title="Un elenco delle modifiche fatte da questo indirizzo IP [y]" accesskey="y">contributi</a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Speciale:MieDiscussioni" title="Discussioni sulle modifiche fatte da questo indirizzo IP [n]" accesskey="n">discussioni</a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Sito"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Indice" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Indice</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">sposta nella barra laterale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">nascondi</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">Inizio</div> </a> </li> <li id="toc-Pseudocodice" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Pseudocodice"> <div class="vector-toc-text"> 1 Pseudocodice </div> </a> <ul id="toc-Pseudocodice-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Dimostrazione_della_correttezza_dell'algoritmo" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Dimostrazione_della_correttezza_dell'algoritmo"> <div class="vector-toc-text"> 2 Dimostrazione della correttezza dell'algoritmo </div> </a> <ul id="toc-Dimostrazione_della_correttezza_dell'algoritmo-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Tempo_di_calcolo" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Tempo_di_calcolo"> <div class="vector-toc-text"> 3 Tempo di calcolo </div> </a> <ul id="toc-Tempo_di_calcolo-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Frazioni_continue" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Frazioni_continue"> <div class="vector-toc-text"> 4 Frazioni continue </div> </a> <ul id="toc-Frazioni_continue-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Codici" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Codici"> <div class="vector-toc-text"> 5 Codici </div> </a> <ul id="toc-Codici-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Note" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Note"> <div class="vector-toc-text"> 6 Note </div> </a> <ul id="toc-Note-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Bibliografia" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Bibliografia"> <div class="vector-toc-text"> 7 Bibliografia </div> </a> <ul id="toc-Bibliografia-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Voci_correlate" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Voci_correlate"> <div class="vector-toc-text"> 8 Voci correlate </div> </a> <ul id="toc-Voci_correlate-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Altri_progetti" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Altri_progetti"> <div class="vector-toc-text"> 9 Altri progetti </div> </a> <ul id="toc-Altri_progetti-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Collegamenti_esterni" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Collegamenti_esterni"> <div class="vector-toc-text"> 10 Collegamenti esterni </div> </a> <ul id="toc-Collegamenti_esterni-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Indice" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Mostra/Nascondi l'indice" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" > Mostra/Nascondi l'indice </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading">Algoritmo di Euclide</h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Vai a una voce in un'altra lingua. Disponibile in 58 lingue" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-58" aria-hidden="true" > 58 lingue </label> <div class="vector-dropdown-content"> <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="خوارزمية أقليدس - arabo" lang="ar" hreflang="ar" data-title="خوارزمية أقليدس" data-language-autonym="العربية" data-language-local-name="arabo" 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 - asturiano" lang="ast" hreflang="ast" data-title="Algoritmu d'Euclides" data-language-autonym="Asturianu" data-language-local-name="asturiano" 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 - azerbaigiano" lang="az" hreflang="az" data-title="Evklid alqoritmi" data-language-autonym="Azərbaycanca" data-language-local-name="azerbaigiano" class="interlanguage-link-target">Azərbaycanca</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="Евклид алгоритмы - baschiro" lang="ba" hreflang="ba" data-title="Евклид алгоритмы" data-language-autonym="Башҡортса" data-language-local-name="baschiro" 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="Алгарытм Эўкліда - bielorusso" lang="be" hreflang="be" data-title="Алгарытм Эўкліда" data-language-autonym="Беларуская" data-language-local-name="bielorusso" 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="Алгоритъм на Евклид - bulgaro" lang="bg" hreflang="bg" data-title="Алгоритъм на Евклид" data-language-autonym="Български" data-language-local-name="bulgaro" class="interlanguage-link-target">Български</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="ইউক্লিডীয় এলগরিদম - bengalese" lang="bn" hreflang="bn" data-title="ইউক্লিডীয় এলগরিদম" data-language-autonym="বাংলা" data-language-local-name="bengalese" 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 - catalano" lang="ca" hreflang="ca" data-title="Algorisme d'Euclides" data-language-autonym="Català" data-language-local-name="catalano" class="interlanguage-link-target">Català</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="ئەلگۆریتمی ئیقلیدس - curdo centrale" lang="ckb" hreflang="ckb" data-title="ئەلگۆریتمی ئیقلیدس" data-language-autonym="کوردی" data-language-local-name="curdo centrale" class="interlanguage-link-target">کوردی</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 - ceco" lang="cs" hreflang="cs" data-title="Eukleidův algoritmus" data-language-autonym="Čeština" data-language-local-name="ceco" 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 - gallese" lang="cy" hreflang="cy" data-title="Algorithm Ewclidaidd" data-language-autonym="Cymraeg" data-language-local-name="gallese" 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 - danese" lang="da" hreflang="da" data-title="Euklids algoritme" data-language-autonym="Dansk" data-language-local-name="danese" 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 - tedesco" lang="de" hreflang="de" data-title="Euklidischer Algorithmus" data-language-autonym="Deutsch" data-language-local-name="tedesco" 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="Αλγόριθμος του Ευκλείδη - greco" lang="el" hreflang="el" data-title="Αλγόριθμος του Ευκλείδη" data-language-autonym="Ελληνικά" data-language-local-name="greco" class="interlanguage-link-target">Ελληνικά</a></li><li class="interlanguage-link interwiki-en badge-Q17437796 badge-featuredarticle mw-list-item" title="voce in vetrina"><a href="https://en.wikipedia.org/wiki/Euclidean_algorithm" title="Euclidean algorithm - inglese" lang="en" hreflang="en" data-title="Euclidean algorithm" data-language-autonym="English" data-language-local-name="inglese" class="interlanguage-link-target">English</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-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Algoritmo_de_Euclides" title="Algoritmo de Euclides - spagnolo" lang="es" hreflang="es" data-title="Algoritmo de Euclides" data-language-autonym="Español" data-language-local-name="spagnolo" class="interlanguage-link-target">Español</a></li><li class="interlanguage-link interwiki-eu mw-list-item"><a href="https://eu.wikipedia.org/wiki/Euklidesen_algoritmo" title="Euklidesen algoritmo - basco" lang="eu" hreflang="eu" data-title="Euklidesen algoritmo" data-language-autonym="Euskara" data-language-local-name="basco" 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="الگوریتم اقلیدس - persiano" lang="fa" hreflang="fa" data-title="الگوریتم اقلیدس" data-language-autonym="فارسی" data-language-local-name="persiano" class="interlanguage-link-target">فارسی</a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/Eukleideen_algoritmi" title="Eukleideen algoritmi - finlandese" lang="fi" hreflang="fi" data-title="Eukleideen algoritmi" data-language-autonym="Suomi" data-language-local-name="finlandese" class="interlanguage-link-target">Suomi</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 - francese" lang="fr" hreflang="fr" data-title="Algorithme d'Euclide" data-language-autonym="Français" data-language-local-name="francese" 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 - galiziano" lang="gl" hreflang="gl" data-title="Algoritmo de Euclides" data-language-autonym="Galego" data-language-local-name="galiziano" class="interlanguage-link-target">Galego</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="אלגוריתם אוקלידס - ebraico" lang="he" hreflang="he" data-title="אלגוריתם אוקלידס" data-language-autonym="עברית" data-language-local-name="ebraico" 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 - croato" lang="hr" hreflang="hr" data-title="Euklidov algoritam" data-language-autonym="Hrvatski" data-language-local-name="croato" class="interlanguage-link-target">Hrvatski</a></li><li class="interlanguage-link interwiki-hu badge-Q17437796 badge-featuredarticle mw-list-item" title="voce in vetrina"><a href="https://hu.wikipedia.org/wiki/Euklideszi_algoritmus" title="Euklideszi algoritmus - ungherese" lang="hu" hreflang="hu" data-title="Euklideszi algoritmus" data-language-autonym="Magyar" data-language-local-name="ungherese" class="interlanguage-link-target">Magyar</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="Էվկլիդեսի ալգորիթմ - armeno" lang="hy" hreflang="hy" data-title="Էվկլիդեսի ալգորիթմ" data-language-autonym="Հայերեն" data-language-local-name="armeno" class="interlanguage-link-target">Հայերեն</a></li><li class="interlanguage-link interwiki-id mw-list-item"><a href="https://id.wikipedia.org/wiki/Algoritma_Euklides" title="Algoritma Euklides - indonesiano" lang="id" hreflang="id" data-title="Algoritma Euklides" data-language-autonym="Bahasa Indonesia" data-language-local-name="indonesiano" class="interlanguage-link-target">Bahasa Indonesia</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="ユークリッドの互除法 - giapponese" lang="ja" hreflang="ja" data-title="ユークリッドの互除法" data-language-autonym="日本語" data-language-local-name="giapponese" class="interlanguage-link-target">日本語</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="유클리드 호제법 - coreano" lang="ko" hreflang="ko" data-title="유클리드 호제법" data-language-autonym="한국어" data-language-local-name="coreano" 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 - latino" lang="la" hreflang="la" data-title="Algorithmus Euclidis" data-language-autonym="Latina" data-language-local-name="latino" class="interlanguage-link-target">Latina</a></li><li class="interlanguage-link interwiki-lt mw-list-item"><a href="https://lt.wikipedia.org/wiki/Euklido_algoritmas" title="Euklido algoritmas - lituano" lang="lt" hreflang="lt" data-title="Euklido algoritmas" data-language-autonym="Lietuvių" data-language-local-name="lituano" class="interlanguage-link-target">Lietuvių</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 - lettone" lang="lv" hreflang="lv" data-title="Eiklīda algoritms" data-language-autonym="Latviešu" data-language-local-name="lettone" class="interlanguage-link-target">Latviešu</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="Евклидов алгоритам - macedone" lang="mk" hreflang="mk" data-title="Евклидов алгоритам" data-language-autonym="Македонски" data-language-local-name="macedone" 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="യൂക്ലിഡിന്റെ അൽഗൊരിതം - malayalam" lang="ml" hreflang="ml" data-title="യൂക്ലിഡിന്റെ അൽഗൊരിതം" data-language-autonym="മലയാളം" data-language-local-name="malayalam" 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="Евклидийн алгоритм - mongolo" lang="mn" hreflang="mn" data-title="Евклидийн алгоритм" data-language-autonym="Монгол" data-language-local-name="mongolo" class="interlanguage-link-target">Монгол</a></li><li class="interlanguage-link interwiki-nds mw-list-item"><a href="https://nds.wikipedia.org/wiki/Euklidsch_Algorithmus" title="Euklidsch Algorithmus - basso tedesco" lang="nds" hreflang="nds" data-title="Euklidsch Algorithmus" data-language-autonym="Plattdüütsch" data-language-local-name="basso tedesco" class="interlanguage-link-target">Plattdüütsch</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 - olandese" lang="nl" hreflang="nl" data-title="Algoritme van Euclides" data-language-autonym="Nederlands" data-language-local-name="olandese" class="interlanguage-link-target">Nederlands</a></li><li class="interlanguage-link interwiki-nn mw-list-item"><a href="https://nn.wikipedia.org/wiki/Euklidsk_algoritme" title="Euklidsk algoritme - norvegese nynorsk" lang="nn" hreflang="nn" data-title="Euklidsk algoritme" data-language-autonym="Norsk nynorsk" data-language-local-name="norvegese nynorsk" class="interlanguage-link-target">Norsk nynorsk</a></li><li class="interlanguage-link interwiki-no mw-list-item"><a href="https://no.wikipedia.org/wiki/Euklids_algoritme" title="Euklids algoritme - norvegese bokmål" lang="nb" hreflang="nb" data-title="Euklids algoritme" data-language-autonym="Norsk bokmål" data-language-local-name="norvegese bokmål" class="interlanguage-link-target">Norsk bokmål</a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Algorytm_Euklidesa" title="Algorytm Euklidesa - polacco" lang="pl" hreflang="pl" data-title="Algorytm Euklidesa" data-language-autonym="Polski" data-language-local-name="polacco" class="interlanguage-link-target">Polski</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 - piemontese" lang="pms" hreflang="pms" data-title="Algoritm d'Euclid" data-language-autonym="Piemontèis" data-language-local-name="piemontese" class="interlanguage-link-target">Piemontèis</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 - portoghese" lang="pt" hreflang="pt" data-title="Algoritmo de Euclides" data-language-autonym="Português" data-language-local-name="portoghese" class="interlanguage-link-target">Português</a></li><li class="interlanguage-link interwiki-ro badge-Q17437796 badge-featuredarticle mw-list-item" title="voce in vetrina"><a href="https://ro.wikipedia.org/wiki/Algoritmul_lui_Euclid" title="Algoritmul lui Euclid - rumeno" lang="ro" hreflang="ro" data-title="Algoritmul lui Euclid" data-language-autonym="Română" data-language-local-name="rumeno" 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="Алгоритм Евклида - russo" lang="ru" hreflang="ru" data-title="Алгоритм Евклида" data-language-autonym="Русский" data-language-local-name="russo" class="interlanguage-link-target">Русский</a></li><li class="interlanguage-link interwiki-sh mw-list-item"><a href="https://sh.wikipedia.org/wiki/Euklidov_algoritam" title="Euklidov algoritam - serbo-croato" lang="sh" hreflang="sh" data-title="Euklidov algoritam" data-language-autonym="Srpskohrvatski / српскохрватски" data-language-local-name="serbo-croato" class="interlanguage-link-target">Srpskohrvatski / српскохрватски</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 - slovacco" lang="sk" hreflang="sk" data-title="Euklidov algoritmus" data-language-autonym="Slovenčina" data-language-local-name="slovacco" 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 - sloveno" lang="sl" hreflang="sl" data-title="Evklidov algoritem" data-language-autonym="Slovenščina" data-language-local-name="sloveno" class="interlanguage-link-target">Slovenščina</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="Еуклидов алгоритам - serbo" lang="sr" hreflang="sr" data-title="Еуклидов алгоритам" data-language-autonym="Српски / srpski" data-language-local-name="serbo" class="interlanguage-link-target">Српски / srpski</a></li><li class="interlanguage-link interwiki-sv mw-list-item"><a href="https://sv.wikipedia.org/wiki/Euklides_algoritm" title="Euklides algoritm - svedese" lang="sv" hreflang="sv" data-title="Euklides algoritm" data-language-autonym="Svenska" data-language-local-name="svedese" 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="யூக்ளிடிய படிமுறைத்தீர்வு - tamil" lang="ta" hreflang="ta" data-title="யூக்ளிடிய படிமுறைத்தீர்வு" data-language-autonym="தமிழ்" data-language-local-name="tamil" 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="ขั้นตอนวิธีแบบยุคลิด - thailandese" lang="th" hreflang="th" data-title="ขั้นตอนวิธีแบบยุคลิด" data-language-autonym="ไทย" data-language-local-name="thailandese" class="interlanguage-link-target">ไทย</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ı - turco" lang="tr" hreflang="tr" data-title="Öklid algoritması" data-language-autonym="Türkçe" data-language-local-name="turco" 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="Алгоритм Евкліда - ucraino" lang="uk" hreflang="uk" data-title="Алгоритм Евкліда" data-language-autonym="Українська" data-language-local-name="ucraino" 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 - vietnamita" lang="vi" hreflang="vi" data-title="Giải thuật Euclid" data-language-autonym="Tiếng Việt" data-language-local-name="vietnamita" class="interlanguage-link-target">Tiếng Việt</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" lang="wuu" hreflang="wuu" data-title="辗转相除法" data-language-autonym="吴语" data-language-local-name="wu" class="interlanguage-link-target">吴语</a></li><li class="interlanguage-link interwiki-zh badge-Q17437798 badge-goodarticle mw-list-item" title="voce di qualità"><a href="https://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95" title="輾轉相除法 - cinese" lang="zh" hreflang="zh" data-title="輾轉相除法" data-language-autonym="中文" data-language-local-name="cinese" 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="輾轉相除法 - cantonese" lang="yue" hreflang="yue" data-title="輾轉相除法" data-language-autonym="粵語" data-language-local-name="cantonese" 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="Modifica collegamenti interlinguistici" class="wbc-editpage">Modifica collegamenti</a></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespace"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Algoritmo_di_Euclide" title="Vedi la voce [c]" accesskey="c">Voce</a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Discussione:Algoritmo_di_Euclide" rel="discussion" title="Vedi le discussioni relative a questa pagina [t]" accesskey="t">Discussione</a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Cambia versione linguistica" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" >italiano </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Visite"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Algoritmo_di_Euclide">Leggi</a></li><li id="ca-ve-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Algoritmo_di_Euclide&veaction=edit" title="Modifica questa pagina [v]" accesskey="v">Modifica</a></li><li id="ca-edit" class="collapsible vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Algoritmo_di_Euclide&action=edit" title="Modifica il wikitesto di questa pagina [e]" accesskey="e">Modifica wikitesto</a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Algoritmo_di_Euclide&action=history" title="Versioni precedenti di questa pagina [h]" accesskey="h">Cronologia</a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Strumenti pagine"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Strumenti" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" >Strumenti </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Strumenti</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">sposta nella barra laterale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">nascondi</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="Altre opzioni" > <div class="vector-menu-heading"> Azioni </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Algoritmo_di_Euclide">Leggi</a></li><li id="ca-more-ve-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Algoritmo_di_Euclide&veaction=edit" title="Modifica questa pagina [v]" accesskey="v">Modifica</a></li><li id="ca-more-edit" class="collapsible vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Algoritmo_di_Euclide&action=edit" title="Modifica il wikitesto di questa pagina [e]" accesskey="e">Modifica wikitesto</a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Algoritmo_di_Euclide&action=history">Cronologia</a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> Generale </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Speciale:PuntanoQui/Algoritmo_di_Euclide" title="Elenco di tutte le pagine che sono collegate a questa [j]" accesskey="j">Puntano qui</a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Speciale:ModificheCorrelate/Algoritmo_di_Euclide" rel="nofollow" title="Elenco delle ultime modifiche alle pagine collegate a questa [k]" accesskey="k">Modifiche correlate</a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Speciale:PagineSpeciali" title="Elenco di tutte le pagine speciali [q]" accesskey="q">Pagine speciali</a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Algoritmo_di_Euclide&oldid=141009238" title="Collegamento permanente a questa versione di questa pagina">Link permanente</a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Algoritmo_di_Euclide&action=info" title="Ulteriori informazioni su questa pagina">Informazioni pagina</a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Speciale:Cita&page=Algoritmo_di_Euclide&id=141009238&wpFormIdentifier=titleform" title="Informazioni su come citare questa pagina">Cita questa voce</a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Speciale:UrlShortener&url=https%3A%2F%2Fit.wikipedia.org%2Fwiki%2FAlgoritmo_di_Euclide">Ottieni URL breve</a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Speciale:QrCode&url=https%3A%2F%2Fit.wikipedia.org%2Fwiki%2FAlgoritmo_di_Euclide">Scarica codice QR</a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Stampa/esporta </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-create_a_book" class="mw-list-item"><a href="/w/index.php?title=Speciale:Libro&bookcmd=book_creator&referer=Algoritmo+di+Euclide">Crea un libro</a></li><li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Speciale:DownloadAsPdf&page=Algoritmo_di_Euclide&action=show-download-screen">Scarica come PDF</a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Algoritmo_di_Euclide&printable=yes" title="Versione stampabile di questa pagina [p]" accesskey="p">Versione stampabile</a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In altri progetti </div> <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 class="wb-otherproject-link wb-otherproject-wikibooks mw-list-item"><a href="https://it.wikibooks.org/wiki/Implementazioni_di_algoritmi/Algoritmo_di_Euclide" hreflang="it">Wikibooks</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="Collegamento all'elemento connesso dell'archivio dati [g]" accesskey="g">Elemento Wikidata</a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Strumenti pagine"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Aspetto"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Aspetto</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">sposta nella barra laterale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">nascondi</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">Da Wikipedia, l'enciclopedia libera.</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="it" dir="ltr">L'algoritmo di Euclide è un <a href="/wiki/Algoritmo" title="Algoritmo">algoritmo</a> per trovare il <a href="/wiki/Massimo_comun_divisore" title="Massimo comun divisore">massimo comune divisore</a> (indicato di seguito con MCD) tra due <a href="/wiki/Numero_intero" title="Numero intero">numeri interi</a>. È uno degli algoritmi più antichi conosciuti, essendo presente negli <a href="/wiki/Elementi_(Euclide)" title="Elementi (Euclide)">Elementi</a> di <a href="/wiki/Euclide" title="Euclide">Euclide</a><a href="#cite_note-1">[1]</a> intorno al <a href="/wiki/300_a.C." title="300 a.C.">300 a.C.</a>; tuttavia, probabilmente l'algoritmo non è stato scoperto da <a href="/wiki/Euclide" title="Euclide">Euclide</a>, ma potrebbe essere stato conosciuto anche 200 anni prima. Certamente era conosciuto da <a href="/wiki/Eudosso_di_Cnido" title="Eudosso di Cnido">Eudosso di Cnido</a> intorno al <a href="/wiki/375_a.C." title="375 a.C.">375 a.C.</a>; <a href="/wiki/Aristotele" title="Aristotele">Aristotele</a> (intorno al <a href="/wiki/330_a.C." title="330 a.C.">330 a.C.</a>) ne ha fatto cenno ne <a href="/wiki/Topici" title="Topici">I topici</a>, 158b, 29-35. L'algoritmo non richiede la <a href="/wiki/Fattorizzazione" title="Fattorizzazione">fattorizzazione</a> dei due interi. Dati due <a href="/wiki/Numero_naturale" title="Numero naturale">numeri naturali</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd2487510aa438433a2579450ab2b3d557e5edc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}"> e <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f11423fbb2e967f986e36804a8ae4271734917c3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}">, l'algoritmo prevede che si controlli se <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f11423fbb2e967f986e36804a8ae4271734917c3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}"> è zero. Se lo è, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd2487510aa438433a2579450ab2b3d557e5edc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}"> è il MCD. Se non lo è, si deve dividere <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {a}{b}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>a</mi> <mi>b</mi> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {a}{b}}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9fbb66e57f89debc3cde3213de12228971148a93" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:2.066ex; height:4.843ex;" alt="{\displaystyle {\frac {a}{b}}}"> e definire <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>r</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0d1ecb613aa2984f0576f70f86650b7c2a132538" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}"> come il resto della divisione (operazione indicata con "a modulo b" più sotto). Se <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r=0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>r</mi> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r=0}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/894a83e863728b4ee2e12f3a999a09f5f2bf1c89" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.31ex; height:2.176ex;" alt="{\displaystyle r=0}"> allora si può affermare che <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f11423fbb2e967f986e36804a8ae4271734917c3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}"> è il MCD cercato, altrimenti occorre assegnare <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a'=b}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>a</mi> <mo>′</mo> </msup> <mo>=</mo> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a'=b}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/10cc2ffb4669ba76c2f6df4633a4e8861e0dd3a2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.011ex; height:2.509ex;" alt="{\displaystyle a'=b}"> e <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b'=r}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>b</mi> <mo>′</mo> </msup> <mo>=</mo> <mi>r</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b'=r}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f06aac0f52c811c63e25edd5d2fd65468dd51e47" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.829ex; height:2.509ex;" alt="{\displaystyle b'=r}"> e ripetere nuovamente la divisione. L'algoritmo può essere espresso in modo naturale utilizzando la <a href="/wiki/Algoritmo_ricorsivo#Ricorsione_in_coda" title="Algoritmo ricorsivo">ricorsione in coda</a>. Tenendo nota dei quozienti ottenuti durante lo svolgimento dell'algoritmo, si possono determinare due interi <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>p</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle p}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}"> e <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>q</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle q}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/06809d64fa7c817ffc7e323f85997f783dbdf71d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}"> tali che <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ap+bq=MCD(a,b)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mi>p</mi> <mo>+</mo> <mi>b</mi> <mi>q</mi> <mo>=</mo> <mi>M</mi> <mi>C</mi> <mi>D</mi> <mo stretchy="false">(</mo> <mi>a</mi> <mo>,</mo> <mi>b</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle ap+bq=MCD(a,b)}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6a3953f446f2b64b1f5ee7b3574fa7676ede05cd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.609ex; height:2.843ex;" alt="{\displaystyle ap+bq=MCD(a,b)}">. Questo è noto con il nome di <a href="/wiki/Algoritmo_esteso_di_Euclide" title="Algoritmo esteso di Euclide">algoritmo di Euclide esteso</a>. Questi algoritmi possono essere usati, oltre che con i <a href="/wiki/Numeri_interi" class="mw-redirect" title="Numeri interi">numeri interi</a>, in ogni contesto in cui è possibile eseguire la divisione col resto. Ad esempio, l'algoritmo funziona per i <a href="/wiki/Polinomio" title="Polinomio">polinomi</a> ad una indeterminata su un <a href="/wiki/Campo_(matematica)" title="Campo (matematica)">campo</a> K, o polinomi omogenei a due indeterminate su un campo, o gli <a href="/wiki/Intero_gaussiano" class="mw-redirect" title="Intero gaussiano">interi gaussiani</a>. Un oggetto algebrico in cui è possibile eseguire la divisione col resto è chiamato <a href="/wiki/Anello_euclideo" class="mw-redirect" title="Anello euclideo">anello euclideo</a>. Euclide originariamente formulò il problema geometricamente, per trovare una "misura" comune per la lunghezza di due segmenti, e il suo algoritmo procedeva sottraendo ripetutamente il più corto dal più lungo. Questo procedimento è equivalente alla implementazione seguente, che è molto meno efficiente del metodo indicato sopra. <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Pseudocodice">Pseudocodice</h2>[<a href="/w/index.php?title=Algoritmo_di_Euclide&veaction=edit&section=1" title="Modifica la sezione Pseudocodice" class="mw-editsection-visualeditor">modifica</a> | <a href="/w/index.php?title=Algoritmo_di_Euclide&action=edit&section=1" title="Edit section's source code: Pseudocodice">modifica wikitesto</a>]</div> Una scrittura in <a href="/wiki/Pseudocodice" title="Pseudocodice">pseudocodice</a> dell'algoritmo (in cui «mod» indica il resto della divisione intera) è la seguente<a href="#cite_note-2">[2]</a>: <pre>inizia leggi (a, b) mentre b > 0 fai: r <- mod(a, b) a <- b b <- r fine ciclo scrivi (a, "è il massimo comun divisore cercato") finisci. </pre> <div class="mw-heading mw-heading2"><h2 id="Dimostrazione_della_correttezza_dell'algoritmo">Dimostrazione della correttezza dell'algoritmo</h2>[<a href="/w/index.php?title=Algoritmo_di_Euclide&veaction=edit&section=2" title="Modifica la sezione Dimostrazione della correttezza dell'algoritmo" class="mw-editsection-visualeditor">modifica</a> | <a href="/w/index.php?title=Algoritmo_di_Euclide&action=edit&section=2" title="Edit section's source code: Dimostrazione della correttezza dell'algoritmo">modifica wikitesto</a>]</div> Siano <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd2487510aa438433a2579450ab2b3d557e5edc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}"> e <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f11423fbb2e967f986e36804a8ae4271734917c3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}"> interi positivi assegnati, e sia <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e85ff03cbe0c7341af6b982e47e9f90d235c66ab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}"> il loro MCD. Definiamo la successione di ricorrenza corrispondente ai passi dell'algoritmo di Euclide: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{0}=a}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>=</mo> <mi>a</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{0}=a}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/da98dae3029aae486772cfef5203856a2101d305" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.612ex; height:2.009ex;" alt="{\displaystyle a_{0}=a}">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{0}=b}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>=</mo> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b_{0}=b}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6631bc7d9c3da1239c5b85682ac87d3e698221a0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.148ex; height:2.509ex;" alt="{\displaystyle b_{0}=b}">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{n+1}=b_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{n+1}=b_{n}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2867332a14ead05dd24ef4684b270e1c9e29333d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.863ex; height:2.509ex;" alt="{\displaystyle a_{n+1}=b_{n}}">, e <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{n+1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b_{n+1}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3f50a7ff414dda7546b9bd2dde97c553084ca542" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.317ex; height:2.509ex;" alt="{\displaystyle b_{n+1}}"> è il resto della divisione di <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{n}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/790f9209748c2dca7ed7b81932c37c02af1dbc31" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.448ex; height:2.009ex;" alt="{\displaystyle a_{n}}"> per <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b_{n}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/28e2d72f6dd9375c8f1f59f1effd9b4e5492ac97" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.216ex; height:2.509ex;" alt="{\displaystyle b_{n}}">, cioè <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{n}=q_{n}b_{n}+b_{n+1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msub> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>+</mo> <msub> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{n}=q_{n}b_{n}+b_{n+1}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4b7faf8bd0eed201e78a96ff7ef4b75c849712d4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.175ex; height:2.509ex;" alt="{\displaystyle a_{n}=q_{n}b_{n}+b_{n+1}}">. Per definizione di resto nella divisione, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{n+1}<b_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo><</mo> <msub> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b_{n+1}<b_{n}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/33a819c330f81578556e74e54045331db3154613" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.631ex; height:2.509ex;" alt="{\displaystyle b_{n+1}<b_{n}}"> per ogni <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}">, quindi la successione dei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b_{n}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/28e2d72f6dd9375c8f1f59f1effd9b4e5492ac97" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.216ex; height:2.509ex;" alt="{\displaystyle b_{n}}"> è strettamente decrescente, e quindi esiste un <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"> tale che <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{N}=0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>N</mi> </mrow> </msub> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b_{N}=0}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/74d7bd2dbb8c8c46ca960ba2875ecf426e155e7a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.95ex; height:2.509ex;" alt="{\displaystyle b_{N}=0}">. Vogliamo dimostrare che <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d=a_{N}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> <mo>=</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>N</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d=a_{N}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2b5c5c234bd463a70efa32c4f086b79653e7e650" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.236ex; height:2.509ex;" alt="{\displaystyle d=a_{N}}">. Infatti, per induzione si ha per ogni <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"> che <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d|a_{n}=b_{n-1}=a_{n-2}-q_{n-2}b_{n-2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>a</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> <mo>−</mo> <mn>2</mn> </mrow> </msub> <msub> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d|a_{n}=b_{n-1}=a_{n-2}-q_{n-2}b_{n-2}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/36483fb50fddd096a7b94aaad408959463af229f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.886ex; height:2.843ex;" alt="{\displaystyle d|a_{n}=b_{n-1}=a_{n-2}-q_{n-2}b_{n-2}}">. Inoltre, sempre per induzione, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{N}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>N</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{N}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/76605d677ea220481dc9cae2c49924c6d0ef82b6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.921ex; height:2.009ex;" alt="{\displaystyle a_{N}}"> divide <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{n}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/790f9209748c2dca7ed7b81932c37c02af1dbc31" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.448ex; height:2.009ex;" alt="{\displaystyle a_{n}}"> per ogni <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\leq N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>≤</mo> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n\leq N}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/26619ac273b9b4a895a2f2bd8542bbf7fe40a52f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.557ex; height:2.343ex;" alt="{\displaystyle n\leq N}">, quindi divide anche <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>b</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b_{n}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/28e2d72f6dd9375c8f1f59f1effd9b4e5492ac97" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.216ex; height:2.509ex;" alt="{\displaystyle b_{n}}"> per ogni <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n<N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo><</mo> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n<N}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/54392dd41def1556b00dbdf7b9108dfa7e9216d6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.557ex; height:2.176ex;" alt="{\displaystyle n<N}">, quindi <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{N}=d}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>N</mi> </mrow> </msub> <mo>=</mo> <mi>d</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{N}=d}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5ec8f9e013152b61954fd434fbb8be39f2bbe64b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.236ex; height:2.509ex;" alt="{\displaystyle a_{N}=d}">. <div class="mw-heading mw-heading2"><h2 id="Tempo_di_calcolo">Tempo di calcolo</h2>[<a href="/w/index.php?title=Algoritmo_di_Euclide&veaction=edit&section=3" title="Modifica la sezione Tempo di calcolo" class="mw-editsection-visualeditor">modifica</a> | <a href="/w/index.php?title=Algoritmo_di_Euclide&action=edit&section=3" title="Edit section's source code: Tempo di calcolo">modifica wikitesto</a>]</div> Quando si analizza il tempo di calcolo dell'algoritmo di Euclide, si trova che i valori di input che richiedono il maggior numero di divisioni sono due successivi <a href="/wiki/Numeri_di_Fibonacci" class="mw-redirect" title="Numeri di Fibonacci">numeri di Fibonacci</a>, e il caso peggiore richiede <a href="/wiki/O-grande" title="O-grande">O(n)</a> divisioni, dove <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"> è il numero di cifre nell'input. Occorre anche notare che le divisioni non sono operazioni atomiche (se i numeri sono più grandi della dimensione naturale delle operazioni aritmetiche del computer), visto che la dimensione degli operandi può essere di <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"> cifre. Allora il tempo di calcolo reale è quindi <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6cd9594a16cb898b8f2a2dff9227a385ec183392" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}">. Questo tempo è comunque considerevolmente migliore rispetto all'algoritmo euclideo originale, in cui l'operazione di modulo è effettuata mediante ripetute sottrazioni in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(2^{n})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(2^{n})}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d4b1a4ff0bc4f81ebf79f28260c6fb54ee08ff8d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.964ex; height:2.843ex;" alt="{\displaystyle O(2^{n})}"> passi. Di conseguenza, questa versione dell'algoritmo richiede un tempo pari a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n2^{n})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n2^{n})}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9c02f556173ce8363d5e2b411cdb57ee5d9c9646" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.358ex; height:2.843ex;" alt="{\displaystyle O(n2^{n})}"> per numeri con <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"> cifre, o <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(m\log m)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>m</mi> <mi>log</mi> <mo>⁡</mo> <mi>m</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(m\log m)}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2e354b25b1bb164da4994cf682e10f4d5abf4ab4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.409ex; height:2.843ex;" alt="{\displaystyle O(m\log m)}"> per il numero <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>m</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle m}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}">. L'algoritmo di Euclide è ampiamente usato nella pratica, specialmente per numeri piccoli, grazie alla sua semplicità. Un algoritmo alternativo, l'algoritmo del MCD binario, utilizza la <a href="/wiki/Sistema_numerico_binario" title="Sistema numerico binario">rappresentazione binaria</a> dei computer per evitare le divisioni e quindi aumentare l'efficienza, sebbene anch'esso sia dell'ordine di <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n^{2})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(n^{2})}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6cd9594a16cb898b8f2a2dff9227a385ec183392" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.032ex; height:3.176ex;" alt="{\displaystyle O(n^{2})}">: infatti su molte macchine reali permette di diminuire le costanti nascoste nella notazione "O grande". <div class="mw-heading mw-heading2"><h2 id="Frazioni_continue">Frazioni continue</h2>[<a href="/w/index.php?title=Algoritmo_di_Euclide&veaction=edit&section=4" title="Modifica la sezione Frazioni continue" class="mw-editsection-visualeditor">modifica</a> | <a href="/w/index.php?title=Algoritmo_di_Euclide&action=edit&section=4" title="Edit section's source code: Frazioni continue">modifica wikitesto</a>]</div> I quozienti che compaiono quando l'algoritmo euclideo viene applicato ai valori di input <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd2487510aa438433a2579450ab2b3d557e5edc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}"> e <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f11423fbb2e967f986e36804a8ae4271734917c3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}"> sono proprio i numeri che compaiono nella rappresentazione in <a href="/wiki/Frazione_continua" title="Frazione continua">frazione continua</a> della frazione <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {a}{b}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>a</mi> <mi>b</mi> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {a}{b}}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9fbb66e57f89debc3cde3213de12228971148a93" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:2.066ex; height:4.843ex;" alt="{\displaystyle {\frac {a}{b}}}">. Si prenda l'esempio di <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a=1071}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mo>=</mo> <mn>1071</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a=1071}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e7d683462a458254127f484f159dfed8998c381f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.978ex; height:2.176ex;" alt="{\displaystyle a=1071}"> e <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b=1029}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>b</mi> <mo>=</mo> <mn>1029</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b=1029}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9675dccadddabffc991827e4a6957e44190a5944" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.746ex; height:2.176ex;" alt="{\displaystyle b=1029}"> usato prima. Questi sono i calcoli con i quozienti in evidenza: <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1071=1029\times \mathbf {1} +42}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1071</mn> <mo>=</mo> <mn>1029</mn> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <mn mathvariant="bold">1</mn> </mrow> <mo>+</mo> <mn>42</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1071=1029\times \mathbf {1} +42}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/65bdb20f329356c17b5d63d0705525e1580de196" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:21.74ex; height:2.343ex;" alt="{\displaystyle 1071=1029\times \mathbf {1} +42}"></dd> <dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1029=42\times \mathbf {24} +21}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1029</mn> <mo>=</mo> <mn>42</mn> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <mn mathvariant="bold">24</mn> </mrow> <mo>+</mo> <mn>21</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1029=42\times \mathbf {24} +21}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cbc6355f39cd1745a3cc4c5d63780b593ed9b159" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:20.752ex; height:2.343ex;" alt="{\displaystyle 1029=42\times \mathbf {24} +21}"></dd> <dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 42=21\times \mathbf {2} +0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>42</mn> <mo>=</mo> <mn>21</mn> <mo>×</mo> <mrow class="MJX-TeXAtom-ORD"> <mn mathvariant="bold">2</mn> </mrow> <mo>+</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 42=21\times \mathbf {2} +0}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/653fb37a518b08b9a63710ac454ecad9261c2ad3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:15.928ex; height:2.343ex;" alt="{\displaystyle 42=21\times \mathbf {2} +0}"></dd></dl> Da questo elenco si può vedere che <dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1071}{1029}}=\mathbf {1} +{\frac {1}{\mathbf {24} +{\frac {1}{\mathbf {2} }}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1071</mn> <mn>1029</mn> </mfrac> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mn mathvariant="bold">1</mn> </mrow> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mrow> <mrow class="MJX-TeXAtom-ORD"> <mn mathvariant="bold">24</mn> </mrow> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mn mathvariant="bold">2</mn> </mrow> </mfrac> </mrow> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {1071}{1029}}=\mathbf {1} +{\frac {1}{\mathbf {24} +{\frac {1}{\mathbf {2} }}}}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/40e7d71e28d3d84f91a98cb83859683285a4bde9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:20.893ex; height:6.676ex;" alt="{\displaystyle {\frac {1071}{1029}}=\mathbf {1} +{\frac {1}{\mathbf {24} +{\frac {1}{\mathbf {2} }}}}}">.</dd></dl> Questo metodo può anche essere usato per valori di <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd2487510aa438433a2579450ab2b3d557e5edc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}"> e <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>b</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle b}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f11423fbb2e967f986e36804a8ae4271734917c3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}"> <a href="/wiki/Numero_reale" title="Numero reale">reali</a>; se <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {a}{b}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>a</mi> <mi>b</mi> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {a}{b}}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9fbb66e57f89debc3cde3213de12228971148a93" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:2.066ex; height:4.843ex;" alt="{\displaystyle {\frac {a}{b}}}"> è <a href="/wiki/Numero_irrazionale" title="Numero irrazionale">irrazionale</a> allora l'algoritmo euclideo non ha termine, ma la sequenza di quozienti che si calcola costituisce sempre la rappresentazione (ora infinita) di <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {a}{b}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mi>a</mi> <mi>b</mi> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {a}{b}}}</annotation> </semantics> </math><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9fbb66e57f89debc3cde3213de12228971148a93" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:2.066ex; height:4.843ex;" alt="{\displaystyle {\frac {a}{b}}}"> in frazione continua. <div class="mw-heading mw-heading2"><h2 id="Codici">Codici</h2>[<a href="/w/index.php?title=Algoritmo_di_Euclide&veaction=edit&section=5" title="Modifica la sezione Codici" class="mw-editsection-visualeditor">modifica</a> | <a href="/w/index.php?title=Algoritmo_di_Euclide&action=edit&section=5" title="Edit section's source code: Codici">modifica wikitesto</a>]</div> <style data-mw-deduplicate="TemplateStyles:r133964453">.mw-parser-output .avviso .mbox-text-div>div,.mw-parser-output .avviso .mbox-text-full-div>div{font-size:90%}.mw-parser-output .avviso .mbox-image{flex-basis:52px;flex-grow:0;flex-shrink:0}.mw-parser-output .avviso .mbox-text-full-div .hide-when-compact{display:block}</style><div style="" class="ambox metadata plainlinks avviso avviso-contenuto"> <div class="avviso-immagine mbox-image noprint"><a href="/wiki/File:Emblem-important.svg" class="mw-file-description" title="Voce da controllare"><img alt="Voce da controllare" src="//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Emblem-important.svg/40px-Emblem-important.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Emblem-important.svg/60px-Emblem-important.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Emblem-important.svg/80px-Emblem-important.svg.png 2x" data-file-width="48" data-file-height="48" /></a></div> <div class="avviso-testo mbox-text"> <div class="mbox-text-div">Questa voce o sezione sull'argomento informatica è ritenuta <a href="/wiki/Aiuto:Voci_da_controllare" title="Aiuto:Voci da controllare">da controllare</a>. <div class="hide-when-compact">Motivo: Controllare se i codici vanno mantenuti o trasferiti ad un altro progetto <div class="noprint"><hr />Partecipa alla <a href="/wiki/Discussione:Algoritmo_di_Euclide" title="Discussione:Algoritmo di Euclide">discussione</a> e/o <a class="external text" href="https://it.wikipedia.org/w/index.php?title=Algoritmo_di_Euclide&action=edit">correggi</a> la voce. Segui i suggerimenti del <a href="/wiki/Progetto:Informatica" title="Progetto:Informatica">progetto di riferimento</a>.</div> </div> </div> </div> </div> <a href="/wiki/C_(linguaggio_di_programmazione)" title="C (linguaggio di programmazione)">C</a> e <a href="/wiki/C%2B%2B" title="C++">C++</a> (algoritmo iterativo) <div class="mw-highlight mw-highlight-lang-c mw-content-ltr mw-highlight-lines" dir="ltr"><pre>/* Algoritmo iterativo */ int euclide(int a, int b) { int r; // resto della divisione while(b != 0) //ripete finché non riduce b a zero { r = a % b; // in r salva il resto della divisione tra a e b a = b; // scambia il ruolo di a e b b = r; // in b ora c'è r = a % b } return a; //... e quando b è (o è diventato) 0, il risultato è in a } </pre></div> <a href="/wiki/C_(linguaggio)" class="mw-redirect" title="C (linguaggio)">C</a> e <a href="/wiki/C%2B%2B" title="C++">C++</a> (algoritmo ricorsivo) <div class="mw-highlight mw-highlight-lang-c mw-content-ltr mw-highlight-lines" dir="ltr"><pre>/* Algoritmo ricorsivo */ int euclide(int a, int b) { if(b == 0) return(a); else return euclide(b, a % b); // la funzione richiama sé stessa } </pre></div> <a href="/wiki/Scala_(linguaggio_di_programmazione)" title="Scala (linguaggio di programmazione)">Scala</a> (algoritmo ricorsivo) <div class="mw-highlight mw-highlight-lang-scala mw-content-ltr mw-highlight-lines" dir="ltr"><pre>@tailrec def euclide(a: Int, b: Int): Int = if (b == 0) a else euclide(b, a % b) </pre></div> <a href="/wiki/MATLAB" title="MATLAB">MATLAB</a> (algoritmo iterativo) <div class="mw-highlight mw-highlight-lang-matlab mw-content-ltr mw-highlight-lines" dir="ltr"><pre>function out = euclide(a, b) if(b == 0) out = a; elseif(b == 1) out = 1; else out = euclide(b, mod(a,b)); end end </pre></div> <a href="/wiki/Python" title="Python">Python</a> (algoritmo iterativo) <div class="mw-highlight mw-highlight-lang-python mw-content-ltr mw-highlight-lines" dir="ltr"><pre>def euclide(a, b): while b: a, b = b, a % b return a </pre></div> <a href="/wiki/Ruby_(linguaggio_di_programmazione)" title="Ruby (linguaggio di programmazione)">Ruby</a> (algoritmo iterativo) <div class="mw-highlight mw-highlight-lang-ruby mw-content-ltr mw-highlight-lines" dir="ltr"><pre>def euclide(a, b) while b != 0 do a, b = b, a % b end a end </pre></div> <a href="/wiki/Pascal_(linguaggio_di_programmazione)" title="Pascal (linguaggio di programmazione)">Pascal</a> (algoritmo iterativo) <div class="mw-highlight mw-highlight-lang-pascal mw-content-ltr mw-highlight-lines" dir="ltr"><pre>function euclide(a, b: integer): integer; var r: integer; begin if b = 0 then MCD := a else begin r := (a mod b); while not (r = 0) do begin a := b; b := r; r := (a mod b); end; MCD := b; end; end; </pre></div> <a href="/wiki/BASIC" title="BASIC">BASIC</a> (vb.net, algoritmo iterativo) <div class="mw-highlight mw-highlight-lang-vbnet mw-content-ltr mw-highlight-lines" dir="ltr"><pre>Function Euclide(ByVal a As Int16, ByVal b As Int16) As Int16 Dim r As Int16 = a Mod b While (r <> 0) a = b b = r r = a Mod b Wend Return b End Function </pre></div> In questo algoritmo è stato usato per la rappresentazione numerica il tipo "int16", ma può essere cambiato a piacimento con qualsiasi altro tipo di variabile numerica secondo i bisogni del programma. <a href="/wiki/PHP" title="PHP">PHP</a> (algoritmo iterativo) <div class="mw-highlight mw-highlight-lang-php mw-content-ltr mw-highlight-lines" dir="ltr"><pre>function euclide($a, $b) { while ($b) { list($a, $b) = array($b, $a % $b); } return $a; } </pre></div> <a href="/wiki/Java_(linguaggio_di_programmazione)" title="Java (linguaggio di programmazione)">Java</a> (algoritmo iterativo) <div class="mw-highlight mw-highlight-lang-java mw-content-ltr mw-highlight-lines" dir="ltr"><pre>private static int euclide(int a, int b) { int r; while (b != 0) { r = a % b; a = b; b = r; } return Math.abs(a); } </pre></div> <a href="/wiki/Rust_(linguaggio_di_programmazione)" title="Rust (linguaggio di programmazione)">Rust</a><a href="#cite_note-3">[3]</a> (algoritmo iterativo) <div class="mw-highlight mw-highlight-lang-rust mw-content-ltr mw-highlight-lines" dir="ltr"><pre>fn euclide(mut a: u64, mut b: u64) -> u64 { assert! (a != 0 && b != 0); while b != 0 { let r = a % b; a = b; b = r; } a } </pre></div> <a href="/wiki/Go_(linguaggio_di_programmazione)" title="Go (linguaggio di programmazione)">Go</a> (algoritmo iterativo) <div class="mw-highlight mw-highlight-lang-go mw-content-ltr mw-highlight-lines" dir="ltr"><pre>func euclide(a, b int) int { for b != 0 { a, b = b, a%b } return a } </pre></div> <div class="mw-heading mw-heading2"><h2 id="Note">Note</h2>[<a href="/w/index.php?title=Algoritmo_di_Euclide&veaction=edit&section=6" title="Modifica la sezione Note" class="mw-editsection-visualeditor">modifica</a> | <a href="/w/index.php?title=Algoritmo_di_Euclide&action=edit&section=6" title="Edit section's source code: Note">modifica wikitesto</a>]</div> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-1"><a href="#cite_ref-1">^</a> F. Acerbi, Euclide, Tutte le opere, 2007, <a href="/wiki/Bompiani" title="Bompiani">Bompiani</a>. (<abbr title="inglese">EN</abbr>) <a href="/w/index.php?title=Thomas_L._Heath&action=edit&redlink=1" class="new" title="Thomas L. Heath (la pagina non esiste)">Thomas L. Heath</a>, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, <a href="/w/index.php?title=Dover_Publications&action=edit&redlink=1" class="new" title="Dover Publications (la pagina non esiste)">Dover Publications</a> </li> <li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite class="citation web" style="font-style:normal"> <a rel="nofollow" class="external text" href="https://www.treccani.it/enciclopedia/algoritmo-di-euclide_(Enciclopedia-della-Matematica)/">Euclide, algoritmo di - Treccani</a>, su Treccani. URL consultato il 27 dicembre 2023.</cite> </li> <li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite class="citation web" style="font-style:normal">(<abbr title="inglese">EN</abbr>) <a rel="nofollow" class="external text" href="https://github.com/ProgrammingRust">Programming Rust</a>, su GitHub. URL consultato il 6 gennaio 2023.</cite> </li> </ol></div> <div class="mw-heading mw-heading2"><h2 id="Bibliografia">Bibliografia</h2>[<a href="/w/index.php?title=Algoritmo_di_Euclide&veaction=edit&section=7" title="Modifica la sezione Bibliografia" class="mw-editsection-visualeditor">modifica</a> | <a href="/w/index.php?title=Algoritmo_di_Euclide&action=edit&section=7" title="Edit section's source code: Bibliografia">modifica wikitesto</a>]</div> <ul><li><a href="/wiki/Donald_Knuth" title="Donald Knuth">Donald Knuth</a>., Charles E. Leiserson, Ronald L. Rivest, e Clifford Stein, Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. <a href="/wiki/Speciale:RicercaISBN/0262032937" class="internal mw-magiclink-isbn">ISBN 0-262-03293-7</a>. Section 31.2: Greatest common divisor, pp. 856–862.</li></ul> <div class="mw-heading mw-heading2"><h2 id="Voci_correlate">Voci correlate</h2>[<a href="/w/index.php?title=Algoritmo_di_Euclide&veaction=edit&section=8" title="Modifica la sezione Voci correlate" class="mw-editsection-visualeditor">modifica</a> | <a href="/w/index.php?title=Algoritmo_di_Euclide&action=edit&section=8" title="Edit section's source code: Voci correlate">modifica wikitesto</a>]</div> <ul><li><a href="/wiki/Minimo_comune_multiplo" title="Minimo comune multiplo">Minimo comune multiplo</a></li> <li><a href="/wiki/Massimo_comun_divisore" title="Massimo comun divisore">Massimo comun divisore</a></li> <li><a href="/wiki/Algoritmo_esteso_di_Euclide" title="Algoritmo esteso di Euclide">Algoritmo esteso di Euclide</a></li> <li><a href="/wiki/Equazione_diofantea_lineare" title="Equazione diofantea lineare">Equazione diofantea lineare</a></li> <li><a href="/wiki/Ritmo_di_Euclide" title="Ritmo di Euclide">Ritmo di Euclide</a></li> <li><a href="/wiki/Identit%C3%A0_di_B%C3%A9zout" title="Identità di Bézout">Identità di Bézout</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="Altri_progetti">Altri progetti</h2>[<a href="/w/index.php?title=Algoritmo_di_Euclide&veaction=edit&section=9" title="Modifica la sezione Altri progetti" class="mw-editsection-visualeditor">modifica</a> | <a href="/w/index.php?title=Algoritmo_di_Euclide&action=edit&section=9" title="Edit section's source code: Altri progetti">modifica wikitesto</a>]</div> <div id="interProject" class="toccolours" style="display: none; clear: both; margin-top: 2em">Altri progetti<ul title="Collegamenti verso gli altri progetti Wikimedia"> <li class="" title=""><a href="https://it.wikibooks.org/wiki/Implementazioni_di_algoritmi/Algoritmo_di_Euclide" class="extiw" title="b:Implementazioni di algoritmi/Algoritmo di Euclide">Wikibooks</a></li> <li class="" title=""><a class="external text" href="https://commons.wikimedia.org/wiki/Category:Euclidean_algorithm?uselang=it">Wikimedia Commons</a></li></ul></div> <ul><li><a href="https://it.wikibooks.org/wiki/" title="Collabora a Wikibooks"><img alt="Collabora a Wikibooks" src="//upload.wikimedia.org/wikipedia/commons/thumb/f/fa/Wikibooks-logo.svg/18px-Wikibooks-logo.svg.png" decoding="async" width="18" height="18" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/f/fa/Wikibooks-logo.svg/27px-Wikibooks-logo.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/f/fa/Wikibooks-logo.svg/36px-Wikibooks-logo.svg.png 2x" data-file-width="300" data-file-height="300" /></a> <a href="https://it.wikibooks.org/wiki/" class="extiw" title="b:">Wikibooks</a> contiene testi o manuali sull'<a href="https://it.wikibooks.org/wiki/Implementazioni_di_algoritmi/Algoritmo_di_Euclide" class="extiw" title="b:Implementazioni di algoritmi/Algoritmo di Euclide">algoritmo di Euclide</a></li> <li><a href="https://commons.wikimedia.org/wiki/?uselang=it" title="Collabora a Wikimedia Commons"><img alt="Collabora a Wikimedia Commons" src="//upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/18px-Commons-logo.svg.png" decoding="async" width="18" height="24" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/27px-Commons-logo.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/36px-Commons-logo.svg.png 2x" data-file-width="1024" data-file-height="1376" /></a> <a class="external text" href="https://commons.wikimedia.org/wiki/?uselang=it">Wikimedia Commons</a> contiene immagini o altri file sull'<a class="external text" href="https://commons.wikimedia.org/wiki/Category:Euclidean_algorithm?uselang=it">algoritmo di Euclide</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="Collegamenti_esterni">Collegamenti esterni</h2>[<a href="/w/index.php?title=Algoritmo_di_Euclide&veaction=edit&section=10" title="Modifica la sezione Collegamenti esterni" class="mw-editsection-visualeditor">modifica</a> | <a href="/w/index.php?title=Algoritmo_di_Euclide&action=edit&section=10" title="Edit section's source code: Collegamenti esterni">modifica wikitesto</a>]</div> <ul><li class="mw-empty-elt"></li> <li><cite id="CITEREFSapere.it" class="citation web" style="font-style:normal"> <a rel="nofollow" class="external text" href="https://www.sapere.it/enciclopedia/euclidèo,+algoritmo-.html">euclidèo, algoritmo-</a>, su sapere.it, <a href="/wiki/De_Agostini" title="De Agostini">De Agostini</a>.</cite> <a href="https://www.wikidata.org/wiki/Q230848#P6706" title="Modifica su Wikidata"><img alt="Modifica su Wikidata" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png" decoding="async" width="10" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/15px-Blue_pencil.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/20px-Blue_pencil.svg.png 2x" data-file-width="600" data-file-height="600" /></a></li> <li><cite id="CITEREFEnciclopedia_della_Matematica" class="citation libro" style="font-style:normal"> <a rel="nofollow" class="external text" href="https://www.treccani.it/enciclopedia/algoritmo-di-euclide_(Enciclopedia-della-Matematica)/">Euclide, algoritmo di</a>, in Enciclopedia della Matematica, <a href="/wiki/Istituto_dell%27Enciclopedia_Italiana" title="Istituto dell'Enciclopedia Italiana">Istituto dell'Enciclopedia Italiana</a>, 2013.</cite> <a href="https://www.wikidata.org/wiki/Q230848#P9621" title="Modifica su Wikidata"><img alt="Modifica su Wikidata" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png" decoding="async" width="10" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/15px-Blue_pencil.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/20px-Blue_pencil.svg.png 2x" data-file-width="600" data-file-height="600" /></a></li> <li><cite id="CITEREFBritannica.com" class="citation web" style="font-style:normal">(<abbr title="inglese">EN</abbr>) <a rel="nofollow" class="external text" href="https://www.britannica.com/topic/Euclidean-algorithm">Euclidean algorithm</a>, su <a href="/wiki/Enciclopedia_Britannica" title="Enciclopedia Britannica">Enciclopedia Britannica</a>, Encyclopædia Britannica, Inc.</cite> <a href="https://www.wikidata.org/wiki/Q230848#P1417" title="Modifica su Wikidata"><img alt="Modifica su Wikidata" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png" decoding="async" width="10" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/15px-Blue_pencil.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/20px-Blue_pencil.svg.png 2x" data-file-width="600" data-file-height="600" /></a></li> <li><cite id="CITEREFOpen_Library" class="citation web" style="font-style:normal">(<abbr title="inglese">EN</abbr>) <a rel="nofollow" class="external text" href="https://openlibrary.org/subjects/euclidean_algorithm">Opere riguardanti Euclidean algorithm</a>, su <a href="/wiki/Open_Library" class="mw-redirect" title="Open Library">Open Library</a>, <a href="/wiki/Internet_Archive" title="Internet Archive">Internet Archive</a>.</cite> <a href="https://www.wikidata.org/wiki/Q230848#P3847" title="Modifica su Wikidata"><img alt="Modifica su Wikidata" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png" decoding="async" width="10" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/15px-Blue_pencil.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/20px-Blue_pencil.svg.png 2x" data-file-width="600" data-file-height="600" /></a></li> <li><cite id="CITEREFMathWorld" class="citation web" style="font-style:normal">(<abbr title="inglese">EN</abbr>) Eric W. Weisstein, <a rel="nofollow" class="external text" href="http://mathworld.wolfram.com/EuclideanAlgorithm.html">Euclidean Algorithm</a>, su <a href="/wiki/MathWorld" title="MathWorld">MathWorld</a>, Wolfram Research.</cite> <a href="https://www.wikidata.org/wiki/Q230848#P2812" title="Modifica su Wikidata"><img alt="Modifica su Wikidata" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png" decoding="async" width="10" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/15px-Blue_pencil.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/20px-Blue_pencil.svg.png 2x" data-file-width="600" data-file-height="600" /></a></li> <li><cite id="CITEREFSpringerEOM" class="citation web" style="font-style:normal">(<abbr title="inglese">EN</abbr>) <a rel="nofollow" class="external text" href="https://encyclopediaofmath.org/wiki/Euclidean_algorithm">Euclidean algorithm</a>, su <a href="/wiki/Encyclopaedia_of_Mathematics" title="Encyclopaedia of Mathematics">Encyclopaedia of Mathematics</a>, Springer e European Mathematical Society.</cite> <a href="https://www.wikidata.org/wiki/Q230848#P7554" title="Modifica su Wikidata"><img alt="Modifica su Wikidata" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/10px-Blue_pencil.svg.png" decoding="async" width="10" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/15px-Blue_pencil.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/73/Blue_pencil.svg/20px-Blue_pencil.svg.png 2x" data-file-width="600" data-file-height="600" /></a></li> <li><cite id="CITEREFFOLDOC" class="citation testo" style="font-style:normal">(<abbr title="inglese">EN</abbr>) Denis Howe, <a href="https://foldoc.org/Euclid%27s_Algorithm" class="extiw" title="foldoc:Euclid's Algorithm">Euclid's Algorithm</a>, in <a href="/wiki/Free_On-line_Dictionary_of_Computing" title="Free On-line Dictionary of Computing">Free On-line Dictionary of Computing</a>.</cite> Disponibile con licenza <a href="/wiki/GNU_Free_Documentation_License" title="GNU Free Documentation License">GFDL</a></li> <li>(<abbr title="inglese">EN</abbr>) <a rel="nofollow" class="external text" href="https://www.cut-the-knot.org/blue/Euclid.shtml">Euclid's Algorithm</a> su cut-the-knot</li> <li>(<abbr title="inglese">EN</abbr>) <a rel="nofollow" class="external text" href="https://www.cut-the-knot.org/blue/binary.shtml">Binary Euclid's Algorithm (Java)</a> su cut-the-knot</li> <li>(<abbr title="inglese">EN</abbr>) <a rel="nofollow" class="external text" href="https://www.cut-the-knot.org/blue/EuclidAlg.shtml">Euclid's Game (Java)</a> su cut-the-knot</li></ul> <style data-mw-deduplicate="TemplateStyles:r141815314">.mw-parser-output .navbox{border:1px solid #aaa;clear:both;margin:auto;padding:2px;width:100%}.mw-parser-output .navbox th{padding-left:1em;padding-right:1em;text-align:center}.mw-parser-output .navbox>tbody>tr:first-child>th{background:#ccf;font-size:90%;width:100%;color:var(--color-base,black)}.mw-parser-output .navbox_navbar{float:left;margin:0;padding:0 10px 0 0;text-align:left;width:6em}.mw-parser-output .navbox_title{font-size:110%}.mw-parser-output .navbox_abovebelow{background:#ddf;font-size:90%;font-weight:normal}.mw-parser-output .navbox_group{background:#ddf;font-size:90%;padding:0 10px;white-space:nowrap}.mw-parser-output .navbox_list{font-size:90%;width:100%}.mw-parser-output .navbox_list a{white-space:nowrap}html:not(.vector-feature-night-mode-enabled) .mw-parser-output .navbox_odd{background:#fdfdfd;color:var(--color-base,black)}html:not(.vector-feature-night-mode-enabled) .mw-parser-output .navbox_even{background:#f7f7f7;color:var(--color-base,black)}.mw-parser-output .navbox a.mw-selflink{color:var(--color-base,black)}.mw-parser-output .navbox_center{text-align:center}.mw-parser-output .navbox .navbox_image{padding-left:7px;vertical-align:middle;width:0}.mw-parser-output .navbox+.navbox{margin-top:-1px}.mw-parser-output .navbox .mw-collapsible-toggle{font-weight:normal;text-align:right;width:7em}body.skin--responsive .mw-parser-output .navbox_image img{max-width:none!important}.mw-parser-output .subnavbox{margin:-3px;width:100%}.mw-parser-output .subnavbox_group{background:#e6e6ff;padding:0 10px}@media screen{html.skin-theme-clientpref-night .mw-parser-output .navbox>tbody>tr:first-child>th{background:var(--background-color-interactive)!important}html.skin-theme-clientpref-night .mw-parser-output .navbox th{color:var(--color-base)!important}html.skin-theme-clientpref-night .mw-parser-output .navbox_abovebelow,html.skin-theme-clientpref-night .mw-parser-output .navbox_group{background:var(--background-color-interactive-subtle)!important}html.skin-theme-clientpref-night .mw-parser-output .subnavbox_group{background:var(--background-color-neutral-subtle)!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbox>tbody>tr:first-child>th{background:var(--background-color-interactive)!important}html.skin-theme-clientpref-os .mw-parser-output .navbox th{color:var(--color-base)!important}html.skin-theme-clientpref-os .mw-parser-output .navbox_abovebelow,html.skin-theme-clientpref-os .mw-parser-output .navbox_group{background:var(--background-color-interactive-subtle)!important}html.skin-theme-clientpref-os .mw-parser-output .subnavbox_group{background:var(--background-color-neutral-subtle)!important}}</style><table class="navbox mw-collapsible mw-collapsed noprint metadata" id="navbox-Algebra"><tbody><tr><th colspan="3" style="background:#ffc0cb;"><div class="navbox_navbar"><div class="noprint plainlinks" style="background-color:transparent; padding:0; font-size:xx-small; color:var(--color-base, #000000); white-space:nowrap;"><a href="/wiki/Template:Algebra" title="Template:Algebra">V</a> · <a href="/w/index.php?title=Discussioni_template:Algebra&action=edit&redlink=1" class="new" title="Discussioni template:Algebra (la pagina non esiste)">D</a> · <a class="external text" href="https://it.wikipedia.org/w/index.php?title=Template:Algebra&action=edit">M</a></div></div><a href="/wiki/Algebra" title="Algebra">Algebra</a></th></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;"><a href="/wiki/Numero" title="Numero">Numeri</a></th><td colspan="1" class="navbox_list navbox_odd" style="text-align:left;"><a href="/wiki/Numero_naturale" title="Numero naturale">Naturali</a> · <a href="/wiki/Numero_intero" title="Numero intero">Interi</a> · <a href="/wiki/Numero_razionale" title="Numero razionale">Razionali</a> · <a href="/wiki/Numero_irrazionale" title="Numero irrazionale">Irrazionali</a> · <a href="/wiki/Numero_algebrico" title="Numero algebrico">Algebrici</a> · <a href="/wiki/Numero_trascendente" title="Numero trascendente">Trascendenti</a> · <a href="/wiki/Numero_reale" title="Numero reale">Reali</a> · <a href="/wiki/Numero_complesso" title="Numero complesso">Complessi</a> · <a href="/wiki/Numero_ipercomplesso" title="Numero ipercomplesso">Numero ipercomplesso</a> · <a href="/wiki/Numero_p-adico" title="Numero p-adico">Numero p-adico</a> · <a href="/wiki/Numero_duale" title="Numero duale">Duali</a> · <a href="/wiki/Numero_complesso_iperbolico" title="Numero complesso iperbolico">Complessi iperbolici</a></td><td rowspan="10" class="navbox_image"><figure class="mw-halign-right" typeof="mw:File"><a href="/wiki/File:Nuvola_apps_edu_mathematics-p.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/c/c2/Nuvola_apps_edu_mathematics-p.svg/58px-Nuvola_apps_edu_mathematics-p.svg.png" decoding="async" width="58" height="58" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/c2/Nuvola_apps_edu_mathematics-p.svg/87px-Nuvola_apps_edu_mathematics-p.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/c2/Nuvola_apps_edu_mathematics-p.svg/116px-Nuvola_apps_edu_mathematics-p.svg.png 2x" data-file-width="128" data-file-height="128" /></a><figcaption></figcaption></figure></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;">Principi fondamentali</th><td colspan="1" class="navbox_list navbox_even" style="text-align:left;"><a href="/wiki/Principio_d%27induzione" title="Principio d'induzione">Principio d'induzione</a> · <a href="/wiki/Principio_del_buon_ordinamento" title="Principio del buon ordinamento">Principio del buon ordinamento</a> · <a href="/wiki/Relazione_di_equivalenza" title="Relazione di equivalenza">Relazione di equivalenza</a> · <a href="/wiki/Relazione_d%27ordine" title="Relazione d'ordine">Relazione d'ordine</a> · <a href="/wiki/Associativit%C3%A0_della_potenza" title="Associatività della potenza">Associatività della potenza</a></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;"><a href="/wiki/Algebra_elementare" title="Algebra elementare">Algebra elementare</a></th><td colspan="1" class="navbox_list navbox_odd" style="text-align:left;"><a href="/wiki/Equazione" title="Equazione">Equazione</a> · <a href="/wiki/Disequazione" title="Disequazione">Disequazione</a> · <a href="/wiki/Polinomio" title="Polinomio">Polinomio</a> · <a href="/wiki/Triangolo_di_Tartaglia" title="Triangolo di Tartaglia">Triangolo di Tartaglia</a> · <a href="/wiki/Teorema_binomiale" title="Teorema binomiale">Teorema binomiale</a> · <a href="/wiki/Teorema_del_resto" title="Teorema del resto">Teorema del resto</a> · <a href="/wiki/Lemma_di_Gauss_(polinomi)" title="Lemma di Gauss (polinomi)">Lemma di Gauss</a> · <a href="/wiki/Teorema_delle_radici_razionali" title="Teorema delle radici razionali">Teorema delle radici razionali</a> · <a href="/wiki/Regola_di_Ruffini" title="Regola di Ruffini">Regola di Ruffini</a> · <a href="/wiki/Criterio_di_Eisenstein" title="Criterio di Eisenstein">Criterio di Eisenstein</a> · <a href="/wiki/Criterio_di_Cartesio" title="Criterio di Cartesio">Criterio di Cartesio</a> · <a href="/wiki/Disequazione_con_il_valore_assoluto" title="Disequazione con il valore assoluto">Disequazione con il valore assoluto</a> · <a href="/wiki/Segno_(matematica)" title="Segno (matematica)">Segno</a> · <a href="/wiki/Metodo_di_Gauss-Seidel" title="Metodo di Gauss-Seidel">Metodo di Gauss-Seidel</a> · <a href="/wiki/Polinomio_simmetrico" title="Polinomio simmetrico">Polinomio simmetrico</a> · <a href="/wiki/Funzione_simmetrica" title="Funzione simmetrica">Funzione simmetrica</a></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;">Elementi di <a href="/wiki/Calcolo_combinatorio" title="Calcolo combinatorio">Calcolo combinatorio</a></th><td colspan="1" class="navbox_list navbox_even" style="text-align:left;"><a href="/wiki/Fattoriale" title="Fattoriale">Fattoriale</a> · <a href="/wiki/Permutazione" title="Permutazione">Permutazione</a> · <a href="/wiki/Disposizione" title="Disposizione">Disposizione</a> · <a href="/wiki/Combinazione" title="Combinazione">Combinazione</a> · <a href="/wiki/Dismutazione_(matematica)" title="Dismutazione (matematica)">Dismutazione</a> · <a href="/wiki/Principio_di_inclusione-esclusione" title="Principio di inclusione-esclusione">Principio di inclusione-esclusione</a></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;">Concetti fondamentali di <a href="/wiki/Teoria_dei_numeri" title="Teoria dei numeri">Teoria dei numeri</a></th><td colspan="1" class="navbox_list navbox_odd" style="text-align:left;"><table class="subnavbox"><tbody><tr><th class="subnavbox_group">Primi</th><td colspan="1"><a href="/wiki/Numero_primo" title="Numero primo">Numero primo</a> · <a href="/wiki/Teorema_dell%27infinit%C3%A0_dei_numeri_primi" title="Teorema dell'infinità dei numeri primi">Teorema dell'infinità dei numeri primi</a> · <a href="/wiki/Crivello_di_Eratostene" title="Crivello di Eratostene">Crivello di Eratostene</a> · <a href="/wiki/Crivello_di_Atkin" title="Crivello di Atkin">Crivello di Atkin</a> · <a href="/wiki/Test_di_primalit%C3%A0" title="Test di primalità">Test di primalità</a> · <a href="/wiki/Teorema_fondamentale_dell%27aritmetica" title="Teorema fondamentale dell'aritmetica">Teorema fondamentale dell'aritmetica</a></td></tr><tr><th class="subnavbox_group">Divisori</th><td colspan="1"><a href="/wiki/Interi_coprimi" title="Interi coprimi">Interi coprimi</a> · <a href="/wiki/Identit%C3%A0_di_B%C3%A9zout" title="Identità di Bézout">Identità di Bézout</a> · <a href="/wiki/Massimo_comun_divisore" title="Massimo comun divisore">MCD</a> · <a href="/wiki/Minimo_comune_multiplo" title="Minimo comune multiplo">mcm</a> · <a class="mw-selflink selflink">Algoritmo di Euclide</a> · <a href="/wiki/Algoritmo_esteso_di_Euclide" title="Algoritmo esteso di Euclide">Algoritmo esteso di Euclide</a> · <a href="/wiki/Criteri_di_divisibilit%C3%A0" title="Criteri di divisibilità">Criteri di divisibilità</a> · <a href="/wiki/Divisore" title="Divisore">Divisore</a></td></tr><tr><th class="subnavbox_group"><a href="/wiki/Aritmetica_modulare" title="Aritmetica modulare">Aritmetica modulare</a></th><td colspan="1"><a href="/wiki/Teorema_cinese_del_resto" title="Teorema cinese del resto">Teorema cinese del resto</a> · <a href="/wiki/Piccolo_teorema_di_Fermat" title="Piccolo teorema di Fermat">Piccolo teorema di Fermat</a> · <a href="/wiki/Teorema_di_Eulero_(aritmetica_modulare)" title="Teorema di Eulero (aritmetica modulare)">Teorema di Eulero</a> · <a href="/wiki/Funzione_%CF%86_di_Eulero" title="Funzione φ di Eulero">Funzione φ di Eulero</a> · <a href="/wiki/Teorema_di_Wilson" title="Teorema di Wilson">Teorema di Wilson</a> · <a href="/wiki/Reciprocit%C3%A0_quadratica" title="Reciprocità quadratica">Reciprocità quadratica</a></td></tr></tbody></table></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;"><a href="/wiki/Teoria_dei_gruppi" title="Teoria dei gruppi">Teoria dei gruppi</a></th><td colspan="1" class="navbox_list navbox_even" style="text-align:left;"><table class="subnavbox"><tbody><tr><th class="subnavbox_group">Gruppi</th><td colspan="1"><a href="/wiki/Gruppo_(matematica)" title="Gruppo (matematica)">Gruppo</a> (<a href="/wiki/Gruppo_finito" title="Gruppo finito">finito</a> · <a href="/wiki/Gruppo_ciclico" title="Gruppo ciclico">ciclico</a> · <a href="/wiki/Gruppo_abeliano" title="Gruppo abeliano">abeliano</a>) · <a href="/wiki/Gruppo_primario" title="Gruppo primario">Gruppo primario</a> · <a href="/wiki/Gruppo_quoziente" title="Gruppo quoziente">Gruppo quoziente</a> · <a href="/wiki/Gruppo_nilpotente" title="Gruppo nilpotente">Gruppo nilpotente</a> · <a href="/wiki/Gruppo_risolubile" title="Gruppo risolubile">Gruppo risolubile</a> · <a href="/wiki/Gruppo_simmetrico" title="Gruppo simmetrico">Gruppo simmetrico</a> · <a href="/wiki/Gruppo_diedrale" title="Gruppo diedrale">Gruppo diedrale</a> · <a href="/wiki/Gruppo_semplice" title="Gruppo semplice">Gruppo semplice</a> · <a href="/wiki/Gruppo_sporadico" title="Gruppo sporadico">Gruppo sporadico</a> · <a href="/wiki/Gruppo_mostro" title="Gruppo mostro">Gruppo mostro</a> · <a href="/wiki/Gruppo_di_Klein" title="Gruppo di Klein">Gruppo di Klein</a> · <a href="/wiki/Gruppo_dei_quaternioni" title="Gruppo dei quaternioni">Gruppo dei quaternioni</a> · <a href="/wiki/Gruppo_generale_lineare" title="Gruppo generale lineare">Gruppo generale lineare</a> · <a href="/wiki/Gruppo_ortogonale" title="Gruppo ortogonale">Gruppo ortogonale</a> · <a href="/wiki/Gruppo_unitario" title="Gruppo unitario">Gruppo unitario</a> · <a href="/wiki/Gruppo_unitario_speciale" title="Gruppo unitario speciale">Gruppo unitario speciale</a> · <a href="/wiki/Gruppo_residualmente_finito" title="Gruppo residualmente finito">Gruppo residualmente finito</a> · <a href="/wiki/Gruppo_spaziale" title="Gruppo spaziale">Gruppo spaziale</a> · <a href="/wiki/Gruppo_profinito" title="Gruppo profinito">Gruppo profinito</a> · <a href="/wiki/Out(Fn)" title="Out(Fn)">Out(Fn)</a> · <a href="/wiki/Parola_(teoria_dei_gruppi)" title="Parola (teoria dei gruppi)">Parola</a> · <a href="/wiki/Prodotto_diretto" title="Prodotto diretto">Prodotto diretto</a> · <a href="/wiki/Prodotto_semidiretto" title="Prodotto semidiretto">Prodotto semidiretto</a> · <a href="/wiki/Prodotto_intrecciato" title="Prodotto intrecciato">Prodotto intrecciato</a></td></tr><tr><th class="subnavbox_group">Teoremi</th><td colspan="1"><a href="/wiki/Alternativa_di_Tits" title="Alternativa di Tits">Alternativa di Tits</a> · <a href="/wiki/Teorema_di_isomorfismo" title="Teorema di isomorfismo">Teorema di isomorfismo</a> · <a href="/wiki/Teorema_di_Lagrange_(teoria_dei_gruppi)" title="Teorema di Lagrange (teoria dei gruppi)">Teorema di Lagrange</a> · <a href="/wiki/Teorema_di_Cauchy_(teoria_dei_gruppi)" title="Teorema di Cauchy (teoria dei gruppi)">Teorema di Cauchy</a> · <a href="/wiki/Teoremi_di_Sylow" title="Teoremi di Sylow">Teoremi di Sylow</a> · <a href="/wiki/Teorema_di_Cayley" title="Teorema di Cayley">Teorema di Cayley</a> · <a href="/wiki/Gruppo_abeliano#Classificazione" title="Gruppo abeliano">Teorema di struttura dei gruppi abeliani finiti</a> · <a href="/wiki/Lemma_della_farfalla" title="Lemma della farfalla">Lemma della farfalla</a> · <a href="/wiki/Lemma_del_ping-pong" title="Lemma del ping-pong">Lemma del ping-pong</a> · <a href="/wiki/Classificazione_dei_gruppi_semplici_finiti" title="Classificazione dei gruppi semplici finiti">Classificazione dei gruppi semplici finiti</a></td></tr><tr><th class="subnavbox_group">Sottoinsiemi</th><td colspan="1"><a href="/wiki/Sottogruppo" title="Sottogruppo">Sottogruppo</a> · <a href="/wiki/Sottogruppo_normale" title="Sottogruppo normale">Sottogruppo normale</a> · <a href="/wiki/Sottogruppo_caratteristico" title="Sottogruppo caratteristico">Sottogruppo caratteristico</a> · <a href="/wiki/Sottogruppo_di_Frattini" title="Sottogruppo di Frattini">Sottogruppo di Frattini</a> · <a href="/wiki/Sottogruppo_di_torsione" title="Sottogruppo di torsione">Sottogruppo di torsione</a> · <a href="/wiki/Classe_laterale" title="Classe laterale">Classe laterale</a> · <a href="/wiki/Classe_di_coniugio" title="Classe di coniugio">Classe di coniugio</a> · <a href="/wiki/Serie_di_composizione" title="Serie di composizione">Serie di composizione</a></td></tr><tr><td colspan="2" class="navbox_center"><a href="/wiki/Omomorfismo_di_gruppi" title="Omomorfismo di gruppi">Omomorfismo</a> · <a href="/wiki/Isomorfismo_tra_gruppi" title="Isomorfismo tra gruppi">Isomorfismo</a> · <a href="/wiki/Automorfismo_interno" title="Automorfismo interno">Automorfismo interno</a> · <a href="/wiki/Automorfismo_esterno" title="Automorfismo esterno">Automorfismo esterno</a> · <a href="/wiki/Permutazione" title="Permutazione">Permutazione</a> · <a href="/wiki/Presentazione_di_un_gruppo" title="Presentazione di un gruppo">Presentazione di un gruppo</a> · <a href="/wiki/Azione_di_gruppo" title="Azione di gruppo">Azione di gruppo</a></td></tr></tbody></table></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;"><a href="/wiki/Teoria_degli_anelli" title="Teoria degli anelli">Teoria degli anelli</a></th><td colspan="1" class="navbox_list navbox_odd" style="text-align:left;"><a href="/wiki/Anello_(algebra)" title="Anello (algebra)">Anello</a> (<a href="/wiki/Anello_artiniano" title="Anello artiniano">artiniano</a> · <a href="/wiki/Anello_noetheriano" title="Anello noetheriano">noetheriano</a> · <a href="/wiki/Anello_locale" title="Anello locale">locale</a>) · <a href="/wiki/Caratteristica_(algebra)" title="Caratteristica (algebra)">Caratteristica</a> · <a href="/wiki/Ideale_(matematica)" title="Ideale (matematica)">Ideale</a> (<a href="/wiki/Ideale_primo" title="Ideale primo">primo</a> · <a href="/wiki/Ideale_massimale" title="Ideale massimale">massimale</a>) · <a href="/wiki/Dominio_d%27integrit%C3%A0" title="Dominio d'integrità">Dominio</a> (<a href="/wiki/Dominio_a_fattorizzazione_unica" title="Dominio a fattorizzazione unica">a fattorizzazione unica</a> · <a href="/wiki/Dominio_ad_ideali_principali" title="Dominio ad ideali principali">a ideali principali</a> · <a href="/wiki/Dominio_euclideo" title="Dominio euclideo">euclideo</a>) · <a href="/wiki/Matrice" title="Matrice">Matrice</a> · <a href="/wiki/Anello_semplice" title="Anello semplice">Anello semplice</a> · <a href="/wiki/Anello_degli_endomorfismi" title="Anello degli endomorfismi">Anello degli endomorfismi</a> · <a href="/wiki/Teorema_di_Artin-Wedderburn" title="Teorema di Artin-Wedderburn">Teorema di Artin-Wedderburn</a> · <a href="/wiki/Modulo_(algebra)" title="Modulo (algebra)">Modulo</a> · <a href="/wiki/Dominio_di_Dedekind" title="Dominio di Dedekind">Dominio di Dedekind</a> · <a href="/wiki/Estensione_di_anelli" title="Estensione di anelli">Estensione di anelli</a> · <a href="/wiki/Teorema_della_base_di_Hilbert" title="Teorema della base di Hilbert">Teorema della base di Hilbert</a> · <a href="/wiki/Anello_di_Gorenstein" title="Anello di Gorenstein">Anello di Gorenstein</a> · <a href="/wiki/Base_di_Gr%C3%B6bner" title="Base di Gröbner">Base di Gröbner</a> · <a href="/wiki/Prodotto_tensoriale" title="Prodotto tensoriale">Prodotto tensoriale</a> · <a href="/wiki/Primo_associato" title="Primo associato">Primo associato</a></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;"><a href="/wiki/Teoria_dei_campi_(matematica)" class="mw-redirect" title="Teoria dei campi (matematica)">Teoria dei campi</a></th><td colspan="1" class="navbox_list navbox_even" style="text-align:left;"><table class="subnavbox"><tbody><tr><td colspan="2" class="navbox_center"><a href="/wiki/Campo_(matematica)" title="Campo (matematica)">Campo</a> · <a href="/wiki/Polinomio_irriducibile" title="Polinomio irriducibile">Polinomio irriducibile</a> · <a href="/wiki/Polinomio_ciclotomico" title="Polinomio ciclotomico">Polinomio ciclotomico</a> · <a href="/wiki/Teorema_fondamentale_dell%27algebra" title="Teorema fondamentale dell'algebra">Teorema fondamentale dell'algebra</a> · <a href="/wiki/Campo_finito" title="Campo finito">Campo finito</a> · <a href="/wiki/Automorfismo" title="Automorfismo">Automorfismo</a> · <a href="/wiki/Endomorfismo_di_Frobenius" title="Endomorfismo di Frobenius">Endomorfismo di Frobenius</a></td></tr><tr><th class="subnavbox_group">Estensioni</th><td colspan="1"><a href="/wiki/Campo_di_spezzamento" title="Campo di spezzamento">Campo di spezzamento</a> · <a href="/wiki/Estensione_di_campi" title="Estensione di campi">Estensione di campi</a> · <a href="/wiki/Estensione_algebrica" title="Estensione algebrica">Estensione algebrica</a> · <a href="/wiki/Estensione_separabile" title="Estensione separabile">Estensione separabile</a> · <a href="/wiki/Chiusura_algebrica" title="Chiusura algebrica">Chiusura algebrica</a> · <a href="/wiki/Campo_di_numeri" title="Campo di numeri">Campo di numeri</a> · <a href="/wiki/Estensione_normale" title="Estensione normale">Estensione normale</a> · <a href="/wiki/Estensione_di_Galois" title="Estensione di Galois">Estensione di Galois</a> · <a href="/wiki/Estensione_abeliana" title="Estensione abeliana">Estensione abeliana</a> · <a href="/wiki/Estensione_ciclotomica" title="Estensione ciclotomica">Estensione ciclotomica</a> · <a href="/wiki/Teoria_di_Kummer" title="Teoria di Kummer">Teoria di Kummer</a></td></tr><tr><th class="subnavbox_group">Teoria di Galois</th><td colspan="1"><a href="/wiki/Gruppo_di_Galois" title="Gruppo di Galois">Gruppo di Galois</a> · <a href="/wiki/Teoria_di_Galois" title="Teoria di Galois">Teoria di Galois</a> · <a href="/wiki/Teorema_fondamentale_della_teoria_di_Galois" title="Teorema fondamentale della teoria di Galois">Teorema fondamentale della teoria di Galois</a> · <a href="/wiki/Teorema_di_Abel-Ruffini" title="Teorema di Abel-Ruffini">Teorema di Abel-Ruffini</a> · <a href="/wiki/Costruzioni_con_riga_e_compasso" title="Costruzioni con riga e compasso">Costruzioni con riga e compasso</a></td></tr></tbody></table></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;">Altre <a href="/wiki/Struttura_algebrica" title="Struttura algebrica">strutture algebriche</a></th><td colspan="1" class="navbox_list navbox_odd" style="text-align:left;"><a href="/wiki/Magma_(matematica)" title="Magma (matematica)">Magma</a> · <a href="/wiki/Semigruppo" title="Semigruppo">Semigruppo</a> · <a href="/wiki/Corpo_(matematica)" title="Corpo (matematica)">Corpo</a> · <a href="/wiki/Spazio_vettoriale" title="Spazio vettoriale">Spazio vettoriale</a> · <a href="/wiki/Algebra_su_campo" title="Algebra su campo">Algebra su campo</a> · <a href="/wiki/Algebra_di_Lie" title="Algebra di Lie">Algebra di Lie</a> · <a href="/wiki/Algebra_differenziale" title="Algebra differenziale">Algebra differenziale</a> · <a href="/wiki/Algebra_di_Clifford" title="Algebra di Clifford">Algebra di Clifford</a> · <a href="/wiki/Gruppo_topologico" title="Gruppo topologico">Gruppo topologico</a> · <a href="/wiki/Gruppo_ordinato" title="Gruppo ordinato">Gruppo ordinato</a> · <a href="/wiki/Quasi-anello" title="Quasi-anello">Quasi-anello</a> · <a href="/wiki/Algebra_di_Boole" title="Algebra di Boole">Algebra di Boole</a></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;">argomenti</th><td colspan="1" class="navbox_list navbox_even" style="text-align:left;"><a href="/wiki/Teoria_delle_categorie" title="Teoria delle categorie">Teoria delle categorie</a> · <a href="/wiki/Algebra_lineare" title="Algebra lineare">Algebra lineare</a> · <a href="/wiki/Algebra_commutativa" title="Algebra commutativa">Algebra commutativa</a> · <a href="/wiki/Algebra_omologica" title="Algebra omologica">Algebra omologica</a> · <a href="/wiki/Algebra_astratta" title="Algebra astratta">Algebra astratta</a> · <a href="/wiki/Algebra_computazionale" class="mw-redirect" title="Algebra computazionale">Algebra computazionale</a> · <a href="/wiki/Algebra_differenziale" title="Algebra differenziale">Algebra differenziale</a> · <a href="/wiki/Algebra_universale" title="Algebra universale">Algebra universale</a></td></tr></tbody></table> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r141815314"><table class="navbox mw-collapsible mw-collapsed noprint metadata" id="navbox-Teoria_dei_numeri"><tbody><tr><th colspan="3" style="background:#ffc0cb;"><div class="navbox_navbar"><div class="noprint plainlinks" style="background-color:transparent; padding:0; font-size:xx-small; color:var(--color-base, #000000); white-space:nowrap;"><a href="/wiki/Template:Teoria_dei_numeri" title="Template:Teoria dei numeri">V</a> · <a href="/w/index.php?title=Discussioni_template:Teoria_dei_numeri&action=edit&redlink=1" class="new" title="Discussioni template:Teoria dei numeri (la pagina non esiste)">D</a> · <a class="external text" href="https://it.wikipedia.org/w/index.php?title=Template:Teoria_dei_numeri&action=edit">M</a></div></div><a href="/wiki/Teoria_dei_numeri" title="Teoria dei numeri">Teoria dei numeri</a></th></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;"><a href="/wiki/Numero" title="Numero">Numeri</a> più usati</th><td colspan="1" class="navbox_list navbox_odd" style="text-align:left;"><a href="/wiki/Numero_naturale" title="Numero naturale">Naturali</a> · <a href="/wiki/Numero_intero" title="Numero intero">Interi</a> · <a href="/wiki/Numeri_pari_e_dispari" title="Numeri pari e dispari">Pari e dispari</a></td><td rowspan="10" class="navbox_image"><figure class="mw-halign-right" typeof="mw:File"><a href="/wiki/File:Nuvola_apps_edu_mathematics-p.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/c/c2/Nuvola_apps_edu_mathematics-p.svg/58px-Nuvola_apps_edu_mathematics-p.svg.png" decoding="async" width="58" height="58" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/c2/Nuvola_apps_edu_mathematics-p.svg/87px-Nuvola_apps_edu_mathematics-p.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/c2/Nuvola_apps_edu_mathematics-p.svg/116px-Nuvola_apps_edu_mathematics-p.svg.png 2x" data-file-width="128" data-file-height="128" /></a><figcaption></figcaption></figure></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;">Principi generali</th><td colspan="1" class="navbox_list navbox_even" style="text-align:left;"><a href="/wiki/Principio_d%27induzione" title="Principio d'induzione">Principio d'induzione</a> · <a href="/wiki/Principio_del_buon_ordinamento" title="Principio del buon ordinamento">Principio del buon ordinamento</a> · <a href="/wiki/Relazione_di_equivalenza" title="Relazione di equivalenza">Relazione di equivalenza</a></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;"><a href="/wiki/Successione_di_interi" title="Successione di interi">Successioni di interi</a></th><td colspan="1" class="navbox_list navbox_odd" style="text-align:left;"><a href="/wiki/Fattoriale" title="Fattoriale">Fattoriale</a> · <a href="/wiki/Successione_di_Fibonacci" title="Successione di Fibonacci">Successione di Fibonacci</a> · <a href="/wiki/Numero_di_Catalan" title="Numero di Catalan">Numero di Catalan</a> · <a href="/wiki/Numero_di_Perrin" title="Numero di Perrin">Numero di Perrin</a> · <a href="/wiki/Numero_di_Eulero_(teoria_dei_numeri)" class="mw-redirect" title="Numero di Eulero (teoria dei numeri)">Numero di Eulero</a> · <a href="/wiki/Successione_di_Mian-Chowla" title="Successione di Mian-Chowla">Successione di Mian-Chowla</a> · <a href="/wiki/Successione_di_Thue-Morse" title="Successione di Thue-Morse">Successione di Thue-Morse</a></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;">Caratteristiche dei numeri primi</th><td colspan="1" class="navbox_list navbox_even" style="text-align:left;"><a href="/wiki/Numero_primo" title="Numero primo">Numero primo</a> · <a href="/wiki/Lemma_di_Euclide" title="Lemma di Euclide">Lemma di Euclide</a> · <a href="/wiki/Teorema_dell%27infinit%C3%A0_dei_numeri_primi" title="Teorema dell'infinità dei numeri primi">Teorema dell'infinità dei numeri primi</a> · <a href="/wiki/Crivello_di_Eratostene" title="Crivello di Eratostene">Crivello di Eratostene</a> · <a href="/wiki/Test_di_primalit%C3%A0" title="Test di primalità">Test di primalità</a> · <a href="/wiki/Teorema_fondamentale_dell%27aritmetica" title="Teorema fondamentale dell'aritmetica">Teorema fondamentale dell'aritmetica</a> · <a href="/wiki/Interi_coprimi" title="Interi coprimi">Interi coprimi</a> · <a href="/wiki/Identit%C3%A0_di_B%C3%A9zout" title="Identità di Bézout">Identità di Bézout</a> · <a href="/wiki/Massimo_comun_divisore" title="Massimo comun divisore">MCD</a> · <a href="/wiki/Minimo_comune_multiplo" title="Minimo comune multiplo">mcm</a> · <a class="mw-selflink selflink">Algoritmo di Euclide</a> · <a href="/wiki/Algoritmo_esteso_di_Euclide" title="Algoritmo esteso di Euclide">Algoritmo esteso di Euclide</a> · <a href="/wiki/Teorema_dei_numeri_primi" title="Teorema dei numeri primi">Teorema dei numeri primi</a></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;"><a href="/wiki/Funzione_aritmetica" title="Funzione aritmetica">Funzioni aritmetiche</a></th><td colspan="1" class="navbox_list navbox_odd" style="text-align:left;"><a href="/wiki/Funzione_moltiplicativa" title="Funzione moltiplicativa">Funzione moltiplicativa</a> · <a href="/wiki/Funzione_additiva" title="Funzione additiva">Funzione additiva</a> · <a href="/wiki/Convoluzione_di_Dirichlet" title="Convoluzione di Dirichlet">Convoluzione di Dirichlet</a> · <a href="/wiki/Funzione_%CF%86_di_Eulero" title="Funzione φ di Eulero">Funzione φ di Eulero</a> · <a href="/wiki/Funzione_di_M%C3%B6bius" title="Funzione di Möbius">Funzione di Möbius</a> · <a href="/wiki/Funzione_tau_sui_positivi" title="Funzione tau sui positivi">Funzione tau sui positivi</a> · <a href="/wiki/Funzione_sigma" title="Funzione sigma">Funzione sigma</a> · <a href="/wiki/Funzione_di_Liouville" title="Funzione di Liouville">Funzione di Liouville</a> · <a href="/wiki/Funzione_di_Mertens" title="Funzione di Mertens">Funzione di Mertens</a></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;"><a href="/wiki/Aritmetica_modulare" title="Aritmetica modulare">Aritmetica modulare</a></th><td colspan="1" class="navbox_list navbox_even" style="text-align:left;"><a href="/wiki/Teorema_cinese_del_resto" title="Teorema cinese del resto">Teorema cinese del resto</a> · <a href="/wiki/Piccolo_teorema_di_Fermat" title="Piccolo teorema di Fermat">Piccolo teorema di Fermat</a> · <a href="/wiki/Teorema_di_Eulero_(aritmetica_modulare)" title="Teorema di Eulero (aritmetica modulare)">Teorema di Eulero</a> · <a href="/wiki/Criteri_di_divisibilit%C3%A0" title="Criteri di divisibilità">Criteri di divisibilità</a> · <a href="/wiki/Teorema_di_Fermat_sulle_somme_di_due_quadrati" title="Teorema di Fermat sulle somme di due quadrati">Teorema di Fermat sulle somme di due quadrati</a> · <a href="/wiki/Teorema_di_Wilson" title="Teorema di Wilson">Teorema di Wilson</a> · <a href="/wiki/Reciprocit%C3%A0_quadratica" title="Reciprocità quadratica">Legge di reciprocità quadratica</a></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;"><a href="/wiki/Congettura" title="Congettura">Congetture</a></th><td colspan="1" class="navbox_list navbox_odd" style="text-align:left;"><a href="/wiki/Congettura_di_Goldbach" title="Congettura di Goldbach">Congettura di Goldbach</a> · <a href="/wiki/Congettura_di_Polignac" title="Congettura di Polignac">Congettura di Polignac</a> · <a href="/wiki/Congettura_abc" title="Congettura abc">Congettura abc</a> · <a href="/wiki/Congettura_dei_numeri_primi_gemelli" title="Congettura dei numeri primi gemelli">Congettura dei numeri primi gemelli</a> · <a href="/wiki/Congettura_di_Legendre" title="Congettura di Legendre">Congettura di Legendre</a> · <a href="/wiki/Nuova_congettura_di_Mersenne" title="Nuova congettura di Mersenne">Nuova congettura di Mersenne</a> · <a href="/wiki/Congettura_di_Collatz" title="Congettura di Collatz">Congettura di Collatz</a> · <a href="/wiki/Ipotesi_di_Riemann" title="Ipotesi di Riemann">Ipotesi di Riemann</a></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;">Altro</th><td colspan="1" class="navbox_list navbox_even" style="text-align:left;"><a href="/wiki/Problema_di_Waring" title="Problema di Waring">Problema di Waring</a></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;">Principali teorici</th><td colspan="1" class="navbox_list navbox_odd" style="text-align:left;"><a href="/wiki/Leonardo_Fibonacci" title="Leonardo Fibonacci">Fibonacci</a> · <a href="/wiki/Pierre_de_Fermat" title="Pierre de Fermat">Fermat</a> · <a href="/wiki/Carl_Friedrich_Gauss" title="Carl Friedrich Gauss">Gauss</a> · <a href="/wiki/Eulero" title="Eulero">Eulero</a> · <a href="/wiki/Adrien-Marie_Legendre" title="Adrien-Marie Legendre">Legendre</a> · <a href="/wiki/Bernhard_Riemann" title="Bernhard Riemann">Riemann</a> · <a href="/wiki/Peter_Gustav_Lejeune_Dirichlet" title="Peter Gustav Lejeune Dirichlet">Dirichlet</a></td></tr><tr><th colspan="1" class="navbox_group" style="background:#FFE0E0; text-align:right;">Discipline connesse</th><td colspan="1" class="navbox_list navbox_even" style="text-align:left;"><a href="/wiki/Teoria_algebrica_dei_numeri" title="Teoria algebrica dei numeri">Teoria algebrica dei numeri</a> · <a href="/wiki/Teoria_analitica_dei_numeri" title="Teoria analitica dei numeri">Teoria analitica dei numeri</a> · <a href="/wiki/Crittografia" title="Crittografia">Crittografia</a> · <a href="/wiki/Teoria_computazionale_dei_numeri" title="Teoria computazionale dei numeri">Teoria computazionale dei numeri</a></td></tr></tbody></table> <style data-mw-deduplicate="TemplateStyles:r140554510">.mw-parser-output .CdA{border:1px solid #aaa;width:100%;margin:auto;font-size:90%;padding:2px}.mw-parser-output .CdA th{background-color:#f2f2f2;font-weight:bold;width:20%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .CdA{border-color:#54595D}html.skin-theme-clientpref-night .mw-parser-output .CdA th{background-color:#202122}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .CdA{border-color:#54595D}html.skin-theme-clientpref-os .mw-parser-output .CdA th{background-color:#202122}}</style><table class="CdA"><tbody><tr><th><a href="/wiki/Aiuto:Controllo_di_autorit%C3%A0" title="Aiuto:Controllo di autorità">Controllo di autorità</a></th><td><a href="/wiki/Gemeinsame_Normdatei" title="Gemeinsame Normdatei">GND</a> (<abbr title="tedesco">DE</abbr>) <a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4659898-4">4659898-4</a></td></tr></tbody></table> <div class="noprint" style="width:100%; padding: 3px 0; display: flex; flex-wrap: wrap; row-gap: 4px; column-gap: 8px; box-sizing: border-box;"><div style="flex-grow: 1"><style data-mw-deduplicate="TemplateStyles:r140555418">.mw-parser-output .itwiki-template-occhiello{width:100%;line-height:25px;border:1px solid #CCF;background-color:#F0EEFF;box-sizing:border-box}.mw-parser-output .itwiki-template-occhiello-progetto{background-color:#FAFAFA}@media screen{html.skin-theme-clientpref-night .mw-parser-output .itwiki-template-occhiello{background-color:#202122;border-color:#54595D}html.skin-theme-clientpref-night .mw-parser-output .itwiki-template-occhiello-progetto{background-color:#282929}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .itwiki-template-occhiello{background-color:#202122;border-color:#54595D}html.skin-theme-clientpref-os .mw-parser-output .itwiki-template-occhiello-progetto{background-color:#282929}}</style><div class="itwiki-template-occhiello"><a href="/wiki/File:Crystal128-kmplot.svg" class="mw-file-description" title="Matematica"><img alt=" " src="//upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png" decoding="async" width="25" height="25" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/38px-Crystal128-kmplot.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/50px-Crystal128-kmplot.svg.png 2x" data-file-width="245" data-file-height="244" /></a> <a href="/wiki/Portale:Matematica" title="Portale:Matematica">Portale Matematica</a>: accedi alle voci di Wikipedia che trattano di matematica</div></div></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1&useformat=desktop" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Estratto da "<a dir="ltr" href="https://it.wikipedia.org/w/index.php?title=Algoritmo_di_Euclide&oldid=141009238">https://it.wikipedia.org/w/index.php?title=Algoritmo_di_Euclide&oldid=141009238</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Categoria:Categorie" title="Categoria:Categorie">Categorie</a>: <ul><li><a href="/wiki/Categoria:Algoritmi_aritmetici" title="Categoria:Algoritmi aritmetici">Algoritmi aritmetici</a></li><li><a href="/wiki/Categoria:Euclide" title="Categoria:Euclide">Euclide</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Categorie nascoste: <ul><li><a href="/wiki/Categoria:Controllare_-_informatica" title="Categoria:Controllare - informatica">Controllare - informatica</a></li><li><a href="/wiki/Categoria:Controllare_-_giugno_2015" title="Categoria:Controllare - giugno 2015">Controllare - giugno 2015</a></li><li><a href="/wiki/Categoria:P6706_letta_da_Wikidata" title="Categoria:P6706 letta da Wikidata">P6706 letta da Wikidata</a></li><li><a href="/wiki/Categoria:P9621_letta_da_Wikidata" title="Categoria:P9621 letta da Wikidata">P9621 letta da Wikidata</a></li><li><a href="/wiki/Categoria:P1417_letta_da_Wikidata" title="Categoria:P1417 letta da Wikidata">P1417 letta da Wikidata</a></li><li><a href="/wiki/Categoria:P3847_letta_da_Wikidata" title="Categoria:P3847 letta da Wikidata">P3847 letta da Wikidata</a></li><li><a href="/wiki/Categoria:P2812_letta_da_Wikidata" title="Categoria:P2812 letta da Wikidata">P2812 letta da Wikidata</a></li><li><a href="/wiki/Categoria:P7554_letta_da_Wikidata" title="Categoria:P7554 letta da Wikidata">P7554 letta da Wikidata</a></li><li><a href="/wiki/Categoria:Voci_con_codice_GND" title="Categoria:Voci con codice GND">Voci con codice GND</a></li><li><a href="/wiki/Categoria:Voci_non_biografiche_con_codici_di_controllo_di_autorit%C3%A0" title="Categoria:Voci non biografiche con codici di controllo di autorità">Voci non biografiche con codici di controllo di autorità</a></li><li><a href="/wiki/Categoria:Pagine_che_utilizzano_collegamenti_magici_ISBN" title="Categoria:Pagine che utilizzano collegamenti magici ISBN">Pagine che utilizzano collegamenti magici ISBN</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> Questa pagina è stata modificata per l'ultima volta il 7 set 2024 alle 12:18.</li> <li id="footer-info-copyright">Il testo è disponibile secondo la <a rel="nofollow" class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.it">licenza Creative Commons Attribuzione-Condividi allo stesso modo</a>; possono applicarsi condizioni ulteriori. Vedi le <a class="external text" href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use/it">condizioni d'uso</a> per i dettagli.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy/it">Informativa sulla privacy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:Sala_stampa/Wikipedia">Informazioni su Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:Avvertenze_generali">Avvertenze</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Codice di condotta</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Sviluppatori</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/it.wikipedia.org">Statistiche</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Dichiarazione sui cookie</a></li> <li id="footer-places-mobileview"><a href="//it.m.wikipedia.org/w/index.php?title=Algoritmo_di_Euclide&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Versione mobile</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> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-79d9bc49cc-mwztf","wgBackendResponseTime":156,"wgPageParseReport":{"limitreport":{"cputime":"0.460","walltime":"1.465","ppvisitednodes":{"value":4962,"limit":1000000},"postexpandincludesize":{"value":80935,"limit":2097152},"templateargumentsize":{"value":1968,"limit":2097152},"expansiondepth":{"value":15,"limit":100},"expensivefunctioncount":{"value":17,"limit":500},"unstrip-depth":{"value":0,"limit":20},"unstrip-size":{"value":36812,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 1188.226 1 -total"," 11.19% 132.977 1 Template:Collegamenti_esterni"," 5.92% 70.352 2 Template:Navbox"," 5.31% 63.137 1 Template:Algebra"," 4.22% 50.139 1 Template:C"," 4.02% 47.746 1 Template:Avviso"," 2.79% 33.131 1 Template:Portale"," 2.72% 32.341 1 Template:Categorie_avviso"," 2.67% 31.719 1 Template:Interprogetto"," 2.52% 29.906 4 Template:En"]},"scribunto":{"limitreport-timeusage":{"value":"0.195","limit":"10.000"},"limitreport-memusage":{"value":6533719,"limit":52428800}},"cachereport":{"origin":"mw-web.eqiad.main-864bbfd546-cc6gz","timestamp":"20241130091215","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Algoritmo di Euclide","url":"https:\/\/it.wikipedia.org\/wiki\/Algoritmo_di_Euclide","sameAs":"http:\/\/www.wikidata.org\/entity\/Q230848","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q230848","author":{"@type":"Organization","name":"Contributori ai progetti Wikimedia"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2005-07-31T20:59:32Z","dateModified":"2024-09-07T11:18:55Z","headline":"algoritmo per trovare il massimo comune divisore tra due numeri interi"}</script> </body> </html>