Exercice 26 Théorème des restes chinois

1. (a) Les nombres $17$ et $5$ sont deux nombres premiers distincts, donc $\mathrm{PGCD}(17,5)=1$. D'après le théorème de Bézout : $$\boxed{\text{Il existe un couple } (u\,;v) \text{ d'entiers relatifs tel que } 17u+5v=1}$$

(b) Montrons que $n_{0}=3\times 17u+9\times 5v$ vérifie les deux congruences.

Modulo 17 : le terme $3\times 17u$ est un multiple de $17$, donc $n_{0}\equiv 9\times 5v\;[17]$. Or l'égalité $17u+5v=1$ donne $5v\equiv 1\;[17]$, d'où : $$n_{0}\equiv 9\times 1\equiv 9\;[17]$$

Modulo 5 : le terme $9\times 5v$ est un multiple de $5$, donc $n_{0}\equiv 3\times 17u\;[5]$. Or $17u\equiv 1\;[5]$, d'où : $$n_{0}\equiv 3\times 1\equiv 3\;[5]$$

(c) Cherchons un couple de Bézout. Comme $17=5\times 3+2$ et $5=2\times 2+1$, la remontée donne : $$\begin{aligned} 1 &= 5-\textcolor{#9e0018}{2}\times 2 &&\text{or } 2=17-5\times 3 \\ &= 5-\textcolor{#9e0018}{(17-5\times 3)}\times 2 && \\ &= 5-17\times 2+5\times 6 && \\ &= 17\times(-2)+5\times 7 && \end{aligned}$$ On peut donc prendre $(u\,;v)=(-2\,;7)$. Alors : $$n_{0}=3\times 17\times(-2)+9\times 5\times 7=-102+315=213$$ On vérifie : $213=17\times 12+9$ et $213=5\times 42+3$. $$\boxed{n_{0}=213 \text{ convient}}$$

2. (a) Soit $n\in S$. Alors $n\equiv 9\;[17]$ et $n_{0}\equiv 9\;[17]$, donc par différence $n-n_{0}\equiv 0\;[17]$ : le nombre $17$ divise $n-n_{0}$. De même, $n\equiv 3\;[5]$ et $n_{0}\equiv 3\;[5]$ donnent que $5$ divise $n-n_{0}$.

Ainsi $17$ et $5$ divisent tous deux $n-n_{0}$, et ils sont premiers entre eux. D'après le corollaire du théorème de Gauss, leur produit divise également $n-n_{0}$ : $$\boxed{n-n_{0}\equiv 0\;[85]}$$

(b) D'après ce qui précède, il existe $k\in\mathbb{Z}$ tel que $n=n_{0}+85k=213+85k$. Or $213=85\times 2+43$, donc en posant $k'=k+2$ : $$n=43+85k'$$ Réciproquement, tout entier de cette forme vérifie $n\equiv 43\equiv 9\;[17]$ (car $43=17\times 2+9$) et $n\equiv 43\equiv 3\;[5]$ (car $43=5\times 8+3$), donc appartient bien à $S$. $$\boxed{S=\left\{43+85k \; ; \; k\in\mathbb{Z}\right\}}$$

3. Le nombre $N$ de jetons vérifie $N\equiv 9\;[17]$ et $N\equiv 3\;[5]$ : il appartient donc à $S$, et s'écrit $N=43+85k$. La condition $300\leqslant N\leqslant 400$ donne : $$300\leqslant 43+85k\leqslant 400 \iff 257\leqslant 85k\leqslant 357 \iff 3{,}02\leqslant k\leqslant 4{,}2$$ Le seul entier convenable est $k=4$ : $$N=43+85\times 4=43+340=\boxed{383 \text{ jetons}}$$ Vérification : $383=17\times 22+9$ et $383=5\times 76+3$.