HOME

Contatti

MATEMATICA CON JAVASCRIPT


MASSIMO COMUN DIVISORE CON IL METODO DI EUCLIDE
PRIMA PARTE - METODO PASSO PER PASSO
F
acciamo il punto.
Argomenti correlati:


Divisori o fattori

Un numero intero b ≠ 0 si dice divisore - o fattore - di un intero a (e si scrive b|a) se esiste un intero c tale che risulti a = bc.
a si dice in questo caso multiplo di b.

Massimo comun divisore

Se a=0 e c=0 non è possibile calcolare MCD(a,c).
Se a ≠ 0 e c=0
    a = MCD(a,c).
Se a=0 e c ≠ 0
    c = MCD(a,c).
Se b|a e b|c, si dice che b è un divisore comune di a e c.
Quando, inoltre, ogni divisore di a e di c è anche un divisore di b, allora si dice che b è il massimo comun divisore fra a e c, e si scrive b=MCD(a,c).

ESEMPIO:
Siano A ={insieme dei divisori di 60}
B = {insieme dei divisori di 24}.

Risulta:

 

A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 30, 60}

B = {1, 2, 3, 4, 6, 12, 24}

A ∩ B = {1, 2, 3, 4, 6, 12}

12 è il massimo dei divisori comuni

 

IN EVIDENZA DAL SITO

 


www.tommasobientinesi.it

La passione per i viaggi e la natura nel nuovo sito di Tommaso Bientinesi

 

Spesso, per trovare il massimo comun divisore di due numeri, si procede in questo modo:

  1. Si scompongono i due numeri in fattori primi;
  2. Si prendono i fattori comuni ai due numeri, ciascuno preso una sola volta, con il minimo esponente.
Tale metodo non è il più adatto per il computer; è invece preferibile usare l'algoritmo di Euclide,che si trova nel Libro degli elementi
.

Medodo di Euclide per il calcolo del massimo comun divisore fra due numeri    

Indichiamo con MCD(a,b) il massimo comun divisore fra due numeri a,b

Sia r il resto della divisione fra a,b.
Se risulta r = 0 allora MCD(a,b) = b;
altrimenti
     MCD(a,b) = MCD(b,r).
Applichiamo il metodo per calcolare MCD(80,25)
  1. In questo caso a = 80; b = 25
  2. Calcoliamo r = resto della divisione fra 80 e 25: r = 5
  3. 5 ≠ 0 e dunque operiamo le sostituzioni:
    • a = 25
    • b = 5
  4. Ripetiamo il procedimento e calcoliamo r = resto della divisione fra 25 e 5: otteniamo r = 0
  5. Allora MCD(25,5) = 5 e anche MCD(80,25) = 5.
Dunque, con il metodo di Euclide, l'ultimo divisore è il massimo comun divisore cercato.

 

PROVA IL METODO DI EUCLIDE PASSO PER PASSO    
   

Possiamo intanto compendere meglio il funzionamento dell'algoritmo di Euclide applicando il metodo passo per passo.

Basta seguire le istruzioni riportate a destra.

Calcola il massimo comun divisore fra

a =

b =

 

ISTRUZIONI

  • Il programma genera automaticamente due numeri interi dei quali è possibile calcolare il MCD. E' però anche possibile inserirne due a scelta nelle caselle di testo.
  • Per iniziare premi il pulsante AVVIA.
  • Per passare alla prossima fase:
    1. premi il pulsante SOSTITUISCI;
    2. premi il pulsante ... PASSO.
  • Il processo termina quando il resto della divisione è zero.
  • In questo caso si legge il massimo comun divisore.

Per calcolare un nuovo MCD premi il pulsante

Con questa premessa, svilupperemo ora il codice del programma che calcola il massimo comun divisore di due numeri interi con il metodo di Euclide.

Seconda parte

IN EVIDENZA DAL SITO

 



CALCOLATRICE
SCIENTIFICA


CON SPIEGAZIONI
ED ESEMPI

 



TARTAMONDO - PER BAMBINI



AREA GIOCHI

 

 

 

 

 


 

INDICE

©2002 - 2013 www.webfract.it