11 · Divisibilité et PGCD¶
Intuition
L'arithmétique étudie les entiers avec une seule opération vraiment intéressante : la division, qui ne tombe presque jamais juste. Tout part de là — le reste, les nombres premiers, le PGCD.
Ce bloc de trois chapitres n'est pas au programme par tradition. Il est là parce que RSA repose entièrement dessus : l'algorithme d'Euclide étendu fabrique la clé privée, le théorème des restes chinois accélère le déchiffrement, et la difficulté de la factorisation fait toute la sécurité.
1. Divisibilité¶
Définition
Soient \(a, b \in \mathbb{Z}\). On dit que \(a\) divise \(b\), noté \(a \mid b\), s'il existe \(k\in\mathbb{Z}\) tel que
Le réflexe de démonstration
Traduire immédiatement \(a\mid b\) par « \(b = ak\) avec \(k\) entier ». Toute démonstration d'arithmétique élémentaire commence par poser cette écriture, puis devient du calcul littéral.
Propriétés.
| Propriété | Énoncé |
|---|---|
| Réflexivité | \(a \mid a\) |
| Transitivité | \(a\mid b\) et \(b\mid c\) \(\implies\) \(a\mid c\) |
| Combinaison linéaire | \(a\mid b\) et \(a\mid c\) \(\implies\) \(a\mid (ub+vc)\) pour tous \(u,v\in\mathbb{Z}\) |
| Zéro | \(a\mid 0\) pour tout \(a\) ; \(0\mid b\) seulement si \(b=0\) |
| Un | \(1\mid a\) et \(-1\mid a\) toujours |
| Encadrement | Si \(a\mid b\) et \(b\neq0\), alors \(\lvert a\rvert \leqslant \lvert b\rvert\) |
La propriété la plus utilisée
\(a\mid b\) et \(a\mid c\) entraîne \(a\mid(ub+vc)\).
C'est celle qui fait fonctionner l'algorithme d'Euclide, et elle sert dans presque tous les exercices. Démonstration : \(b=ak\), \(c=a\ell\), donc \(ub+vc = a(uk+v\ell)\).
2. Division euclidienne¶
Théorème
Soient \(a\in\mathbb{Z}\) et \(b\in\mathbb{N}^*\). Il existe un unique couple \((q,r)\in\mathbb{Z}\times\mathbb{N}\) tel que
\(q\) est le quotient, \(r\) le reste.
La condition \(0\leqslant r < b\) fait toute l'unicité
\(17 = 5\times3+2\) et \(17 = 5\times2+7\) sont deux écritures valides de la forme \(a = bq+r\), mais seule la première a un reste dans \([0;b[\).
Pour \(a\) négatif, le reste reste positif : \(-17 = 5\times(-4)+3\). Le quotient est \(-4\), pas \(-3\).
L'opérateur % de C et de Java n'est pas le reste euclidien
En C, C++, Java, JavaScript, -17 % 5 vaut \(-2\), pas 3 : ces langages
tronquent le quotient vers zéro.
En Python, -17 % 5 vaut 3 : le reste suit la convention
mathématique.
C'est une source de bugs classique en cryptographie et en hachage, où l'on
veut toujours un résultat dans \([0;b[\). En Java, on écrit
Math.floorMod(a, b).
Lien avec la divisibilité : \(b\mid a\) si et seulement si le reste de la division de \(a\) par \(b\) est nul.
3. Nombres premiers¶
Définition
Un entier \(p \geqslant 2\) est premier s'il n'admet que 1 et \(p\) comme diviseurs positifs.
1 n'est pas premier, par convention — sinon la décomposition en facteurs premiers ne serait plus unique.
Test de primalité naïf : il suffit de tester les diviseurs jusqu'à \(\sqrt n\).
Pourquoi \(\sqrt n\) suffit
Si \(n = ab\) avec \(1 < a \leqslant b < n\), alors \(a^2 \leqslant ab = n\), donc \(a \leqslant \sqrt n\).
Autrement dit, tout diviseur non trivial s'accompagne d'un « partenaire » de l'autre côté de \(\sqrt n\) ; en cherchant jusqu'à \(\sqrt n\) on les trouve tous. \(\blacksquare\)
Coût : \(O(\sqrt n)\) divisions. Pour un nombre de 2048 bits, cela ferait \(2^{1024}\) opérations — d'où l'utilisation de tests probabilistes (Miller-Rabin) en cryptographie.
Théorème fondamental de l'arithmétique
Tout entier \(n \geqslant 2\) s'écrit de manière unique (à l'ordre près) comme produit de nombres premiers :
Exemple. \(360 = 2^3\times3^2\times5\).
Théorème d'Euclide : il existe une infinité de nombres premiers.
Démonstration (par l'absurde)
Supposons qu'il n'y en ait qu'un nombre fini : \(p_1,\dots,p_k\). Posons
\(N \geqslant 2\) admet donc un diviseur premier \(p\), qui est nécessairement l'un des \(p_i\).
Mais \(p_i \mid p_1\cdots p_k\) et \(p_i \mid N\) entraînerait \(p_i \mid (N - p_1\cdots p_k) = 1\), ce qui est impossible pour un nombre premier.
Contradiction. \(\blacksquare\)
4. PGCD¶
Définition
Le PGCD de \(a\) et \(b\) (non tous deux nuls) est le plus grand entier positif divisant à la fois \(a\) et \(b\). On le note \(\operatorname{pgcd}(a,b)\) ou \(a\wedge b\).
Conventions : \(\operatorname{pgcd}(a,0) = |a|\), et \(\operatorname{pgcd}(0,0)\) n'est pas défini.
\(a\) et \(b\) sont premiers entre eux si \(\operatorname{pgcd}(a,b)=1\).
4.1 Par décomposition en facteurs premiers¶
Exemple. \(a = 360 = 2^3\cdot3^2\cdot5\) et \(b = 84 = 2^2\cdot3\cdot7\).
Relation fondamentale (puisque \(\min+\max\) = somme) :
Vérification : \(12\times2520 = 30\,240 = 360\times84\) ✓
La factorisation n'est PAS une méthode de calcul
Elle est parfaite en exercice avec de petits nombres. Elle est inutilisable dès que les nombres dépassent quelques dizaines de chiffres : factoriser un entier de 2048 bits est précisément le problème que personne ne sait résoudre — c'est la sécurité de RSA.
Le PGCD, lui, se calcule instantanément sur des nombres de 2048 bits. C'est tout l'intérêt de l'algorithme d'Euclide.
5. L'algorithme d'Euclide¶
Lemme fondamental
Si \(a = bq+r\), alors
Démonstration
Montrons que les deux couples ont exactement les mêmes diviseurs communs.
- Si \(d\mid a\) et \(d\mid b\), alors \(d \mid (a - bq) = r\). Donc \(d\) divise \(b\) et \(r\).
- Si \(d\mid b\) et \(d\mid r\), alors \(d\mid(bq+r) = a\). Donc \(d\) divise \(a\) et \(b\).
Les ensembles de diviseurs communs coïncident, donc leurs plus grands éléments aussi. \(\blacksquare\)
On a utilisé deux fois la propriété de combinaison linéaire du §1.
L'algorithme : on remplace \((a,b)\) par \((b, a \bmod b)\) jusqu'à obtenir un reste nul. Le dernier reste non nul est le PGCD.
5.1 Exemple¶
\(\operatorname{pgcd}(1071, 462)\) :
| Division | Reste |
|---|---|
| \(1071 = 2\times462 + 147\) | 147 |
| \(462 = 3\times147 + 21\) | 21 |
| \(147 = 7\times21 + 0\) | 0 |
Le dernier reste non nul est 21.
Vérification : \(1071 = 3\times7\times51 = 3^2\times7\times17\) et \(462 = 2\times3\times7\times11\). PGCD \(= 3\times7 = 21\) ✓
5.2 Terminaison et complexité¶
Terminaison : la suite des restes est strictement décroissante dans \(\mathbb{N}\). Elle atteint donc 0 en un nombre fini d'étapes.
Théorème de Lamé
Le nombre d'étapes de l'algorithme d'Euclide sur \((a,b)\) avec \(a>b\) est au plus \(5\) fois le nombre de chiffres décimaux de \(b\).
Autrement dit, la complexité est en \(O(\log b)\) divisions.
Le pire cas est atteint pour deux nombres de Fibonacci consécutifs — c'est là que les quotients valent tous 1, donc que les restes décroissent le plus lentement possible.
Ordre de grandeur : pour deux entiers de 2048 bits, Euclide demande moins de 3000 divisions. La factorisation, elle, est hors de portée.
Exemples traités¶
Exemple 1 — Démonstration de divisibilité
Montrer que pour tout \(n\in\mathbb{N}\), \(n(n+1)(n+2)\) est divisible par 6.
Divisible par 2 : parmi deux entiers consécutifs \(n\) et \(n+1\), l'un est pair.
Divisible par 3 : parmi trois entiers consécutifs, l'un est multiple de 3 — en effet le reste de \(n\) dans la division par 3 vaut 0, 1 ou 2, et dans chaque cas l'un des trois est divisible.
Comme 2 et 3 sont premiers entre eux et divisent tous deux le produit, leur produit \(6\) le divise aussi. \(\blacksquare\)
L'hypothèse « premiers entre eux » est indispensable
\(4\) divise \(12\) et \(6\) divise \(12\), mais \(24\) ne divise pas \(12\). On ne peut multiplier les diviseurs que s'ils sont premiers entre eux.
Exemple 2 — Euclide sur de grands nombres
\(\operatorname{pgcd}(9\,876\,543, 1\,234\,567)\) :
| Division | Reste |
|---|---|
| \(9\,876\,543 = 8\times1\,234\,567 + 32\,007\) | 32 007 |
| \(1\,234\,567 = 38\times32\,007 + 18\,301\) | 18 301 |
| \(32\,007 = 1\times18\,301 + 13\,706\) | 13 706 |
| \(18\,301 = 1\times13\,706 + 4\,595\) | 4 595 |
| \(13\,706 = 2\times4\,595 + 4\,516\) | 4 516 |
| \(4\,595 = 1\times4\,516 + 79\) | 79 |
| \(4\,516 = 57\times79 + 13\) | 13 |
| \(79 = 6\times13 + 1\) | 1 |
| \(13 = 13\times1 + 0\) | 0 |
PGCD \(= 1\) : les deux nombres sont premiers entre eux.
Neuf divisions pour des nombres à sept chiffres. Factoriser ces deux nombres aurait demandé bien davantage.
Exemple 3 — PGCD avec paramètre
Déterminer \(\operatorname{pgcd}(n, n+6)\) selon \(n\in\mathbb{N}^*\).
Par le lemme : \(\operatorname{pgcd}(n, n+6) = \operatorname{pgcd}(n, 6)\) puisque \(n+6 = 1\times n + 6\).
Le résultat dépend donc de \(n\) modulo 6 :
| Condition | PGCD |
|---|---|
| \(6\mid n\) | 6 |
| \(3\mid n\), \(n\) impair | 3 |
| \(2\mid n\), \(3\nmid n\) | 2 |
| \(n\) premier avec 6 | 1 |
Vérification : \(n=4\) donne \(\operatorname{pgcd}(4,10)=2\) ✓ \(n=9\) donne \(\operatorname{pgcd}(9,15)=3\) ✓
Erreurs fréquentes¶
| Erreur | Correction |
|---|---|
| \(a\mid b\) et \(c\mid b\) \(\implies\) \(ac\mid b\) | Faux sauf si \(a\wedge c = 1\) |
| Reste négatif | Le reste euclidien est dans \([0;b[\) |
Confondre % et le reste euclidien |
Diffèrent pour \(a<0\) en C/Java |
| 1 est premier | Non, par convention |
| Chercher les diviseurs jusqu'à \(n\) | \(\sqrt n\) suffit |
| Calculer un PGCD par factorisation | Utiliser Euclide |
Exercices¶
★ Exercice 1. Effectuer la division euclidienne.
a) 157 par 12 b) 1000 par 37 c) \(-45\) par 7 d) \(-100\) par 9
★ Exercice 2. Calculer par l'algorithme d'Euclide.
a) \(\operatorname{pgcd}(48, 18)\) b) \(\operatorname{pgcd}(1071, 1029)\) c) \(\operatorname{pgcd}(2024, 1024)\)
★ Exercice 3. Décomposer en facteurs premiers, puis en déduire PGCD et PPCM.
a) \(a=180\), \(b=126\) b) \(a=1024\), \(b=768\)
★★ Exercice 4. Montrer que pour tout \(n\in\mathbb{N}\) :
a) \(n^2+n\) est pair b) \(n^3-n\) est divisible par 6 c) \(5^n - 1\) est divisible par 4
★★ Exercice 5. Déterminer tous les entiers \(n\) tels que \(n+3\) divise \(n^2+5\).
Indication : effectuez la division euclidienne du polynôme.
★★ Exercice 6. Déterminer \(\operatorname{pgcd}(2n+3, n+1)\) pour tout \(n\in\mathbb{N}\).
★★★ Exercice 7. Soient \(a\) et \(b\) deux entiers.
a) Montrer que \(\operatorname{pgcd}(a,b) = \operatorname{pgcd}(a, b-a)\). b) Écrire un algorithme de calcul du PGCD n'utilisant que des soustractions. c) Comparer sa complexité à celle d'Euclide sur \((1000000, 1)\).
★★★ Exercice 8. Trouver tous les couples \((a,b)\) d'entiers naturels tels que
★★★ Exercice 9. Soit \(F_n\) la suite de Fibonacci.
a) Calculer \(\operatorname{pgcd}(F_n, F_{n+1})\) pour \(n\) de 1 à 8. b) Conjecturer et démontrer le résultat général. c) En déduire que l'algorithme d'Euclide sur \((F_{n+1}, F_n)\) effectue exactement \(n-1\) divisions. Pourquoi est-ce le pire cas ?
★★★★ Exercice 10. Montrer que si \(2^n - 1\) est premier, alors \(n\) est premier.
Indication : utilisez la factorisation \(a^k-1 = (a-1)(a^{k-1}+\dots+1)\).
La réciproque est-elle vraie ? Tester \(n = 11\).
★★★★ Exercice 11 — lien informatique. On veut calculer \(\operatorname{pgcd}(a,b)\) pour des entiers de \(k\) bits.
a) Écrire l'algorithme d'Euclide en Python, en version itérative. b) La version « binaire » (algorithme de Stein) remplace les divisions par des décalages de bits et des soustractions, en exploitant : \(\operatorname{pgcd}(2a,2b)=2\operatorname{pgcd}(a,b)\), \(\operatorname{pgcd}(2a,b)=\operatorname{pgcd}(a,b)\) si \(b\) impair, et \(\operatorname{pgcd}(a,b)=\operatorname{pgcd}(\frac{|a-b|}{2},\min(a,b))\) si les deux sont impairs. Justifier chacune de ces trois identités. c) Pourquoi Stein est-il plus rapide en pratique alors qu'il effectue plus d'itérations qu'Euclide ?
Corrigés¶
Corrigé — Exercice 1
a) \(157 = 12\times13 + 1\). \(q=13\), \(r=1\).
b) \(1000 = 37\times27 + 1\). \(q=27\), \(r=1\). (Car \(37\times27 = 999\).)
c) \(-45 = 7\times(-7) + 4\). \(q=-7\), \(r=4\).
Warning
Le quotient est \(-7\) et non \(-6\) : il faut que le reste soit positif. Avec \(q=-6\), on aurait \(-45 = -42 - 3\), soit un reste de \(-3\), interdit.
d) \(-100 = 9\times(-12)+8\). \(q=-12\), \(r=8\). (Car \(9\times(-12) = -108\) et \(-108+8 = -100\).)
Corrigé — Exercice 2
a) \(48 = 2\times18+12\) ; \(18=1\times12+6\) ; \(12 = 2\times6+0\). PGCD = 6.
b) \(1071 = 1\times1029+42\) ; \(1029 = 24\times42+21\) ; \(42 = 2\times21+0\). PGCD = 21.
c) \(2024 = 1\times1024+1000\) ; \(1024=1\times1000+24\) ; \(1000 = 41\times24+16\) ; \(24=1\times16+8\) ; \(16=2\times8+0\). PGCD = 8.
Corrigé — Exercice 3
a) \(180 = 2^2\cdot3^2\cdot5\), \(126 = 2\cdot3^2\cdot7\).
Vérification : \(18\times1260 = 22\,680 = 180\times126\) ✓
b) \(1024 = 2^{10}\), \(768 = 2^8\cdot3\).
Vérification : \(256\times3072 = 786\,432 = 1024\times768\) ✓
Corrigé — Exercice 4
a) \(n^2+n = n(n+1)\), produit de deux entiers consécutifs dont l'un est pair. \(\blacksquare\)
b) \(n^3-n = n(n^2-1) = (n-1)n(n+1)\), produit de trois entiers consécutifs. Divisible par 2 et par 3 (voir l'exemple 1), donc par 6. \(\blacksquare\)
c) Par la factorisation \(a^n-1 = (a-1)(a^{n-1}+\dots+1)\) avec \(a=5\) :
Le second facteur est entier, donc \(4 \mid 5^n-1\). \(\blacksquare\)
(Une récurrence marcherait aussi, mais serait plus longue.)
Corrigé — Exercice 5
Division du polynôme : \(n^2+5 = (n+3)(n-3) + 14\).
Donc \(n+3\) divise \(n^2+5\) si et seulement si \(n+3\) divise 14.
Les diviseurs de 14 dans \(\mathbb{Z}\) sont \(\pm1, \pm2, \pm7, \pm14\).
| \(n+3\) | \(n\) |
|---|---|
| \(1\) | \(-2\) |
| \(2\) | \(-1\) |
| \(7\) | \(4\) |
| \(14\) | \(11\) |
| \(-1\) | \(-4\) |
| \(-2\) | \(-5\) |
| \(-7\) | \(-10\) |
| \(-14\) | \(-17\) |
Vérification pour \(n=4\) : \(n+3 = 7\) et \(n^2+5 = 21 = 3\times7\) ✓ Pour \(n=11\) : \(14\) et \(126 = 9\times14\) ✓
La technique standard
Pour résoudre « \(A(n)\) divise \(B(n)\) », on effectue la division euclidienne de \(B\) par \(A\) : \(B = AQ + R\) avec \(R\) constant. Alors \(A\mid B \iff A\mid R\), et il ne reste que les diviseurs d'un entier fixe à énumérer.
Corrigé — Exercice 6
\(2n+3 = 2(n+1)+1\), donc par le lemme d'Euclide
\(2n+3\) et \(n+1\) sont premiers entre eux pour tout \(n\).
Vérification : \(n=5\) donne \(\operatorname{pgcd}(13,6)=1\) ✓
Corrigé — Exercice 7
a) Comme pour le lemme d'Euclide : si \(d\mid a\) et \(d\mid b\), alors \(d\mid(b-a)\) ; réciproquement si \(d\mid a\) et \(d\mid(b-a)\), alors \(d\mid a+(b-a) = b\). Mêmes diviseurs communs, même PGCD. \(\blacksquare\)
b)
def pgcd_soustraction(a, b):
a, b = abs(a), abs(b)
while a != b:
if a > b:
a = a - b
else:
b = b - a
return a
c) Sur \((1\,000\,000, 1)\) :
- Euclide : \(1\,000\,000 = 1\,000\,000\times1 + 0\). Une division.
- Soustractions : on retranche 1 à chaque tour. 999 999 itérations.
L'écart est colossal. La division euclidienne effectue « d'un coup » toutes les soustractions par le même nombre — c'est exactement ce que signifie le quotient. C'est la raison pour laquelle Euclide est en \(O(\log)\) et la version soustractive en \(O(a/b)\) dans le pire cas.
Corrigé — Exercice 8
Posons \(d = \operatorname{pgcd}(a,b) = 12\). Alors \(a = 12a'\) et \(b = 12b'\) avec \(\operatorname{pgcd}(a',b')=1\).
De la relation \(\operatorname{pgcd}\times\operatorname{ppcm} = ab\) :
Il faut donc \(a'b' = 60\) avec \(a'\) et \(b'\) premiers entre eux.
Décomposons \(60 = 2^2\cdot3\cdot5\). Chaque facteur premier doit aller entièrement dans \(a'\) ou dans \(b'\) (sinon ils auraient un facteur commun). Il y a \(2^3 = 8\) répartitions, soit 4 paires non ordonnées :
| \(a'\) | \(b'\) | \(a\) | \(b\) |
|---|---|---|---|
| 1 | 60 | 12 | 720 |
| 4 | 15 | 48 | 180 |
| 3 | 20 | 36 | 240 |
| 5 | 12 | 60 | 144 |
Vérification pour \((48,180)\) : \(48 = 2^4\cdot3\), \(180 = 2^2\cdot3^2\cdot5\). PGCD \(= 2^2\cdot3 = 12\) ✓ PPCM \(= 2^4\cdot3^2\cdot5 = 720\) ✓
(Plus les couples symétriques, si l'ordre compte.)
Corrigé — Exercice 9
a) \(F\) : \(1, 1, 2, 3, 5, 8, 13, 21, 34\).
Tous les \(\operatorname{pgcd}(F_n,F_{n+1})\) valent 1.
b) Conjecture : \(\operatorname{pgcd}(F_n, F_{n+1}) = 1\) pour tout \(n\geqslant1\).
Démonstration par récurrence.
Initialisation : \(\operatorname{pgcd}(F_1,F_2) = \operatorname{pgcd}(1,1)=1\) ✓
Hérédité. Supposons \(\operatorname{pgcd}(F_n,F_{n+1})=1\). Comme \(F_{n+2} = F_{n+1}+F_n\), le lemme d'Euclide donne
✓ \(\blacksquare\)
c) L'algorithme d'Euclide sur \((F_{n+1}, F_n)\) effectue les divisions
Tous les quotients valent 1 (puisque \(F_{n+1} < 2F_n\) dès que \(n\geqslant2\)). On descend donc d'un cran par division, jusqu'à \(F_2 = 1\times F_1 + 0\) : cela fait \(n-1\) divisions.
C'est le pire cas parce qu'un quotient de 1 est le plus petit possible : il fait décroître les restes le plus lentement. Tout quotient \(\geqslant2\) diviserait au moins par 2 la taille du reste.
Comme \(F_n \sim \frac{\varphi^n}{\sqrt5}\), le nombre de divisions est \(\approx \log_\varphi(F_n\sqrt5) \approx \frac{\ln F_n}{\ln\varphi} \approx 2{,}08 \ln F_n\) — ce qui donne, en base 10, environ 4,79 divisions par chiffre décimal. C'est exactement le théorème de Lamé, dont la constante 5 est une majoration de ce 4,79.
Corrigé — Exercice 10
Démonstration par contraposée. Supposons \(n\) non premier : \(n = ab\) avec \(1 < a, b < n\).
En posant \(x = 2^a\) :
Le premier facteur vaut \(2^a - 1 \geqslant 2^2-1 = 3 > 1\).
Le second vaut au moins \(x+1 = 2^a+1 \geqslant 5 > 1\).
Donc \(2^n-1\) est le produit de deux facteurs strictement supérieurs à 1 : il est composé.
Par contraposée, si \(2^n-1\) est premier, alors \(n\) est premier. \(\blacksquare\)
Réciproque : fausse. \(n = 11\) est premier, mais
Nombres de Mersenne
Les nombres \(M_n = 2^n-1\) avec \(n\) premier sont les nombres de Mersenne. Certains sont premiers (\(n = 2,3,5,7,13,17,19,31,\dots\)), d'autres non (\(n=11,23,29,\dots\)).
Au 30 août 2026, seuls 52 nombres premiers de Mersenne sont connus. Ils détiennent le record du plus grand nombre premier connu, parce qu'il existe pour eux un test de primalité spécifique et très efficace, le test de Lucas-Lehmer.
Corrigé — Exercice 11
a)
def pgcd(a, b):
a, b = abs(a), abs(b)
while b:
a, b = b, a % b
return a
assert pgcd(1071, 462) == 21
assert pgcd(1000000, 1) == 1
assert pgcd(0, 5) == 5
b) Justification des trois identités.
(i) \(\operatorname{pgcd}(2a,2b) = 2\operatorname{pgcd}(a,b)\). Tout diviseur commun de \(a\) et \(b\) donne, multiplié par 2, un diviseur commun de \(2a\) et \(2b\), et réciproquement tout diviseur commun pair de \(2a\) et \(2b\) se ramène à un diviseur commun de \(a,b\). Le facteur 2 se factorise dans le PGCD.
(ii) \(\operatorname{pgcd}(2a, b) = \operatorname{pgcd}(a,b)\) si \(b\) est impair. Comme \(b\) est impair, aucun diviseur commun de \(2a\) et \(b\) n'est pair. Un tel diviseur \(d\) impair divise \(2a\) et est premier avec 2, donc divise \(a\). Les ensembles de diviseurs communs coïncident.
(iii) \(a,b\) impairs. Alors \(a-b\) est pair. Par le lemme de soustraction (exercice 7a), \(\operatorname{pgcd}(a,b) = \operatorname{pgcd}(|a-b|, \min(a,b))\). Et comme \(\min(a,b)\) est impair, on peut retirer le facteur 2 de \(|a-b|\) par (ii) : \(\operatorname{pgcd}(|a-b|,\min) = \operatorname{pgcd}(\frac{|a-b|}{2},\min)\).
c) Stein effectue davantage d'itérations — jusqu'à \(O(k)\) pour des entiers de \(k\) bits, contre \(O(\log)\) divisions pour Euclide.
Mais chaque itération de Stein ne fait que des décalages de bits, des tests de parité et des soustractions : des opérations qui coûtent un cycle processeur. L'itération d'Euclide fait une division entière, qui est l'opération arithmétique la plus lente d'un processeur — typiquement 20 à 40 cycles pour des entiers machine, et bien davantage pour des grands entiers où elle est en \(O(k^2)\) ou \(O(k\log k)\).
Le bilan penche donc en faveur de Stein pour les grands entiers, malgré un nombre d'itérations supérieur.
La leçon de modélisation
« Moins d'itérations » ne signifie pas « plus rapide » : il faut compter le coût de chaque itération sur le matériel réel. C'est le même phénomène que pour l'algorithme de Strassen (Algèbre 05, exercice 11), et exactement le type d'analyse que demande le module de modélisation.
Chapitre suivant : Bézout et algorithme d'Euclide étendu.