Rechercher un outil
PGCD (Plus Grand Commun Diviseur)

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.

Résultats

PGCD (Plus Grand Commun Diviseur) -

Catégorie(s) : Arithmétique

dCode et vous

dCode est gratuit et ses outils sont une aide précieuse dans les jeux, les énigmes et les problèmes à résoudre au quotidien !
Vous avez un problème, une idée de projet, besoin d'un outil spécifique et dCode ne peut pas (encore) vous aider ? Vous désirez une prestation de développement sur mesure ? Contactez-moi !


dCode aime toutes les remarques et commentaires pertinents, pour avoir une réponse, laisser un email (non publié) ! C'est grâce à vous que dCode a le meilleur outil de PGCD (Plus Grand Commun Diviseur), Merci.

PGCD (Plus Grand Commun Diviseur)

Annonces sponsorisées

Calcul du PGCD de plusieurs nombres







Liste des Diviseurs

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.

Réponses aux Questions

Qu'est ce que le PGCD ? (Définition)

Le PGCD (pour plus grand commun diviseur) de deux entiers est le plus grand entier naturel est un diviseur de ces deux entiers.

Comment calculer un PGCD ? (Algorithme de calcul)

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

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

Comment trouver le PGCD avec plusieurs nombres ? (PGCD de 3 nombres ou plus)

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

Quelle est la définition de nombres premiers entre eux

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 \)

Quelle est la différence entre PGCD et PGCF ?

Le PGCF est le plus grand commun facteur, c'est l'autre nom du PGCD.

Comment calculer le PGCD avec des nombres négatifs ?

Le programme converti 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).

Comment calculer le PGCD avec des soustractions ?

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.

Comment programmer le PGCD ?

// 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=a,a%b
return a

Comment démontrer que si PGCD(b,c)=1, alors PGCD(a,b*c) = PGCD(a,b).PGCD(a,c)

En utilisant la décomposition en facteurs premiers

$$ b = p_1^{a_1} * p_2^{a_2} * ... * p_n^{a_n} $$

$$ c = q_1^{b_1} * q_2^{b_2} * ... * 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*c) \) est un produit de facteurs \( p \) et \( q \). Donc \( PGCD(a,b*c) = PGCD(a,b) * PGCD(a,c) \)

Comment calculer le PGCD avec une calculatrice (TI ou Casio)

Les calculatrices intègrent les fonction 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

Poser une nouvelle question

Code source

dCode se réserve la propriété du code source du script PGCD (Plus Grand Commun Diviseur) en ligne. Sauf code licence open source explicite (indiqué Creative Commons / gratuit), tout algorithme, applet, snippet ou logiciel (convertisseur, solveur, chiffrement / déchiffrement, encodage / décodage, encryptage / décryptage, traducteur) ou toute fonction (convertir, résoudre, décrypter, encrypter, déchiffrer, chiffrer, décoder, traduire) codé en langage informatique (PHP, Java, C#, Python, Javascript, Matlab, etc.) dont dCode a les droits ne sera pas cédé gratuitement. Pour télécharger le script en ligne PGCD (Plus Grand Commun Diviseur) pour un usage hors ligne, PC, iPhone ou Android, demandez un devis sur la page de contact !

Questions / Commentaires


dCode aime toutes les remarques et commentaires pertinents, pour avoir une réponse, laisser un email (non publié) ! C'est grâce à vous que dCode a le meilleur outil de PGCD (Plus Grand Commun Diviseur), Merci.


Source : https://www.dcode.fr/pgcd
© 2018 dCode — La 'boite à outils' indispensable qui sait résoudre tous les jeux / énigmes / géocaches. dCode
Un problème ?