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