• Istituto
    • Chi Siamo
    • La nostra storia
  • Magazine
    • Agenda
    • Atlante
    • Il Faro
    • Il Chiasmo
    • Diritto
    • Il Tascabile
    • Le Parole Valgono
    • Lingua italiana
    • WebTv
  • Catalogo
    • Le Opere
    • Bottega Treccani
    • Gli Ebook
    • Le Nostre Sedi
  • Scuola e Formazione
    • Portale Treccani Scuola
    • Formazione Digitale
    • Formazione Master
    • Scuola del Tascabile
  • Libri
    • Vai al portale
  • Arte
    • Vai al portale
  • Treccani Cultura
    • Chi Siamo
    • Come Aderire
    • Progetti
    • Iniziative Cultura
    • Eventi Sala Igea
  • ACQUISTA SU EMPORIUM
    • Arte
    • Cartoleria
    • Design & Alto Artigianato
    • Editoria
    • Idee
    • Marchi e Selezioni
  • Accedi
    • Modifica Profilo
    • Treccani X

Euclide, algoritmo di

Enciclopedia della Matematica (2013)
  • Condividi

Euclide, algoritmo di


Euclide, algoritmo di (per il MCD) o algoritmo delle divisioni successive, algoritmo che, dati due numeri interi a e b, permette di calcolarne il → massimo comune divisore mcd(a, b). Esso si fonda su una successione finita di divisioni con resto, in modo che il divisore e il resto (qualora non nullo) di una divisione diventino rispettivamente il dividendo e il divisore della divisione successiva. L’algoritmo ha termine quando si trova un resto nullo: l’ultimo resto diverso da zero fornisce la soluzione del problema. Si può supporre che a e b siano entrambi positivi con a maggiore di b: se così non fosse, infatti, si potrebbe scambiarli eventualmente con il loro opposto e permutarli tra loro e tali operazioni non altererebbero il loro massimo comun divisore. Al primo passo, si divide a per b e, se q1 e r1 indicano rispettivamente il quoziente e il resto di tale divisione, si ottiene

formula

Se r1 = 0, allora l’algoritmo ha termine e fornisce la soluzione mcd(a, b) = b; altrimenti si procede con la divisione successiva, ottenuta dividendo b per r1:

formula

Se r2 = 0, allora l’algoritmo ha termine e fornisce la soluzione mcd(a, b) = r1; altrimenti si procede in modo analogo con le divisioni successive fintanto che si ottiene un resto rh positivo tale che il resto successivo è zero. Pertanto gli ultimi due passi saranno

formula

A questo punto l’algoritmo ha termine e fornisce la soluzione mcd(a, b) = rh.

Formalizzando le successive operazioni in linguaggio algoritmico (per poi eventualmente codificarle in un linguaggio di programmazione), si può così rappresentare l’algoritmo (in cui «mod» indica il resto della divisione intera):

formula

Per esempio, per trovare mcd(120, 264), l’algoritmo procede nel modo seguente:

mcd(120, 264) = mcd(264, 120)

b > 0 vero

r = mod(264, 120) = 24

a = 120

b = 24

b > 0 vero

r = mod(120, 24) =0

a = 24

b = 0

b > 0 falso

24 è il mcd cercato

L’algoritmo di Euclide può essere riformulato in modo sostanzialmente analogo nel caso di due polinomi a coefficienti reali in una indeterminata, purché si sostituisca a ogni passo la condizione 0 ≤ ri < ri−1 con la condizione

formula

dove ri (x) è l’i-esimo resto ottenuto e «deg» indica il grado del polinomio. Più in generale, l’algoritmo di Euclide può essere riformulato in ogni dominio euclideo D, richiedendo a ogni passo che sia verificata la condizione

formula

dove ν: D − {0} → N è la valutazione definita in D.

Vedi anche
polinomio In matematica, somma di monomi (in senso proprio, solo con riferimento a monomi interi), detti termini del p.: binomio, trinomio, quadrinomio ecc., è un polinomio rispettivamente di 2, 3, 4 ecc. termini; coefficienti di un p. sono i coefficienti dei suoi monomi; grado di un p. rispetto a una lettera ... massimo comun divisore (MCD) In matematica, dati 2 o più numeri interi, il più grande tra i divisori a essi comuni. Se due o più numeri hanno per MCD l’unità, si dicono primi tra loro. Naturalmente più numeri primi sono anche primi tra loro, ma non viceversa. Il MCD può trovarsi con il metodo delle divisioni successive, oppure ... congruenza Nella geometria elementare, sinonimo di uguaglianza (➔) diretta, cioè di sovrapponibilità. Nella teoria dei numeri, relazione di due numeri interi relativi a, b tali che la differenza a−b è divisibile per un numero intero positivo m (detto modulo di una c.); essa si scrive a≡b (mod. m) e si legge: «a ... equazione Matematica Definizioni Si chiama e. un’uguaglianza tra due espressioni contenenti una o più variabili ovvero una o più funzioni o anche enti di natura più generale ( incognite dell’e.); se essa è soddisfatta, qualunque sia la determinazione delle variabili o delle funzioni o degli enti che sono presenti ...
Tag
  • MASSIMO COMUNE DIVISORE
  • ALGORITMO DI EUCLIDE
  • DOMINIO EUCLIDEO
  • NUMERI INTERI
  • POLINOMIO
Vocabolario
algoritmo
algoritmo (ant. algorismo) s. m. [dal lat. mediev. algorithmus o algorismus, dal nome d’origine, al-Khuwārizmī, del matematico arabo Muḥammad ibn Mūsa del 9° sec. (così chiamato perché nativo di Khwarizm, regione dell’Asia Centrale)]. –...
algorìtmico
algoritmico algorìtmico agg. [der. di algoritmo] (pl. m. -ci). – Che fa uso di algoritmi o riguarda gli algoritmi: procedimento algoritmico.
  • Istituto
    • Chi Siamo
    • La nostra storia
  • Magazine
    • Agenda
    • Atlante
    • Il Faro
    • Il Chiasmo
    • Diritto
    • Il Tascabile
    • Le Parole Valgono
    • Lingua italiana
    • WebTv
  • Catalogo
    • Le Opere
    • Bottega Treccani
    • Gli Ebook
    • Le Nostre Sedi
  • Scuola e Formazione
    • Portale Treccani Scuola
    • Formazione Digitale
    • Formazione Master
    • Scuola del Tascabile
  • Libri
    • Vai al portale
  • Arte
    • Vai al portale
  • Treccani Cultura
    • Chi Siamo
    • Come Aderire
    • Progetti
    • Iniziative Cultura
    • Eventi Sala Igea
  • ACQUISTA SU EMPORIUM
    • Arte
    • Cartoleria
    • Design & Alto Artigianato
    • Editoria
    • Idee
    • Marchi e Selezioni
  • Accedi
    • Modifica Profilo
    • Treccani X
  • Ricerca
    • Enciclopedia
    • Vocabolario
    • Sinonimi
    • Biografico
    • Indice Alfabetico

Istituto della Enciclopedia Italiana fondata da Giovanni Treccani S.p.A. © Tutti i diritti riservati

Partita Iva 00892411000

  • facebook
  • twitter
  • youtube
  • instagram
  • Contatti
  • Redazione
  • Termini e Condizioni generali
  • Condizioni di utilizzo dei Servizi
  • Informazioni sui Cookie
  • Trattamento dei dati personali