diff options
| -rw-r--r-- | controle-20081202.tex | 75 |
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} + % % % |