Exercice 12

1. Étape 1 : l'algorithme d'Euclide. $$\begin{aligned} 87 &= 31\times 2+25 \qquad (L_{1}) \\ 31 &= 25\times 1+6 \qquad (L_{2}) \\ 25 &= 6\times 4+1 \qquad (L_{3}) \\ 6 &= 1\times 6+0 \end{aligned}$$ Le dernier reste non nul vaut $1$, donc $\mathrm{PGCD}(87,31)=1$ : $\boxed{87 \text{ et } 31 \text{ sont premiers entre eux}}$

Étape 2 : la remontée. On isole le $1$ dans $(L_{3})$, puis on remplace successivement les restes en remontant les lignes, de façon à faire réapparaître $87$ et $31$. $$\begin{aligned} 1 &= 25-\textcolor{#9e0018}{6}\times 4 &&\text{or d'après } (L_{2}), \; 6=31-25\times 1 \\ &= 25-\textcolor{#9e0018}{(31-25)}\times 4 && \\ &= 25-31\times 4+25\times 4 && \\ &= 5\times\textcolor{#9e0018}{25}-31\times 4 &&\text{or d'après } (L_{1}), \; 25=87-31\times 2 \\ &= 5\times\textcolor{#9e0018}{(87-31\times 2)}-31\times 4 && \\ &= 5\times 87-31\times 10-31\times 4 && \\ &= 5\times 87-14\times 31 && \end{aligned}$$

$$\boxed{(x\,;y)=(5\,;-14) \quad \text{car} \quad 87\times 5+31\times(-14)=1}$$ Vérification : $435-434=1$.

2. Algorithme d'Euclide appliqué à $45$ et $38$ : $$\begin{aligned} 45 &= 38\times 1+7 \qquad (L_{1}) \\ 38 &= 7\times 5+3 \qquad (L_{2}) \\ 7 &= 3\times 2+1 \qquad (L_{3}) \\ 3 &= 1\times 3+0 \end{aligned}$$

Remontée : $$\begin{aligned} 1 &= 7-\textcolor{#9e0018}{3}\times 2 &&\text{or d'après } (L_{2}), \; 3=38-7\times 5 \\ &= 7-\textcolor{#9e0018}{(38-7\times 5)}\times 2 && \\ &= 7-38\times 2+7\times 10 && \\ &= 11\times\textcolor{#9e0018}{7}-38\times 2 &&\text{or d'après } (L_{1}), \; 7=45-38\times 1 \\ &= 11\times\textcolor{#9e0018}{(45-38)}-38\times 2 && \\ &= 11\times 45-38\times 11-38\times 2 && \\ &= -13\times 38+11\times 45 && \end{aligned}$$

$$\boxed{(x\,;y)=(-13\,;11) \quad \text{car} \quad 38\times(-13)+45\times 11=1}$$ Vérification : $-494+495=1$.

3. Algorithme d'Euclide appliqué à $41$ et $25$ : $$\begin{aligned} 41 &= 25\times 1+16 \qquad (L_{1}) \\ 25 &= 16\times 1+9 \qquad (L_{2}) \\ 16 &= 9\times 1+7 \qquad (L_{3}) \\ 9 &= 7\times 1+2 \qquad (L_{4}) \\ 7 &= 2\times 3+1 \qquad (L_{5}) \\ 2 &= 1\times 2+0 \end{aligned}$$

Remontée : elle comporte ici quatre substitutions. $$\begin{aligned} 1 &= 7-\textcolor{#9e0018}{2}\times 3 &&\text{or } (L_{4}) : \; 2=9-7 \\ &= 7-\textcolor{#9e0018}{(9-7)}\times 3=4\times\textcolor{#9e0018}{7}-3\times 9 &&\text{or } (L_{3}) : \; 7=16-9 \\ &= 4\times\textcolor{#9e0018}{(16-9)}-3\times 9=4\times 16-7\times\textcolor{#9e0018}{9} &&\text{or } (L_{2}) : \; 9=25-16 \\ &= 4\times 16-7\times\textcolor{#9e0018}{(25-16)} =11\times\textcolor{#9e0018}{16}-7\times 25 &&\text{or } (L_{1}) : \; 16=41-25 \\ &= 11\times\textcolor{#9e0018}{(41-25)}-7\times 25=11\times 41-18\times 25 && \end{aligned}$$ L'équation demandée étant $41x-25y=1$, on identifie directement : $$\boxed{(x\,;y)=(11\,;18) \quad \text{car} \quad 41\times 11-25\times 18=1}$$ Vérification : $451-450=1$.

4. Algorithme d'Euclide appliqué à $331$ et $221$ : $$\begin{aligned} 331 &= 221\times 1+110 \qquad (L_{1}) \\ 221 &= 110\times 2+1 \qquad (L_{2}) \\ 110 &= 1\times 110+0 \end{aligned}$$

Remontée : elle est très courte, une seule substitution suffit. $$\begin{aligned} 1 &= 221-\textcolor{#9e0018}{110}\times 2 &&\text{or d'après } (L_{1}), \; 110=331-221 \\ &= 221-\textcolor{#9e0018}{(331-221)}\times 2 && \\ &= 221+221\times 2-331\times 2 && \\ &= 3\times 221-2\times 331 && \end{aligned}$$ L'équation demandée étant $221x-331y=1$ : $$\boxed{(x\,;y)=(3\,;2) \quad \text{car} \quad 221\times 3-331\times 2=1}$$ Vérification : $663-662=1$.