From a390bb936ec7ed5c4568d456e902cb6f460999fd Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Thu, 22 Nov 2012 23:35:12 +0100
Subject: Write solution for exercise 1.

---
 controle-20121127.tex | 93 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 93 insertions(+)

(limited to 'controle-20121127.tex')

diff --git a/controle-20121127.tex b/controle-20121127.tex
index d402e5f..1d3c8d5 100644
--- a/controle-20121127.tex
+++ b/controle-20121127.tex
@@ -81,29 +81,89 @@ La décomposition en facteurs premiers de $65\,535$ est : $3 \times 5
 discutera selon la valeur de $x$ modulo $p$, et on dira clairement
 quelles sont toutes les valeurs possibles que peut prendre $x^{256}$
 modulo $p$.)
+\begin{corrige}
+Le petit théorème de Fermat (ou le théorème d'Euler) affirme que
+$x^{256} \equiv 1 \pmod{257}$ si $x$ n'est pas nul modulo $257$ ; et
+si $x$ \emph{est} nul modulo $257$ (c'est-à-dire, multiple de lui),
+alors évidemment $x^{256} \equiv 0 \pmod{257}$.  Les deux valeurs
+possibles de $x^{256}$ modulo $257$ sont donc $0$ et $1$.
+\end{corrige}
 
 (1b) Même question que (1a) mais cette fois pour $x^{256}$ modulo $p$
 avec $p \in \{3,5,17\}$ (on prendra garde que l'exposant est toujours
 $256$ dans cette question, ce n'est pas une erreur de l'énoncé).
+\begin{corrige}
+Comme en (1a), on a $x^{p-1} \equiv 1 \pmod{p}$ si $x$ n'est pas nul
+modulo $p$ et $x^{p-1} \equiv 0 \pmod{p}$ si $x$ est nul modulo $p$ ;
+et comme $256$ est multiple de $p-1$ dans chacun des cas considérés
+(c'est-à-dire multiple de $2,4,16$), et comme toute puissance de $1$
+vaut $1$ et toute puissance non nulle de $0$ vaut $0$, on a aussi
+$x^{256} \equiv 1 \pmod{p}$ si $x$ n'est pas nul modulo $p$ et
+$x^{256} \equiv 0 \pmod{p}$ si $x$ est nul modulo $p$.
+\end{corrige}
 
 (2) Montrer que $x^{256} \equiv 1 \pmod{65\,535}$ si $x$ est premier
 avec $65\,535$.  Que peut-on en déduire sur l'ordre multiplicatif des
 éléments de $(\mathbb{Z}/65535\mathbb{Z})^\times$ ?
+\begin{corrige}
+Si $x$ est premier avec $65\,535$, cela signifie qu'il est n'est pas
+multiple de $p$ pour $p \in \{3,5,17,257\}$, autrement dit qu'il est
+non-nul modulo $p$ pour chacun de ces $p$.  On a vu que dans ces
+conditions $x^{256} \equiv 1 \pmod{p}$ pour chacun de ces $p$.  Comme
+$3,5,17,257$ sont premiers entre eux deux à deux, le théorème chinois
+assure que la congruence $x^{256} \equiv 1$ modulo ces quatre nombres
+implique la même congruence $x^{256} \equiv 1$ modulo leur produit,
+c'est-à-dire $x^{256} \equiv 1 \pmod{65\,535}$.
+
+Autrement dit, l'ordre multiplicatif de n'importe quel élément de
+$(\mathbb{Z}/65535\mathbb{Z})^\times$ divise $256$ (ou, si on préfère,
+est de la forme $2^i$ pour un $0\leq i \leq 8$).
+\end{corrige}
 
 (3) Que vaut $\varphi(65\,535)$ ?
+\begin{corrige}
+Par multiplicativité de $\varphi$, cela vaut $(3-1) \times (5-1)
+\times (17-1) \times (257-1) = 2 \times 4 \times 16 \times 256 =
+2^{1+2+4+8} = 2^{15} = 32\,768$.
+\end{corrige}
 
 (4) Comparer le résultat de la question (2) à l'énoncé du théorème
 d'Euler modulo $65\,535$.
+\begin{corrige}
+Le théorème d'Euler modulo $65\,535$ assure que $x^{\varphi(65\,535)}
+\equiv 1 \pmod{65\,535}$ pour tout $x$ premier avec $65\,535$,
+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$).
+\end{corrige}
 
 (5) Montrer que $x^{257} \equiv x \pmod{p}$ pour tout entier $x$ et
 pour tout $p \in \{3,5,17, 257\}$.
+\begin{corrige}
+Si $x$ n'est pas multiple de $p$, on a vu $x^{256} \equiv 1 \pmod{p}$
+et on en déduit $x^{257} \equiv x \pmod{p}$ ; si $x$ est multiple
+de $p$, alors $x^{257} \equiv 0 \equiv x \pmod{p}$.
+\end{corrige}
 
 (6) En déduire que $x^{257} \equiv x \pmod{65\,535}$ pour tout
 entier $x$.
+\begin{corrige}
+Comme $3,5,17,257$ sont premiers entre eux deux à deux, le théorème
+chinois assure que la congruence $x^{257} \equiv x$ modulo ces quatre
+nombres implique la même congruence $x^{257} \equiv x$ modulo leur
+produit, c'est-à-dire $x^{257} \equiv x \pmod{65\,535}$.
+\end{corrige}
 
 (7) Rappeler pourquoi il existe des éléments de
 $(\mathbb{Z}/257\mathbb{Z})^\times$ dont l'ordre multiplicatif vaut
 exactement $256$.
+\begin{corrige}
+Ces éléments sont dits primitifs, et ils existent car $257$ est
+premier.
+\end{corrige}
 
 (8) On suppose que $x$ est un entier premier avec $65\,535$ et que
 l'ordre multiplicatif de sa classe modulo $257$ (qui est un élément de
@@ -111,15 +171,48 @@ $(\mathbb{Z}/257\mathbb{Z})^\times$) vaut exactement $256$.  Montrer
 que la classe de $x$ modulo $65\,535$ (qui est cette fois un élément
 de $(\mathbb{Z}/65535\mathbb{Z})^\times$) est elle aussi d'ordre
 multiplicatif $256$.
+\begin{corrige}
+On sait déjà que l'ordre multiplicatif de $x$ modulo $65\,535$
+divise $256$ (c'est la question (2)), il s'agit de montrer qu'il n'est
+pas moindre.  Mais si on avait $x^i \equiv 1 \pmod{65\,536}$ pour $0 <
+i < 256$, alors \emph{en particulier} on aurait $x^i \equiv 1
+\pmod{257}$ puisque $257$ divise $65\,536$.  Or on a supposé que
+l'ordre multiplicatif de $x$ modulo $257$ vaut $256$, ce qui signifie
+que $x^i \equiv 1 \pmod{257}$ ne se produit pas avant $256$.
+\end{corrige}
 
 (9) En déduire l'ordre multiplicatif maximal possible d'un élément de
 $(\mathbb{Z}/65535\mathbb{Z})^\times$.
+\begin{corrige}
+On a vu en question (2) que l'ordre multiplicatif d'un élément de
+$(\mathbb{Z}/65535\mathbb{Z})^\times$ divise toujours $256$, et on
+vient de voir en combinant (7) et (8) qu'il existe effectivement des
+éléments d'ordre $256$.
+\end{corrige}
 
 (10) Sans aucune hypothèse sur l'entier $x$, combien de valeurs
 distinctes peut prendre $x^{256}$ modulo $65\,535$ ?  (On ne demande
 pas de calculer ces valeurs, uniquement de calculer leur nombre,
 c'est-à-dire, si on préfère, le cardinal de l'image de $x \mapsto
 x^{256}$ sur $\mathbb{Z}/65535\mathbb{Z}$.)
+\begin{corrige}
+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}$.
+\end{corrige}
 
 %
 %
-- 
cgit v1.2.3