Exercice 20

1. Algorithme d'Euclide appliqué à $23$ et $13$ : $$\begin{aligned} 23 &= 13\times 1+10 \qquad (L_{1}) \\ 13 &= 10\times 1+3 \qquad (L_{2}) \\ 10 &= 3\times 3+1 \qquad (L_{3}) \\ 3 &= 1\times 3+0 \end{aligned}$$ Le dernier reste non nul vaut $1$, donc $\mathrm{PGCD}(13,23)=1$ et l'équation admet des solutions.

Remontée : $$\begin{aligned} 1 &= 10-\textcolor{#9e0018}{3}\times 3 &&\text{or d'après } (L_{2}), \; 3=13-10 \\ &= 10-\textcolor{#9e0018}{(13-10)}\times 3 && \\ &= 4\times\textcolor{#9e0018}{10}-13\times 3 &&\text{or d'après } (L_{1}), \; 10=23-13 \\ &= 4\times\textcolor{#9e0018}{(23-13)}-13\times 3 && \\ &= 4\times 23-13\times 4-13\times 3 && \\ &= 4\times 23-7\times 13 && \end{aligned}$$ On obtient $-7\times 13+4\times 23=1$, que l'on réécrit sous la forme demandée $13x-23y=1$ : $$13\times(-7)-23\times(-4)=-91+92=1$$

2. Soit $(x\,;y)$ une solution. En soustrayant terme à terme : $$13(x+7)-23(y+4)=0 \qquad \text{soit} \qquad 13(x+7)=23(y+4)$$ Comme $23$ divise $13(x+7)$ et que $\mathrm{PGCD}(13,23)=1$, le théorème de Gauss donne $23\mid(x+7)$ : il existe $k\in\mathbb{Z}$ tel que $x=23k-7$. En reportant, $13\times 23k=23(y+4)$, d'où $y=13k-4$. $$\boxed{S=\left\{(23k-7\,;13k-4) \; ; \; k\in\mathbb{Z}\right\}}$$ Vérification : $13(23k-7)-23(13k-4)=299k-91-299k+92=1$.