From ff9fef0802a338c737514e51495155ceed495fc2 Mon Sep 17 00:00:00 2001
From: david <david>
Date: Mon, 12 Jan 2009 17:03:32 +0000
Subject: Correction for exercise 3.

---
 controle-20081202.tex | 75 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 75 insertions(+)

(limited to 'controle-20081202.tex')

diff --git a/controle-20081202.tex b/controle-20081202.tex
index 094350a..3ad1420 100644
--- a/controle-20081202.tex
+++ b/controle-20081202.tex
@@ -204,6 +204,81 @@ Par
 
 % Réponses : 97, 196
 
+\begin{corrige}
+(1) Le théorème d'Euler (ou une vérification naïve immédiate) assure
+  que $2^2 \equiv 1 \pmod{3}$.  Par conséquent, $2^{100} = (2^2)^{50}
+  \equiv 1^{50} = 1 \pmod{3}$.  De même, modulo $5$, on a (toujours
+  par Euler ou vérification naïve) $2^4 \equiv 1 \pmod {5}$ donc
+  $2^{100} = (2^5)^{25} \equiv 1^{25} = 1 \pmod{5}$.
+
+(2) Le théorème chinois assure que la classe de congruence de $n$
+  modulo $6$ dépend de celles de $n$ modulo $2$ et $3$.  La question
+  précédente a déterminé la classe de $n$ modulo $3$ (c'est $1$), et
+  on a visiblement $n = 2^{100} \equiv 0 \pmod{2}$ (manifestement,
+  $2^{100}$ est pair...).  Pour reconstituer $n$ modulo $6$, on
+  cherche donc un nombre congru à $1$ modulo $3$ et à $0$ modulo $2$ :
+  on peut chercher une relation de Bézout ($3-2=1$), mais il est plus
+  simple d'examiner rapidement les différentes classes possibles
+  entre $0$ et $5$ : visiblement $4$ convient, donc $n \equiv 4
+  \pmod{6}$.
+
+De même, pour déterminer la classe de $n$ modulo $10$, le théorème
+chinois assure qu'elle ne dépend que de $n$ modulo $2$ et $5$.  Or on
+a vu $n \equiv 0 \pmod{2}$ et $n \equiv 1 \pmod{5}$.  On voit
+rapidement que $6$ est congru aux mêmes quantités, donc $n \equiv 6
+\pmod{10}$.
+
+Enfin, il est clair que $2^{100}$ est multiple de $4$ (i.e., congru
+à $0$ modulo $4$).
+
+(3) Le théorème d'Euler assure que $2^6 \equiv 1 \pmod{9}$ (on a
+$\varphi(9) = \frac{2}{3}\times 9 = 6$).  Par conséquent, $2^{6k} =
+(2^6)^k \equiv 1^{k} = 1 \pmod{9}$ pour tout $k \in \mathbb{N}$.  Or
+on a vu à la question précédente que $n = 2^{100}$ peut s'écrire sous
+la forme $6k + 4$ : on a donc $2^n = 2^{6k+4} \equiv 2^4 \equiv 7
+\pmod{9}$.
+
+Modulo $11$, le raisonnement est analogue : le théorème d'Euler (ou
+Fermat) assure que $2^{10} \equiv 1 \pmod{11}$.  Par conséquent,
+$2^{10k} = (2^{10})^k \equiv 1^k = 1 \pmod{11}$ pour tout $k \in
+\mathbb{N}$.  Or on a vu que $n = 2^{100}$ peut s'écrire sous la forme
+$10k+6$ : on a donc $2^n = 2^{10k+6} \equiv 2^6 \equiv 9 \pmod{11}$.
+
+Modulo $10$, on ne peut pas appliquer le même raisonnement ($2$ n'est
+pas premier à $10$ !), mais on peut appliquer celui des questions
+(1) et (2) : on a vu $n \equiv 0 \pmod{4}$, c'est-à-dire qu'on peut
+écrire $n = 4k$ (avec $k = 2^{98}$ mais peu importe), donc $2^n =
+(2^4)^k \equiv 1^k = 1 \pmod{5}$, et comme $2^n \equiv 0 \pmod{2}$, on
+a $2^n \equiv 6 \pmod{10}$ (exactement comme on l'a fait en (2)).
+
+(4) Il s'agit enfin d'appliquer le théorème chinois de façon effective
+pour reconstituer la classe de $N$ modulo $99$ puis $990$ à partir de
+ses classes modulo $9$, $11$ et $10$, déjà calculées (soit $N \equiv 7
+\pmod{9}$, $N \equiv 9 \pmod{11}$ et $N \equiv 6 \pmod{10}$).
+
+Trouvons une relation de Bézout entre $9$ et $11$ (qui sont bien
+premiers entre eux !).  Pour cela, on peut appliquer l'algorithme
+d'Euclide étendu, qui termine en deux divisions : $11 = 1\times 9 + 2$
+puis $9 = 4\times 2 + 1$, donc $1 = 1\times 9 - 4\times 2$ et ($2 = 11
+- 1\times 9$ donc) $1 = 5\times 9 - 4\times 11$ (on pouvait aussi
+trouver rapidement cette relation en cherchant dans les petits
+multiples de $9$ et $11$ lesquels deux sont consécutifs).  On sait
+donc (cours) que $N \equiv 9\times 5\times 9 - 7\times 4\times 11
+\pmod{99}$ : pour faire ce calcul plus simplement à la main, on peut
+réduire $9\times 5$ modulo $11$ et $7\times 4$ modulo $9$, ce qui fait
+respectivement $1$ et $1$, donc $N \equiv 1\times 9 - 1\times 11 = -2
+\equiv 97 \pmod{99}$.
+
+Enfin, reconstruisons $N$ modulo $990$ à partir de $N \equiv 6
+\pmod{10}$ et $N \equiv 97 \pmod{99}$.  Une relation de Bézout entre
+$99$ et $10$ est évidente : c'est $10\times 10 - 1\times 99 = 1$.  Par
+conséquent, $N \equiv 97\times 10\times 10 - 6\times 1\times 99
+\pmod{990}$.  De nouveau, pour simplifier les calculs, on peut se
+contenter de calculer $97\times 10 \equiv (-2)\times 10 = -20$
+modulo $99$ et $-6\times 1 \equiv 4 \pmod{10}$, donc on a $N \equiv
+-20\times 0 + 4\times 99 = 196 \pmod{990}$.
+\end{corrige}
+
 %
 %
 %
-- 
cgit v1.2.3