1 files changed, 75 insertions, 0 deletions
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�$990$�?
 
 % 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}
+
 %
 %
 %