Introduction à l'Algorithme d'Euclide
L'algorithme d'Euclide est une méthode efficace pour calculer le Plus Grand Commun Diviseur (PGCD) de deux nombres entiers. Cet algorithme, nommé d'après le mathématicien grec Euclide, est l'un des plus anciens algorithmes connus et est encore largement utilisé aujourd'hui.
Principe de l'Algorithme
L'algorithme d'Euclide repose sur le principe suivant : le PGCD de deux nombres est égal au PGCD du plus petit de ces nombres et du reste de la division euclidienne du plus grand par le plus petit.
Exemple :
Pour trouver le PGCD de 48 et 18 :
48 = 2 × 18 + 12
18 = 1 × 12 + 6
12 = 2 × 6 + 0Le dernier reste non nul est 6, donc PGCD(48, 18) = 6
Implémentation en Python
Voici une implémentation simple de l'algorithme d'Euclide en Python :
def pgcd(a, b):
while b != 0:
a, b = b, a % b
return a
# Exemple d'utilisation
print(pgcd(48, 18)) # Affiche : 6Note :
L'algorithme d'Euclide est très efficace, avec une complexité temporelle de O(log(min(a,b))).
Applications de l'Algorithme d'Euclide
- Simplification de fractions
- Résolution d'équations diophantiennes linéaires
- Calcul de coefficients de Bézout
- Cryptographie (notamment dans l'algorithme RSA)
Extension : L'Algorithme d'Euclide Étendu
L'algorithme d'Euclide étendu permet non seulement de calculer le PGCD de deux nombres, mais aussi de trouver les coefficients de Bézout. C'est-à-dire, pour deux entiers a et b, il trouve x et y tels que :
ax + by = PGCD(a, b)Voici une implémentation en Python :
def euclide_etendu(a, b):
if a == 0:
return b, 0, 1
else:
gcd, x, y = euclide_etendu(b % a, a)
return gcd, y - (b // a) * x, x
# Exemple d'utilisation
gcd, x, y = euclide_etendu(48, 18)
print(f"PGCD = {gcd}")
print(f"Coefficients de Bézout : x = {x}, y = {y}")
print(f"Vérification : {48}*{x} + {18}*{y} = {48*x + 18*y}")