\documentclass[11pt]{amsart}
\usepackage{kb}
\usepackage[theo]{kbexo}

\begin{document}
\agregtitle{Lemme de Hensel} 

\section{Cas régulier}
Le texte est consacré à l'étude du résultat suivant, appelé «Lemme de
Hensel»:
\begin{lemme}
Soit $P$ un polynôme de $\ZM[X]$ et $p$ un nombre premier. Soit
$n$ un entier supérieur ou égal à $1$. On suppose que l'on dispose
d'un entier $x$ tel que
$$P(x)\equiv 0 \pmod{p^n}\quad \text{et}\quad P'(x)\not\equiv0 \pmod{p}.$$
Alors il existe un entier $y$ dans $\ZM$ tel que 
$$y\equiv x \pmod{p^n}\quad\text{et}\quad
P(y) \equiv0 \pmod{p^{2n}}.$$
De plus, cet entier est unique modulo $p^{2n}$.
On peut le prendre égal à $x-P(x)s$, où $s$ est tel que
$sP'(x)\equiv1 \pmod{p^n}$.
\end{lemme}

\begin{rem}
On reconnaît ici une version algébrique de la méthode de Newton, qui
s'écrirait $y=x-P(x)P'(x)^{-1}$.
\end{rem}

\begin{proof} On cherche l'entier $y$ sous la forme $x+tp^n$;
ce sera un antécédent ``bien choisi'' de $x$ par la surjection
canonique $\ZM/p^{2n}\ZM\twoheadrightarrow\ZM/p^n\ZM$.
On écrit la formule de Taylor à l'ordre $1$
$$P(x+tp^n)=P(x)+tp^nP'(x)+t^2p^{2n}R(x),$$
où $R\in\ZM[X]$.
Ainsi,
$$P(x+tp^n)\equiv P(x)+tp^nP'(x)\pmod{p^{2n}}.$$
Posons $P(x)=p^nP_0$, où $P_0\in\ZM$.
Alors $P(x+tp^n)\equiv0 \pmod{p^{2n}}$ si et seulement si
$$t\equiv-P'(x)^{-1}P_0 \pmod{p^n},$$
où $P'(x)^{-1}$ est l'inverse de $P'(x)$ modulo $p^n$,
qui existe d'après les hypothèses.
\end{proof}

\begin{rem}
On doit ici calculer à chaque étape un
inverse modulaire. On peut pour cela utiliser directement l'algorithme
d'Euclide étendu. On peut également utiliser le résultat suivant: 
\begin{lemme}
Si $v$ est un inverse de $u$ modulo $N$, alors $2v-uv^2$ est un inverse de
$u$ modulo $N^2$.
\end{lemme}
\begin{proof}
On peut le voir directement, en calculant $1-u(2v-uv^2)=(uv-1)^2$; on peut
aussi remarquer que c'est une conséquence du lemme de Hensel, pour le
polynôme $P(x)=ux-1$.
\end{proof}
\end{rem}

\begin{coro}
Si $p$ est un nombre premier impair et si $a$ est un entier premier à $p$
qui est reste quadratique modulo $p$, alors $a$ est reste quadratique modulo
$p^n$ pour tout $n\geq 1$.
\end{coro}

\begin{proof}
On considère le polynôme $P(X)=X^2-a$. L'équation à résoudre est donc
$$P(x)\equiv0\pmod{p^n}.$$
Soit $x$ un entier tel que $P(x)\equiv0$ mod $p$. Alors $P'(x)=2x$ est
premier à $p$. On peut alors utiliser le théorème précédent pour montrer par
récurrence l'existence d'une solution.
\end{proof}

\section{Cas singulier}

On ne suppose plus que $P'(x)\not\equiv0 \pmod{p}$. Le théorème ci-dessus
peut être adapté dans ce cadre plus général. Pour $x\in\ZM$, $x\neq 0$, on
appelle valuation de $x$ en $p$, notée $v_p(x)$, l'unique entier
$v$ tel que $p^v \mid x$, mais $p^{v+1}\nmid x$.

\begin{theo}
Soit $P\in\ZM[X]$ et $p$ un nombre premier. Soit $x$ un entier, tel que
$P'(x)\neq 0$ et soit $v = v_p(P'(x))$. Soit $n\geq2v+1$ un entier. Si
$y\equiv x$ mod $p^{n-v}$, alors $v_p(P'(y)) = v$ et $P(x)\equiv P(y) \pmod
{p^n}$.

Si de plus $P(x)\equiv 0 \pmod{p^n}$, alors il existe un entier $y$ dans
$\ZM$ tel que 
$$y\equiv x \pmod{p^{n-v}}  \quad \text{et}\quad
P(y)\equiv0 \pmod{p^{2(n-v)}}.$$
De plus, cet entier est unique modulo $p^{2n-3v}$.
On peut le prendre égal à
$$x-\frac{P(x)}{p^v}s,$$
où $s$ est tel que
$sP'(x)/p^v\equiv1 \pmod{p^{n-2v}}$.
\end{theo}

\begin{proof} La démonstration est analogue.
Posons $y=x+tp^{n-v}$; la formule de Taylor donne maintenant
\begin{align}\label{congruence}
  P(x+tp^{n-v}) &\equiv P(x)+tp^{n-v}P'(x) \pmod{p^{2(n-v)}},\\
  P'(x+tp^{n-v})& \equiv P'(x)+tp^{n-v}P''(x) \pmod{p^{2(n-v)}},
\end{align}
soit $P(y)\equiv P(x) \pmod{p^n}$ et $P'(y)\equiv P'(x) \pmod{p^{n-v}}$.
Comme $n\geq2v+1$, on en déduit que $P'(y)\equiv P'(x) \pmod{p^{v+1}}$, soit
$v_p(P'(y)) = v$.

Enfin, si $P(x)\equiv0 \pmod{p^n}$, on déduit de (\ref{congruence}) que
$$P(y)\equiv0 \pmod{p^{2(n-v)}}$$
si et seulement si
$$t\frac{P'(x)}{p^v}\equiv-\frac{P(x)}{p^n} \pmod{p^{n-2v}},$$
qui adment une unique solution $t$ modulo $p^{n-2v}$.
\end{proof}

\begin{coro}
Soit $a$ est un entier impair. Alors $a$ est reste quadratique modulo
$2^n$ pour tout entier $n\geq 3$ si et seulement si $a\equiv1 \pmod{8}$.
\end{coro}
\begin{proof}
L'entier $a$ est un carré modulo 8 si et seulement si $a\equiv1$ mod $8$. On
applique le théorème précédent au polynôme $P(X)=X^2-a$.
\end{proof}

\section{Racine carrée dans $\ZM/n\ZM$}

Si $n$ est une puissance d'un nombre premier, il reste à considérer le cas où
l'on rechercherait une racine carrée d'un entier $a$ divisible par $p$.

\begin{prop}
Soient $p$ un nombre premier, $\alpha$, $\beta$ deux entiers tels que
$0\leq\alpha<\beta$, et $a$ un entier premier à $p$. Alors $ap^{\alpha}$
est reste quadratique modulo $p^{\beta}$ si et seulement si $\alpha$ est
pair et $a$ est reste quadratique modulo $p^{\beta-\alpha}$.
\end{prop}

Si $n$ n'est pas une puissance d'un nombre premier, on se ramène à ce
cas en utilisant le théorème chinois.
\end{document}

\noindent{\bf Références.}

Joachim von zur Gathen, J\"urgen Gerhard~: Modern computer algebra.
Victor Shoup~: A computational introduction to number theory and
algebra.

Ivan Niven, Herbert S. Zuckerman, Hugh L Montgomery~:
An introduction to the theory of numbers.

Victor Shoup~: A computational introduction to number theory and
algebra.
