summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2011-11-08 20:17:21 (GMT)
committerDavid A. Madore <david+git@madore.org>2011-11-08 20:17:21 (GMT)
commite9f19cdf29a745ce932a7902162fce013b07ff3b (patch)
treef4df5279f649d6a9bf6c32c5ea55d4ac77a027f1
parent6b06d2f8ddcfeb733cce560324fada129490eed0 (diff)
downloadinfmdi720-e9f19cdf29a745ce932a7902162fce013b07ff3b.zip
infmdi720-e9f19cdf29a745ce932a7902162fce013b07ff3b.tar.gz
infmdi720-e9f19cdf29a745ce932a7902162fce013b07ff3b.tar.bz2
Solution to second exercise.
-rw-r--r--exercices2b.tex137
1 files changed, 120 insertions, 17 deletions
diff --git a/exercices2b.tex b/exercices2b.tex
index 17f032c..2c9e39a 100644
--- a/exercices2b.tex
+++ b/exercices2b.tex
@@ -27,6 +27,8 @@
\newcommand{\signe}{\operatorname{signe}}
\newcommand{\tee}{\mathbin{\top}}
\newcommand{\Frob}{\operatorname{Frob}}
+\newcommand{\trace}{\operatorname{tr}}
+\newcommand{\Norm}{\operatorname{N}}
\newcommand{\dothis}{\leavevmode\hbox to0pt{\hskip-\parindent\HandRight{}\hskip0ptplus1fil}}
\DeclareUnicodeCharacter{00A0}{~}
%
@@ -258,57 +260,158 @@ Le résultat est donc $250 \otimes 250 = 2$.
Soit $q = p^d$ une puissance d'un nombre premier $p$.
(A) On appelle \emph{trace absolue} dans $\mathbb{F}_q$ (ou bien trace
-dans $\mathbb{F}_q$ sur $\mathbb{F}_p$) l'application $\mathrm{tr}
+dans $\mathbb{F}_q$ sur $\mathbb{F}_p$) l'application $\trace
\colon \mathbb{F}_q \to \mathbb{F}_q$ qui envoie un élément $x \in
\mathbb{F}_q$ sur la somme $\sum_{i=0}^{d-1} \Frob^i(x)$ des $d$
itérées consécutives du Frobenius, où comme d'habitude $\Frob^i(x)$
désigne $x^{p^i}$.
-(0) Montrer que $\mathrm{tr}(x+y) = \mathrm{tr}(x) + \mathrm{tr}(y)$
-pour tous $x,y \in \mathbb{F}_q$ et que $\mathrm{tr}(cx) =
-c\,\mathrm{tr}(x)$ si $c \in \mathbb{F}_p$ et $x \in \mathbb{F}_q$.
+(0) Montrer que $\trace(x+y) = \trace(x) + \trace(y)$
+pour tous $x,y \in \mathbb{F}_q$ et que $\trace(cx) =
+c\,\trace(x)$ si $c \in \mathbb{F}_p$ et $x \in \mathbb{F}_q$.
-(1) Montrer que $\mathrm{tr}$ prend en fait des valeurs dans
+\begin{corrige}
+On rappelle que $\Frob(x+y) = \Frob(x) + \Frob(y)$, et par conséquent
+$\Frob^i(x+y) = \Frob^i(x) + \Frob^i(y)$ pour n'importe quel $i$ ; a
+donc $\trace(x+y) = \sum_{i=0}^{d-1} \Frob^i(x+y) = \sum_{i=0}^{d-1}
+(\Frob^i(x) + \Frob^i(y)) = \sum_{i=0}^{d-1} \Frob^i(x) +
+\sum_{i=0}^{d-1} \Frob^i(y) = \trace(x) + \trace(y)$.
+
+Pour la seconde égalité, lorsque $c\in \mathbb{F}_p$ on a $\Frob(cx) =
+\Frob(c)\,\Frob(x) = c\,\Frob(x)$, et par conséquent $\Frob^i(cx) =
+c\,\Frob^i(x)$ pour tout $i$. On peut donc écrire $\trace(cx) =
+\sum_{i=0}^{d-1} \Frob^i(cx) = \sum_{i=0}^{d-1} (c \Frob^i(x)) = c
+\sum_{i=0}^{d-1} \Frob^i(x) = c\,\trace(x)$.
+\end{corrige}
+
+(1) Montrer que $\trace$ prend en fait des valeurs dans
$\mathbb{F}_p$. (On pourra pour cela chercher à calculer
-$\Frob(\mathrm{tr}(x))$.)
+$\Frob(\trace(x))$.)
+
+\begin{corrige}
+On a $\Frob(\trace(x)) = \Frob(\sum_{i=0}^{d-1} \Frob^i(x)) =
+\sum_{i=0}^{d-1} \Frob^{i+1}(x) = \sum_{i=1}^{d} \Frob^i(x)$. Or
+$\Frob^d(x) = x$ pour tout $x \in \mathbb{F}_q$ (où $q = p^d$) d'après
+le petit théorème de Fermat. La somme se réécrit donc bien comme
+$\sum_{i=0}^{d-1} \Frob^i(x) = \trace(x)$. Ceci montre que
+$\trace(x)$ est stable par le Frobenius, i.e., vérifie $\trace(x)^p =
+\trace(x)$, donc $\trace(x) \in \mathbb{F}_p$.
+\end{corrige}
-(2) Expliquer pourquoi $\mathrm{tr}(x)$ est un polynôme de $x$ (dont
+(2) Expliquer pourquoi $\trace(x)$ est un polynôme de $x$ (dont
on calculera le degré).
-(3) Montrer qu'il existe $x \in \mathbb{F}_q$ tel que $\mathrm{tr}(x)
+\begin{corrige}
+On a $\trace(x) = x + x^p + x^{p^2} + \cdots + x^{p^{d-1}}$, qui est
+manifestement un polynôme de degré $p^{d-1}$ (remarquons que ceci est
+strictement plus petit que $p^d$).
+\end{corrige}
+
+(3) Montrer qu'il existe $x \in \mathbb{F}_q$ tel que $\trace(x)
\neq 0$.
-(4) En déduire que $\mathrm{tr}$ prend toutes les valeurs
+\begin{corrige}
+Le polynôme $\trace$ étant de degré $p^{d-1} < p^d$ non identiquement
+nul, il ne peut pas s'annuler en les $p^d$ points de $\mathbb{F}_q$.
+Il existe donc $x \in \mathbb{F}_q$ tel que $\trace(x) \neq 0$.
+\end{corrige}
+
+(4) En déduire que $\trace$ prend toutes les valeurs
de $\mathbb{F}_p$ (i.e., qu'il s'agit d'une fonction surjective ; on
pourra par exemple commencer par montrer qu'elle prend la valeur $1$).
+\begin{corrige}
+Si $\trace(x) = c \neq 0$ (on vient de voir qu'un tel $x$ existe),
+comme $c \in \mathbb{F}_p$ d'après la question (1), on a
+$\trace(\frac{1}{c}x) = 1$. Si $a \in \mathbb{F}_p$ est quelconque,
+on a alors $\trace(\frac{a}{c}x) = a$. Donc $\trace$ prend bien
+toutes les valeurs de $\mathbb{F}_p$.
+\end{corrige}
+
\smallbreak
(B) On appelle \emph{norme absolue} dans $\mathbb{F}_q$ (ou bien norme
-dans $\mathbb{F}_q$ sur $\mathbb{F}_p$) l'application $\mathrm{N}
+dans $\mathbb{F}_q$ sur $\mathbb{F}_p$) l'application $\Norm
\colon \mathbb{F}_q \to \mathbb{F}_q$ qui envoie un élément $x \in
\mathbb{F}_q$ sur le produit $\prod_{i=0}^{d-1} \Frob^i(x)$ des $d$
itérées consécutives du Frobenius, où comme d'habitude $\Frob^i(x)$
désigne $x^{p^i}$.
-(0) Montrer que $\mathrm{N}(xy) = \mathrm{N}(x)\,\mathrm{N}(y)$ pour
+(0) Montrer que $\Norm(xy) = \Norm(x)\,\Norm(y)$ pour
tous $x,y \in \mathbb{F}_q$.
-(1) Montrer que $\mathrm{N}$ prend en fait des valeurs dans
+\begin{corrige}
+On rappelle que $\Frob(xy) = \Frob(x) \, \Frob(y)$, et par conséquent
+$\Frob^i(xy) = \Frob^i(x) \, \Frob^i(y)$ pour n'importe quel $i$ ; a
+donc $\Norm(xy) = \prod_{i=0}^{d-1} \Frob^i(xy) = \prod_{i=0}^{d-1}
+(\Frob^i(x) \, \Frob^i(y)) = \prod_{i=0}^{d-1} \Frob^i(x) \times
+\prod_{i=0}^{d-1} \Frob^i(y) = \Norm(x) \, \Norm(y)$.
+\end{corrige}
+
+(1) Montrer que $\Norm$ prend en fait des valeurs dans
$\mathbb{F}_p$. (On pourra pour cela chercher à calculer
-$\Frob(\mathrm{N}(x))$.)
+$\Frob(\Norm(x))$.)
+
+\begin{corrige}
+On a $\Frob(\Norm(x)) = \Frob(\prod_{i=0}^{d-1} \Frob^i(x)) =
+\prod_{i=0}^{d-1} \Frob^{i+1}(x) = \prod_{i=1}^{d} \Frob^i(x)$. Or
+$\Frob^d(x) = x$ pour tout $x \in \mathbb{F}_q$ (où $q = p^d$) d'après
+le petit théorème de Fermat. Le produit se réécrit donc bien comme
+$\prod_{i=0}^{d-1} \Frob^i(x) = \Norm(x)$. Ceci montre que $\Norm(x)$
+est stable par le Frobenius, i.e., vérifie $\Norm(x)^p = \Norm(x)$,
+donc $\Norm(x) \in \mathbb{F}_p$.
+\end{corrige}
-(2) Exprimer $\mathrm{N}(x)$ comme une certaine puissance de $x$ (dont
+(2) Exprimer $\Norm(x)$ comme une certaine puissance de $x$ (dont
on calculera l'exposant).
-(3) Montrer que $\mathrm{N}(x) = 0$ si et seulement si $x=0$.
+\begin{corrige}
+On a $\Norm(x) = x \times x^p \times x^{p^2} \times \cdots \times
+x^{p^{d-1}} = x^{1+p+p^2+\cdots+p^{d-1}}$. L'exposant est la somme
+d'une série géométrique et vaut $\frac{p^d-1}{p-1}$ (remarquer que
+ceci est un entier). On a peut donc écrire $\Norm(x) =
+x^{\frac{p^d-1}{p-1}}$.
+\end{corrige}
-(4) Montrer que $\mathrm{N}$ prend toutes les valeurs
+(3) Montrer que $\Norm(x) = 0$ si et seulement si $x=0$.
+
+\begin{corrige}
+Le fait que $\Norm(0) = 0$ est trivial.
+
+Dans un corps (ou plus généralement, un anneau intègre), un produit
+est nul si et seulement si un des facteurs est nul. Si on a
+$x^{\frac{p^d-1}{p-1}} = 0$, la seule possibilité est que $x=0$ (ou
+bien directement sur la définition : si $\prod_{i=0}^{d-1} \Frob^i(x)
+= 0$, c'est qu'un des facteurs $\Frob^i(x)$ est nul, ce qui en
+appliquant $\Frob^{d-i}$ implique $x=0$).
+\end{corrige}
+
+(4) Montrer que $\Norm$ prend toutes les valeurs
de $\mathbb{F}_p$ (i.e., qu'il s'agit d'une fonction surjective ; on
-pourra considérer $\mathrm{N}(g)$ pour $g$ un élément primitif de
+pourra considérer $\Norm(g)$ pour $g$ un élément primitif de
$\mathbb{F}_q^\times$, et montrer qu'il est d'ordre $p-1$ dans
$\mathbb{F}_p^\times$).
+\begin{corrige}
+Soit $g$ un élément primitif de $\mathbb{F}_q^\times$ : il est donc
+d'ordre exactement $q-1 = p^d-1$ (i.e., $g^j = 1$ si et seulement si
+$j$ est multiple de $p^d-1$). On a vu que $\Norm(g) =
+g^{\frac{p^d-1}{p-1}}$. On a donc $\Norm(g)^i = g^{\frac{p^d-1}{p-1}
+ i}$. On a donc $\Norm(g)^i = 1$ si et seulement si
+$\frac{p^d-1}{p-1} i$ est multiple de $p^d-1$, c'est-à-dire si et
+seulement si $\frac{p^d-1}{p-1} i = (p^d-1)k$ pour un certain
+entier $k$, ce qui signifie $\frac{i}{p-1} = k$ pour un certain
+entier $k$, autrement dit $i$ multiple de $p-1$. On a donc bien
+montré que $\Norm(g)$ est d'ordre $p-1$, i.e., primitif
+dans $\mathbb{F}_p^\times$.
+
+Si $a$ est un élément quelconque de $\mathbb{F}_p$, soit $a = 0$
+auquel cas il est la norme de $0$, soit $a \neq 0$, auquel cas on peut
+écrire $a = \Norm(g)^i$ pour un certain $i$ (puisqu'on vient de voir
+que $\Norm(g)$ est primitif), et du coup $a = \Norm(g^i)$. Donc
+$\Norm$ prend bien toutes les valeurs de $\mathbb{F}_p$.
+\end{corrige}
+
%
%
%