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
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
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
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
Applications du PGCD
Les fractions irréductibles
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
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.