From 06437e108957dfea54779e88bd9e031adee49443 Mon Sep 17 00:00:00 2001 From: david Date: Tue, 17 Nov 2009 16:24:53 +0000 Subject: Correction of exercise 1. --- controle-20091124.tex | 138 +++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 137 insertions(+), 1 deletion(-) (limited to 'controle-20091124.tex') 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 (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 (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 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} + % % % -- cgit v1.2.3