Calculatrice Euclide Etendu (Bezout)

Algorithme d'Euclide etendu : calcule gcd(a,b) et coefficients de Bezout ax+by=g. Inverse modulaire a^(-1) mod n, équations diophantiennes ax+by=c par etapes.

Paramètres de calcul
Scegli il tipo di calcolo.
Primo intero. In mod_inverse: elemento da invertire.
Secondo intero o modulo n nell'inverso.
Solo per ax + by = c. Soluzioni esistono sse gcd(a, b) divide c.
Ce calculateur vous a-t-il été utile ?

L'algorithme d'Euclide etendu

L'algorithme d'Euclide etendu (EEA) calcule gcd(a, b) et les coefficients de Bezout x, y tels que a·x + b·y = gcd(a, b). Théorème de Bezout (1753) : ces x, y existent pour toute paire. Complexite O(log min(|a|, |b|)).

Algorithme

De a = 1·a + 0·b, b = 0·a + 1·b, on itere r_(i+1) = r_(i-1) − q_i·r_i, s_(i+1) = s_(i-1) − q_i·s_i, t_(i+1) = t_(i-1) − q_i·t_i avec q_i = floor(r_(i-1)/r_i). Termine en r_(i+1) = 0, laissant r_i = gcd et (s_i, t_i) = (x, y).

Les quatre modes

  1. Euclide classique : gcd avec divisions.
  2. Bezout : coefficients x, y.
  3. Inverse modulaire a^(-1) mod n (cas gcd(a, n) = 1).
  4. Diophantien ax + by = c : solution particulière + générale.

Théorème de Bezout

Pour tout couple a, b : il existe x, y dans ℤ avec a·x + b·y = gcd(a, b). a et b coprimes sse il existe ax + by = 1.

Inverse modulaire

gcd(a, n) = 1 → a^(-1) mod n = x mod n ou ax + ny = 1 via EEA. Exemple : 17^(-1) mod 43 = 38.

Équations diophantiennes

ax + by = c a des solutions entières sse gcd(a, b) | c. Solution générale : x = x_0 + (b/g)·k, y = y_0 − (a/g)·k, k ∈ ℤ.

Applications

  • RSA : cle privee d = e^(-1) mod φ(n) via EEA.
  • Courbes elliptiques : inversion modulaire.
  • Théorème des restes chinois.
  • Réduction a la forme de Smith.
  • Codes Reed-Solomon, BCH sur GF(p^m).

Variantes

  • Euclide binaire (Stein 1967) : remplace les divisions par des decalages de bits ; plus rapide sur CPU sans division efficiente.
  • Lehmer : approxime les quotients par les chiffres de poids fort ; plus efficace pour tres grands nombres (> 1000 bits).
  • Half-gcd : diviser pour regner avec O(M(n)·log n) ou M(n) est le coût de la multiplication ; utilise dans GMP, NTL, FLINT pour des nombres de millions de bits.

Exemple detaille pas a pas

Calculons EEA(240, 46) : 240 = 5·46 + 10 ; 46 = 4·10 + 6 ; 10 = 1·6 + 4 ; 6 = 1·4 + 2 ; 4 = 2·2 + 0. gcd = 2. En reconstruisant : 2 = 6 − 1·4 = 6 − 1·(10 − 1·6) = 2·6 − 1·10 = 2·(46 − 4·10) − 1·10 = 2·46 − 9·10 = 2·46 − 9·(240 − 5·46) = −9·240 + 47·46. Verification : −9·240 + 47·46 = −2160 + 2162 = 2 = gcd. ✓

Histoire et portee

Euclide (300 av. J.-C.) decrit l'algorithme de base dans les Éléments livre VII, propositions 1-2 : le premier algorithme non trivial des mathématiques. Bezout (1730-1783) en donne la forme étendue avec coefficients. Knuth (TAOCP vol. 2, 1969) l'analyse en profondeur et prouve la complexite logarithmique.

Inverses modulaires et leur role en cryptographie

L'application la plus precieuse de l'algorithme d'Euclide etendu est le calcul des inverses modulaires. Un nombre a possede un inverse modulo n, c'est-a-dire une valeur qui multipliee par a donne un modulo n, si et seulement si a et n sont premiers entre eux, et l'algorithme le fournit immediatement : le coefficient de Bezout x de l'equation a x + n y = 1 est precisement cet inverse, ramene a la bonne plage. C'est l'operation de "division" dans l'arithmetique modulaire, impossible par des methodes directes.

Cette capacite est au coeur de la cryptographie moderne. Dans le systeme RSA, generer la cle privee consiste exactement a trouver l'inverse modulaire de l'exposant public par rapport a une quantite derivee des facteurs premiers, une etape resolue par l'algorithme d'Euclide etendu. La meme operation apparait dans le theoreme des restes chinois, dans la cryptographie sur courbes elliptiques et dans d'innombrables protocoles. Sans une methode rapide pour inverser modulairement, une bonne partie de la securite numerique que nous utilisons chaque jour serait irrealisable.

Equations diophantiennes lineaires : quand des solutions entieres existent

L'algorithme resout aussi les equations diophantiennes lineaires, de la forme a x + b y = c, ou l'on cherche des solutions avec x et y entiers. Le theoreme de Bezout donne la condition exacte d'existence : de telles solutions existent si et seulement si le plus grand commun diviseur de a et b divise c. Quand c'est le cas, a partir d'une solution particuliere on engendre une famille infinie, x = x_0 + (b/g) k et y = y_0 - (a/g) k pour tout entier k, que la calculatrice expose explicitement.

Ces equations apparaissent dans des problemes quotidiens deguises. Le classique casse-tete des cruches d'eau, ou il faut mesurer une quantite exacte avec des recipients de capacites fixes, est une equation diophantienne ; le sont aussi certains problemes de rendu de monnaie avec des pieces de valeurs donnees, ou de synchronisation d'evenements se repetant a des periodes differentes. La meme theorie sous-tend le theoreme des restes chinois, outil central en arithmetique modulaire et dans l'acceleration des calculs cryptographiques.

Mis à jour en juillet 2026

Questions fréquentes

Qu'est-ce que l'algorithme d'Euclide etendu ?

C'est un algorithme qui, outre le calcul du plus grand commun diviseur gcd(a, b), trouve les coefficients de Bezout x et y tels que a x + b y = gcd(a, b). Il etend l'ancien algorithme d'Euclide en suivant comment le gcd s'exprime comme combinaison lineaire de a et b. Il a une complexite O(log min(|a|, |b|)).

Qu'est-ce que le theoreme de Bezout ?

Il affirme que pour tout couple d'entiers a et b il existe des entiers x et y tels que a x + b y = gcd(a, b). Autrement dit, le plus grand commun diviseur est toujours exprimable comme combinaison lineaire entiere des deux nombres. Le nom vient d'Etienne Bezout, qui le formalisa au XVIIIe siecle.

Quels modes offre la calculatrice ?

Quatre : l'algorithme d'Euclide classique avec les etapes des divisions, l'identite de Bezout avec les coefficients x et y, le calcul de l'inverse modulaire, et la resolution des equations diophantiennes lineaires ax + by = c avec toute la famille de solutions.

Qu'est-ce que l'inverse modulaire ?

C'est un nombre qui, multiplie par a, donne 1 modulo n. Il existe si et seulement si a et n sont premiers entre eux, soit gcd(a, n) = 1. Il s'obtient de l'algorithme d'Euclide etendu : le coefficient x de l'equation a x + n y = 1, reduit modulo n, est justement l'inverse. C'est la "division" dans l'arithmetique modulaire.

Pourquoi l'inverse modulaire est-il important en cryptographie ?

Parce que c'est l'etape cle de la generation des cles RSA : la cle privee est l'inverse modulaire de l'exposant public par rapport a une quantite derivee des facteurs premiers. Le meme calcul apparait dans le theoreme des restes chinois, dans la cryptographie sur courbes elliptiques et dans de nombreux protocoles de securite.

Quand une equation diophantienne a-t-elle des solutions ?

L'equation a x + b y = c a des solutions entieres si et seulement si gcd(a, b) divise c (theoreme de Bezout). Si la condition est verifiee, a partir d'une solution particuliere (x_0, y_0) on obtient toutes les autres avec x = x_0 + (b/g) k et y = y_0 - (a/g) k, pour tout entier k.

Qui a invente l'algorithme d'Euclide ?

Euclide le decrivit vers 300 av. J.-C. dans les Elements, livre VII : il est considere comme le premier algorithme non trivial des mathematiques. La forme etendue avec les coefficients fut developpee plus tard, et Donald Knuth en donna une analyse approfondie demontrant la complexite logarithmique.

A quoi sert l'algorithme d'Euclide etendu ?

A calculer des inverses modulaires pour la cryptographie (RSA, courbes elliptiques), a resoudre des equations diophantiennes lineaires, a appliquer le theoreme des restes chinois, a simplifier des fractions et a reduire des congruences. C'est un outil fondamental de la theorie des nombres et de l'informatique.

Commentaires (0)

Pas encore de commentaire. Soyez le premier !