Conversions    
 
  Units   
 
  Le carré de Durer   
 
  Optimisation  
 
  home  
 
  ask us  
 

 

Mathématiques
2

Propriétés des
nombres entiers


Calculateurs


Exercices de
perfectionnement



© The scientific sentence. 2010


Mathématiques 45: Arithmétique
Le Plus Grand Commun Divisuer (PGCD)




1. Définition du PGCD de deux nombres


Le plus grand diviseur d'un nombre, c'est lui même.

Le plus grand commun diviseur (PGCD) de deux nombres est le diviseur commun à ces deux nombres, mais le plus grand.

Pour trouver le PGCD de deux nombres entiers, on dispose de trois façons.



2. PGCD de deux nombres
méthode de listes de diviseurs


2.1. La méthode

On dresse la liste des diviseurs des deux nombres selon les étapes suivantes:

• On développe les deux nombres en produit de facteurs premiers,
•On note tous les facteurs communs aux deux nombres ,
•On fait le produit de ses facteurs communs,
•Ce produit est le PGCD de ses nombes.



2.2. Exemple

On cherche le pgcd de 420 et 45.

• Liste des diviseurs de 420:
420 = 2 x 2 x 3 x 5 x 7 = 22 x 3 x 5 x 7


• Liste des diviseurs de: 45
45 = 3 x 3 x 5 = 32 x 5

15 est le plus grand commun diviseur, donc

pgcd(450,45)= 15



3. PGCD de deux nombres
méthode de soustractions successives


3.1. La méthode

On procède selon les étapes suivantes:

• On soustrait le plus petit des deux nombres du plus grand,
• On note les deux plus petits nombres parmi les trois,
• On soustrait le plus petit des deux nombres du plus grand,
• On note les deux plus petits nombres parmi les trois,
• On soustrait le plus petit des deux nombres du plus grand,
• ...
• On continue jusqu'à ce qu'on trouve zéro.

Le pgcd est le dernier résultat non nul.



3.2. Exemple

On cherche le pgcd de 420 et 45.

• On soustrait le plus petit des deux nombres du plus grand: 420 - 45 = 375
• On note les deux plus petits nombres parmi les trois: 375 et 45 et on recommence:
• 375 - 45 = 330
• 330 - 45 = 285
• 285 - 45 = 240
• 240 - 45 = 195
• 195 - 45 = 150
• 150 - 45 = 105
• 105 - 45 = 60
• 60 - 45 = 15
• 45 - 15 = 30
• 30 - 15 = 15 : dernir résultat non nul.
• 15 - 15 = 0
on trouve zéro.

Le pgcd est le dernier résultat non nul = 15 .



4. PGCD de deux nombres:
Algorithme d'Euclide


4.1. La méthode

On considère deux nombres a et b, a le plus grand.

On procède selon les étapes suivantes:

• On fait la division euclidienne du plus grand nombre (a) par le plus petit (b):
a = b x q + r,
• On recommence la division avec le diviseur (b) et le reste (r) de la division précédente:
b = r x q' + r'
• On répète les deux étapes,
• On s'arrête lorsque le reste est nul.

Le Pgcd est le dernier reste non nul.



4.2. Exemple

On cherche le pgcd de 420 et 45.

420 = 45 x 9 + 15
45 = 15 x 3 + 0

Le Pgcd est le dernier reste non nul = 15 .



Vérifier vos résulats par ce logiciel





  


chimie labs
|
Physics and Measurements
|
Probability & Statistics
|
Combinatorics - Probability
|
Chimie
|
Optics
|
contact
|


© Scientificsentence 2010. All rights reserved.