diff options
| author | david <david> | 2009-11-17 16:24:53 +0000 |
|---|---|---|
| committer | david <david> | 2009-11-17 16:24:53 +0000 |
| commit | 06437e108957dfea54779e88bd9e031adee49443 (patch) | |
| tree | b28e5c7317166b87939975159560579d88a1826a | |
| parent | eae8d9e3ae6ab3c9f5d908637676d86a93b8c47b (diff) | |
| download | infmdi720-06437e108957dfea54779e88bd9e031adee49443.tar.gz infmdi720-06437e108957dfea54779e88bd9e031adee49443.tar.bz2 infmdi720-06437e108957dfea54779e88bd9e031adee49443.zip | |
Correction of exercise 1.
| -rw-r--r-- | controle-20091124.tex | 138 |
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} + % % % |