diff options
Diffstat (limited to 'controle-20091124.tex')
| -rw-r--r-- | controle-20091124.tex | 24 |
1 files changed, 12 insertions, 12 deletions
diff --git a/controle-20091124.tex b/controle-20091124.tex index 98eaf11..bbc62dc 100644 --- a/controle-20091124.tex +++ b/controle-20091124.tex @@ -97,7 +97,7 @@ $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 + 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é @@ -137,7 +137,7 @@ $745\,330\,964 \times 390\,158\,565 = 290\,797\,259\,517\,306\,660$. (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 + $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 : @@ -197,7 +197,7 @@ $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) +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 @@ -224,7 +224,7 @@ $6$\hphantom{\textbackslash $i\rightarrow$}&$6$&$4$&$5$&$1$&$3$&$2$\\ \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 +\sum_{i=0}^{+\infty} a_i\, 10^i$, il suffit de sommer modulo $7$ 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 @@ -264,7 +264,7 @@ $13$ modulo $19$ ? rendre compte que $19+13 = 32$ convient pour des raisons de symétrie. Pour procéder de façon plus systématique, cherchons une relation de Bézout entre $19$ et $13$, qui sont visiblement premiers - entre eux (et ceci va de toute façon le confirmer) : on a $19 = 13 + + entre eux (et ceci va de toute façon le confirmer) : on a $19 = 1\times 13 + 6$ puis $13 = 2\times 6 + 1$ donc le pgcd est bien $1$, et on a $1 = 13 - 2\times 6 = 3\times 13 - 2\times 19$. Ainsi, d'après un résultat du cours (version « effective » du théorème chinois), un @@ -293,7 +293,7 @@ est multiple de $19$ ? (B) Se terminer par $23$ en base $10$ signifie être congru à $23$ modulo $100$. Cherchons une relation de Bézout entre $100$ et $19$ qui sont premiers entre eux : on a $100 = 5\times 19 + 5$ et $19 = - 3\times 5 + 4$ et $5 = 4 + 1$ donc $1 = 5 - 4 = 4 \times 5 - 19 = 4 + 3\times 5 + 4$ et $5 = 1\times 4 + 1$ donc $1 = 5 - 4 = 4 \times 5 - 19 = 4 \times 100 - 21 \times 19$. Ainsi, d'après un résultat du cours (version « effective » du théorème chinois), un nombre congru à $23$ modulo $100$ et à $0$ modulo $19$ (i.e., divisible par $19$) est @@ -324,7 +324,7 @@ et à $2$ modulo $3$, et à $3$ modulo $5$, et à $4$ modulo $7$.) congruences de ce genre, il vaut mieux les trouver de même taille et, si possible, vérifiant une relation de Bézout simple : le plus économique est donc de mettre $2$ avec $7$ et $3$ avec $5$, ce qui a - le bon goût que $15-14 = 1$ est une relation de Bézout évidente + le bon goût que $1\times 15 - 1\times 14 = 1$ est une relation de Bézout évidente entre $3\times 5$ et $2\times 7$. Par tâtonnement, on trouve que $11$ (et exactement les nombres de sa classe modulo $14$) est congru à $1$ modulo $2$ et à $4$ modulo $7$, et que $8$ (et exactement les @@ -425,7 +425,7 @@ primitifs ? \begin{corrige} (A) (1) On peut par exemple remarquer que le polynôme $f = t^2 + t - 1 - \in \mathbb{F}_3[t]$ n'a pas de racine dans $\mathbb{F}_3$ (car + \penalty0 \in \mathbb{F}_3[t]$ n'a pas de racine dans $\mathbb{F}_3$ (car $f(0) = -1$, $f(1) = 1$ et $f(-1) = -1$), ce qui interdit qu'il possède une factorisation non-triviale (car si $f = f_1 f_2$ avec $f_1,f_2$ de degré $<2$, ils seront chacun de degré $1$, donc ils @@ -498,16 +498,16 @@ $\bar t^i$&$1$&$\bar t$&$-\bar t+1$&$-\bar t-1$&$-1$&$-\bar t$&$-\bar t-1$&$\bar \noindent Le fait (qu'on trouve ensuite) que $\bar t^8 = 1$ était prévu par le petit théorème de Fermat généralisé. Comme on a trouvé $8$ puissances de $\bar t$ distinctes (c'est-à-dire qu'on n'est pas -retombé sur $1$ avant ce que le petit théorème de Fermat imposé), +retombé sur $1$ avant ce que le petit théorème de Fermat impose), l'élément $\bar t$ est primitif. La table ci-dessus est alors la donnée d'un isomorphisme $i \mapsto \bar t^i$ entre le groupe additif $\mathbb{Z}/8\mathbb{Z}$ et le groupe multiplicatif $\mathbb{F}_9^\times$ (tous deux étant cycliques d'ordre $8$). Les générateurs de $\mathbb{F}_9^\times$ sont alors les $\varphi(8) = 4$ -éléments écrits qui correspondent à un générateur de +éléments qui correspondent à un générateur de $\mathbb{Z}/8\mathbb{Z}$ par cet isomorphisme : comme les générateurs du groupe additif $\mathbb{Z}/8\mathbb{Z}$ sont $1,3,5,7$ (ce sont les -éléments nombres premiers avec $8$ modulo $8$, c'est-à-dire les +nombres premiers avec $8$ modulo $8$, c'est-à-dire les nombres impairs), les générateurs de $\mathbb{F}_9^\times$, autrement dit les éléments primitifs de $\mathbb{F}_9$, sont $\bar t$, $-\bar t-1$, $-\bar t$ et $\bar t+1$. @@ -564,7 +564,7 @@ $\bar t$ est-il primitif dans $\mathbb{F}_2[t]/(t^5 + t^2 + 1)$ ? Forbenius), $t^{16} \equiv t^6 + t^4 + 1 \equiv t^4 + t^3 + t + 1 \pmod{f}$ (car on a vu $t^6 \equiv t^3 + t$), et en élevant de nouveau au carré, $t^{32} \equiv t^8 + t^6 + t^2 + 1 \equiv (t^3 + - t^2 + 1) + (t^3 + t) + t^2 + 1 \equiv t \pmod{f}$, ce qui prouve + t^2 + 1) + (t^3 + t) + t^2 + 1 = t \pmod{f}$, ce qui prouve bien que $f$ divise $t^{32} - t$. On pouvait aussi, bien entendu, poser la division euclidienne (mais elle est un peu fastidieuse\footnote{On trouve $t^{32} + t = (t^{27} + t^{24} + |