Correct exercise 2.

1 files changed, 93 insertions, 0 deletions

diff --git a/controle-20091124.tex b/controle-20091124.tex
index 22686ac..8274a5d 100644
--- a/controle-20091124.tex
+++ b/controle-20091124.tex
@@ -256,21 +256,114 @@ proposé n'est pas la valeur correcte de $3^{31}$.
 (A) Quel entier entre $0$ et $100$ est congru à $19$ modulo $13$ et à
 $13$ modulo $19$ ?
 
+\begin{corrige}
+(A) Commençons par trouver un entier qui convient.  On pourrait se
+  rendre compte que $19+13 = 32$ convient pour des raisons de
+  symétrie.  Pour procéder de façon plus systématique, cherchons une
+  relation de Bézout entre $19$ et $13$, qui sont visiblement premiers
+  entre eux (et ceci va de toute façon le confirmer) : on a $19 = 13 +
+  6$ puis $13 = 2\times 6 + 1$ donc le pgcd est bien $1$, et on a $1 =
+  13 - 2\times 6 = 3\times 13 - 2\times 19$.  Ainsi, d'après un
+  résultat du cours (version « effective » du théorème chinois), un
+  nombre congru à $19$ (soit $6$) modulo $13$ et à $13$ modulo $19$
+  est donné par $3 \times 13 \times 13 - 2 \times 19 \times 6$ : ceci
+  vaut $279$, mais pour simplifier les calculs on pouvait calculer
+  $3\times 13 \equiv 1 \pmod{19}$ et $-2 \times 6 \equiv 1 \pmod{13}$,
+  donc il reste $13 + 19 = 32$.  En tout état de cause, comme $13$ et
+  $19$ sont premiers entre eux, les nombres congrus à $x$ modulo $13$
+  et à $y$ modulo $19$, quels que soient $x$ et $y$ entiers, forment
+  une unique classe de congruence modulo $13 \times 19 = 247$ (qu'il
+  n'était pas vraiment nécessaire de calculer, seul importe que ce
+  soit $>100$, ce qui est évident), donc dès qu'on a trouvé un nombre
+  vérifiant les congruences demandées (en l'occurrence $32$), on sait
+  que les autres sont les nombres qui lui sont congrus modulo $13
+  \times 19$, et en particulier il n'y en a pas d'autre entre $0$
+  et $100$.
+\end{corrige}
+
+\ifcorrige\medbreak\else\relax\fi
+
 (B) Quel entier à trois chiffres en base $10$ se termine par $23$ et
 est multiple de $19$ ?
 
+\begin{corrige}
+(B) Se terminer par $23$ en base $10$ signifie être congru à $23$
+  modulo $100$.  Cherchons une relation de Bézout entre $100$ et $19$
+  qui sont premiers entre eux : on a $100 = 5\times 19 + 5$ et $19 =
+  3\times 5 + 4$ et $5 = 4 + 1$ donc $1 = 5 - 4 = 4 \times 5 - 19 = 4
+  \times 100 - 21 \times 19$.  Ainsi, d'après un résultat du cours
+  (version « effective » du théorème chinois), un nombre congru à $23$
+  modulo $100$ et à $0$ modulo $19$ (i.e., divisible par $19$) est
+  donné par $- 21 \times 19 \times 23$ : ceci vaut $-9177$, mais pour
+  simplifier les calculs on pouvait calculer $-21\times 23 \equiv -83
+  \equiv 17 \pmod{100}$ et ainsi $- 21 \times 19 \times 23 \equiv 17
+  \times 19 = 323 \pmod{1900}$.  Le nombre $323$ répond aux conditions
+  demandées, et comme tout les entiers congrus à $23$ modulo $100$ et
+  à $0$ modulo $19$ forment une unique classe de congruence
+  modulo $1900$, on a trouvé le seul nombre à trois chiffres.
+\end{corrige}
+
+\ifcorrige\medbreak\else\relax\fi
+
 (C) Quel entier entre $0$ et $100$ est congru respectivement à
 $1,2,3,4$ modulo $2,3,5,7$ ?  (C'est-à-dire : congru à $1$ modulo $2$,
 et à $2$ modulo $3$, et à $3$ modulo $5$, et à $4$ modulo $7$.)
 
+\begin{corrige}
+(C) Les nombres $2,3,5,7$ sont premiers entre eux deux à deux.
+  Commençons par trouver des solutions à deux congruences
+  simultanées : comme les nombres sont assez petits, il est plus
+  simple de le faire par tâtonnement : par exemple, $5$ est congru à
+  $1$ modulo $2$ et à $2$ modulo $3$, cela se trouve immédiatement en
+  parcourant les entiers de $0$ à $5$ ou plus astucieusement ceux qui
+  vérifient une des deux congruences pour chercher ceux qui vérifient
+  l'autre.  Comme on va vouloir mettre ensuite ensemble deux
+  congruences de ce genre, il vaut mieux les trouver de même taille
+  et, si possible, vérifiant une relation de Bézout simple : le plus
+  économique est donc de mettre $2$ avec $7$ et $3$ avec $5$, ce qui a
+  le bon goût que $15-14 = 1$ est une relation de Bézout évidente
+  entre $3\times 5$ et $2\times 7$.  Par tâtonnement, on trouve que
+  $11$ (et exactement les nombres de sa classe modulo $14$) est congru
+  à $1$ modulo $2$ et à $4$ modulo $7$, et que $8$ (et exactement les
+  nombres de sa classe modulo $15$) est congru à $2$ modulo $3$ et à
+  $3$ modulo $5$.  Avec la relation de Bézout $1\times 15 - 1\times 14
+  = 1$, toujours en appliquant la même version « effective » du
+  théorème chinois, on voit que les entiers vérifiant les quatre
+  congruences demandées sont exactement la classe de $1\times 15\times
+  11 - 1\times 14\times 8 = 53$ modulo $15 \times 14 = 210$, donc le
+  seul entre $0$ et $100$ est $53$.
+\end{corrige}
+
+\ifcorrige\medbreak\else\relax\fi
+
 (D) Déterminer tous les entiers entre $0$ et $2009$ congrus à $1$
 modulo chacun des nombres $7$, $11$ et $13$.  (C'est-à-dire : congrus
 à $1$ modulo $7$, et à $1$ modulo $11$, et à $1$ modulo $13$.)
 (Indication : y-t-il un nombre évident qui répond à cette condition ?)
 
+\begin{corrige}
+(D) Comme le suggère l'indication, il y a un nombre évident congru à
+  $1$ modulo $7$ et $11$ et $13$ à la fois, c'est $1$ lui-même.  Le
+  théorème chinois assure que, comme $7$ et $11$ et $13$ sont premiers
+  entre eux deux à deux, les entiers congrus à $1$ modulo chacun d'eux
+  forment une classe de congruence modulo $7 \times 11 \times 13 =
+  1001$.  Les nombres entre $0$ et $2009$ vérifiant les congruences
+  demandées sont donc : $1$, $1002$ et $2003$.
+\end{corrige}
+
+\ifcorrige\medbreak\else\relax\fi
+
 (E) Déterminer tous les entiers entre $0$ et $100\,000$ congrus à
 $192$ modulo $300$ et à $169$ modulo $305$.
 
+\begin{corrige}
+(E) Un entier congru à $192$ modulo $300$ est (comme $5|300$) congru à
+  $192 \equiv 2$ modulo $5$, et un entier congru à $169$ modulo $305$
+  est (comme $5|305$) congru à $169 \equiv 4$ modulo $5$.  Comme $2
+  \not\equiv 4 \pmod{5}$, il n'existe \emph{aucun} entier vérifiant
+  les deux congruences demandées.
+\end{corrige}
+
 %
 %
 %