\documentclass{article}

\usepackage{lmodern}
\usepackage[T1]{fontenc}      
\usepackage[francais]{babel}

\usepackage{enumerate}
\usepackage{setspace}
\usepackage{soul}
\usepackage{amsthm, amsmath, amssymb}
%\usepackage{mathrsfs}
%\usepackage{graphicx}
%\usepackage{centernot}
%\usepackage[all]{xy}
%\usepackage{fullpage}

%\setlength\parindent{0em}

\newcommand{\RR}{\mathbb R}
\newcommand{\NN}{\mathbb N}
\newcommand{\ZZ}{\mathbb Z}
\newcommand{\CC}{\mathbb C}
\newcommand{\KK}{\mathbb K}
\newcommand{\FF}{\mathbb F}
\newcommand{\QQ}{\mathbb Q}
\newcommand{\MM}{\mathcal M}
\newcommand{\dt}{\,\mathrm d}
\newcommand{\transp}{\,{}^t\!}
\newcommand{\fnc}[5]{\begin{align*}#1#2&\longrightarrow#3\\#4&\longmapsto#5\end{align*}}

\title{123 -- Corps finis. Applications.}
\author{}
\date{2013 -- 2014}
\begin{document}
\maketitle
\section*{Question.}
Utiliser l'algorithme de Berlekamp pour factoriser $X^4+1$ sur $\FF_7$.

\section*{Réponse.}
On pose $P:=X^4+1$, alors $P'(X)=4X^3$ donc $P\land P'=1$, donc $P$ est sans facteur carré.

En notant \fnc{S_p:}{\FF_7[X]/(P)}{\FF_7[X]/(P)}{Q(X)}{Q(X^7),}
on doit calculer la matrice de $S_p-\text{id}$ dans la base $(1,X,X^2,X^3)$. On obtient
\[\begin{pmatrix}0&0&0&0\\0&-1&0&-1\\0&0&-2&0\\0&-1&0&-1\end{pmatrix}.\]
Le noyau de cette matrice est engendré par $1$ et $X^3-X$.

On calcule maintenant le pgcd de $X^3-X-3$ avec $P$. On trouve $X^2+3X+1$, ce qui constitue un des facteurs de $P$, on trouve l'autre en divisant $P$ par $X^2+3X+1$. On obtient
\[X^4+1=(X^2+3X+1)(X^2+4X+1).\]

\section*{Question.}
Est-ce que $2+\sqrt 3$ est un carré de $\FF_{49}$ ?

\section*{Réponse.}
On regarde d'abord si $\sqrt 3\in\FF_7$.
\[\left(\frac 37\right)=-\left(\frac 73\right)=-\left(\frac 13\right)=-1.\]
Donc $\sqrt 3\notin\FF_7$. On calcule alors la norme de $2+\sqrt 3$ :
\[N(2+\sqrt 3)=2^2-3=1,\]
qui est bien un carré de $\FF^7$. Donc $2+\sqrt 3$ est un carré de $\FF_{49}$.

\section*{Question.}
Trouver un générateur de $\FF_8$.

\section*{Réponse.}
$\FF_8^\times$ est d'ordre 7 donc tout élément différent de 0 et 1 est générateur.

\section*{Question}
Soit $N$ un nombre de Fermat : $N=2^{2^n}+1$, avec $n\ge 2$. Montrer que 5 n'est pas un carré modulo $N$ lorsque $N$ est premier.

\section*{Réponse.}
\[\left(\frac 5N\right)=\left(\frac N5\right)=\left(\frac{(-1)^{2^{n-1}}+1}5\right)=\left(\frac 25\right)=-1.\]

\section*{Question}
Que vaut $5^{N-1}$ mod $N$ lorsque $N$ est premier ? Et $5^{\frac{N-1}2}$ mod $N$ ?

\section*{Réponse.}
D'après le théorème de Fermat, $5^{N-1}\equiv 1[N]$ lorsque $N$ est premier. De plus, puisque 5 n'est pas un carré modulo $N$, $5^{\frac{N-1}2}\equiv -1[N]$.

\section*{Question.}
On suppose seulement que $5^{\frac{N-1}2}\equiv -1[N]$. En considérant un diviseur premier $p$ de $N$, montrer que $N$ est premier.

\section*{Réponse.}
On regarde l'ordre de $5$ dans $\FF_p$. On a $5^{N-1}\equiv 1[p]$, donc l'ordre de $5$ divise $N-1=2^{2^n}$, donc est une puissance de 2. Or $5^{\frac{N-1}2}\equiv -1[p]$ donc $5$ est d'ordre $N-1$. Or $5^{p-1}\equiv 1[p]$ par le théorème de Fermat, donc $N-1\mid p-1$, donc $N=p$ et $N$ est premier.

\section*{Question.}
On considère $\theta$ un générateur de $\FF_{p^2}^\times$, quel est l'ordre de $\theta$ dans $\FF_{p^2}^\times/\FF_p^\times$ ?

\section*{Réponse.}
L'ordre de $\FF_{p^2}^\times/\FF_p^\times$ est $\frac{p^2-1}{p-1}=p+1$, donc l'ordre de $\theta$ est $p+1$ car $\theta$ engendre le quotient.

\section*{Question.}
Soit $x\in\FF_{p^2}$, étudier les zéros de la suite $u_n:=x^n-\mathcal F(x^n)$, où $\mathcal F$ est le Frobenius.

\section*{Réponse.}
$u_n=0$ lorsque $x^n\in\FF_p$. Pour $x\in\FF_p$, alors $u_n=0$ pour tout $n$.

Réciproquement, si $u_n=0$ pour tout $n$, alors en particulier $x=\mathcal F(x)$ donc $x\in\FF_p$.

On pose $x:=\theta$, alors $u_n=0$ si et seulement si $\theta^n\in\FF_p$, c'est-à-dire si et seulement si $p+1$ divise $n$ par la question précédente. 
\end{document}