\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}
\usepackage{amssymb}
\newcommand{\R}{{\mathbb{R}}}
\newcommand{\C}{{\mathbb{C}}}
\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\N}{{\mathbb{N}}}
%\title{HP49}
%\date{}
\begin{document}
\textheight 23cm
\textwidth 16.5cm \columnsep 10pt \columnseprule 0pt
\begin{center}
{\Large \bf PGCD, r\'esultant et applications}
\end{center}

\section{Instructions compl\'ementaires (polyn\^omes)}
\begin{itemize}
\item \verb|interp| (MuPAD \verb|interpolate|)~: interpolation de Lagrange
\item \verb|convert(.,sqrfree)| 
(MuPAD \verb|polylib::sqrfree|)~:
d\'ecomposition en facteurs n'ayant pas de racine multiples
\item \verb|convert(.,parfrac)| 
(MuPAD \verb|polylib::partfrac|)~: d\'ecomposition en \'el\'ements simples
\item \verb|resultant| (MuPAD \verb|polylib::resultant|)~: 
calcule le r\'esultant de 2 polyn\^omes par rapport \`a une variable.
\end{itemize}

\section{Exercices et probl\`emes.}
\subsection{Exercices}
\begin{enumerate}
\item Pour quelles valeurs de $p$ le polyn\^ome $X^5+X^3-pX+1$ admet-il
une racine multiple?
\item R\'esoudre le syst\`eme en \'eliminant successivement les
variables gr\^ace au r\'esultant~:
\[
\left\{\begin{array}{rcl}
a^{3}+b^{3}+c^{3} & = & 8 \\
a^{2}+b^{2}+c^{2} & = & 6 \\
a+b+2c & = & 4
\end{array}\right.
\]
\item Donner le d\'etail des calculs avec B\'ezout de la d\'ecomposition
en \'el\'ements simples de~:
\[ \frac{1}{(x^2-1)^2(x+2)}\]
puis calculer le coefficient de $x^n$ du d\'eveloppement en s\'eries
enti\`eres de cette fraction en 0.
\item Calculer 
\[ \int \frac{1-x^2}{1+x^4} \ dx \]
en utilisant le r\'esultant pour calculer les logarithmes.
\item En utilisant uniquement l'instruction de calcul de PGCD
d\'eterminer la multiplicit\'e maximale d'un facteur irr\'eductible
de 
$x^{14}-x^{13}-14x^{12}+12x^{11}+78x^{10}-54x^9-224x^8+116x^7+361x^6-129x^5-330x^4+72x^3+160x^2-16x-32$
\end{enumerate}

\subsection{Bézout modulaire}
Soit $A$ et $B$ deux polynômes à coefficients entiers et premiers
entre eux. Soit $c \in \Z^* $ le résultant de $A$ et $B$,
on va calculer les polynômes $U$ et $V$ de l'identité de Bézout 
\begin{equation} \label{eq:bezout}
 A U + B V = c , \quad \mbox{deg}(U)<\mbox{deg}(B), \mbox{deg}(V)<\mbox{deg}(A)
\end{equation}
par une méthode modulaire.
\begin{enumerate}
\item Montrer, en utilisant les formules de Cramer,
que les coefficients de $U$ et $V$ sont des entiers de
valeur absolue inférieure ou égale à la borne de Hadamard $h$ de
la matrice de Sylvester de $A$ et $B$ (dont le déterminant est $c$,
le résultant de $A$ et $B$). Calculer $h$ en fonction
de la norme euclidienne de $A$, $B$ et de leurs degr\'es. 
\item On calcule $c \in \Z^*$ puis on
résoud (\ref{eq:bezout}) dans $\Z/p_i Z[X]$ pour
plusieurs nombres premiers $p_i$ (choisis si possible inférieurs 
à $\sqrt{2^{31}}$ pour des raisons d'efficacité), puis on calcule par le
théorème des restes chinois (\ref{eq:bezout}) 
dans $\Z/\prod p_i Z[X]$. Donner une minoration de 
$\prod_i p_i$ faisant intervenir $h$ qui permette de garantir
que l'écriture en représentation symétrique de (\ref{eq:bezout})
dans $\Z/\prod p_i Z[X]$ est identique \`a (\ref{eq:bezout}) dans $\Z[X]$.
\item Application~: résoudre de cette manière l'équation de
Bézout pour 
\[ A=(X+1)^4(X-3), \quad B=(X-1)^4(X+2)\] 
(vous pouvez utiliser
sans justifications l'instruction de calcul de r\'esultant,
des coefficients de Bézout dans $\Z/p_iZ[X]$ et 
de reste chinois de votre logiciel).
\item \'Ecrire une fonction mettant en oeuvre cet algorithme.
\item Que pensez-vous de l'intérêt de cet algorithme par rapport à
l'algorithme d'Euclide étendu dans $\Z[X]$?
\end{enumerate}

\subsection{G\'eom\'etrie et r\'esultants.}
On cherche une relation alg\'ebrique entre les coordonn\'ees de 4 points
$A,B,C,D$ qui traduise le fait que ces 4 points sont cocycliques. Cette
condition \'etant invariante par translation, on cherche une
relation entre les 6 coordonn\'ees des 3 vecteurs $v_1=(x_1,y_1)$, 
$v_2=(x_2,y_2)$ et $v_3=(x_3,y_3)$ 
d'origine $A$ et d'extr\'emit\'e $B$, $C$ et $D$.
On peut supposer quitte \`a translater que le centre du cercle est
l'origine, on a donc 5 param\`etres~: le rayon du cercle $R$ et les
4 angles des points sur le cercle $\theta_0$, $\theta_1$, $\theta_2$ et
$\theta_3$. La relation cherch\'ee va s'obtenir en \'eliminant les
5 param\`etres des expressions des 6 coordonn\'ees en fonction de
ces param\`etres.
\begin{enumerate}
\item Exprimer les 6 coordonn\'ees en fonction de 
$R$ et $a=\tan(\theta_0/2)$, $b=\tan(\theta_1/2)$, $c=\tan(\theta_2/2)$
et $d=\tan(\theta_3/2)$. On obtient ainsi 6 \'equations, par exemple les
deux premi\`eres sont de la forme
\[ x_1- F(R,a,b)= 0, \quad y_1- G(R,a,b)= 0 \]
o\`u $F$ et $G$ sont deux fractions rationnelles.
\item En r\'eduisant au m\^eme d\'enominateur, calculer 6 
polyn\^omes, fonction de
$x_1,y_1,x_2,y_2,x_3,y_3,R,a,b,c,d$, qui doivent s'annuler
pour que les points soient cocycliques
(Vous pouvez utiliser l'instruction \verb|numer| pour obtenir le
num\'erateur d'une fraction rationnelle).
\item \'Eliminer $b$ des polyn\^omes
contenant $x_1$ et $y_1$ et factoriser
le polyn\^ome obtenu, faire de m\^eme avec $c$, $x_2$ et $y_2$
et $d$, $x_3$ et $y_3$, en d\'eduire (en supposant que les points sont
tous distincts) 3 polyn\^omes en $x_1,y_1,x_2,y_2,x_3,y_3,R,a$ qui
s'annulent.
\item \'Eliminer $R$ et $a$, en d\'eduire la relation cherch\'ee.
\item V\'erifier que cette relation est \'equivalente \`a la nullit\'e
de la partie imaginaire du birapport des affixes $\alpha, \beta, \gamma,
\delta$ des 4 points~:
\[ \Im \left( \frac{\alpha-\beta}{\alpha-\gamma}
\frac{\delta-\gamma}{\delta-\beta} \right) = 0\]
\end{enumerate}


\end{document}