Aide pour la navigation
Contacts
- Connexion
- Livre d'or
- Forum
- Auteurs
- Liens
Grandes parties
Collège

Maths, Informatique, Jeux

Site Web réalisé par Frédéric et François WANG

Répertoire principal→ Maths→ Exercices→ Collège→ PGCD (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

Soit n est un nombre entier naturel. Tout nombre de la forme k × n (avec k entier naturel) est appelé multiple de n. Exemple : 12 = 4 × 3 est un multiple de 3.
Si a est un multiple de b, alors b est un diviseur de a. Exemple : 5 est un diviseur de 45 = 9 × 5.

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.

Quand on écrit 245 - 56 = 189, cela revient à : 35 × 7 - 8 × 7 = 189 ⇔ (35 - 8) × 7 = 189 ⇔ 189 = 27 × 7. 189 est donc un multiple de 7, ou autrement dit, 7 est un diviseur de 189. C'est d'ailleurs le PGCD(189,56) car si on trouvait un diviseur commun à 189 et 56 supérieur à 7, alors il diviserait aussi 245 = 189 + 56 et serait un diviseur commun à 245 et 56, ce qui est impossible. En répetant le procédé, on trouve PGCD(245,56) = PGCD(189,56) = PGCD(133,56) = ... PGCD(7, 7) = 7.
Il s'agit du même raisonnement appliqué à 245 = 56 × 4 + 21. On a en effet 21 = 245 - 56 × 4 = 7 × (35 - 8 × 4) = 7 × 3. Donc 7 = PGCD(56,21). En continuant on aurait PGCD(245,56) = PGCD(56,21) = PGCD(21,14) = PGCD(14,7) = 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

\frac{20}{40}

peut être simplifiée en divisant 20 et 40 par 2 :

\frac{20}{40} = \frac{10}{20}

. La fraction est sous forme irréductible lorsque les numérateur et dénominateur sont les plus petits possibles :

\frac{20}{40} = \frac{1}{2}

. 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

\frac{245}{56} = \frac{35}{8}

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