summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2010-11-16 15:01:44 +0100
committerDavid A. Madore <david+git@madore.org>2010-11-16 15:01:44 +0100
commit8e2faac546057826f25b9a6f913c02b2fb2415aa (patch)
tree0d0bd9c9fce5ec6b62b92c49b9ab41c419da6052
parent414eea7cacf47ec149fdc13fe25664dd53e9296e (diff)
downloadinfmdi720-8e2faac546057826f25b9a6f913c02b2fb2415aa.tar.gz
infmdi720-8e2faac546057826f25b9a6f913c02b2fb2415aa.tar.bz2
infmdi720-8e2faac546057826f25b9a6f913c02b2fb2415aa.zip
Alter and solve first exercise.
-rw-r--r--controle-20101123.tex76
1 files changed, 71 insertions, 5 deletions
diff --git a/controle-20101123.tex b/controle-20101123.tex
index 8157167..129d3a3 100644
--- a/controle-20101123.tex
+++ b/controle-20101123.tex
@@ -76,15 +76,81 @@ Durée : 1h30
(A) Quel entier entre $1500$ et $2500$ est congru à $36$ modulo $47$
et à $49$ modulo $53$ ?
-(B) Quel est le plus petit entier naturel multiple de $9$ et de $11$
-et congru à $6$ modulo $10$ ?
-
-(C) Quels sont les entier entre $0$ et $100$ congrus à $6$ modulo $18$
-et à $15$ modulo $27$ ?
+\begin{corrige}
+Trouvons d'abord une relation de Bézout entre $47$ et $53$, en
+vérifiant du même coup qu'ils sont premiers entre eux. On a les
+divisions euclidiennes successives $53 = 1 \times 47 + 6$, puis $47 =
+7 \times 6 + 5$, puis $6 = 1 \times 5 + 1$ : ceci montre que le pgcd
+est bien $1$, et on peut ensuite écrire $1 = 1\times 6 - 1\times 5 =
+8\times 6 - 1\times 47 = 8\times 53 - 9\times 47$, cette dernière
+constituant la relation de Bézout recherchée.
+
+Comme $47$ et $53$ sont premiers entre eux, le théorème chinois assure
+que se donner une congruence modulo $47$ et une congruence modulo $53$
+équivaut à se donner une congruence modulo $47\times 53$ ; comme
+$47\times 53$ est certainement $>1000$, ceci suffira à définir un
+unique entier entre $1500$ et $2500$ s'il en existe un. On sait par
+ailleurs que l'entier $36\times 8\times 53 - 49\times 9\times 47$
+vérifiera les congruences recherchées ; on peut simplifier le calcul
+en calculant $36\times 8 = 288 \equiv 6 \pmod{47}$ et $-49\times 9 =
+-441 \equiv 36 \pmod{53}$, ce qui donne $6\times 53 + 36\times 47 =
+2010$, qui vérifie les conditions demandées.
+\end{corrige}
+
+\ifcorrige\medbreak\else\relax\fi
+
+(B) Quel est le plus petit entier naturel multiple de $9$, congru à
+$6$ modulo $11$ et congru à $6$ modulo $10$ ?
+
+\begin{corrige}
+D'après le théorème chinois, être congru à $6$ modulo $10$ et $11$,
+comme ceux-ci sont premiers entre eux, revient à être congru à $6$
+modulo $10 \times 11 = 110$. Cherchons maintenant une relation de
+Bézout entre $110$ et $9$ : on a $110 = 12\times 9 + 2$ et $9 =
+4\times 2 + 1$ donc $1 = 1\times 9 - 4\times 2 = 49\times 9 - 4\times
+110$. Le théorème chinois assure qu'être congru à $6$ modulo $110$ et
+à $0$ modulo $9$ équivaut à être congru à $6\times 49\times 9 -
+0\times 4\times 110$ modulo $990$ ; or $6\times 49 = 294 \equiv 74
+\pmod{110}$ donc $6\times 49\times 9 \equiv 74\times 9 = 666
+\pmod{990}$. Ceci démontre que les entiers congrus à $0$ modulo $9$,
+à $6$ modulo $11$ et à $6$ modulo $10$ sont ceux congrus à $666$
+modulo $990$, dont le plus petit positif est $666$.
+\end{corrige}
+
+\ifcorrige\medbreak\else\relax\fi
+
+(C) Quels sont les entier entre $0$ et $100$ congrus à $12$ modulo $15$
+et à $2$ modulo $20$ ?
+
+\begin{corrige}
+Les nombres $15$ et $20$ ne sont pas premiers entre eux : leur pgcd
+vaut $5$ puisque $15 = 3\times 5$ et $20 = 4\times 5$. Ceci étant,
+les congruences $12$ modulo $15$ et $2$ modulo $20$ sont compatibles
+modulo $5$ (toutes deux se réduisent sur $2$). Vérifier ces deux
+congruences revient donc simplement à être congru à $12$ modulo $15$
+et à $2$ modulo $4$. Trouvons une relation de Bézout entre $15$
+et $4$ : on a $15 = 3\times 4 + 3$ et $4 = 1\times 3 + 1$ donc $1 =
+1\times 4 - 1\times 3 = 4\times 4 - 1\times 15$. Donc être congru à
+$12$ modulo $15$, et à $2$ modulo $4$ (ou ce qui revient au même à $2$
+modulo $20$) revient à être congru à $12\times 4\times 4 - 2\times
+1\times 15 = 162$ modulo $15\times 4 = 60$. Le seul nombre entre $0$
+et $100$ vérifiant cette congruence est $42$.
+\end{corrige}
+
+\ifcorrige\medbreak\else\relax\fi
(D) Quels sont les entier entre $0$ et $9000$ congrus à $18$
modulo $91$ et à $24$ modulo $105$ ?
+\begin{corrige}
+Les nombres $91$ et $105$ ne sont pas premiers entre eux : leur pgcd
+est $7$ comme on le voit par exemple en appliquant l'algorithme
+d'Euclide ($105 = 1\times 91+14$ puis $91 = 6\times 14 + 7$ puis $14 =
+2\times 7$). Or $18$ et $24$ ne sont pas congrus modulo $7$, donc
+aucun nombre congru à $18$ modulo $91$ n'est congru à $24$
+modulo $105$.
+\end{corrige}
+
%
%
%