diff options
| author | David A. Madore <david+git@madore.org> | 2010-11-16 15:01:44 +0100 |
|---|---|---|
| committer | David A. Madore <david+git@madore.org> | 2010-11-16 15:01:44 +0100 |
| commit | 8e2faac546057826f25b9a6f913c02b2fb2415aa (patch) | |
| tree | 0d0bd9c9fce5ec6b62b92c49b9ab41c419da6052 | |
| parent | 414eea7cacf47ec149fdc13fe25664dd53e9296e (diff) | |
| download | infmdi720-8e2faac546057826f25b9a6f913c02b2fb2415aa.tar.gz infmdi720-8e2faac546057826f25b9a6f913c02b2fb2415aa.tar.bz2 infmdi720-8e2faac546057826f25b9a6f913c02b2fb2415aa.zip | |
Alter and solve first exercise.
| -rw-r--r-- | controle-20101123.tex | 76 |
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} + % % % |