Outil pour calculer le PGCD. Le plus grand commun diviseur de deux entiers est le plus grand entier naturel qui divise simultanément ces deux entiers.
PGCD (Plus Grand Commun Diviseur) - dCode
Catégorie(s) : Arithmétique
dCode est gratuit et ses outils sont une aide précieuse dans les jeux, les maths, les énigmes, les géocaches, et les problèmes à résoudre au quotidien !
Une suggestion ? un problème ? une idée ? Écrire à dCode !
Méthode de calcul de PGCD 1 : lister les diviseurs des nombres et trouver le plus grand diviseur commun.
Exemple : PGCD des nombres 10 et 12.
10 a pour liste de diviseurs 1,2,5,10
12 a pour liste de diviseurs 1,2,3,4,6,12
Le plus grand commun diviseur à ces listes est 2 (le plus grand nombre présent dans toutes les listes).
Donc PGCD(10,12) = 2
Méthode de calcul de PGCD 2 : utiliser l'algorithme d'Euclide (méthode préférée pour les calculatrice)
Etape 1. Réaliser une division euclidienne du plus grand des deux nombres A par le second B, pour trouver un dividende D et un reste R. Conserver les nombres B et R.
Etape 2. Répéter l'étape 1 (avec les nombres conservés : B devient le nouveau A et R devient le nouveau B) jusqu'à arriver à un reste nul.
Etape 3. Le PGCD des nombres A et B de départ est égal au dernier reste non nul.
Exemple : A=12, B=10, calculer (étape 1) A/B = 12/10 = 1 reste R=2
(étape 2) 10/2 = 5 reste 0, le reste est nul.
(étape 3) Le PGCD est le dernier reste non nul : 2. Donc PGCD(10,12) = 2.
Méthode de calcul de PGCD 3 : utiliser la décomposition en facteurs premiers
Le PGCD est le produit des facteurs communs (c'est à dire, la multiplication des nombres présents dans toutes les décompositions)
Exemple : Les nombres 10 et 12 dont les décompositions en facteurs premiers sont : 10 = 2 * 5 et 12 = 2 * 2 * 3. Le seul facteur commun est 2. Donc PGCD(10,12) = 2
Méthode de calcul de PGCD 4 : connaissant le PPCM, utiliser la formule PGCD(a, b) = a * b / PPCM(a, b)
Exemple : Le PPCM de 10 et 12 est 60, donc PGCD(10, 12) = 10 * 12 / 60 = 2
Méthode PGCD 1 : lister les diviseurs des nombres et trouver le plus grand commun.
Exemple : Recherche du PGCD des nombres 10, 20 et 25.
10 a pour diviseurs 1,2,5,10.
20 a pour diviseurs 1,2,4,5,10,20.
25 a pour diviseurs 1,5,25.
Le plus grand commun diviseur est 5.
Méthode PGCD 2 : utiliser la formule PGCD(a,b,c) = PGCD( PGCD(a,b) , c )
Exemple : PGCD(10,20) = 10
Exemple : PGCD(10,20,25) = PGCD( PGCD(10,20), 25) = PGCD(10, 25) = 5
Méthode PGCD 3 : utiliser la décomposition en facteurs premiers
Exemple : 10 = 2 * 5
20 = 2 * 2 * 5
25 = 5 * 5
Le PGCD est la multiplication des facteurs communs
Exemple : PGCD(10,20,25) = 5
Pour simplifier une fraction, il est possible de diviser le numérateur et de démonimateur par leur PGCD afin d'obtenir une fraction irréductible.
Deux nombres $ a $ et $ b $ sont dits premiers entre eux si il n'y a aucun nombre à part $ 1 $ qui soit à la fois diviseur de $ a $ et de $ b $.
Deux nombres $ a $ et $ b $ sont dits premiers entre eux si leur PGCD est $ 1 $ : $ pgcd(a,b) = 1 $
Le PGCF est le plus grand commun facteur, c'est l'autre nom du PGCD.
Le programme convertit les nombres négatifs en positifs. Cependant pour être rigoureux mathématiquement, tout dépend de la définition du PGCD retenue, défini sur N*, il est toujours positif, défini sur Z* il est positif ou négatif, mais c'est le même à un coefficient -1 près. Par convention, seule la valeur positive est retenue. $$ PGCD(a,b) = PGCD(-a,b) = PGCD(a,-b) = PGCD(-a,-b) $$
Exemple : Dans ce second cas, pour toutes les solutions proposées l'opposé est aussi valable : PGCD(6,9) = PGCD(-6,9) = PGCD(6,-9) = PGCD(-6,-9) = 3 (ou -3).
Une méthode alternative aux divisions euclidiennes successive : les soustractions successives basé sur la propriété $$ pgcd(a,b) = pgcd(b,a) = pgcd(b,a-b) = pgcd(a,b-a) $$
Exemple : PGCD(12, 10) = PGCD(10, 12-10=2) = PGCD(2, 10-2=8) = PGCD(8, 8-2=6) = PGCD(6, 8-6=2) = PGCD(6, 6-2=4) = PGCD(4, 6-4=2) = PGCD(4, 4-2=2) = PGCD(2, 2) = 2.
Utiliser la formule $ PGCD(a,b) = (a \times b) / PPCM(a, b) $
avec $ a \times b $ le produit des 2 nombres et PPCM leur plus petit commun multiple
// JAVASCRIPT
function pgcd(a,b) {
return (b==0)?a:pgcd(b,a%b);
}
// PHP
function pgcd($a,$b) {
return ($b==0)?$a:pgcd($b,$a%$b);
}
// Python
def pgcd(a, b):
while b!=0:
a,b=b,a%b
return a
En utilisant la décomposition en facteurs premiers
$$ b = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_n^{a_n} $$
$$ c = q_1^{b_1} \times q_2^{b_2} \times \cdots \times q_m^{b_m} $$
Comme PGCD(b,c)=1, aucun des facteurs $ p $ n'est égal à un facteur $ q $. Or $ PGCD(a,b) $ est un produit de facteurs p et et $ PGCD(a,c) $ est un produit de facteurs $ q $ et $ PGCD(a, b \times c) $ est un produit de facteurs $ p $ et $ q $. Donc $ PGCD(a, b \times c) = PGCD(a,b) \times PGCD(a,c) $
Les calculatrices intègrent les fonctions de PGCD sous le nom de GCD (Greatest Common Divisor). Si non voici des programmes
Pour Casio// Calcul PGCD
"A=" : ? -> R
"B=" : ? -> Y
I -> U : 0 -> W : 0 -> V : I -> X
While Y <> 0
Int(R/Y) -> Q
U -> Z : W -> U : Z-Q*W -> W
V -> Z : X -> V : Z-Q*X -> X
R -> Z : Y -> R : Z-Q*Y -> Y
WhileEnd
"U=" : U : "V=" : V
"PGCD=" : R
Pour TI (82,83,84,89)Input "A=", R
Input "B=", Y
I -> U : 0 -> W : 0 -> V : I -> X
While Y <> 0
Int(R/Y) -> Q
U -> Z : W -> U : Z-Q*W -> W
V -> Z : X -> V : Z-Q*X -> X
R -> Z : Y -> R : Z-Q*Y -> Y
End
Disp "U=", U, "V=3, V
Disp "PGCD=", R
Le PGCD est un diviseurs communs à 2 nombres, donc un nombre plus petit ayant les 2 nombres comme multiples.
Le PPCM est un multiple commun à 2 nombres, donc un nombre plus grand ayant les 2 nombres comme diviseurs.
Le PGCD et le PPCM sont reliés par la formule : $$ PGCD(a, b) = \frac{ a \times b }{ PPCM(a, b) } $$
dCode se réserve la propriété du code source pour "PGCD (Plus Grand Commun Diviseur)". Sauf code licence open source explicite (indiqué Creative Commons / gratuit), l'algorithme pour "PGCD (Plus Grand Commun Diviseur)", l'applet ou snippet (convertisseur, solveur, chiffrement / déchiffrement, encodage / décodage, encryptage / décryptage, traducteur) ou les fonctions liées à "PGCD (Plus Grand Commun Diviseur)" (calculer, convertir, résoudre, décrypter / encrypter, déchiffrer / chiffrer, décoder / encoder, traduire) codés en langage informatique (Python, Java, C#, PHP, Javascript, Matlab, etc.) ou les données, en téléchargement, script, ou les accès API à "PGCD (Plus Grand Commun Diviseur)" ne sont pas publics, idem pour un usage hors ligne, PC, mobile, tablette, appli iPhone ou Android !
Rappel : dCode est gratuit.
Le copier-coller de la page "PGCD (Plus Grand Commun Diviseur)" ou de ses résultats est autorisée (même pour un usage commercial) tant que vous créditez dCode !
L'exportation des résultats sous forme de fichier .csv ou .txt est gratuite en cliquant sur l'icone export
Citer comme source bibliographique :
PGCD (Plus Grand Commun Diviseur) sur dCode.fr [site web en ligne], consulté le 04/10/2024,