Cours : PGCD et fractions irréductibles

PGCD et fractions irréductibles

Introduction :

Ce cours va introduire un nouvel outil mathématique utilisé en arithmétique. On y trouvera des définitions, des propriétés, des méthodes et des exemples.

Diviseurs d’un nombre entier

Propriété

$a$ et $b$ désignent des nombres entiers positifs avec $b \neq 0$. Faire la division euclidienne de $a$ par $b$, c’est déterminer le quotient $q$ et le reste $r$ tels que : $a = b \times q + r$, avec :

$q$ et $r$ des nombres entiers positifs,
$r < b$ (r est strictement inférieur à b).

Exemple

Effectuons la division euclidienne de $159$ par $17$.

On écrit : $159 = 17 \times 9 + 6$ et $ 6 < 17$. $159$ est le dividende, $17$ est le diviseur, $9$ est le quotient et $6 $ est le reste.

Propriété

$a$ et $b$ désignent des nombres entiers positifs avec $b \neq 0$.

On dit que $b$ est un diviseur de $a$ lorsque le reste de la division euclidienne de $a$ par $b$ est égal à $0$. On écrit : $a = b \times q $.

On dit aussi que $a$ est un multiple de $b$.

Exemple

Écrivons la liste des diviseurs de $28$.

$28 = 1 \times 28$

$28 = 2 \times 14$

$28 = 4 \times 7$

Les diviseurs de $28$ sont donc $\lbrace 1 ; 2 ; 4 ; 7 ; 14 ; 28 \rbrace$.

Définition

Nombre premier :

Un nombre entier strictement plus grand que $1$ qui admet exactement deux diviseurs ($1$ et lui-même) est appelé nombre premier.

Exemple

$2 ; 3 ; 5 ; 7 ; 11 ; 13 ; 17 ; 19$ sont des nombres premiers.

$1 ; 4 ; 6 ; 8 ; 9 ; 10$ ne sont pas des nombres premiers.

PGCD de deux nombres entiers

Définition

Diviseur commun :

On dit qu’un nombre est un diviseur commun de deux nombres $a$ et $b$ s’il divise à la fois $a$ et $b$.

Exemple

Établissons la liste des diviseurs communs de $28$ et $70$.

Les diviseurs de $28 $ sont $\lbrace 1 ; 2 ; 4 ; 7 ; 14 ; 28 \rbrace$.

Les diviseurs de $70$ sont $\lbrace 1; 2; 5; 7; 10; 14; 35; 70 \rbrace$.

Les diviseurs communs de $28$ et $70$ sont donc $\lbrace 1 ; 2 ; 7 ; 14 \rbrace$.

Propriété

$a$ et $b$ désignent des nombres entiers strictement positifs.

Le plus grand des diviseurs commun à $a$ et $b$ s’appelle le $PGCD$ (Plus Grand Commun Diviseur) des nombres $a$ et $b$. Il se note $PGCD(a ; b)$.

Exemple

Calculs des PGDC

Dans l’exemple précédent, dans la liste des diviseurs communs de $28$ et $70$, $14$ est le plus grand nombre. On a donc $14 = PGCD(28;70)$.
Pour les nombres $12$ et $21$ :

Les diviseurs de $12$ sont $\lbrace 1 ; 2 ; 3 ; 4 ; 6 ; 12 \rbrace$

Les diviseurs de $21$ sont $\lbrace 1; 3; 7; 21 \rbrace$

Les diviseurs communs de $12$ et $21$ sont $\lbrace 1 ; 3 \rbrace$

Donc $PGCD(12 ; 21) = 3$.

Propriété

$a$ et $b$ désignent des nombres entiers strictement positifs.

$PGCD(a;b) = PGCD(b ;a)$,
$PGCD( a;a)=a$,
$PGCD( a;1)=1$,
si $b$ est un diviseur de $a$, $PGCD( a;b)=b$.

À retenir

Deux nombres $a$ et $b$ sont premiers entre eux s’ils ont pour seul diviseur commun $1$. En d’autres termes, deux nombres $a$ et $b$ sont premiers entre eux si $PGCD( a;b)=1$.

Exemple

Les nombres $10$ et $49$ sont-ils premiers entre eux ?

Les diviseurs de $10 $ sont $\lbrace 1; 2; 5; 10 \rbrace$.

Les diviseurs de $49$ sont $\lbrace 1; 7; 49 \rbrace$.

Le seul diviseur commun de $10$ et $49$ est $1$.

Donc $PGCD(10 ; 49) = 1$ et ainsi, on montre que $10 $ et $49$ sont premiers entre eux.

Algorithme d’Euclide

Astuce

Méthode de détermination du $PGCD$ pour des nombres relativement peu élevés :

lister l’ensemble des diviseurs de $a$,
lister l’ensemble des diviseurs de $b$,
lister l’ensemble des diviseurs communs de $a$ et de $b$,
prendre le plus grand élément de cette liste et l’identifier comme $PGCD( a;b)$.

Propriété

$a$ et $b$ désignent des nombres entiers strictement positifs avec $a>b$.

On note $r$ le reste de la division euclidienne de $a$ par $b$.

Alors :

$PGCD(a;b)=PGCD(b;r)$.

Exemple

Calculons le $PGCD $de $1 058$ et $76$.

On effectue la division euclidienne de $1 058$ par $76$ :

$1 058 = 76 \times 13 + 70$

d’où $PGCD(1 058 ; 76) = PGCD(76 ; 70)$

$76 = 70 \times 1 + 6$

d’où $PGCD(76 ; 70) = PGCD(70 ; 6)$

$70 = 6 \times 11 + 4$

d’où $PGCD(70 ; 6) = PGCD(6;4)$

$6=4\times1+2$

d’où $PGCD(6 ; 4) = PGCD(4;2)$

$4=2\times2+0$

Or $PGCD(4;2)=2$ donc $PGCD(1 058; 76) = 2$

Récapitulons dans le tableau suivant :

À retenir

Dans l’algorithme d’Euclide, le $PGCD$ est le dernier reste non nul ($2$ dans cet exemple).

Applications du PGCD

Les fractions irréductibles

Définition

Fraction irréductible :

La fraction $\dfrac{a}{b}$ est dite irréductible si les nombres $a$ et $b$ sont premiers entre eux.

À retenir

Une fraction est irréductible lorsque l’on ne peut plus simplifier son écriture, c’est-à-dire si son numérateur et son dénominateur n’admettent pas de diviseurs communs (à part $1$).

Exemple

$\dfrac{15}{8}$ est irréductible car $15$ et $8$ n’ont en commun que $1$ comme diviseur. On peut aussi dire que $15$ et $8$ sont premiers entre eux.

Astuce

Le $PGCD$ est très utile pour simplifier des écritures fractionnaires : pour rendre une fraction $\dfrac{a}{b}$ irréductible, il suffit de la simplifier par le $PGCD$ de $a$ et $b$.

Exemple

Simplifions $\dfrac{70}{28}$ et $\dfrac{1058}{76}$

On a vu que $PGCD(28;70) = 14$, donc $\dfrac{70}{28} = \dfrac{70 \div 14}{28 \div 14} = \dfrac{5}{2}$, qui est une fraction irréductible.
On a vu que $PGCD(1058;76) = 2$, donc $\dfrac{1058}{76} = \dfrac{1058 \div 2}{76 \div 2} = \dfrac{529}{38}$, qui est une fraction irrréductible.

Un problème de partage

À retenir

Dans les problèmes de partage de quantités en parts identiques, on utilise le $PGCD$ de ces quantités pour la recherche des solutions optimales.

Exemple

Dans un collège, il y a $108$ filles et $135$ garçons. On veut utiliser tous les élèves pour créer des groupes identiques (contenant chacun autant de filles que de garçons).

Le nombre de groupes possible doit nécessairement être un diviseur commun de $108$ et $135$.

Le nombre maximal de groupes possible sera le plus grand de ces diviseurs communs, c’est-à-dire $PGCD(135;108) = 27$.

On pourra donc former au maximum $27$ groupes identiques.

De plus, il y aura $4$ filles et $5$ garçons dans chaque groupe.