PGCD et PPCM

Sommaire

Introduction
Liste des diviseurs
Division euclidienne
Soustractions successives
Décomposition en facteurs premiers
PPCM
Simplification de fractions
Nombres premiers entre eux
Exercices

Introduction

Dans ce cours nous allons parler du PGCD, qui est le Plus Grand Diviseur Commun.
Tu auras remarqué que cela devrait donc être PGDC et non PGCD. PGCD signifie donc Plus Grand Commun Diviseur, mais c’est plus joli de dire plus grand diviseur commun
Mais qu’est-ce-que le PGCD ? Comme son nom l’indique, c’est un diviseur. Pour trouver les diviseurs, il faut parfaitement connaître les règles de divisibilité. Tu es donc fortement invité à voir (ou à revoir) ces règles sur la divisibilité qui ont été détaillées ici.
De plus, ce PGCD est un diviseur commun, mais commun à qui ? Et bien tout simplement à deux autres nombres.
Par exemple 24 et 16 sont tous les deux divisibles par 2, donc 2 est un diviseur commun à 24 et 16.
Mais 24 et 16 sont également divisibles par 4, et par 8, donc 4 et 8 sont aussi des diviseurs communs à 4 et 8.
Le PGCD, c’est tout simplement le plus grand de tous ces diviseurs communs.

Nous verrons également le PPCM, qui signifie Plus Petit Commun Multiple, tu verras que c’est assez simple avec la méthode que nous expliquerons

Liste des diviseurs

Si tu as bien suivi le petit exemple dans l’introduction avec 16 et 24, tu auras peut-être deviné que la première méthode pour calculer le PGCD de deux nombres est de faire la liste des diviseurs de chaque nombre.
On regarde ensuite ceux qui sont en commun, et on prend le plus grand parmi tous ces diviseurs communs (d’où le terme de plus grand diviseur commun^^).

Mais comment faire la liste de tous les diviseurs ?
Comme c’est plus simple de l’expliquer en vidéo, regarde ces deux exemples !
Dans la première vidéo il s’agit de trouver les diviseurs de 24 et de 64.
Dans la deuxième vidéo il faut trouver les diviseurs de 560.

Pour notre exemple avec 16 et 24, tu devrais obtenir :
16 : 1 – 2 – 4 – 8 – 16
24 : 1 – 2 – 3 – 4 – 6 – 8 – 12 – 24

Une fois que l’on a la liste des diviseurs de chaque nombre, on ne garde que ceux qui apparaissent dans les deux listes (c’est-à-dire les diviseurs COMMUNS).
Les diviseurs communs sont 1 – 2 – 4 – 8

Il suffit ensuite de prendre le plus grand : c’est le PGCD.
Le plus grand est 8, donc le pgcd de 16 et 24 est 8 !

Cela se note :

\(\displaystyle pgcd(16 \, ; \, 24) = 8 \)

Bien sûr cette technique de calcul marche surtout pour les petits nombres, si on te demande le pgcd de 512 et 846, cela peut être long et compliqué de faire tous les diviseurs de 512 et 846… Rassure-toi il existe d’autres méthodes que nous allons étudier !

Division euclidienne

Haut de page

La division euclidienne est la méthode généralement utilisée pour calculer le pgcd. Dans les exercices la méthode de calcul est parfois imposée, et c’est souvent la méthode de la division euclidienne qui est demandée.

Le principe est de poser successivement des divisions comme on le faisait à l’école primaire (souvenirs souvenirs…).
Mais au fait, quelle est la différence entre une division euclidienne et une division tout court ?
Là encore deux petites vidéos vont t’expliquer tout ça.
Dans la première vidéo il faut faire trois divisions euclidiennes.
Dans la 2ème c’est la division euclidienne de 68 par 5. On précisera en détails dans cette vidéo le vocabulaire.

Tu sais donc maintenant comment écrire une division euclidienne, et tu as appris des mots : dividende, diviseur, quotient et reste selon le schéma suivant :

On peut écrire la division euclidienne a = q × b + r, avec r < b (la condition r < b est très importante !!!).
Remarque : dans la suite nous écrirons directement les divisions sous forme d’égalité mais bien sûr tu peux poser la division au brouillon comme dans la vidéo avant d’écrire l’égalité

L’idée va être de réaliser successivement des divisions euclidiennes entre le diviseur et le reste (donc b par r).
Reprenons l’exemple de 90 et 125.
Nous allons d’abord écrire la division de 125 par 90, puis celle du diviseur et du reste en recommençant à chaque fois jusqu’à obtenir un reste nul (r = 0).
125 = 1 × 90 + 35 : b = 90 et r = 35, donc on fait la division de 90 par 35.
90 = 2 × 35 + 20 : b = 35 et r = 20, donc on fait la division de 35 par 20.
35 = 1 × 20 + 15
20 = 1 × 15 + 5
15 = 3 × 5 + 0

Le reste étant nul, on s’arrête !! (en effet on ne peut pas faire la division de 5 par 0 puisqu’on ne peut pas diviser par 0…).

\(\displaystyle Le \, pgcd \, est \, alors \)

\(\displaystyle le \, dernier \, reste \, non \, nul \)

Ici le dernier reste non nul est 5, donc pgcd(90 ; 125) = 5.


ATTENTION !! Quand tu écris la division euclidienne, écris-la bien sous forme a = q × b + r et non a = b × q + r.
Ce n’est pas faux évidemment, mais cela est beaucoup plus simple pour savoir quelle division effectuer ensuite.
En effet, si tu écris 30 = 7 × 4 + 2, comment savoir si ensuite on divise 7 par 2 ou 4 par 2 ?
On sait qu’à chaque fois il faut diviser le b par le r et non le q par le r, donc si tu prends l’habitude d’écrire a = q × b + r, tu sauras qui tu dois diviser par qui…
Pour vérifier que tu ne t’es pas trompé, tu peux regarder à la fin si les restes se retrouvent bien quotient puis dividende comme sur l’image ci-dessous :

Autre exemple : calculons pgcd(240; 84)
240 = 2 × 84 + 72
84 = 1 × 72 + 12
72 = 6 × 12 + 0

Le dernier reste non nul est 12, donc pgcd(240; 84) = 12.

Comme tu le vois cette méthode peut être assez rapide, le tout est de ne pas se tromper dans les calculs !



Soustractions successives

Haut de page

La méthode par soustractions successives est assez simple, mais peut s’avérer très longue dans certains cas !
Si on cherche pgcd(a ; b) par exemple, on va calculer a – b.
On va avoir une équation du style a – b = t, où t est le résultat de la soustraction.
Ensuite, on va refaire des soustractions entre les deux plus petits nombres (qui sont toujours b et t).
Et on recommence jusqu’à obtenir 0.
Le dernier résultat non nul sera le pgcd.

Exemple : calcul du pgcd(15 ; 21)
21 – 15 = 6 : entre 6, 15 et 21 les deux plus petits sont 15 et 6.
15 – 6 = 9
9 – 6 = 3
6 – 3 = 3
3 – 3 = 0

Comme on obtient 0, on regarde le résultat de l’avant-dernière ligne, à savoir 3 (celui qui est souligné).
Donc pgcd(15 ; 21) = 3


Remarque : évidemment on fait toujours le plus grand moins le plus petit, par exemple on fait 9 – 6 et non 6 – 9 pour ne pas avoir un résultat négatif…

Autre exemple : pgcd(30 , 105)
105 – 30 = 75
75 – 30 = 45
45 – 30 = 15
30 – 15 = 15
15 – 15 = 0

Le dernier résultat non nul est 15, donc pgcd(30 ;105) = 15.

Sur ces 2 exemples le problème est résolu en 4 lignes. Voyons maintenant un exemple beeeeeeeaaaaaaauuuuucoup plus long

Pgcd(96 ; 100) :
100 – 96 = 4
96 – 4 = 92
92 – 4 = 88
88 – 4 = 84
84 – 4 = 80
80 – 4 = 76
76 – 4 =

Tu l’auras compris, avant d’arriver à 0 on est pas sorti de l’auberge…
Cette technique n’est donc pas adaptée à tous les calculs de pgcd, le problème est qu’on ne peut pas savoir à l’avance si cela va être rapide avec cette méthode ou non…
Le mieux est de ne faire cette technique qu’avec des petits nombres (au maximum 30 par exemple), ou bien si l’énoncé demande explicitement d’appliquer cette méthode.

Décomposition en facteurs premiers

Haut de page

Une autre technique pour calculer le pgcd de deux nombres est de les décomposer en facteurs premiers.
Mais qu’est-ce-qu’un facteur premier ? C’est un diviseur qui est un nombre premier.
Et qu’est-ce-qu’un nombre premier ? C’est un nombre qui n’est divisible que par 1 et lui-même.

Par exemple 7 est un nombre premier car on ne peut pas le diviser par autre chose que 1 et 7.
Idem pour 11.
En revanche 6 n’est pas premier car il est divisible par 2 (et par 3).
15 n’est pas premier car il est divisible par 3 (et par 5).
16 n’est pas premier car il est divisible par 2 (et par 4 et 8).


Les nombres premiers les plus courants que tu rencontreras sont :
2 – 3 – 5 – 7 – 11 – 13 – 17 – 19

L’idée va être d’écrire le nombre sous forme de produit en commençant par 2, puis 3, puis 5 etc…
Exemple avec 72 :
72 = 2 × 36
72 = 2 × 2 × 18
72 = 2 × 2 × 2 × 9
72 = 2 × 2 × 2 × 3 × 3

On s’arrête puisqu’il n’y a plus que des nombres premiers.
On regroupe ensuite sous forme de puissance :
72 = 23 × 32

Autre exemple : 260
260 = 2 × 130
260 = 2 × 2 × 65
260 = 2 × 2 × 5 × 13

On s’arrête puisqu’il n’y a plus que des nombres premiers.
On regroupe ensuite sous forme de puissance :
260 = 2 2 × 5 × 13

Dans ces exemples on a décomposé dans l’ordre, d’abord par 2, puis par 3, puis 5 etc…
Rien ne t’empêche évidemment de prendre un autre ordre, en décomposant avec les nombres que tu veux.
260 = 10 × 26
260 = 2 × 5 × 2 × 13
260 = 2 × 2 × 5 × 13
260 = 2 2 × 5 × 13

Plusieurs remarques : il faut développer tous les nombres obtenus jusqu’à obtenir des nombres premiers.
Pour 10 × 26, ni le 10 ni le 26 ne sont premiers, il faut donc les décomposer.

De plus, tu as dû remarqué qu’à la fin on a remis les facteurs dans l’ordre (du plus petit au plus grand).
Cela est important pour regrouper ensuite les facteurs identiques sous forme de puissance.

Dernier exemple : 450
450 = 10 × 45
450 = 2 × 5 × 9 × 5
450 = 2 × 5 × 3 × 3 × 5
450 = 2 × 3 × 3 × 5 × 5
450 = 2 × 32 × 52

Bon maintenant que l’on a vu comment décomposer en facteurs premiers, comment trouver le pgcd de 2 nombres ??
Première étape : décomposer les 2 nombres en facteurs premiers (tu devais t’en douter )
Deuxième étape : garder UNIQUEMENT ce qu’il y a en commun dans chaque décomposition en facteurs premiers.

Par exemple :
260 = 22 × 51 × 131
450 = 21 × 32 × 52
(On a mis exprès les puissances 1, tu verras après pourquoi)

Dans chaque décomposition il y a 2 et 5, donc on garde
En revanche il n’y a pas de 13 dans 450, ni de 3 dans 260, donc on ne garde pas.

Mais quelle puissance de 2 et 5 garder ?
On garde la puissance la plus PETITE entre les deux décompositions.
Dans 260 il y a 22 alors que dans 450 il y a 21, donc on garde 21 !
De même dans 260 il y a 51 alors que dans 450 il y a 52, donc on garde 51.

Le pgcd est donc 21 × 51 = 10.
Pgcd(260 ; 450) = 10.

Autre exemple : pgcd(1047816 ; 189917728) (tu m’amuseras à faire les décompositions )
1047816 = 23 × 35 × 72 × 111
189917728 = 25 × 73 × 113 × 131

Ce qu’il y a en commun (en conservant les plus petites puissances) est :
23 × 72 × 111 = 4312
Donc pgcd(1047816 ; 189917728) = 4312.

Le plus compliqué dans cette méthode est la décomposition en facteurs premiers (l’exemple ci-dessus est volontairement compliqué pour t’expliquer le principe de ce qu’il faut garder, évidemment tu auras toujours des nombres plus simples à décomposer ). Mais une fois les décompositions des deux nombres effectuées le principe est assez simple.



PPCM

Haut de page

Comme l’on vient de voir la décomposition en facteurs premiers, profitons-en pour voir comment calculer le PPCM, à savoir le Plus Petit Commun Multiple.
Pour comprendre ce que c’est, prenons un exemple : calculons le PPCM de 3 et 4.
On va faire la liste des multiples de 3 et des multiples de 4 :
3 – 6 – 9 – 12 – 15 – 18 – 21 – 24 – 27 – 30 – 33 – 36 – 39 – 42 – 45 – 48 – 51 etc…
4 – 8 – 12 – 16 – 20 – 24 – 28 – 32 – 36 – 40 – 44 – 48 – 52 etc…
Il s’agit alors de regarder les nombres communs, et de prendre le plus PETIT (d’où le nom de plus petit commun multiple…).

Ici il n’y a que 12, 24 et 48 en commun. Le plus petit est 12 : c’est le PPCM !
Donc ppcm(3 ; 4) = 12.

Evidemment rien ne sert de faire toute la liste des multiples, à partir du moment où on en trouve un en commun ce sera le plus petit, donc le ppcm.

Avec 3 et 4 on peut faire facilement la liste des multiples, mais pour de plus grands nombres cela peut vite devenir compliqué…c’est là qu’intervient la décomposition en facteurs premiers !
Le principe est de décomposer chacun des deux nombres.
Ensuite, à l’inverse du pgcd, on prend TOUT ce qu’il y a dans chaque décomposition, même si ce n’est pas en commun !!
Petite précision : s’il y a des facteurs communs, on prend la PLUS GRANDE puissance et non la plus petite comme c’était le cas pour le pgcd.
Exemple :
260 = 22 × 51 × 131
450 = 21 × 32 × 52

Pour 2 on prend 22 (la plus grande puissance)
Pour 3 on prend 32 (qui est dans 450 mais pas dans 260)
Pour 5 on prend 52 (la plus grande puissance)
Pour 13 on prend 131 (qui est dans 260 mais pas dans 450)

Ce qui donne : 22 × 32 × 52 × 131 = 11700
Donc ppcm(260 ; 450) = 11700

Au niveau de la décomposition, c’est la même chose que pour le pgcd. En revanche, pour savoir ce que l’on garde, c’est l’inverse du pgcd (on prend la plus grande puissance, même ce qui n’est pas en commun).

Simplification de fractions

Haut de page

Une des applications du pgcd est la simplification de fractions.
En effet, simplifier une fraction revient à trouver les diviseurs communs au numérateur et au dénominateur. Et comme on veut simplifier la fraction au maximum, il faut trouver le plus grand diviseur commun, c’est-à-dire le pgcd !

Ainsi, pour simplifier une fraction, on calcule le pgcd du numérateur et du dénominateur, et on factorise chacun par ce pgcd.
Exemple : on avait vu que pgcd(260 ; 450) = 10
Donc :

\(\textstyle \frac{260}{450} = \frac{10 \times 26}{10 \times 45} \)

\(\textstyle \frac{260}{450} = \frac{26}{45} \)

Autre exemple : pgcd(30 ; 105) = 15. D’où :

\(\textstyle \frac{105}{30} = \frac{15 \times 7}{15 \times 2} \)

\(\textstyle \frac{105}{300} = \frac{7}{2} \)

Comme tu le vois c’est plutôt simple. Pour vérifier que tu ne t’es pas trompé, vérifie bien que la fraction finale est irréductible (26/45 et 7/2 sont bien des fractions irréductibles).

Nombres premiers entre eux

Haut de page

Avant de passer aux exercices, voyons une dernière petite chose : les nombres premiers ENTRE EUX.
Nous avions vu précédemment qu’un nombre premier était un nombre dont les seuls diviseurs sont 1 et lui-même (par exemple 2, 3, 5, 7 etc…)

Il ne faut surtout pas confondre avec des nombres premiers ENTRE EUX !!

Déjà il s’agit d’une relation entre deux nombres, alors qu’un nombre premier est une caractéristique d’un nombre (un nombre est premier ou il ne l’est pas).
La définition de deux nombres premiers entre eux est simple : deux nombres sont premiers entre eux si leur pgcd vaut 1.

Par exemple : pgcd(260 ; 450) = 10, donc 260 et 450 ne sont pas premiers entre eux.
pgcd(4 ; 9) = 1, donc 4 et 9 sont premiers entre eux (et pourtant 4 et 9 ne sont pas premiers…)


ATTENTION !! Il n’existe pas de lien entre nombre premier et nombres premiers entre eux !!
7 est premier mais 7 n’est pas premier avec 21 (car pgcd(7 ; 21) = 7).
4 et 9 sont premiers entre eux (pgcd(4 ; 9) = 1) et pourtant 4 et 9 ne sont pas premiers.

Exercices

A venir prochainement !

Retour au sommaire des coursRemonter en haut de la page