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

1. a)$413=4\times 95+33$ ; $95=2\times 33+29$ ; $33=1\times 29+4$ ; $29=7\times 4+1$ ; $4=4\times 1+0$. Le dernier reste non nul vaut $1$ : $\text{pgcd}(413;95)=1$, les deux entiers sont premiers entre eux. (1)
2. b)Remontée : $1=29-7\times 4$ $=29-7(33-29)$ $=8\times 29-7\times 33$ $=8(95-2\times 33)-7\times 33$ $=8\times 95-23\times 33$ $=8\times 95-23(413-4\times 95)$ $=100\times 95-23\times 413$. Donc $(u;v)=(-23;100)$. Vérification : $9500-9499=1$. (1)
3. c)Si $413u+95v=1$, en soustrayant $413\times (-23)+95\times 100=1$ : $413(u+23)=95(100-v)$. Ainsi $95$ divise $413(u+23)$ ; comme $\text{pgcd}(95;413)=1$, le théorème de Gauss donne : $95$ divise $u+23$, soit $u=-23+95k$ avec $k\in \mathbb{Z}$. En reportant, $413\times 95k=95(100-v)$, d’où $v=100-413k$. Réciproquement, $413(-23+95k)+95(100-413k)=1$. Les couples sont les $(-23+95k;100-413k)$, $k\in \mathbb{Z}$. (1)
4. d)De $413\times (-23)+95\times 100=1$, on tire $95\times 100\equiv 1[413]$, car $413\times (-23)$ est un multiple de $413$. L’inverse de $95$ modulo $413$ est $100$, qui est bien entre $0$ et $412$ ; contrôle : $95\times 100=9500=23\times 413+1$. (1)

Repère — Pendant la remontée, on garde 413 et 95 visibles et on ne regroupe que leurs coefficients ; une vérification numérique termine toujours le calcul.

1. a)$41=1\times 24+17$ ; $24=1\times 17+7$ ; $17=2\times 7+3$ ; $7=2\times 3+1$ ; $3=3\times 1+0$. Donc $\text{pgcd}(41;24)=1$, qui divise $3$ : d’après la condition d’existence, $(E)$ admet des solutions. (1)
2. b)Remontée : $1=7-2\times 3$ $=7-2(17-2\times 7)$ $=5\times 7-2\times 17$ $=5(24-17)-2\times 17$ $=5\times 24-7\times 17$ $=5\times 24-7(41-24)$ $=12\times 24-7\times 41$. En multipliant par $3$ : $41\times (-21)+24\times 36=3$ ($-861+864=3$) : $(-21;36)$ est une solution particulière. (1)
3. c)Soit $(x;y)$ une solution. En soustrayant : $41(x+21)=24(36-y)$. Ainsi $24$ divise $41(x+21)$ et $\text{pgcd}(24;41)=1$ : par le théorème de Gauss, $24$ divise $x+21$, soit $x=-21+24k$, $k\in \mathbb{Z}$. En reportant : $41\times 24k=24(36-y)$, d’où $y=36-41k$. Réciproquement, $41(-21+24k)+24(36-41k)=-861+864=3$. $S=\{(-21+24k;36-41k),k\in \mathbb{Z}\}$. (1)
4. d)$0⩽-21+24k⩽23$ équivaut à $21⩽24k⩽44$, soit $\frac{21}{24}⩽k⩽\frac{44}{24}$, environ $0,9⩽k⩽1,8$ : $k=1$. La solution est $(3;-5)$ ; contrôle : $123-120=3$. (1)

Repère — Solution particulière par Bézout, soustraction, Gauss appliqué à deux entiers premiers entre eux, réciproque : les quatre temps de la résolution.

1. a)$35=2\times 16+3$ ; $16=5\times 3+1$ : $\text{pgcd}(16;35)=1$, donc $16$ est inversible modulo $35$ (critère d’inversibilité, conséquence du théorème de Bézout). Remontée : $1=16-5\times 3=16-5(35-2\times 16)=11\times 16-5\times 35$. Donc $16\times 11\equiv 1[35]$ : l’inverse est $11$ ($176=5\times 35+1$). (1)
2. b)En multipliant les deux membres par $11$ : $11\times 16x\equiv 11\times 9[35]$, soit $x\equiv 99[35]$, et $99=2\times 35+29$, donc $x\equiv 29[35]$. Réciproquement, si $x\equiv 29[35]$, $16x\equiv 464=13\times 35+9\equiv 9[35]$. Les solutions sont les entiers $29+35k$, $k\in \mathbb{Z}$. (1)
3. c)Les solutions positives sont $29$, $64$, $99$, $134$… La plus petite supérieure à $100$ est $134$ ; contrôle : $16\times 134=2144=61\times 35+9$. (1)
4. d)S’il existait des entiers $x$ et $k$ tels que $14x-35k=9$, alors $7$, qui divise $14$ et $35$, diviserait $14x-35k=9$ : c’est faux. Autrement dit, $\text{pgcd}(14;35)=7$ ne divise pas $9$ : l’équation n’a pas de solution (et $14$ n’est pas inversible modulo $35$). (1)

Repère — Inverse par l’algorithme d’Euclide étendu, puis multiplication des deux membres : la solution est une classe ; sans inverse, on teste si le PGCD divise le second membre.

1. a)$9\times 5-2\times 22=45-44=1$ : d’après le théorème de Bézout, $\text{pgcd}(9;22)=1$. Comme $9$ divise $22n$ et que $9$ est premier avec $22$, le théorème de Gauss donne : $9$ divise $n$. (1)
2. b)$5(8n+3)-8(5n+2)=40n+15-40n-16=-1$, donc $(-5)(8n+3)+8(5n+2)=1$, avec $-5$ et $8$ entiers. D’après le théorème de Bézout, $8n+3$ et $5n+2$ sont premiers entre eux, quel que soit l’entier $n$. (1)
3. c)$25\times 13-18\times 18=325-324=1$, donc $\text{pgcd}(25;18)=1$ (Bézout). Comme $25$ et $18$ divisent $N$ et sont premiers entre eux, le corollaire du théorème de Gauss donne : $25\times 18=450$ divise $N$. (1)
4. d)$45=3\times 15=5\times 9$ est divisible par $15$ et par $9$, mais $0<45<135$, donc $135$ ne divise pas $45$. Il n’y a pas de contradiction : $\text{pgcd}(15;9)=3\ne 1$, l’hypothèse « premiers entre eux » du corollaire n’est pas vérifiée. (1)

Repère — Avant chaque « d’après Gauss », une relation de Bézout égale à 1 justifie que les deux entiers sont premiers entre eux.

1. a)Fausse. Le couple $(2;0)$ donne bien $10\times 2+15\times 0=20$, mais $\text{pgcd}(10;15)=5$. Une combinaison linéaire est seulement un multiple du PGCD ; seule une combinaison égale à $1$ permet de conclure (théorème de Bézout). (1)
2. b)Vraie. $a$ divise $6b=3\times (2b)$ et $a$ est premier avec $3$ : le théorème de Gauss donne $a$ divise $2b$. (1)
3. c)Vraie. $35=21+14$, $21=14+7$, $14=2\times 7$ : $\text{pgcd}(21;35)=7$, et $14=2\times 7$, donc la condition d’existence est vérifiée. Une solution explicite : $21\times (-1)+35\times 1=14$. (1)
4. d)Fausse. L’entier $6$ n’a pas d’inverse modulo $16$, car $\text{pgcd}(6;16)=2\ne 1$ : tout entier $6u-16v$ est pair, donc ne vaut jamais $1$, et $6u$ n’est jamais congru à $1$ modulo $16$. (1)

Repère — Pour « faux », un seul contre-exemple suffit ; pour « vrai », il faut citer le théorème et vérifier ses hypothèses.