L'algoritmo di Euclide su 1071 e 465 raggiunge il MCD 3 attraverso i resti 141, 42, 15, 12

Prendi i resti finché uno è zero; l'ultimo resto non nullo è il massimo comun divisore.

Equazioni e algebra · Livello: Risultato classico · Aggiornato il 2026-11-10

1071 mod 465 fa 141. 465 mod 141 fa 42. 141 mod 42 fa 15, 42 mod 15 fa 12, 15 mod 12 fa 3, e 12 mod 3 fa 0. L'ultimo resto non nullo, 3, è il massimo comun divisore, e ogni passo è legittimo per lo stesso motivo: ogni numero che divide sia a sia b divide anche a − qb, quindi la coppia e il suo resto hanno esattamente gli stessi divisori. Nulla qui richiede la fattorizzazione, che è il punto pratico: 3 è la risposta molto prima che qualcuno sappia perché 1071 è 3·357.

Il numero di passi è la cosa da osservare. Lamé dimostrò nel 1844 che l'algoritmo euclideo su una coppia di interi non richiede mai più di circa cinque volte il numero di cifre decimali del più piccolo, e che i casi peggiori sono numeri di Fibonacci consecutivi: ecco perché 141, 42, 15, 12, 3 in questa pagina si restringono in fretta, nulla qui è un vicino di Fibonacci. La versione estesa della stessa tavola dei resti restituisce anche coefficienti con 3 = 1071s + 465t, l'ingrediente di ogni routine di divisione modulare in un sistema di algebra computerizzata.

Risposta

3

Come leggerla

15 mod 12, l'ultimo resto non nullo. I primi due link sono i passi iniziali, 1071 mod 465 = 141 e 465 mod 141 = 42.

Fonte

Euclid, Elements VII.1-2 describes antanairesis — repeatedly subtracting the lesser from the greater until a common measure is reached; the remainder form used here is the same procedure written with division, and 1071 = 3²·7·17 against 465 = 3·5·31 confirms the answer the remainders give

Svolgilo nella calcolatrice

Questi link aprono la calcolatrice giusta con i numeri di questo problema già digitati. La riga sopra è ciò che lo schermo dovrebbe mostrare — verifica tu stesso.

Questo è un sito di strumenti indipendente di terze parti. Non è affiliato, sponsorizzato né autorizzato da Casio, Texas Instruments o dai loro distributori. I nomi dei modelli e dei prodotti sono marchi dei rispettivi proprietari e compaiono qui solo per identificare i dispositivi.

Le sequenze di tasti in questi manuali sono state scritte a partire dai dati di layout propri di questo sito — gli stessi che usa la calcolatrice online — insieme a informazioni sul prodotto disponibili pubblicamente. Le specifiche e le configurazioni regionali sono verificate sul dispositivo fisico e sulla documentazione più recente del produttore.