Correction of exercise 1.

1 files changed, 137 insertions, 1 deletions

diff --git a/controle-20091124.tex b/controle-20091124.tex
index dbecd31..22686ac 100644
--- a/controle-20091124.tex
+++ b/controle-20091124.tex
@@ -26,7 +26,7 @@
 \newcommand{\Frob}{\operatorname{Fr}}
 %
 \newif\ifcorrige
-\corrigefalse
+\corrigetrue
 \newenvironment{corrige}%
 {\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
 \smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
@@ -95,6 +95,36 @@ euclidienne par $9$ d'un entier naturel écrit en décimal ?
 (3) Montrer que la multiplication suivante est erronée :
 $745\,330\,964 \times 390\,158\,565 = 290\,797\,259\,507\,306\,660$.
 
+\begin{corrige}
+(A) (1) On a $10 \equiv 1 \pmod{9}$ donc $10^n \equiv 1^n \equiv
+  1\pmod{9}$.  (2) Si $A = \sum_{i=0}^{+\infty} a_i 10^i$ (avec $a_i
+  \in \{0,1,2,\ldots,9\}$) est l'écriture en base $10$ d'un entier
+  naturel $A$, alors $A \equiv \sum_{i=0}^{+\infty} a_i \pmod{9}$
+  puisque $10^i \equiv 1$ comme on vient de le voir : on a bien montré
+  que $A$ est congru modulo $9$ à la somme $\sum_{i=0}^{+\infty} a_i$
+  de ses chiffres décimaux.  Pour calculer le reste de la division
+  euclidienne par $9$ d'un entier naturel $A$, il suffit donc de
+  calculer celui de la somme de ses chiffres décimaux (ce qui peut se
+  faire en itérant l'opération « somme des chiffres décimaux » jusqu'à
+  obtenir un résultat à un chiffre, et remplacer $9$ par $0$ à la fin
+  si nécessaire).  Remarquons qu'on peut simplifier certaines choses :
+  par exemple, ignorer les $9$ dans l'écriture décimale, et remplacer
+  les $8$ par des $-1$, et évidemment remplacer un nombre par la somme
+  de ses chiffres décimaux à n'importe quelle étape du calcul.
+
+\leavevmode\hphantom{(A)} (3) En appliquant ce procédé, on voit que
+$745\,330\,964 \equiv\penalty-100 7+4+5+\penalty0 3+3+\penalty0 6+4
+=\penalty0 32 \equiv 5 \pmod{9}$, que $390\,158\,565
+\equiv\penalty-100 3+\penalty0 1+5+8+\penalty0 5+6+5 =\penalty0 33
+\equiv 6 \pmod{9}$ et que $290\,797\,259\,507\,306\,660
+\equiv\penalty-100 2+\penalty0 7+7+\penalty0 2+5+\penalty0
+5+7+\penalty0 3+6+\penalty0 6+6 = 56 \equiv 2 \pmod{9}$.  Comme
+$5\times 6 \equiv 3 \not\equiv 2 \pmod{9}$, cette « preuve par $9$ »
+montre que la multiplication proposée est erronée.
+\end{corrige}
+
+\ifcorrige\medbreak\else\relax\fi
+
 (B) (1) À quoi est congru $10^n$ modulo $11$ (en fonction
 éventuellement de l'entier naturel $n$) ?  (Remarque : le nombre $10$
 peut s'écrire d'une manière très simple modulo $11$...)  (2) Comment
@@ -103,6 +133,40 @@ euclidienne par $11$ d'un entier naturel écrit en décimal ?
 (3) Montrer que la multiplication suivante est encore erronée :
 $745\,330\,964 \times 390\,158\,565 = 290\,797\,259\,517\,306\,660$.
 
+\begin{corrige}
+(B) (1) On a $10 \equiv -1 \pmod{11}$ donc $10^n \equiv (-1)^n \equiv
+  1\pmod{11}$, c'est-à-dire concrètement que $10^n$ vaut $+1$ ou $-1$
+  modulo $11$ selon que $n$ est respectivement pair ou impair.  (2) Si
+  $A = \sum_{i=0}^{+\infty} a_i 10^i$ (avec $a_i \in
+  \{0,1,2,\ldots,9\}$) est l'écriture en base $10$ d'un entier
+  naturel $A$, alors $A \equiv \sum_{i=0}^{+\infty} (-1)^i a_i
+  \pmod{11}$ puisque $10^i \equiv (-1)^i$ comme on vient de le voir :
+  on a bien montré que $A$ est congru modulo $11$ à la somme
+  \emph{alternée} $\sum_{i=0}^{+\infty} (-1)^i a_i$ de ses chiffres
+  décimaux, c'est-à-dire en comptant avec un $+$ tous les chiffres de
+  puissance paire (unités, centaines, dizaines de milliers...) et avec
+  un $-$ tous les chiffres de puissance impaire (dizaines, milliers,
+  etc.).  Pour calculer le reste de la division euclidienne par $11$
+  d'un entier naturel $A$, il suffit donc de calculer celui de la
+  somme alternée de ses chiffres décimaux (ce qui peut se faire en
+  itérant l'opération « somme alternée des chiffres décimaux », en
+  n'oubliant pas les signes, jusqu'à obtenir un résultat entre $-9$ et
+  $9$, et ajouter $11$ à la fin si nécessaire pour obtenir un reste
+  entre $0$ et $10$ inclus).
+
+\leavevmode\hphantom{(B)} (3) En appliquant ce procédé, on voit que
+$745\,330\,964 \equiv\penalty-100 7-4+5-\penalty0 3+3+\penalty0 9-6+4
+=\penalty0 15 \equiv 4 \pmod{11}$, que $390\,158\,565
+\equiv\penalty-100 3-9-\penalty0 1+5-8+\penalty0 5-6+5 =\penalty0 -6
+\equiv 5 \pmod{11}$ et que $290\,797\,259\,517\,306\,660
+\equiv\penalty-100 -2+9+\penalty0 7-9+7-\penalty0 2+5-9+\penalty0
+5-1+7-\penalty0 3-6+\penalty0 6-6 =\penalty0 8 \pmod{11}$.  Comme
+$4\times 5 \equiv\penalty0 9 \not\equiv 8 \pmod{11}$, cette « preuve
+  par $11$ » montre que la multiplication proposée est erronée.
+\end{corrige}
+
+\ifcorrige\medbreak\else\relax\fi
+
 (C) (1) À quoi est congru $10^n$ modulo $7$, selon la valeur de $n$ ?
 (2) Proposer une méthode (moins simple que celles données en A et B,
 mais néanmoins plus économique que de poser la division) permettant de
@@ -111,6 +175,78 @@ naturel écrit en décimal.  (On cherchera à se limiter à des additions
 et des multiplications par $\pm 1, \pm 2, \pm 3$.)  (3) Montrer que le
 calcul suivant est erroné : $3^{31} = 617\,673\,693\,283\,947$.
 
+\begin{corrige}
+(C) (1) Remarquons tout d'abord que $10 \equiv 3 \pmod{7}$.  On peut
+dresser de proche en proche la table suivante des puissances de $10$
+modulo $7$ :
+
+\begin{center}
+\begin{tabular}{c|c|c|c|c|c|c}
+$i$&$0$&$1$&$2$&$3$&$4$&$5$\\\hline
+$10^i$&$1$&$3$&$2$&$-1$&$-3$&$-2$\\
+\end{tabular}
+\end{center}
+
+\noindent (On a représenté $6$, $4$ et $5$ modulo $7$ par $-1$, $-3$
+et $-2$ respectivement, de façon à rendre les calculs plus faciles.)
+Le fait (qu'on trouve ensuite) que $10^6 \equiv 1 \pmod{7}$ était
+prévu par le petit théorème de Fermat.  De façon plus générale,
+$10^{6k} \equiv 1 \pmod{7}$ donc $10^{6k+i} \equiv 10^i \pmod{7}$ :
+ainsi, dans la table ci-dessus, l'indice $i$ peut se lire modulo $6$.
+
+\leavevmode\hphantom{(C)} (2) D'après ce qu'on vient d'expliquer, un
+entier naturel $A = \sum_{i=0}^{+\infty} a_i 10^i$ (écrit en décimal)
+est congru modulo $7$ à la somme de ses chiffres décimaux $a_i$ chacun
+multiplié par une valeur dans $\{\pm 1, \pm 2, \pm 3\}$ donnée (en
+fonction de $i$ modulo $6$) par la table ci-dessus : c'est-à-dire $a_0
++\penalty100 3 \times a_1 +\penalty0 2 \times a_2 -\penalty0 a_3
+-\penalty0 3\times a_4 -\penalty0 2 \times a_5 +\penalty0 a_6
++\penalty0 3 \times a_7 + \cdots$.  Pour simplifier les calculs
+ultérieurs, il peut être astucieux de précalculer les multiplications
+par tous les chiffres décimaux possibles, c'est-à-dire de dresser le
+tableau des valeurs de $a_i \times 10^i$ modulo $7$ en fonction de
+$a_i$ et de $i$ :
+
+\begin{center}
+\begin{tabular}{r|c|c|c|c|c|c}
+$a_i\downarrow$\textbackslash $i\rightarrow$&$0$&$1$&$2$&$3$&$4$&$5$\\\hline
+$0$\rlap{, $7$}\hphantom{\textbackslash $i\rightarrow$}&$0$&$0$&$0$&$0$&$0$&$0$\\
+$1$\rlap{, $8$}\hphantom{\textbackslash $i\rightarrow$}&$1$&$3$&$2$&$6$&$4$&$5$\\
+$2$\rlap{, $9$}\hphantom{\textbackslash $i\rightarrow$}&$2$&$6$&$4$&$5$&$1$&$3$\\
+$3$\hphantom{\textbackslash $i\rightarrow$}&$3$&$2$&$6$&$4$&$5$&$1$\\
+$4$\hphantom{\textbackslash $i\rightarrow$}&$4$&$5$&$1$&$3$&$2$&$6$\\
+$5$\hphantom{\textbackslash $i\rightarrow$}&$5$&$1$&$3$&$2$&$6$&$4$\\
+$6$\hphantom{\textbackslash $i\rightarrow$}&$6$&$4$&$5$&$1$&$3$&$2$\\
+\end{tabular}
+\end{center}
+
+\noindent Avec ce tableau, pour calculer la classe modulo $7$ de $A =
+\sum_{i=0}^{+\infty} a_i 10^i$, il suffit de sommer les valeurs des
+cases de chaque chiffre (la ligne étant déterminée par la valeur $a_i$
+du chiffre décimal en question, et la colonne par l'exposant $i$
+modulo $6$ de la puissance de $10$ utilisée).  Il s'agit simplement
+d'une façon de regrouper une fois pour toutes le calcul des
+multiplications par $\pm 1, \pm 2, \pm 3$, le calcul étant toujours le
+même.  Pour être encore plus efficace, on peut d'ailleurs remplir le
+tableau de façon « paresseuse », c'est-à-dire en ne calculant le
+contenu des cases que lorsqu'on en a besoin.
+
+\leavevmode\hphantom{(C)} (3) En appliquant ce procédé, on voit qu'on
+a $617\,673\,693\,283\,947 \equiv\penalty-100 2\times 6 +\penalty1000
+3\times 1 +\penalty1000 7 -\penalty0 2\times 6 -\penalty1000 3\times 7
+-\penalty1000 3 +\penalty0 2\times 6 +\penalty1000 3\times 9
++\penalty1000 3 -\penalty0 2\times 2 -\penalty1000 3\times 8
+-\penalty1000 3 +\penalty0 2\times 9 +\penalty1000 3\times 4
++\penalty1000 7 =\penalty-100 34 \equiv 6 \pmod{7}$ ou, en utilisant
+directement le tableau ci-dessus, $\equiv 5 + 3 + 0 +\penalty0 2 + 0 +
+4 +\penalty0 5 + 6 + 3 +\penalty0 3 + 4 + 4 +\penalty0 4 + 5 + 0
+=\penalty-100 48 \equiv 6 \pmod{7}$.  Mais d'autre part $3^{31}$ est,
+modulo $7$, congru à ($10^{31}$ donc à) $3$ puisque $31 \equiv 1 \pmod
+6$ (ou si on veut, $3^{31} \equiv 3^{5\times 6 + 1} \equiv 3 \pmod{7}$
+puisque $3^6 \equiv 1 \pmod{7}$).  Comme $6 \not\equiv 3$, le nombre
+proposé n'est pas la valeur correcte de $3^{31}$.
+\end{corrige}
+
 %
 %
 %