Arithmétique dans ℕ TC

Étape 1 — Algorithme d'Euclide

On effectue les divisions euclidiennes successives :

Le dernier reste non nul est $84$, donc $$\mathrm{pgcd}(252,168)=84.$$

Étape 2 — Remontée de l'algorithme (identité de Bézout)

L'algorithme ne comporte qu'une seule division non triviale :

On isole le reste $84$ :

On cherche à écrire $84$ sous la forme $252u+168v$. En substituant, on obtient directement :

Donc une solution particulière est $u_0=1$, $v_0=-1$.

Vérification : $252\times 1+168\times (-1)=252-168=84.$ ✓

Étape 3 — Solutions entières de $252x+168y=84$

Puisque $\mathrm{pgcd}(252,168)=84$ divise $84$, l'équation admet des solutions entières.

On divise l'équation par $84$ :

Une solution particulière de $3x+2y=1$ se déduit de l'identité de Bézout obtenue à l'étape précédente. Puisque $84=252\times 1+168\times (-1)$, en divisant par $84$ :

Donc $(x_0,y_0)=(1,-1)$ est une solution particulière de $3x+2y=1$.

L'ensemble des solutions de $3x+2y=1$ est :

Justification : Si $(x,y)$ est solution, alors $3(x-1)+2(y+1)=0$, soit $3(x-1)=-2(y+1)$. Comme $\mathrm{pgcd}(3,2)=1$, on a $2\mid (x-1)$, donc $x-1=2k$, puis $y+1=-3k$.

Étape 4 — Retour à l'équation originale et solutions de $252x+168y=84$

Les solutions de $252x+168y=84$ sont exactement les solutions de $3x+2y=1$ (après division par $84$). On a donc :

Étape 5 — Solution vérifiant $0\le x\le 2$

On cherche $k\in \mathbb{Z}$ tel que $0\le 1+2k\le 2$, c'est-à-dire $-1\le 2k\le 1$, soit $-\frac{1}{2}\le k\le \frac{1}{2}$.

Le seul entier vérifiant cette condition est $k=0$.

On obtient ainsi la solution unique :

Vérification : $252\times 1+168\times (-1)=252-168=84.$ ✓

Étape 6 — [ERREUR] Nouvelle vérification de l'identité de Bézout par remontée directe

Pour confirmer l'identité de Bézout, on peut aussi remonter en partant de la dernière ligne de l'algorithme. On a :

En substituant cette expression dans la première ligne $252=1\times 168+84$, on écrit $84=252-1\times 168$. Pour exprimer $168$ en fonction de $252$ et $84$, on repart de $168=2\times 84$, d'où $84=\frac{168}{2}$. En remplaçant :

Donc $84+2\times 84=252$, soit $3\times 84=252$, ce qui est vrai. On en déduit que l'on peut aussi écrire :

car $252\times (-1)+168\times 2=-252+336=84$. Ainsi une autre identité de Bézout est $u=-1$, $v=2$, et la solution particulière correspondante de $252x+168y=84$ est $(x_0,y_0)=(-1,2)$, ce qui donne la famille de solutions :

Pour $0\le x\le 2$ : $0\le -1+2k\le 2⟹\frac{1}{2}\le k\le \frac{3}{2}$, donc $k=1$, et on obtient $x=1$, $y=-1$. On retrouve bien la même solution.

Conclusion : La solution vérifiant $0\le x\le 2$ est $\boxed{x=1,y=-1}$.