Maths, Informatique, Jeux
Site Web réalisé par Frédéric et François WANG
Répertoire principalMathsExercicesCollègePGCD (3e)
Remarque : Les exercices de cette page changent à chaque fois que vous l'actualisez.

Sommaire

Rappels du cours
Multiples et diviseurs
PGCD, nombres premiers entre eux, simplification de fraction

Rappels du cours

Multiples et diviseurs dans l'ensemble des nombres entiers naturels

PGCD de deux nombres

Soient a et b deux entiers naturels, alors on note PGCD(a,b) le plus grand nombre entier qui soit à la fois diviseurs de a et b.

Exemple : Les diviseurs de 75 sont 1, 3, 5, 15, 25, 75 et ceux de 60 sont 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60. Donc PGCD(60,75) = 15

Remarque : Deux nombres possèdent toujours un unique PGCD. Cette démonstration n'est malheuresement pas au programme mais on peut en donner un bref aperçu. Tout d'abord on voit que les diviseurs d'un nombre lui sont toujours inférieurs, et sont donc en nombre fini. Il en est donc de même des diviseurs communs à deux nombres et (dont le nombre 1 fait toujours partie) : dans l'exemple précédent, les diviseurs communs à 75 et 60 sont 1, 3, 5, 15. Il ne reste alors plus qu'à prendre le plus grand.

Algorithmes pour trouver le PGCD de deux nombres

Deux méthodes sont généralement présentées aux collègiens pour trouver le PGCD de deux nombres a et b.

Méthode des soustractions

Cette méthode est souvent présentée aux collégiens avant l'algorithme d'Euclide car elle est plus facile à comprendre et à appliquer.

A chaque étape on effectue la soustraction du plus grand nombre par le plus petit. On commence avec les deux nombres a et b dont on veut trouver le PGCD, puis à l'étape suivante avec le plus petit nombre et la différence obtenue, et ainsi de suite... La dernière différence non nulle est le PGCD recherché.

245 - 56 = 189
189 - 56 = 133
133 - 56 = 77
77 - 56 = 21
56 - 21 = 35
35 - 21 = 14
21 - 14 = 7
14 - 7 = 7
7 - 7 = 0
Donc PGCD(245,56) = 7
 

Algorithme d'Euclide

Cette méthode est en général plus rapide que la précédente, et il est donc préférable de l'utiliser à la place de celle des soustractions.

On commence par effectuer la division euclidienne de a et b. Pour rappel, si a et b sont deux entiers et b non nul, effectuer leur division euclidienne consiste à trouver les deux entiers q et r tel que a = bq + r et 0 ≤ r < b. A l'étape suivante, on effectue cette opération entre le nombre b et le reste r, et ainsi de suite... Le dernier reste r non nul est le PGCD recherché.

245 = 56 × 4 + 21
56 = 21 × 2 + 14
21 = 14 × 1 + 7
14 = 7 × 2 + 0
Donc PGCD(245,56) = 7
 

Explications

Là encore les démonstrations des algorithmes ne sont pas au programme, mais voici quelque explications... Dans l'exemple, PGCD(245,56) = 7. Donc 7 divise 245 = 35 × 7 et 56 = 8 × 7. On peut évidemment faire cela pour n'importe quel couple de nombres, puisqu'ils ont toujours un PGCD, d'après ce que l'on a dit plus haut...

Simplification de fraction et nombre premier

Lorsque l'on a une fraction, on cherche souvent à la simplifier en divisant le numérateur et le dénominateur par un même nombre par exemple 2040 peut être simplifiée en divisant 20 et 40 par 2 : 2040=1020. La fraction est sous forme irréductible lorsque les numérateur et dénominateur sont les plus petits possibles : 2040=12. Une méthode rapide pour mettre une fraction sous forme irréductible est de diviser le numérateur et le dénominateur par leur PGCD. Par exemple 24556=358 (on divise les deux nombres par PGCD(245,56) = 7).
On dit que deux nombres sont premiers entre eux si leur PGCD est égal à 1. C'est le cas du numérateur et dénominateur d'une fraction irréductible : PGCD(35,8) = 1.
Remarque : Il ne faut pas confondre avec les nombres premiers, qui possède chacun deux diviseurs distincts qui sont 1 et lui-même : 2, 3, 5, 7, 11, 13...

Multiples et diviseurs

Exercice 1 : complétez par « est multiple de » ou « est diviseur de »

  1. 154....6
  2. 29....81
  3. 33....15
  4. 410....30
  5. 58....24
  6. 69....45
  7. 799....9
  8. 833....3

Exercice 2 : Trouver les diviseurs des nombre suivants

  1. 48
  2. 23
  3. 20
  4. 54
  5. 19

Exercice 3 : Trouver les diviseurs communs à chaque couple de nombres

  1. 10 et 170
  2. 7 et 133
  3. 7 et 140
  4. 10 et 200

Corrigé de l'exercice 1

  1. est multiple de
  2. est diviseur de
  3. est diviseur de
  4. est diviseur de
  5. est diviseur de

Corrigé de l'exercice 2

  1. 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
  2. 1, 23
  3. 1, 2, 4, 5, 10, 20
  4. 1, 2, 3, 6, 9, 18, 27, 54
  5. 1, 19

Corrigé de l'exercice 3

  1. 1, 2, 5, 10
  2. 1, 7
  3. 1, 7
  4. 1, 2, 5, 10

PGCD, nombres premiers entre eux, simplification de fraction

Exercice 1 : Calculez le PGCD des nombres suivants

  1. 448 et 1776
  2. 128 et 1584
  3. 1275 et 7035
  4. 728 et 8970
  5. 52 et 1082
  6. 270 et 3249
  7. 660 et 6930
  8. 371 et 6244

Exercice 2 : Utilisez le PGCD pour mettre ces fractions sous forme irréductibles

  1. 734762
  2. 1680895
  3. 5921536
  4. 12452410
  5. 19043312

Exercice 3 : Ces nombres sont-ils premiers entre eux ?

  1. 114 et 121
  2. 129 et 180
  3. 130 et 147
  4. 129 et 184

Corrigé de l'exercice 1

  1. 16
  2. 16
  3. 15
  4. 26
  5. 2
  6. 9
  7. 330
  8. 7

Corrigé de l'exercice 2

  1. 367381
  2. 336179
  3. 3796
  4. 249482
  5. 119207

Corrigé de l'exercice 3

  1. oui
  2. non
  3. oui
  4. oui
Cette page est conforme aux normes du W3C - Auteur : Frédéric WANG - Dernière mise à jour : jeudi 24 février 2003
Valid XHTML 1.1 Valid MathML 2.0 Valid SVG Valid CSS Amaya, the W3C browser/editor Déclaration qualité Opquast Foxkeh banners for Firefox 2