F |
acciamo il punto.
Argomenti correlati:
|
- Divisori o fattori
- Un numero intero b diverso da zero 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 è diverso da zero e c=0
a = MCD(a,c).
Se a=0 e c è diverso da zero
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:
1, 2, 3, 4, 6, 12 sono divisori comuni di 24 e 60.
12 è il loro massimo comun divisore.
|
|
|
Spesso, per trovare il massimo comun divisore di due numeri, si procede in questo modo:
- Si scompongono i due numeri in fattori primi;
- 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 a,b, che indichiamo con MCD(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)
- In questo caso a = 80; b = 25
- Calcoliamo r = resto della divisione fra 80 e 25: r = 5
- 5 risulta diverso da zero e dunque operiamo le sostituzioni:
- Ripetiamo il procedimento e calcoliamo r = resto della divisione fra 25 e 5: r = 0
- Poiché risulta r = 0 MCD(25,5) = 5 ed anche MCD(80,25) = 5.
Dunque, con il metodo di Euclide, l'ultimo divisore è il massimo comun divisore cercato.
| |
PROVA IL METODO DI EUCLIDE
|
|  webfract@tin.it
|
|
