diff options
| -rw-r--r-- | controle-20121127.tex | 40 |
1 files changed, 20 insertions, 20 deletions
diff --git a/controle-20121127.tex b/controle-20121127.tex index eae9647..29786f2 100644 --- a/controle-20121127.tex +++ b/controle-20121127.tex @@ -136,8 +136,8 @@ c'est-à-dire $x^{32\,768} \equiv 1 \pmod{65\,535}$. Le résultat de la question (2) est plus fort puisqu'il affirme que déjà $x^{256} \equiv 1 \pmod{65\,535}$ (autrement dit, le théorème d'Euler affirme que l'ordre multiplicatif de n'importe quel élément de -$(\mathbb{Z}/65535\mathbb{Z})^\times$ divise $32\,768$ tandis que la -question (2) affirme qu'en fait il divise $256$). +$(\mathbb{Z}/65535\mathbb{Z})^\times$ divise $2^{15}$ tandis que la +question (2) affirme qu'en fait il divise $2^8$). \end{corrige} (5) Montrer que $x^{257} \equiv x \pmod{p}$ pour tout entier $x$ et @@ -200,18 +200,18 @@ On a vu que modulo chacun des $p \in \{3,5,17, 257\}$, il n'y a que deux valeurs possibles de $x^{256}$ modulo $p$, à savoir $0$ ou $1$. Comme $3,5,17,257$ sont premiers entre eux deux à deux, le théorème chinois assure qu'une congruence modulo $65\,535$ équivaut exactement -à une congruence modulo chacun de $3,5,17, 257$. Appelons « valeur - magique » une classe de congruence $65\,535$ qui est congrue à $0$ -ou $1$ modulo chacun des $4$ nombres $3,5,17, 257$ : il y a $16$ -« valeurs magiques » (une pour chacune des combinaisons de $0$ ou de -$1$ modulo chacun des $4$ nombres $3,5,17, 257$, ce qui fait $2^4 = -16$). D'après ce qu'on a vu, $x^{256}$ est toujours une valeur -magique modulo $65\,535$. Et de plus, si $x$ lui-même est une valeur -magique, alors $x^{i} \equiv x \pmod{65\,535}$ pour tout $i\geq 1$ -puisque $0^{i} \equiv 0$ et $1^{i} \equiv 1$ modulo chacun des $p \in -\{3,5,17, 257\}$. En particulier, $x^{256} \equiv x \pmod{65\,535}$. -Donc les $16$ valeurs magiques sont bien toutes atteintes -par $x^{256}$. +à une congruence modulo chacun de $3,5,17, 257$. Appelons +temporairement « valeur magique » une classe de congruence $65\,535$ +qui est congrue à $0$ ou à $1$ modulo chacun des $4$ nombres $3,5,17, +257$ : il y a $16$ « valeurs magiques » (une pour chacune des +combinaisons de $0$ ou de $1$ modulo chacun des $4$ nombres $3,5,17, +257$, ce qui fait $2^4 = 16$). D'après ce qu'on a vu, $x^{256}$ est +toujours une valeur magique modulo $65\,535$. Et de plus, si $x$ +lui-même est une valeur magique, alors $x^{i} \equiv x \pmod{65\,535}$ +pour tout $i\geq 1$ puisque $0^{i} \equiv 0$ et $1^{i} \equiv 1$ +modulo chacun des $p \in \{3,5,17, 257\}$. En particulier, $x^{256} +\equiv x \pmod{65\,535}$ pour un tel $x$. Donc les $16$ valeurs +magiques sont bien toutes atteintes par $x^{256}$. \end{corrige} % @@ -326,12 +326,12 @@ $\alpha^{85} = \alpha^7 + \alpha^6 + \alpha^4 + \alpha^2 + \alpha$. qualifie-t-on l'élément $\alpha$ de $E$ ? Quel est l'ordre multiplicatif de $\beta = \alpha^{17}$ ? \begin{corrige} -On a vu en (2) que l'ordre de $\alpha$ est un des nombres $3, 5, -17,\penalty0 15, \penalty0 51, \penalty0 85, \penalty0 255$. Or on a -calculé $\alpha^i$ pour chacune des valeurs $3, 5, 17,\penalty0 15, -\penalty0 51, \penalty0 85$, et trouvé un résultat $\neq 1$. La seule -possibilité qui demeure est donc $255$ : l'élément $\alpha$ est -primitif dans $E$. +On a vu en (2) que l'ordre de $\alpha$ est un des nombres $3, +5,\penalty0 15,\penalty0 17, \penalty0 51, \penalty0 85, \penalty0 +255$. Or on a calculé $\alpha^i$ pour chacune des valeurs $3, +5,\penalty0 15,\penalty0 17, \penalty0 51, \penalty0 85$, et trouvé un +résultat $\neq 1$. La seule possibilité qui demeure est donc $255$ : +l'élément $\alpha$ est primitif dans $E$. Quant à l'ordre de $\beta$, puisque $\beta^i = \alpha^{17i}$ vaut $1$ si et seulement si $17i$ est un multiple de $255$, c'est-à-dire si et |