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,Mathématiques

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 !


dCodeur lit tous les messages et y répond si vous indiquez un email (non publié) ! C'est grâce à vous que dCode a le meilleur outil de PGCD (Plus Grand Commun Diviseur), Merci.

Voici la nouvelle version de dCode
Qu'en pensez-vous ?   Retour version précédente

PGCD (Plus Grand Commun Diviseur)

Annonces sponsorisées

Cet outil a été mis à jour, merci de signaler tout problème.

Calcul du PGCD de plusieurs nombres



Liste des Diviseurs

Aussi sur dCode : Diviseurs d'un Nombre

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

Comment calculer un PGCD ? (Algorithme de calcul)

Méthode 1 : lister les diviseurshref des nombres et trouver le plus grand commun.

Soient les nombres 10 et 12, on cherche le PGCD

10 a pour diviseurshref 1,2,5,10.

12 a pour diviseurshref 1,2,3,4,6,12.

Le plus grand commun diviseur est 2.

Méthode 2 : utiliser l'algorithme d'Euclide

Etape 1. On réalise une division euclidiennehref du plus grand des deux nombres A par le second B, pour trouver un dividende D et un reste R. On conserve les nombres B et R.

Etape 2. Répéter l'étape 1 (avec les nombres conservés) jusqu'à arriver à un reste nul.

Etape 3. Le PGCD de A et B est égal au dernier reste non nul.

12 / 10 = 1 reste 2

10 / 2 = 5 reste 0, le reste est nul

Le PGCD est donc le dernier reste non nul : 2

Méthode 3 : utiliser la décomposition en facteurs premiershref

10 = 2 * 5

12 = 2 * 2 * 3

Le PGCD est le produit des facteurs communs (multiplicationhref)

PGCD (10,12) = 2

Comment calculer un PGCD avec plusieurs nombres ? (PGCD de 3 nombres ou plus)

Méthode 1 : lister les diviseurshref des nombres et trouver le plus grand commun.

Soient les nombres 10, 20 et 25, on cherche le PGCD

10 a pour diviseurshref 1,2,5,10.

20 a pour diviseurshref 1,2,4,5,10,20.

25 a pour diviseurshref 1,5,25.

Le plus grand commun diviseur est 5.

Méthode 2 : utiliser la formule PGCD(a,b,c) = PGCD( PGCD (a,b) , c )

PGCD (10,20) = 10

PGCD (10,20,25) = PGCD( PGCD(10,20), 25) = PGCD(10, 25) = 5

Méthode 3 : utiliser la décomposition en facteurs premiershref

10 = 2 * 5

20 = 2 * 2 * 5

25 = 5 * 5

Le PGCD est la multiplicationhref des facteurs communs

PGCD (10,20,25) = 5

Quelle est la définition de nombres premiers entre eux

Deux nombres a et b sont dits premiers entre euxhref 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 euxhref si leur PGCD est 1.

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.

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). Par convention, seule la valeur positive est retenue.

Comment calculer le PGCD avec des soustractions ?

Une méthode alternative aux divisions euclidiennehref successive : les soustractions successives basé sur ls propriétés pgcd(a,b) = pgcd(b,a) = pgcd(b,a-b) = pgcd(a,b-a).

PGCD(12, 10) = PGCD(10, 12-10=2) = PGCD(2, 10-2=6) = PGCD(6, 6-2=4) = 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);
}

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 premiershref

$$ 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 q

Or PGCD(a,b) = un produit de facteurs p

Et PGCD(a,c) = un produit de facteurs q

Et PGCD(a,b*c) = 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 calculatriceshref intègrent les fonction de PGCD sous le nom de GCD (Greatest Common Divisor). Si non voici des programmes

Pour Casio"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 TIInput "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

dCodeur se réserve la propriété du code source du script PGCD (Plus Grand Commun Diviseur). Sauf code licence open source explicite (gratuit / freeware), tout algorithme, applet ou logiciel (convertisseur, solveur, chiffrement / déchiffrement, encodage / décodage, encryptage / décryptage, traducteur) ou tout snippet ou fonction (convertir, résoudre, décrypter, encrypter, déchiffrer, chiffrer, décoder, traduire) écrit en langage PHP (ou Java, C#, Python, Javascript, etc.) dont dCode a les droits pourra être cédé(e) après devis. Donc si vous avez besoin de télécharger le script PGCD (Plus Grand Commun Diviseur) hors ligne pour vous, votre entreprise ou association, rendez-vous sur la page de contact !

Questions / Commentaires


dCodeur lit tous les messages et y répond si vous indiquez un email (non publié) ! C'est grâce à vous que dCode a le meilleur outil de PGCD (Plus Grand Commun Diviseur), Merci.


Source : http://www.dcode.fr/pgcd
© 2016 dCode — Le site 'boite à outils' indispensable qui sait résoudre tous les problèmes. dCode