Équations diophantiennes $ax+by=c$~2 min
Soit $a,b$ non nuls, $d=\mathrm{pgcd}(a,b)$. L'équation $ax+by=c$ admet des solutions dans $\mathbb{Z}^2$ si et seulement si $\boldsymbol{d\mid c}$.
$d$ divise tout $ax+by$ ; réciproquement si $c=dc'$, l'identité de Bézout $au+bv=d$ donne la solution $(uc',vc')$.
1. Existence : calculer $d=\mathrm{pgcd}(a,b)$. Si $d\nmid c$ : pas de solution. Sinon diviser l'équation par $d$ : $a'x+b'y=c'$ avec $a'\wedge b'=1$.
2. Solution particulière $(x_0,y_0)$ : évidente, ou obtenue en multipliant par $c'$ une relation de Bézout $a'u+b'v=1$.
3. Solution générale : soustraire membre à membre $a'x+b'y=c'$ et $a'x_0+b'y_0=c'$ : $a'(x-x_0)=b'(y_0-y)$. Comme $b'\mid a'(x-x_0)$ et $b'\wedge a'=1$, Gauss donne $b'\mid x-x_0$ : $x=x_0+b'k$, puis $y=y_0-a'k$ ($k\in\mathbb{Z}$).
4. Réciproque : vérifier que $(x_0+b'k,\,y_0-a'k)$ est bien solution pour tout $k$, puis conclure.
Résoudre $12x+35y=2$ dans $\mathbb{Z}^2$.
1. $12\wedge35=1$ : des solutions existent. 2. $12\times3-35\times1=1$, donc $12\times6+35\times(-2)=2$ : $(x_0,y_0)=(6,-2)$.
3. Si $(x,y)$ est solution : $12x+35y=12\times6+35\times(-2)$, soit $12(x-6)=35(-2-y)$. Donc $35\mid12(x-6)$ ; comme $35\wedge12=1$, Gauss donne $35\mid x-6$ : $x=6+35k$. En reportant : $12\times35k=35(-2-y)$, d'où $y=-2-12k$.
4. Réciproquement $12(6+35k)+35(-2-12k)=72-70=2$. $\mathcal S=\{(6+35k\,;\,-2-12k)\,;\,k\in\mathbb{Z}\}$.
$12x+18y=30$. $\mathrm{pgcd}=6\mid30$ : équivaut à $2x+3y=5$, solution évidente $(1,1)$, d'où $\mathcal S=\{(1+3k\,;\,1-2k)\,;\,k\in\mathbb{Z}\}$. $12x+18y=7$ : aucune solution ($6\nmid7$).
Les solutions entières de $2x+3y=5$ : des points régulièrement espacés sur la droite (pas $(+3\,;-2)$).
Avec contrainte. Les solutions de $12x+35y=2$ avec $0\leq x\leq100$ : $0\leq6+35k\leq100\iff-\frac{6}{35}\leq k\leq\frac{94}{35}$, soit $k\in\{0,1,2\}$ : $(6,-2)$, $(41,-14)$, $(76,-26)$.