1071 mod 465 fait 141. 465 mod 141 fait 42. 141 mod 42 fait 15, 42 mod 15 fait 12, 15 mod 12 fait 3, et 12 mod 3 fait 0. Le dernier reste non nul, 3, est le plus grand commun diviseur, et chaque pas est légitime pour la même raison : tout nombre qui divise à la fois a et b divise aussi a − qb, donc le couple et son reste ont exactement les mêmes diviseurs. Ici il n'est besoin de factoriser quoi que ce soit, et c'est le point pratique : 3 est la réponse bien avant que quiconque sache pourquoi 1071 est 3·357.
Le nombre de pas est ce qu'il faut surveiller. Lamé a démontré en 1844 que l'algorithme d'Euclide sur une paire d'entiers ne prend jamais plus d'environ cinq fois le nombre de chiffres décimaux du plus petit, et que les pires cas sont des nombres de Fibonacci consécutifs ; c'est pour cela que 141, 42, 15, 12, 3 sur cette page rapetissent vite : ici rien n'est voisin de Fibonacci. La version étendue de la même table de restes renvoie aussi des coefficients avec 3 = 1071s + 465t, l'ingrédient de toute routine de division modulaire dans un système de calcul formel.
Réponse
3
Comment la lire
15 mod 12, le dernier reste non nul. Les deux premiers liens sont les pas initiaux, 1071 mod 465 = 141 et 465 mod 141 = 42.
Source
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
Résolvez-le dans la calculatrice
Ces liens ouvrent la calculatrice appropriée avec les nombres de ce problème déjà saisis. La ligne ci-dessus correspond à ce que l'écran devrait afficher : vérifiez par vous-même.