\exo{Pas bête ce général chinois} Pour dénombrer un de ses bataillons, un général chinois a l'idée suivante~: tout d'abord, il sait que ce bataillons compte moins de~$1000$ soldats. Ensuite il exige de ses troupes de se mettre par paquets de sept et remarque que seuls deux soldats n'ont pas trouvé place dans aucun groupe. Il prend note de ce nombre deux. Il réitère le même expérience en exigeant que les soldats se rangent par paquets de onze puis treize. Dans le premier cas il note que seulement trois soldats n'ont pas trouvé place dans aucun groupe et dans le second seul un hurluberlu n'a pas trouvé à s'insérer nul part. Ces informations lui suffisent pour dénombrer son bataillon. \q Quel est donc le secret de cet ingénieux général chinois~? {\bfseries Indication~:} les premiers~$7$, $11$ et~$13$ n'ont évidemment pas été choisis au hasard. De même l'ordre des exercices de cette feuille ne relève pas d'un tirage aléatoire... \ifwithcorrection \correction Notons~$x$ le nombre de soldats composant le bataillon de ce général. Par hypothèse, ce nombre satisfait le système de congruences suivant~: $$ \begin{cases} x \equiv 2 \pmod{7} \\ x \equiv 3 \pmod{11} \\ x \equiv 1 \pmod{13} \end{cases} $$ Ce système admet des solutions,~$7$,~$11$ et~$13$ étant premiers entre eux deux-à-deux. Pour déterminer ces solutions, on sait qu'il convient de déterminer les coefficients de Bezout liant les entiers~$7 \times 11$, $7 \times 13$ et~$11 \times 13$. Comme~: $$ 6 (7 \times 11) - 5 (7 \times 13) = 7 \qquad \text{et} \qquad 41 \times 7 - 2 (11 \times 13) = 1 $$ (les coefficients de Bezout étant déterminés gr’ce à l'algorithme d'Euclide étendu) on obtient~: $$ 41 \times \left[ 6 (7 \times 11) - 5 (7 \times 13) \right] -2(11 \times 13) = 1 \qquad \Rightarrow \qquad 246 (7 \times 11) - 205 (7 \times 13) - 2 (11 \times 13) = 1 $$ Posons~$x_{13} = 246 (7 \times 11)$, $x_{11} = - 205 (7 \times 13)$ et~$x_7 = - 2 (11 \times 13)$ alors l'entier~: $$ 2 x_7 + 3 x_{11} + x_{13} = -37595 $$ est solution du système de congruences. Comme~$1001 = 7 \times 11 \times 13$, l'ensemble~$S$ des solutions est donné par~: $$ S = \{-37595 + 1001q, \; q \in \ZZ\} $$ Parmi ces entiers, seul un est positif et inférieur ou égal à~$1000$, c'est~$443$ (obtenu avec~$q = 38$). Par conséquent le bataillon compte~$443$ soldats. \fi