L'algoritmo di Euclide per i grandi numeri, teoria

Un metodo per calcolare (trovare) il massimo comune divisore (mcd) di grandi numeri

  • Per i grandi numeri, la scomposizione in fattori primi (la fattorizzazione in numeri primi) è un processo lungo e difficile. Se dovessimo calcolare il massimo comune divisore (mcd) per numeri così grandi, allora un metodo che non si basa sulla scomposizione in fattori primi dei numeri sarebbe più che benvenuto. L'algoritmo di Euclide è uno di questi metodi per calcolare il mcd.
  • Vediamo l'esempio qui sotto. Spiegheremo anche perché funziona.
  • Questo algoritmo inizia dividendo i numeri e registrando il resto dell'operazione.
  • Se 'a' e 'b' sono i due numeri interi positivi, 'a' >= 'b'.
  • Dividi 'a' per 'b' e ottieni il resto, 'r'.
  • Se 'r' = 0, STOP. 'b' è l'mcd di 'a' e 'b'.
  • Altrimenti: sostituisci ('a' con 'b') e ('b' con 'r'). Torna al passaggio precedente.

Vediamo qual è il massimo comune divisore (mcd) dei numeri 53.667 e 25.527:

  • [1] Inizia dividendo il numero più grande per il più piccolo:
  • 53.667 : 25.527 = 2 e il Resto = 2.613 => 53.667 = 25.527 × 2 + 2.613
  • [2] Quindi dividi il numero più piccolo per il resto dell'operazione precedente:
  • 25.527 : 2.613 = 9 e il Resto = 2.010 => 25.527 = 2.613 × 9 + 2.010
  • [3] Dividi il resto della prima operazione per il resto della seconda operazione:
  • 2.613 : 2.010 = 1 e il Resto = 603 => 2.613 = 2.010 × 1 + 603
  • [4] Dividi il resto della seconda operazione per il resto della terza operazione:
  • 2.010 : 603 = 3 e il Resto = 201 => 2.010 = 603 × 3 + 201
  • [5] Dividi il resto della terza operazione per il resto della quarta operazione:
  • 603 : 201 = 3 e il Resto = 0 => 603 = 201 × 3
  • A questo punto il resto è zero, quindi ci fermiamo: 201 è il numero che stavamo cercando.
  • Concludendo:
  • 201 è l'ultimo resto diverso da zero. Questo è il massimo comune divisore, mcd, dei numeri.

Il massimo comune divisore dei due numeri è l'ultimo resto diverso da zero.

  • Se quest'ultimo resto è uguale a 1, allora i due numeri sono primi tra loro (coprime, relativamente primi).
  • Per le operazioni di cui sopra, l'ultimo resto diverso da zero, 201, è il massimo comune divisore (mcd) dei numeri 53.667 e 25.527.
  • Usando l'algoritmo di Euclide possiamo dimostrare che due numeri sono primi relativamente, vedi l'esempio seguente.

Calcola il mcd (87, 41):

  • [1] Inizia dividendo il numero più grande per il più piccolo:
  • 87 : 41 = 2 e il Resto = 5 => 87 = 41 × 2 + 5
  • [2] Quindi dividi il numero più piccolo per il resto dell'operazione precedente:
  • 41 : 5 = 8 e il Resto = 1 => 41 = 5 × 8 + 1
  • [3] Dividi il resto della prima operazione per il resto della seconda operazione:
  • 5 : 1 = 5 e il Resto = 0 => 5 = 1 × 5 + 0
  • L'ultimo resto diverso da zero delle operazioni precedenti è uguale a 1.
  • mcd (87, 41) = 1, quindi i numeri sono primi tra loro.

Ma perché il numero così ottenuto è divisore dei valori iniziali 'a' e 'b'?

  • Nota: la divisione 'a' : 'b' = 'q' + 'r' corrisponde all'equazione: 'a' = 'b' × 'q' + 'r', dove 'q' è il quoziente della divisione.
  • Se l'ultimo valore di 'r' = 0, l'ultimo valore di 'b' è un divisore dell'ultimo valore di 'a' poiché 'a' = 'b' '. $multiply.' 'q' + 0.
  • Calcoliamo il mcd (a, b):
  • 1. Passo: 'a' = 'b' × 'q1' + 'r1', 'r1' non è zero.
  • 2. Passo: 'b' = 'r1' × 'q2' + 'r2', 'r2' non è zero.
  • 3. Passo: 'r1' = 'r2' × 'q3' + 'r3', 'r3' non è zero.
  • ...
  • (n-3). Passo: 'r(n-5)' = 'r(n-4)' × 'q(n-3)' + 'r(n-3)', 'r(n-3)' non è zero.
  • (n-2). Passo: 'r(n-4)' = 'r(n-3)' × 'q(n-2)' + 'r(n-2)', 'r(n-2)' non è zero.
  • (n-1). Passo: 'r(n-3)' = 'r(n-2)' × 'q(n-1)' + 'r(n-1)', 'r(n-1)' non è zero.
  • n. Passo: 'r(n-2)' = 'r(n-1)' × 'qn' + 'rn', 'rn' = zero.
  • Il resto è zero, quindi ci fermiamo.
  • Se 'rn' = 0 => secondo il passo con il numero n: 'r(n-1)' è un divisore di 'r(n-2)'.
  • 'r(n-1)' è anche l'ultimo resto diverso da zero.
  • Secondo il passo con il numero (n-1): 'r(n-1)' è un divisore di entrambi 'r(n-1)' (il numero stesso) e 'r(n-2)', quindi è anche un divisore di 'r(n-3)'.
  • Secondo il passo con il numero (n-2): 'r(n-1)' è un divisore di entrambi 'r(n-2)' e 'r(n-3)', quindi è anche un divisore di 'r(n-4)'.
  • Secondo il passo con il numero (n-3): 'r(n-1)' è un divisore di entrambi 'r(n-3)' e 'r(n-4)', quindi è anche un divisore di 'r(n-5)'.
  • ...
  • Secondo il passo con il numero 3: 'r(n-1)' è un divisore di entrambi 'r3' e 'r2', quindi è anche un divisore di 'r1'.
  • Secondo il passo con il numero 2: 'r(n-1)' è un divisore di entrambi 'r2' e 'r1', quindi è anche un divisore di 'b'.
  • Secondo il passo con il numero 1: 'r(n-1)' è un divisore di entrambi 'r1' e 'b', quindi è anche un divisore di 'a'.
  • Quindi, abbiamo appena mostrato che l'ultimo resto diverso da zero, r(n-1), è un divisore di entrambi 'a' e 'b'.

Perché il numero ottenuto in questo modo è sempre uguale al massimo comune divisore, mcd?

  • Come abbiamo visto sopra, il resto finale diverso da zero divide senza resto sia 'a' che 'b'. Chiamiamo questo divisore 't'.
  • Secondo il passo di divisione con il numero 1: Se 't' è un divisore di entrambi 'a' e 'b', allora è anche un divisore di 'r1'.
  • Secondo il passo di divisione con il numero 2: Se 't' è un divisore di entrambi 'b' e 'r1', allora è anche un divisore di 'r2'.
  • E così via, fino al passo con il numero (n-1): Se 't' è un divisore di 'r(n-3)' e 'r(n-2)', allora è anche un divisore di 'r(n-1)'. Ma come abbiamo calcolato sopra, questo divisore è l'ultimo resto diverso da zero, che nel nostro caso lo è 'r(n-1)'.
  • Quindi, 't' non potrebbe essere maggiore di 'r(n-1)' poiché deve esserne un divisore.

Come utilizzare l'algoritmo di Euclide per più di due numeri:

  • L'algoritmo di Euclide può essere utilizzato anche per trovare il massimo comune divisore di più numeri, più di due, come 'a', 'b' e 'c'.
  • Per prima cosa calcola mcd ('a', 'b') = 'd' e poi calcola mcd ('c', 'd').

L'algoritmo di Euclide: calcola il minimo comune multiplo (mcm) per numeri grandi

  • Per numeri molto grandi, diventa impraticabile calcolare il minimo comune multiplo (mcm) perché ottenere la scomposizione in fattori primi di quei numeri richiede troppo tempo.
  • Con l'aiuto dell'algoritmo di Euclide non solo si trova il massimo comune divisore (mcd) - come visto sopra, ma si calcola anche il minimo comune multiplo (mcm) secondo la formula:
  • mcm ('a', 'b') = ('a' × 'b') / mcd ('a', 'b')

  • Questo metodo può essere utilizzato quando non ci sono più di due numeri.

Dimostrazione della formula mcm

  • Supponiamo che la scomposizione in fattori primi (la fattorizzazione in numeri primi) di 'a' e 'b' sia:
  • 'a' = 'm' × 'n' × 'p', dove 'm', 'n', 'p' sono numeri primi.
  • 'b' = 'm' × 'q' × 't', dove 'm', 'q', 't' sono numeri primi.
  • => mcm ('a', 'b') = 'm' × 'n' × 'p' × 'q' × 't'
  • => mcd ('a', 'b') = 'm'
  • Dunque:
  • ('a' × 'b') / mcd ('a', 'b') =
  • ('m' × 'm' × 'n' × 'p' × 'q' × 't') / 'm' =
  • 'm' × 'n' × 'p' × 'q' × 't' =
  • mcm ('a', 'b').