2.1.2.1 Calcul du pgcd et du ppcm : l'algorithme d'Euclide

D'après ce qui précède, on peut toujours supposer que $a \geqslant b > 0$. L'algorithme^2.10 d' Euclide consiste à effectuer la division euclidienne de $\vert a\vert$ par $\vert b\vert$, puis à recommencer en remplaçant le dividende $dvd$ par le diviseur $dvs$, le diviseur par le reste $rst$, et ainsi de suite.

$$\begin{array}{rcll} dvd&=& dvs.q + rst&\\ \cline{1-3}&\\ a... ...agup& \mspace{54.0mu} \diagup&\\ r_{k-1}&=&r_kq_k& \end{array}$$

Puisque $0 \leqslant r_k<r_{k-1}<r_{k-2}<\dots<r < \vert b\vert$, il exite un indice $k$ tel que $r_{k+1}=0$ (en posant $r_{-1}=\vert b\vert$ et $r_0=r$ pour inclure le cas $r=0$ c'est-à-dire $b \mid a$).

Théorème 2.1.6
Soient $a \in {\mathbb{Z}}$ et $b \in {\mathbb{Z}}$. Le pgcd $\delta$ de $a$ et $b$ est le dernier reste non nul de l'algorithme d'Euclide. Leur ppcm $\mu$ vérifie $\delta\mu = \vert ab\vert$.

Démonstration :

On a vu qu'on peut supposer $a \geqslant b > 0$. On a pour $n \in {\mathbb{Z}}$

$$\begin{array}{lcll} n \mid a \text{ et } n \mid b &\Leftrigh... ...rightarrow& n \mid r_k & \text{car } r_{k-1}=r_kq_k \end{array}$$

Donc $r_k=\delta=$pgcd$(a,b)$ ; alors $a=a_1\delta$ $b=b_1\delta$ avec pgcd $(a_1,b_1)=1$^2.11 ; d'où pour $n \in {\mathbb{Z}}$^2.12

$$\begin{array}{lclr} a \mid n \text{ et } b \mid n &\Leftrigh... ...mid n &\\ &\Leftrightarrow& a_1b_1\delta \mid n & \end{array}$$

Donc $\mu=$ppcm$(a,b)=a_1b_1\delta$ et $\mu\delta=a_1b_1\delta^2=ab$.

C.Q.F.D.