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
Pgcd de deux entiers naturels
Exercices de perfectionnement




1. PGCD: Exercice résolu

On dispose de plusieurs façons pour trouver le pgcd de deux entiers naturels a et b.

On prendra l'exemple des deux entiers naturels:

a = 525 et
b = 420



• Méthode Des diviseurs

On ecrit tous les diviseurs du nombre a et du nombre b, ensuite on note le plus grand commun diviseur des deux nombres.

On cherche les diviseurs de 525 à partir de 2 jusqu'à √525 ou √625 = 25 qui est la racine carré du carré parfait qui vient immédiatement après. Ensuite on complète par ecrire les quotients correspondants:

525: 1, 3, 5, 7, 15, 21
  525, 175, 105, 75, 35, 25

On cherrhe les diviseurs de 420 à partir de 2 jusqu'à √420 ou √441 = 21 qui est la racine carré du carré parfait qui vient immédiatement après. Ensuite on complète par ecrire les quotients correspondants:

420: 1, 2, 3, 4, 5, 6, 7, 10, 12, 14, 15, 20
  420, 210, 140, 105 84, 70, 60, 42, 35, 30, 28, 21

Les diviseurs communs à 525 et à 420 sont
1, 3, 5, 7, 15, 21, 35, et 105.

Le plus grand est 105 .

Ainsi, le pgcd de 525 et 420 est pgcd(525, 420) = 105.

Cette méthode est trop longue!



• Méthode Des facteurs premiers

On décompose chaque nombre en un produit de facteurs premiers.

Le PGCD est alors le produit des facteurs premiers COMMUNS affectés du plus PETIT EXPOSANT .

525| 3
175| 5
35 | 5
7  | 7
1

525 = 3 x 52 x 7.

420 | 2
210 | 2
105 | 3
35  | 5
7   | 7
1

420 = 22 x 3 x 5 x 7.

Les diviseurs premiers communs à 525 et à 420 sont
3, 5, et 7.

Chacun avec son plus petit exposant, le pgcd est donc pgcd(525, 420) = 3 x 5 x 7 = 105.

Cette méthode est longue!



• Méthode Des soustractions successives

Il s'agit de faire la soustraction entre le dividende a et le diviseur b, puis ensuite la soustraction des deux petits nombres parmi les trois; jusqu'à ce qu'on trouve zéro. Le pgcd(a, b) est alors égal au nombre qui donne zéro.

525 - 420 = 105
420 - 105 = 315
315 - 105 = 210
210 - 105 = 105
105 - 105 = 0

Le pgcd(a, b) est dnc égal à 105.

Cette méthode n'est pas très longue !



• Méthode d'Algorithme d'Euclide

Il s'agit ici de faire la division euclidienne entre le dividende a et le diviseur b, puis ensuite la division euclidienne entre les diviseurs et les restes; jusqu'à ce qu'on trouve zéro. Le pgcd(a, b) est alors égal au dernier reste non nul.

525 = 420 x 1 + 105
420 = 105 x 4 + 0


Le dernier reste non nul est 105.

Donc pgcd(525, 420) = 105.

Cette méthode est la plus rapide !


2. Exercices

a) Calculer le pgcd de 60 et 42 par les trois méthodes.

b) Calcluer par trois méthodes de votre choix le pgcd des couples d'entiers naturels suivants:

18 et 42
30 et 50
45 et 66
25 et 100
105 et 180
30 et 160



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.