Théorèmes de Bézout et de Gauss

On considère les entiers $319$ et $116$.

1. $\text{pgcd}(319;116)$ =
   $319=2\times 116+87$ ; $116=1\times 87+29$ ; $87=3\times 29+0$. Le dernier reste non nul est $29$.
2. En remontant l’algorithme, on obtient un couple $(u;v)$ tel que $319u+116v=29$ avec $u=-1$. Valeur de $v$ :
   La deuxième ligne donne $29=116-87$, la première $87=319-2\times 116$. Donc $29=116-(319-2\times 116)=3\times 116-319$ : $(u;v)=(-1;3)$. Vérification : $-319+348=29$.
3. On a $319=29\times 11$ et $116=29\times 4$. En divisant la relation précédente par $29$, démontrer que $11$ et $4$ sont premiers entre eux. Coefficient de $4$ dans la relation obtenue :
   Rédaction attendue. De $319\times (-1)+116\times 3=29$, on tire $29\times 11\times (-1)+29\times 4\times 3=29$, puis, en divisant par $29\ne 0$ : $11\times (-1)+4\times 3=1$. Il existe donc des entiers $u=-1$ et $v=3$ tels que $11u+4v=1$ : d’après le théorème de Bézout, $11$ et $4$ sont premiers entre eux. Le coefficient de $4$ vaut $3$.

On considère les entiers $85$ et $24$.

1. Dernier reste non nul de l’algorithme d’Euclide appliqué à $85$ et $24$ :
   $85=3\times 24+13$ ; $24=1\times 13+11$ ; $13=1\times 11+2$ ; $11=5\times 2+1$ ; $2=2\times 1+0$. Le dernier reste non nul vaut $1$ : $85$ et $24$ sont premiers entre eux.
2. Couple $(u;v)$ tel que $85u+24v=1$ avec $-24<u<0$ : $u$ =
   Remontée : $1=11-5\times 2$ $=11-5(13-11)$ $=6\times 11-5\times 13$ $=6(24-13)-5\times 13$ $=6\times 24-11\times 13$ $=6\times 24-11(85-3\times 24)$ $=39\times 24-11\times 85$. Donc $u=-11$, qui est bien entre $-24$ et $0$ (les autres couples ont des $u$ qui diffèrent de $-11$ d’un multiple de $24$).
3. Pour ce couple, $v$ =
   $85\times (-11)+24v=1$ donne $24v=936$, soit $v=39$. Vérification : $39\times 24=936$ et $11\times 85=935$, de différence $1$.

On considère $a=434$ et $b=154$.

1. $\text{pgcd}(434;154)$ =
   $434=2\times 154+126$ ; $154=1\times 126+28$ ; $126=4\times 28+14$ ; $28=2\times 14+0$. Le PGCD vaut $14$.
2. En remontant l’algorithme, on obtient $434u+154v=14$ avec $u=5$. Valeur de $v$ :
   $14=126-4\times 28$ $=126-4(154-126)$ $=5\times 126-4\times 154$ $=5(434-2\times 154)-4\times 154$ $=5\times 434-14\times 154$. Vérification : $2170-2156=14$.
3. Démontrer que pour tout entier $k$, le couple $(5+11k;-14-31k)$ est aussi un couple de Bézout de $434$ et $154$. Valeur de $v$ pour le couple où $u=-6$ :
   Rédaction attendue. Pour tout entier $k$ : $434(5+11k)+154(-14-31k)$ $=(5\times 434-14\times 154)+(434\times 11-154\times 31)k$ $=14+(4774-4774)k=14$. Ce sont donc des couples de Bézout ($11=\frac{154}{14}$ et $31=\frac{434}{14}$). Pour $u=-6$, $k=-1$ et $v=-14+31=17$. Vérification : $-2604+2618=14$.

On note $E$ l’ensemble des entiers strictement positifs de la forme $84u+60v$, avec $u$ et $v$ entiers relatifs. Puis on reprend le raisonnement dans le cas général.

1. Démontrer que tout élément de $E$ est un multiple de $12$. Plus petit élément de $E$ :
   Rédaction attendue. $84=12\times 7$ et $60=12\times 5$, donc $84u+60v=12(7u+5v)$ est un multiple de $12$ : tout élément de $E$ est supérieur ou égal à $12$. Or $84\times (-2)+60\times 3=-168+180=12$ : $12$ appartient à $E$. C’est son plus petit élément, et c’est $\text{pgcd}(84;60)$.
2. Cas général : $a$ et $b$ sont non tous deux nuls et $m=a{u}_0+b{v}_0$ est le plus petit entier strictement positif de la forme $au+bv$. Démontrer que $m$ divise $a$ et $b$. Pour $a=84$ et $b=60$, couple $(u;v)$ tel que $84u+60v=12$ avec $0<u<5$ : $u$ =
   Rédaction attendue. Division euclidienne : $a=mq+r$ avec $0⩽r<m$. Alors $r=a-q(a{u}_0+b{v}_0)=a(1-q{u}_0)+b(-q{v}_0)$ est de la forme $au+bv$ ; s’il était strictement positif, il serait un entier de cette forme plus petit que $m$, ce qui est impossible. Donc $r=0$ : $m$ divise $a$, et de même $m$ divise $b$. Pour $84$ et $60$ : les couples $(-2+5k;3-7k)$ conviennent, et $0<-2+5k<5$ donne $k=1$, soit $u=3$.
3. En déduire que $m=\text{pgcd}(a;b)$, ce qui démontre l’identité de Bézout. Pour $a=84$ et $b=60$, valeur de $v$ dans le couple de la question précédente :
   Rédaction attendue. D’après la question précédente, $m$ est un diviseur commun positif de $a$ et $b$, donc $m⩽\text{pgcd}(a;b)$. Inversement, $\text{pgcd}(a;b)$ divise $a$ et $b$, donc la combinaison $a{u}_0+b{v}_0=m$ ; comme $m>0$, $\text{pgcd}(a;b)⩽m$. Ainsi $m=\text{pgcd}(a;b)=a{u}_0+b{v}_0$. Pour $u=3$ : $84\times 3+60v=12$ donne $60v=-240$, soit $v=-4$.

Dans cet exercice, $n$ désigne un entier relatif.

1. Valeur de la combinaison $7(5n+2)-5(7n+3)$ :
   $7(5n+2)-5(7n+3)=35n+14-35n-15=-1$ : le terme en $n$ disparaît.
2. En déduire que $5n+2$ et $7n+3$ sont premiers entre eux pour tout $n$. Entier $v$ tel que $-7(5n+2)+v(7n+3)=1$ :
   Rédaction attendue. En changeant les signes de l’égalité précédente : $(-7)(5n+2)+5(7n+3)=1$. Les coefficients $-7$ et $5$ sont des entiers : d’après le théorème de Bézout, $5n+2$ et $7n+3$ sont premiers entre eux, quel que soit l’entier $n$.
3. Démontrer que $4n+1$ et $9n+2$ sont premiers entre eux pour tout $n$. Entier $u$ tel que $u(4n+1)-4(9n+2)=1$ :
   Rédaction attendue. $9(4n+1)-4(9n+2)=36n+9-36n-8=1$. C’est une relation de Bézout à coefficients entiers $9$ et $-4$ : d’après le théorème de Bézout, $4n+1$ et $9n+2$ sont premiers entre eux pour tout entier $n$.

Une copie affirme : « Comme $57\times 2+38\times (-1)=76$, on a $\text{pgcd}(57;38)=76$. »

1. Valeur exacte de $\text{pgcd}(57;38)$ :
   $57=1\times 38+19$ et $38=2\times 19+0$ : le PGCD vaut $19$. Le calcul de la copie est juste ($114-38=76$), mais pas la conclusion : un PGCD ne dépasse jamais $38$.
2. Démontrer que si $au+bv=m$ ($u$, $v$, $m$ entiers), alors $\text{pgcd}(a;b)$ divise $m$. Quotient de $76$ par $\text{pgcd}(57;38)$ :
   Rédaction attendue. Posons $d=\text{pgcd}(a;b)$ : $a=da\prime$ et $b=db\prime$ avec $a\prime$ et $b\prime$ entiers. Alors $m=au+bv=d(a\prime u+b\prime v)$, et $a\prime u+b\prime v$ est un entier : $d$ divise $m$. Ici $76=4\times 19$ est bien un multiple du PGCD, sans lui être égal.
3. Plus petit entier strictement positif de la forme $57u+38v$, avec $u$ et $v$ entiers :
   Rédaction attendue. Tout entier $57u+38v$ est un multiple de $19$ d’après la question précédente, donc tout entier strictement positif de cette forme vaut au moins $19$. Et $19=57\times 1+38\times (-1)$ est de cette forme (identité de Bézout). Le plus petit est donc $19$ : c’est le PGCD.

On veut démontrer que $35$ et $276=12\times 23$ sont premiers entre eux sans calculer leur PGCD.

1. Couple $(u;v)$ tel que $35u+12v=1$ avec $u=-1$ : $v$ =
   $35\times (-1)+12v=1$ donne $12v=36$, soit $v=3$ : $36-35=1$.
2. Couple $(s;t)$ tel que $35s+23t=1$ avec $s=2$ : $t$ =
   $70+23t=1$ donne $23t=-69$, soit $t=-3$ : $70-69=1$.
3. En multipliant ces deux relations, démontrer que $35$ et $276$ sont premiers entre eux. On obtient $35U+276V=1$ avec $V=3\times (-3)=-9$. Valeur de $U$ :
   Rédaction attendue. $(35\times (-1)+12\times 3)(35\times 2+23\times (-3))=1\times 1=1$. En développant, les trois termes qui contiennent le facteur $35$ se regroupent en $35[(-1)\times 35\times 2+(-1)\times 23\times (-3)+3\times 12\times 2]$, soit $35\times (-70+69+72)$ $=35\times 71$, et le quatrième vaut $(12\times 23)\times (3\times (-3))$ $=276\times (-9)$. On obtient $35\times 71+276\times (-9)=1$. Vérification : $2485-2484=1$. D’après le théorème de Bézout, $35$ et $276$ sont premiers entre eux.

Dans cet exercice, $n$ désigne un entier naturel.

1. Montrer que la fraction ${\displaystyle \frac{9n+8}{6n+5}}$ est irréductible pour tout $n$. Entier $u$ tel que $u(9n+8)-3(6n+5)=1$ :
   Rédaction attendue. $2(9n+8)-3(6n+5)=18n+16-18n-15=1$. D’après le théorème de Bézout, $9n+8$ et $6n+5$ sont premiers entre eux : la fraction est irréductible pour tout entier naturel $n$.
2. On pose $d_n=\text{pgcd}(5n+3;3n+1)$. Constante obtenue en calculant $3(5n+3)-5(3n+1)$ :
   $15n+9-15n-5=4$. Comme $d_n$ divise $5n+3$ et $3n+1$, il divise cette combinaison : $d_n\in \{1;2;4\}$.
3. Démontrer que $d_n=1$ si $n$ est pair et que $d_n\in \{2;4\}$ si $n$ est impair. Valeur de $d_n$ lorsque $n\equiv 3[4]$ :
   Rédaction attendue. Si $n$ est pair, $3n+1$ est impair, donc $d_n$ est impair ; diviseur de $4$, il vaut $1$. Si $n$ est impair, $5n+3$ et $3n+1$ sont pairs, donc $d_n=2$ ou $4$. Si $n\equiv 3[4]$, $3n+1\equiv 10\equiv 2[4]$ : $4$ ne divise pas $3n+1$, donc $d_n=2$ (exemple : $n=3$ donne $18$ et $10$).
4. Démontrer que $d_n=4$ si et seulement si $n\equiv c[4]$, avec $0⩽c⩽3$. Valeur de $c$ :
   Rédaction attendue. $d_n=4$ impose que $4$ divise $3n+1$, soit $3n\equiv -1\equiv 3[4]$ ; en multipliant par $3$ (inverse de $3$ modulo $4$, car $9\equiv 1$) : $n\equiv 1[4]$. Réciproquement, si $n\equiv 1[4]$, alors $5n+3\equiv 8\equiv 0$ et $3n+1\equiv 4\equiv 0[4]$ : $4$ divise les deux, et $d_n=4$ (exemple : $n=1$ donne $8$ et $4$).

Dans tout l’exercice, $n$ désigne un entier relatif.

1. On suppose que $12$ divise $25n$. Démontrer que $12$ divise $n$. Entier $v$ tel que $12\times (-2)+25v=1$ :
   Rédaction attendue. $12\times (-2)+25\times 1=1$ : d’après le théorème de Bézout, $\text{pgcd}(12;25)=1$. Comme $12$ divise $25n$ et que $12$ est premier avec $25$, le théorème de Gauss donne : $12$ divise $n$.
2. Démontrer que tout entier divisible par $8$ et par $21$ est divisible par $168$. Plus petit entier naturel non nul divisible par $8$ et par $21$ :
   Rédaction attendue. $8\times 8-3\times 21=64-63=1$, donc $8$ et $21$ sont premiers entre eux (Bézout). Si $8$ et $21$ divisent $n$, le corollaire du théorème de Gauss donne : $8\times 21=168$ divise $n$. Tout entier naturel non nul divisible par $8$ et par $21$ vaut donc au moins $168$, et $168$ convient.
3. Plus petit entier naturel non nul divisible par $6$ et par $10$, mais pas par $60$ :
   $6$ et $10$ divisent $30$, et $60$ ne divise pas $30$ (les entiers $6$, $12$, $18$, $24$ ne sont pas multiples de $10$). Cela ne contredit pas le corollaire : $\text{pgcd}(6;10)=2\ne 1$, son hypothèse n’est pas vérifiée.

Démonstrations du cours. Les lettres désignent des entiers relatifs non nuls ; les deux questions sont indépendantes.

1. Démontrer le théorème de Gauss à partir du théorème de Bézout. Application : $17$ divise $10n$, où $n$ est un entier naturel non nul ; plus petite valeur possible de $n$ :
   Rédaction attendue. Supposons que $a$ divise $bc$ et que $\text{pgcd}(a;b)=1$. D’après le théorème de Bézout, il existe des entiers $u$ et $v$ tels que $au+bv=1$. En multipliant par $c$ : $acu+bcv=c$. D’une part $a$ divise $acu$ ; d’autre part $a$ divise $bc$, donc $bcv$. Une somme de deux multiples de $a$ est un multiple de $a$ : $a$ divise $c$. Application : $3\times 17-5\times 10=1$, donc $\text{pgcd}(17;10)=1$, donc $17$ divise $n$. La plus petite valeur est $n=17$.
2. Démontrer que si $a$ et $b$ divisent $c$ et sont premiers entre eux, alors $ab$ divise $c$. Application : $9$ et $14$ divisent un entier $N$ ; reste de $N$ dans la division par $126$ :
   Rédaction attendue. Comme $a$ divise $c$, il existe $k$ entier tel que $c=ak$. Alors $b$ divise $ak$ et $b$ est premier avec $a$ : par le théorème de Gauss, $b$ divise $k$, soit $k=bk\prime$. Donc $c=abk\prime$ : $ab$ divise $c$. Application : $2\times 14-3\times 9=1$, donc $9$ et $14$ sont premiers entre eux, et $9\times 14=126$ divise $N$ : le reste vaut $0$.

Une copie affirme : « Comme $20$ divise $36n$, on en déduit que $20$ divise $n$. » Ici $n$ est un entier naturel.

1. Plus petit entier naturel non nul de la forme $36n$ qui soit un multiple de $20$ :
   $36$, $72$, $108$, $144$ ne sont pas des multiples de $20$, mais $36\times 5=180=20\times 9$ en est un, alors que $20$ ne divise pas $5$ : $n=5$ est un contre-exemple. L’erreur : appliquer Gauss alors que $\text{pgcd}(20;36)=4\ne 1$.
2. Démontrer que $20$ divise $36n$ si et seulement si $5$ divise $n$. Plus petit entier $n>100$ tel que $20$ divise $36n$ :
   Rédaction attendue. Si $36n=20k$, en divisant par $4$ : $9n=5k$, donc $5$ divise $9n$ ; comme $\text{pgcd}(5;9)=1$ ($2\times 5-9=1$), le théorème de Gauss donne : $5$ divise $n$. Réciproquement, si $n=5j$, alors $36n=180j=20\times 9j$. Le plus petit multiple de $5$ supérieur à $100$ est $105$.
3. Nombre d’entiers $n$ compris entre $1$ et $100$ tels que $20$ divise $36n$ :
   D’après la question précédente, ce sont les multiples de $5$ : $5$, $10$, …, $100$, soit $20$ entiers.

Dans cet exercice, $a$, $b$, $p$ et $q$ sont des entiers relatifs.

1. Démontrer que si $12a=7b$, il existe un entier $k$ tel que $a=7k$ et $b=12k$. Valeur de $b$ lorsque $a=35$ :
   Rédaction attendue. $7$ divise $7b=12a$, et $\text{pgcd}(7;12)=1$ ($12-7=5$, $7-5=2$, $5=2\times 2+1$). Par le théorème de Gauss, $7$ divise $a$ : $a=7k$. Alors $12\times 7k=7b$, d’où $b=12k$. Pour $a=35$, $k=5$ et $b=60$.
2. Entiers naturels $a$ et $b$ tels que $12a=7b$ et $a+b=76$ : $a$ =
   $a=7k$ et $b=12k$ donnent $19k=76$, soit $k=4$ : $a=28$ et $b=48$. Vérification : $12\times 28=336=7\times 48$.
3. Démontrer qu’aucun rationnel $r$ ne vérifie $r^3=4$ (on écrira $r={\displaystyle \frac{p}{q}}$ avec $q⩾1$ et $\text{pgcd}(p;q)=1$). Seule valeur possible de $q$ :
   Rédaction attendue. Si ${\left({\displaystyle \frac{p}{q}}\right)}^3=4$, alors $p^3=4q^3$, donc $q$ divise $p^3=p\times p^2$. Comme $q$ est premier avec $p$, le théorème de Gauss donne $q$ divise $p^2=p\times p$, puis de même $q$ divise $p$. Un diviseur positif commun à $q$ et $p$ vaut $1$ : $q=1$. Il resterait $p^3=4$, impossible pour un entier ($1^3=1<4<8=2^3$, et un cube d’entier négatif est négatif). Aucun rationnel ne convient : $\sqrt[3]{4}$ est irrationnel.

On considère l’équation $(F)$ : $42x+63y=105$, d’inconnue $(x;y)\in {\mathbb{Z}}^2$.

1. $\text{pgcd}(42;63)$ =
   $63=1\times 42+21$ et $42=2\times 21+0$ : le PGCD vaut $21$, et $105=5\times 21$ : $(F)$ a des solutions.
2. Résoudre $(F)$ dans ${\mathbb{Z}}^2$ (on pourra remarquer une solution évidente de $2x+3y=5$). Valeur de $y$ dans la solution où $x=31$ :
   Rédaction attendue. En divisant par $21$, $(F)$ équivaut à $2x+3y=5$, dont $(1;1)$ est solution. Si $(x;y)$ est solution, $2(x-1)=3(1-y)$ ; $3$ divise $2(x-1)$ et $\text{pgcd}(3;2)=1$, donc par Gauss $x=1+3k$, puis $y=1-2k$. Réciproquement $42(1+3k)+63(1-2k)=105$. $S=\{(1+3k;1-2k),k\in \mathbb{Z}\}$. Pour $x=31$, $k=10$ et $y=-19$ : $1302-1197=105$.
3. Expliquer pourquoi l’équation $42x+63y=100$ n’a aucune solution entière. Reste de $100$ dans la division euclidienne par $21$ :
   Rédaction attendue. Pour tous entiers $x$ et $y$, $42x+63y=21(2x+3y)$ est un multiple de $21$. Or $100=4\times 21+16$ : le reste vaut $16\ne 0$, donc $100$ n’est pas un multiple de $21$ et l’équation n’a aucune solution.

On considère l’équation $(E)$ : $37x+15y=2$, d’inconnue $(x;y)\in {\mathbb{Z}}^2$.

1. Justifier que $(E)$ a des solutions, puis en déduire une solution particulière à l’aide d’une relation de Bézout. Pour $x=-4$, $y$ =
   Rédaction attendue. $37=2\times 15+7$ ; $15=2\times 7+1$ : $\text{pgcd}(37;15)=1$, qui divise $2$, donc $(E)$ a des solutions. Remontée : $1=15-2\times 7=15-2(37-2\times 15)=5\times 15-2\times 37$. En multipliant par $2$ : $37\times (-4)+15\times 10=2$ ($-148+150=2$).
2. Déterminer toutes les solutions de $(E)$ dans ${\mathbb{Z}}^2$. Nombre de solutions telles que $0⩽x⩽100$ :
   Rédaction attendue. Si $(x;y)$ est solution, $37(x+4)=15(10-y)$ ; $15$ divise $37(x+4)$ et $\text{pgcd}(15;37)=1$, donc par Gauss $x=-4+15k$, puis $37\times 15k=15(10-y)$ donne $y=10-37k$. Réciproquement, $37(-4+15k)+15(10-37k)=-148+150=2$. $S=\{(-4+15k;10-37k),k\in \mathbb{Z}\}$. Puis $0⩽-4+15k⩽100$ équivaut à $\frac{4}{15}⩽k⩽\frac{104}{15}\approx 6,9$ : $k\in \{1;2;3;4;5;6\}$, soit $6$ solutions.
3. Parmi ces solutions, valeur de $y$ pour la plus grande valeur de $x$ :
   $k=6$ donne $x=86$ et $y=10-222=-212$. Vérification : $37\times 86-15\times 212=3182-3180=2$.

On cherche tous les couples d’entiers relatifs $(u;v)$ tels que $29u+12v=1$.

1. Vérifier que $(5;-12)$ convient, puis déterminer tous les couples. Couple tel que $12<u<24$ : $u$ =
   Rédaction attendue. $29\times 5+12\times (-12)=145-144=1$. Si $29u+12v=1$, en soustrayant : $29(u-5)=12(-12-v)$ ; $12$ divise $29(u-5)$ et $\text{pgcd}(12;29)=1$, donc par Gauss $u=5+12k$, puis $29\times 12k=12(-12-v)$ donne $v=-12-29k$. Réciproquement, le calcul redonne $1$. Les couples sont les $(5+12k;-12-29k)$, $k\in \mathbb{Z}$, et $12<5+12k<24$ donne $k=1$ : $u=17$.
2. Pour ce couple, $v$ =
   $v=-12-29=-41$. Vérification : $29\times 17=493$ et $12\times 41=492$.
3. Inverse de $29$ modulo $12$, compris entre $0$ et $11$ :
   De $29\times 5+12\times (-12)=1$ on tire $29\times 5\equiv 1[12]$. Contrôle : $29\equiv 5[12]$ et $5\times 5=25=2\times 12+1$.

Un théâtre vend des places à $9$ € et à $16$ €. Un soir, la recette vaut exactement $300$ €. On note $x$ le nombre de places à $9$ € et $y$ celui des places à $16$ € : $9x+16y=300$, avec $x$ et $y$ entiers naturels.

1. Couple $(u;v)$ tel que $9u+16v=1$ avec $u=-7$ : $v$ =
   $16=9+7$ ; $9=7+2$ ; $7=3\times 2+1$. Remontée : $1=7-3\times 2=7-3(9-7)=4\times 7-3\times 9=4(16-9)-3\times 9=4\times 16-7\times 9$ : $(u;v)=(-7;4)$.
2. Résoudre $9x+16y=300$ dans ${\mathbb{Z}}^2$, puis déterminer les solutions en entiers naturels. Nombre de ventes possibles :
   Rédaction attendue. En multipliant par $300$ : $9\times (-2100)+16\times 1200=300$. Si $(x;y)$ est solution, $9(x+2100)=16(1200-y)$ ; $16$ divise $9(x+2100)$ et $\text{pgcd}(16;9)=1$, donc par Gauss $x=-2100+16k$, puis $y=1200-9k$ (la réciproque se vérifie). $x⩾0$ donne $k⩾\frac{2100}{16}=131,25$, donc $k⩾132$ ; $y⩾0$ donne $k⩽\frac{1200}{9}\approx 133,3$, donc $k⩽133$. Deux ventes : $(12;12)$ et $(28;3)$. Vérification : $108+192=300$ et $252+48=300$.
3. Plus grand nombre total de places vendues ce soir-là :
   $12+12=24$ et $28+3=31$ : le plus grand total est $31$ places.

On étudie l’entier $23$ modulo $30$.

1. Justifier que $23$ est inversible modulo $30$. Inverse de $23$ modulo $30$, compris entre $0$ et $29$ :
   Rédaction attendue. $30=1\times 23+7$ ; $23=3\times 7+2$ ; $7=3\times 2+1$ : $\text{pgcd}(23;30)=1$, donc $23$ est inversible modulo $30$. Remontée : $1=7-3\times 2=7-3(23-3\times 7)=10\times 7-3\times 23=10(30-23)-3\times 23=10\times 30-13\times 23$. Donc $23\times (-13)\equiv 1[30]$, et $-13\equiv 17[30]$. Vérification : $23\times 17=391=13\times 30+1$.
2. Les solutions de $23x\equiv 7[30]$ vérifient $x\equiv c[30]$ avec $0⩽c⩽29$ : $c$ =
   En multipliant par $17$ : $x\equiv 17\times 7=119[30]$, et $119=3\times 30+29$. Réciproquement, $23\times 29=667=22\times 30+7$.
3. Plus petite solution strictement supérieure à $150$ :
   Les solutions sont $29$, $59$, $89$, $119$, $149$, $179$… : la première au-delà de $150$ est $179$. Contrôle : $23\times 179=4117=137\times 30+7$.

On travaille modulo $100$ : le reste modulo $100$ d’un entier naturel est le nombre formé par ses deux derniers chiffres.

1. Inverse de $27$ modulo $100$, compris entre $0$ et $99$ :
   $100=3\times 27+19$ ; $27=19+8$ ; $19=2\times 8+3$ ; $8=2\times 3+2$ ; $3=2+1$. Remontée : $1=3-2=3\times 3-8=3\times 19-7\times 8=10\times 19-7\times 27=10\times 100-37\times 27$. Donc l’inverse est $-37\equiv 63[100]$ : $27\times 63=1701$.
2. Les solutions de $27x\equiv 9[100]$ vérifient $x\equiv c[100]$ avec $0⩽c⩽99$ : $c$ =
   $x\equiv 63\times 9=567\equiv 67[100]$. Vérification : $27\times 67=1809$, qui se termine par $09$.
3. Démontrer que $15$ n’a pas d’inverse modulo $100$. $\text{pgcd}(15;100)$ =
   Rédaction attendue. $100=6\times 15+10$, $15=10+5$, $10=2\times 5$ : $\text{pgcd}(15;100)=5\ne 1$. D’après le critère, $15$ n’est pas inversible. Directement : $15u-100v=5(3u-20v)$ est un multiple de $5$, il ne peut pas valoir $1$.

On cherche les entiers $x$ tels que $x\equiv 3[7]$ et $x\equiv 5[12]$.

1. Couple $(u;v)$ tel que $7u+12v=1$ avec $u=-5$ : $v$ =
   $12=7+5$ ; $7=5+2$ ; $5=2\times 2+1$. Remontée : $1=5-2\times 2=3\times 5-2\times 7=3\times 12-5\times 7$. Donc $v=3$ : $-35+36=1$.
2. Démontrer que $x_0=3\times 12\times 3+5\times 7\times (-5)$ est solution du système. Entier compris entre $0$ et $83$ congru à $x_0$ modulo $84$ :
   Rédaction attendue. $12\times 3=1-7\times (-5)\equiv 1[7]$, donc $x_0\equiv 3\times 1+0=3[7]$ ; et $7\times (-5)=1-12\times 3\equiv 1[12]$, donc $x_0\equiv 0+5\times 1=5[12]$. Or $x_0=108-175=-67$, et $-67+84=17$. Contrôle : $17=2\times 7+3=12+5$.
3. Démontrer que les solutions sont exactement les entiers congrus à $17$ modulo $84$. Plus grande solution inférieure à $1000$ :
   Rédaction attendue. Si $x$ est solution, $7$ et $12$ divisent $x-17$ ; ils sont premiers entre eux, donc par le corollaire de Gauss $84$ divise $x-17$. Réciproquement, si $x=17+84k$, comme $84=7\times 12$, $x\equiv 17\equiv 3[7]$ et $x\equiv 17\equiv 5[12]$. Enfin $17+84k<1000$ donne $k⩽11$ : $17+924=941$.

On étudie l’équation $35x\equiv 14[56]$, d’inconnue $x$ entière.

1. Démontrer que l’équation équivaut à $5x\equiv 2[8]$. Inverse de $5$ modulo $8$, compris entre $0$ et $7$ :
   Rédaction attendue. $35x\equiv 14[56]$ signifie qu’il existe un entier $k$ tel que $35x-14=56k$, soit $7(5x-2)=7\times 8k$, c’est-à-dire $5x-2=8k$ : $5x\equiv 2[8]$. Les étapes sont réversibles. Et $5\times 5=25=3\times 8+1$ : $5$ est son propre inverse modulo $8$.
2. Les solutions vérifient $x\equiv c[8]$ avec $0⩽c⩽7$ : $c$ =
   En multipliant par $5$ : $x\equiv 10\equiv 2[8]$. Vérification : $35\times 2=70=56+14$.
3. Nombre de solutions comprises entre $0$ et $55$ :
   Ce sont $2$, $10$, $18$, $26$, $34$, $42$ et $50$ : $7$ solutions, soit $7$ classes modulo $56$ ($7=\text{pgcd}(35;56)$).
4. Démontrer que $35x\equiv 15[56]$ n’a aucune solution. Reste de la division euclidienne de $15$ par $\text{pgcd}(35;56)$ :
   Rédaction attendue. $56=35+21$, $35=21+14$, $21=14+7$, $14=2\times 7$ : le PGCD vaut $7$. Si $35x-15=56k$, alors $15=35x-56k=7(5x-8k)$ serait un multiple de $7$ : c’est faux, car $15=2\times 7+1$ (reste $1\ne 0$). Aucune solution.