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

Partager
Partager
dCode et plus

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 !


Rendez-vous sur notre communauté Discord dCode pour participer au forum d'entraide !
PS : Pour les messages codés, testez notre détecteur de chiffrement !


Remarques et suggestions sont les bienvenues afin que dCode propose le meilleur outil 'PGCD (Plus Grand Commun Diviseur)' gratuit ! Merci !

PGCD (Plus Grand Commun Diviseur)

Calcul du PGCD de plusieurs nombres







Calcul de PPCM

Liste des Diviseurs

⮞ Aller à : Diviseurs d'un Nombre

Réponses aux Questions (FAQ)

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 (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

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

Pourquoi calculer le PGCD du numérateur et démonimateur ?

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.

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

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 calculer le PGCD de 2 nombres connaissant leur produit et leur PPCM ?

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

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=b,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} \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) $

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

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

Quelle est la différence entre PGCD et PPCM ?

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) } $$

Code source

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.

Citation

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, https://www.dcode.fr/pgcd

Besoin d'Aide ?

Rendez-vous sur notre communauté Discord dCode pour participer au forum d'entraide !
PS : Pour les messages codés, testez notre détecteur de chiffrement !

Questions / Commentaires

Remarques et suggestions sont les bienvenues afin que dCode propose le meilleur outil 'PGCD (Plus Grand Commun Diviseur)' gratuit ! Merci !


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