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.