summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authordavid <david>2009-01-12 17:03:32 +0000
committerdavid <david>2009-01-12 17:03:32 +0000
commitff9fef0802a338c737514e51495155ceed495fc2 (patch)
treed994992ab4625c5a92002afeb9e7c3d9bb7e75fb
parentab853785f483befb8f9504782863feaf45716505 (diff)
downloadinfmdi720-ff9fef0802a338c737514e51495155ceed495fc2.tar.gz
infmdi720-ff9fef0802a338c737514e51495155ceed495fc2.tar.bz2
infmdi720-ff9fef0802a338c737514e51495155ceed495fc2.zip
Correction for exercise 3.
-rw-r--r--controle-20081202.tex75
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}
+
%
%
%