GCD
Le PGCD (plus grand commun diviseur) est le plus grand entier positif qui divise deux entiers ou plus, calculé efficacement par l'algorithme d'Euclide.
Objectif
Trouver le plus grand facteur commun d'entiers, utilisé dans la réduction de fractions et en théorie des nombres.
Mécanisme
Algorithme d'Euclide : gcd(a,b) = gcd(b, a mod b), jusqu'à b=0. L'algorithme d'Euclide étendu trouve en outre les coefficients de Bézout x,y tels que ax+by=gcd(a,b), utilisés pour les inverses modulaires. lcm(a,b) = |a×b|/gcd(a,b).
Cas d’usage
- Réduction de fractions
- Calcul d'inverses modulaires
- Validation de clés RSA
- Arithmétique rationnelle
Exemples
- entrée
gcd(48, 18)Output648=6×8, 18=6×3
Erreurs courantes
- gcd with 0 left unhandled
- gcd(a,0)=|a|, gcd(0,0)=0
Termes associés
LCM
Le PPCM (plus petit commun multiple) est le plus petit entier positif multiple de deux entiers ou plus, calculé via le PGCD. GLOSSAIRE
Modular Arithmetic
L'arithmétique modulaire prend les restes après les opérations entières, en gardant les résultats dans [0, n) ; c'est le fondement de la théorie des nombres et de la cryptographie. GLOSSAIRE
Prime Number
Un nombre premier est un entier naturel supérieur à 1 divisible uniquement par 1 et par lui-même ; c'est la brique élémentaire de la théorie des nombres, et tout entier se décompose de façon unique en facteurs premiers. GLOSSAIRE