summaryrefslogtreecommitdiffstats
path: root/controle-20091124.tex
diff options
context:
space:
mode:
authordavid <david>2009-11-17 17:13:09 (GMT)
committerdavid <david>2009-11-17 17:13:09 (GMT)
commite36a72557f72d6737440a0ae39acb75ad85e6de7 (patch)
tree5c9341f8e7133b3dae4d92a3dd3ff981668c5c31 /controle-20091124.tex
parent06437e108957dfea54779e88bd9e031adee49443 (diff)
downloadinfmdi720-e36a72557f72d6737440a0ae39acb75ad85e6de7.zip
infmdi720-e36a72557f72d6737440a0ae39acb75ad85e6de7.tar.gz
infmdi720-e36a72557f72d6737440a0ae39acb75ad85e6de7.tar.bz2
Correct exercise 2.
Diffstat (limited to 'controle-20091124.tex')
-rw-r--r--controle-20091124.tex93
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}
+
%
%
%