Calcul du et PGCD par la méthode des listes des diviseurs

1. La méthode des listes des diviseurs

Propriété 1. Première méthode : Les listes des diviseurs
Soient $a$ et $b$ deux nombres entiers naturels non nuls. On note ${\mathcal L}_a$ et ${\mathcal L}_b$ les listes des diviseurs de $a$ et $b$ respectivement et ${\mathcal L}_c$ la liste des diviseurs communs à $a$ et $b$. Alors le PGCD de $a$ et $b$ est égal au plus grand élément de ${\mathcal L}_c$.

2. Comment déterminer la liste des diviseurs d’un nombre entier naturel

Soit $a$ un nombre entier naturel non nul et différent de $1$. Alors, on distingue deux cas :

1er cas : $a$ est premier.

Donc $a$ n’admet que deux diviseurs : $1$ et $a$. Et on a : $$\boxed{\;\;a=1\times a\;\;}$$
La liste ${\mathcal L}_a$ des diviseurs de $a$ est donnée par : $$\boxed{\;\;{\mathcal L}_a=\{ 1;a \}\;\;}$$
On note $L_a$ la liste des diviseurs de $a$.

2ème cas : $a$ n’est pas premiers.

Comme $a$ est différent de $0$ et de $1$, $a$ admet d’autres diviseurs que $1$ et $a$.
On teste successivement la division de $a$ par les entiers successifs inférieurs à $a$ : $2$ ; $3$ ; $4$ ; $5$ ; etc. et on constate qu’à chaque fois qu’on trouve un (petit) diviseur, on obtient par symétrie un autre (grand) diviseur. On continue jusqu’à atteindre un point de bascule ou point d’équilibre.

Exemple.
Déterminer les listes des diviseurs de $18$ et $24$. Puis en déduire le PGCD de $18$ et $24$.

Liste des diviseurs de $18$ et $24$. On teste successivement la division de $18$ et de $24$ par les entiers successifs : $2$ ; $3$ ; $4$ ; $5$ ; $6$ ; etc. jusqu’à atteindre un point de bascule ou point d’équilibre. $$\begin{array}{lcl} 18=1\times 18 &~~\text{et}~~& 24=1\times 24 \\
\phantom{18}=2\times 9 &&\phantom{24}=2\times 12\\
\phantom{18}=3\times 6 && \phantom{24}=3\times 8 \\
&& \phantom{24}=4\times 6 \\
\end{array}$$
A partir du point de bascule, on retrouve les mêmes diviseurs dans l’autre sens. Donc, on s’arrête au point de bascule et on a toute la liste des diviseurs de chacun des deux nombres. On obtient donc : $$\color{brown}{\boxed{\;\;{\mathcal L}_{18}=\{ 1~;~2~;~3~;~6~;~9~;~18 \}\;\;}}\quad\text{et}\quad\color{brown}{\boxed{\;\;{\mathcal L}_{24}=\{ 1~;~2~;~3~;~4~;~6~;~8~;~12~;~24 \}\;\;}}$$
La liste des diviseurs communs à $18$ et $24$ est : $$\color{brown}{\boxed{\;\;{\mathcal L}_c=\{ 1~;~2~;~3~;~6~\}\;\;}}$$
Le plus grand élement de cette liste est $6$. Donc $$\color{brown}{\boxed{\;\;PGCD(18;24)=6\;\;}}$$
CQFD.$\blacktriangle$

Vues : 9