PGCD et fractions irréductibles

Le plus grand diviseur commun

Deux entiers ont toujours $1$ pour diviseur commun. Ils en ont souvent d'autres. Le plus grand s'appelle le PGCD, noté $\operatorname{pgcd}(a,b)$.

Exemple. Les diviseurs de $18$ sont $1$, $2$, $3$, $6$, $9$, $18$. Ceux de $24$ sont $1$, $2$, $3$, $4$, $6$, $8$, $12$, $24$. Les diviseurs communs sont $1$, $2$, $3$, $6$, donc $\operatorname{pgcd}(18, 24) = 6$.

Quand $\operatorname{pgcd}(a,b) = 1$, on dit que $a$ et $b$ sont premiers entre eux. $8$ et $15$ le sont : aucun premier ne les divise tous les deux. Ce n'est pas la même chose qu'être premier : $8$ n'est pas premier, et pourtant $8$ et $15$ sont premiers entre eux.

Attention au piège. Le PGCD n'est pas le plus petit des deux nombres. $\operatorname{pgcd}(12, 18) = 6$, et $6$ est plus petit que $12$ et que $18$. Il n'est pas non plus leur différence : $18 - 12 = 6$ ici par hasard, $\operatorname{pgcd}(15, 25) = 5$ et $25 - 15 = 10$.

L'algorithme d'Euclide

Lister tous les diviseurs devient impraticable dès que les nombres grossissent. Euclide remarque que les diviseurs communs à $a$ et $b$ sont exactement ceux de $b$ et du reste de la division de $a$ par $b$. On remplace donc le plus grand par ce reste, et on recommence, jusqu'à un reste nul. Le dernier reste non nul est le PGCD.

Un contrôle utile. Le PGCD divise chacun des deux nombres. Si vous trouvez $\operatorname{pgcd}(48, 18) = 8$, vérifiez : $8$ ne divise pas $18$, donc le calcul est faux, sans avoir à le refaire.

Simplifier une fraction

Une fraction $\dfrac{a}{b}$ (avec $b \neq 0$) est irréductible lorsque $\operatorname{pgcd}(a,b) = 1$. Dans le cas contraire, on simplifie en divisant le numérateur et le dénominateur par leur PGCD :

$3$ et $4$ sont premiers entre eux, donc $\dfrac{3}{4}$ est irréductible. C'est la même fraction que $\dfrac{18}{24}$ : on a multiplié haut et bas par le même nombre (ici, on a divisé, ce qui revient à multiplier par $\dfrac{1}{6}$), donc on n'a pas changé la valeur.

On peut aussi lire le PGCD sur les décompositions : on garde, pour chaque premier, la plus petite puissance. $18 = 2 \times 3^2$ et $24 = 2^3 \times 3$, donc $\operatorname{pgcd}(18,24) = 2 \times 3 = 6$.

La leçon suivante reprend les fractions pour elles-mêmes : comparaison, opérations. Ici, le PGCD n'est qu'un outil : il dit par quel nombre simplifier, et il garantit qu'après simplification il n'y a plus rien à simplifier.