% \documentclass[landscape,12pt,a4paper]{article}
% \textwidth 26cm
% \evensidemargin 0mm
% \oddsidemargin 0mm
% \topmargin 0mm
\documentclass{article}
\topmargin-1cm
\oddsidemargin-2.4mm
\textwidth17.5cm
\textheight23cm
\parskip=3pt
\parindent=0pt

\usepackage{graphicx}
\usepackage[francais]{babel}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{times}
\usepackage{ifpdf}
\usepackage{makeidx}
\ifpdf
 \usepackage[pdftex,colorlinks]{hyperref}
\else
 \usepackage[ps2pdf,breaklinks=true,colorlinks=true,linkcolor=red,citecolor=green]{hyperref}
 \fi

\newtheorem{rem}{Remarque}
\newcommand{\R}{{\mathbb{R}}}
\newcommand{\C}{{\mathbb{C}}}
\newcommand{\Q}{{\mathbb{Q}}}
\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\N}{{\mathbb{N}}}
\newcommand{\faux}{$\square\;$}
\newcommand{\vrai}{$\square\;$}
%\newcommand{\vrai}{$\boxtimes\;$}
\newcommand{\itemf}{\item\faux}
\newcommand{\itemv}{\item\vrai}

\newtheorem{exo}{Exercice}[section]


\begin{document}

\noindent M1 Alg\`ebre effective \hfill Résultant, applications \hfill UGA

{\bf Exercice 1, polynôme à paramètre}\\
Pour quelles valeurs de $p$ le polyn\^ome $X^5+X^3-pX+1$ admet-il
une racine multiple~? Factoriser le polyn\^ome pour cette valeur de $p$.

{\bf Exercice 2, système polynomial}\\
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.
\]
et en calculant le PGCD des équations obtenues par substitution.

{\bf Exercice 3, intersection de courbes}\\
D\'eterminer l'intersection de $xy=4$ et $ y^2=(x-3)(x^2-16)$,
rep\'esenter graphiquement les courbes. Discuter la multiplicit\'e
et le nombre d'intersections.
M\^eme question pour $(x-2)^2+y^2=4$ et $y^2=(x-3)(x^2-16)$.

{\bf Exercice 4, primitive}\\
Déterminer 
\[ \int \frac{1-x^2}{1+x^4} \ dx \]
en utilisant le r\'esultant pour calculer les termes logarithmiques.

{\bf Exercice 5, extension algébrique}\\
Montrer que $\mathbb{Q}[\sqrt{2},\sqrt[3]{3}]$ est une extension
de degré 6 de $\mathbb{Q}$ en déterminant le polynôme minimal
de $\gamma=\sqrt{2}+\sqrt[3]{3}$ par un calcul de résultant et en
vérifiant que ce polynôme est irréductible.
Exprimer $\sqrt{2}$ puis $\sqrt[3]{3}$ en fonction de $\gamma$.

{\bf Exercice 6, paramétrisation rationnelle de coniques}\\
Si on connait un point d'une conique, on peut paramétrer rationnellement
la conique en cherchant la 2ème intersection d'une droite de pente $t$ 
et passant par ce point avec la conique.\\
Le faire pour 
$$x^2+4y^2+2xy=4, \quad x^2-3y^2+2xy=4$$
qui passent par le point $(2,0)$.
Vérifier qu'on retrouve bien les équations cartésiennes en éliminant
$t$ sur les équations paramétriques obtenues.

{\bf Exercice 7, Bézout modulaire}\\
Soient $A$ et $B$ des polynômes à coefficients entiers et $U$ et $V$
les polynômes de l'identité
de Bézout
$$ A=(X+1)^4(X-3), \quad B=(X-1)^4(X+2), \quad AU+BV=\mbox{resultant}(A,B)$$ 
\begin{enumerate}
\item Donner une majoration à priori des coefficients de $U$ et $V$.
\item Combien de nombres premiers de taille 31 bits sont-ils nécessaires
pour reconstruire $U$ et $V$ à partir du calcul de $U$ et $V$
dans $\mathbb{Z}/p\mathbb{Z}[X]$~?
\item Que peut-on dire du coût de cet algorithme en fonction de $A$ et $B$
quelconques~?
\end{enumerate}

%% {\bf Problème 5, décalage entier entre racines}\\
%% Soit $P$ un polynôme à coefficients entiers sans racines multiples. 
%% On dira que $P$ a la propriété $\mathcal{I}$ si
%% deux des racines de $P$ sont d\'ecal\'ees d'un entier. 
%% En d'autres termes, si $r_1,...,r_n$ d\'esignent
%% les racines complexes distinctes de $P$, $P$ poss\`ede la
%% propri\'et\'e $\mathcal{I}$
%% s'il existe 
%% au moins un entier parmi les différences $r_i-r_j$ pour $i \neq j$. 
%% \begin{enumerate}
%% \item Soit
%% \[ R(t)=\mbox{resultant}_x(P(x),P(x+t)) \]
%% Montrer que $R$ est à coefficients entiers.
%% Montrer que la propriété $\mathcal{I}$ est équivalente à
%% la propriété ``$R$ possède une racine entière non nulle''.
%% On va maintenant construire un algorithme d\'eterminant les racines
%% enti\`eres du polyn\^ome $R$.
%% \item Apr\`es division de $R$ par une puissance de $t$, on peut
%% supposer que $R$ a un coefficient constant non nul. Apr\`es division de
%% $R$ par son contenu, on peut aussi supposer
%% que le contenu de $R$ est 1. En effectuant ensuite une factorisation
%% square-free de $R$, on peut se ramener au cas o\`u $R$ et $R'$ sont
%% premiers entre eux.
%% Soit $a$ une racine de $R$.
%% \begin{enumerate}
%% \item Donner une majoration de $|a|$ 
%% en fonction du coefficient constant de $R$.
%% \item Soit $p$ un nombre premier ne divisant pas le coefficient dominant
%% de $R$ et tel que $R$ et $R'$ soient premiers entre eux modulo $p$. 
%% On peut calculer $a$ à partir d'une racine
%% de $R$ modulo $p$ en la ``remontant'' modulo $p^k$ pour $k$
%% assez grand (algorithme p-adique). Pour quelle valeur de $k$ peut-on
%% reconstruire toutes les racines enti\`eres de $R$~? 
%% \item Comparer l'algorithme ci-dessus avec les algorithmes suivants~:
%% la factorisation de $R$ sur $\mathbb{Z}$, 
%% la recherche num\'erique des racines complexes de $R$,
%% la recherche des racines enti\`eres de $R$ parmi les diviseurs 
%% entiers du coefficient constant de $R$ et leurs oppos\'es.
%% \end{enumerate}
%% \item Une fois les racines entières de $R$ connues, comment
%% peut-on en déduire les facteurs de $P$ dont les racines diffèrent
%% de cet(ces) entier(s)?
%% \item Soit 
%% \[P(x)=x^6+9x^5+29x^4+41x^3+37 x^2+59x+31\]
%% Montrer que $P$ a la propriété $\mathcal{I}$. Calculer
%% la ou les racines entières de $R$ et donner la factorisation
%% correspondante de $P$. 
%% \item \'Ecrire un programme qui effectue cet algorithme sur un
%% polyn\^ome quelconque. On pourra utiliser la fonction 
%% \verb|rationalroot| de Xcas pour d\'eterminer les racines
%% enti\`eres de $R$.
%% \item Application~: on cherche \`a calculer
%% \begin{equation} \label{eq}
%%  \sum_{k=1}^n \frac{-9x^2-27x-30}{P(x)}
%% \end{equation}
%% D\'ecomposer cette fraction
%% en \'el\'ements simples (donner le d\'etail des calculs en utilisant
%% la factorisation pr\'ec\'edente et l'identit\'e de Bezout 
%% \verb|abcuv| en Xcas). 
%% \item Calculer la somme pr\'ec\'edente (\(\ref{eq}\)).
%% On pourra remarquer que pour $k$ entier strictement positif,
%% $\frac{1}{f(x+k)}-\frac{1}{f(x)}$
%% s'exprime comme une somme de diff\'erences  
%% $\frac{1}{f(x+j+1)}-\frac{1}{f(x+j)}$.
%% \item \'Ecrire un programme effectuant ce calcul avec une fraction
%% quelconque, lorsque cela est possible.
%% \end{enumerate}


{\bf TP exercice 1, courbe param\'etrique d\'ependant d'un param\`etre~:}\\
On consid\`ere la courbe $C_m$ d\'ependant du r\'eel $m$~:
$$ x(t)=\frac{t+m}{t^2+1+m^2}, \quad y(t)=\frac{t^2}{t-m}$$
\begin{enumerate}
\item Repr\'esenter la courbe pour quelques valeurs de $m$ (on pourra
utiliser dans un niveau de g\'eom\'etrie, le menu Edit, Ajouter un
param\`etre pour cr\'eer un curseur repr\'esentant $m$, puis 
utiliser la commande \verb|plotparam|). 
\item Donner une \'equation cart\'esienne de $C_m$ en éliminant $t$
\item D\'eterminer les valeurs de $m$ pour lesquelles
la courbe admet un point singulier (i.e. $x'=y'=0$), 
repr\'esenter le graphe dans ce(s) cas.
\end{enumerate}

{\bf TP Exercice 2, racines complexes, résultant, Sturm}\\
Pour localiser les racines complexes $z=x+iy$ d'un polynôme $P(z)$,
on peut écrire $P(z)=P(x+iy)=R(x,y)+iI(x,y)$ avec $R$ et $I$ les parties
réelles et imaginaires de $P$, vus comme des polynômes en deux variables.
Les parties réelles (resp. imaginaires) des racines sont alors
racine réelles du résultant de $R$ et $I$ par rapport à $y$ (resp. $x$)
et on peut appliquer une méthode de localisation réelle, par exemple Sturm.
Tester par exemple avec $P(z)=z^3+z+1$ puis avec un polynôme
de degré quelques dizaines. Que peut-on dire du cout de cette 
méthode en fonction du degré $n$ du polynôme $P$~?

{\bf TP Exercice 3, calcul du résultant modulaire par Euclide}\\
On se donne un nombre premier $p$ et
deux polynômes $P,Q \in \mathbb{Z}/p\mathbb{Z}[X]$.
\'Ecrire un programme calculant le résultant de $P$ et $Q$ en utilisant 
l'algorithme d'Euclide~: si $R$ est le reste de $P$ par $Q$,
on calcule le résultant de $Q$ et $R$ et on multiplie par
$\pm q^d \pmod p$, où $q$ est le coefficient dominant de $Q$, $d$ la
différence entre le degré de $P$ et de $R$ et le signe $\pm$ est -
si $P$ et $Q$ sont de degré pairs.\\
Comment peut-on se servir de ce programme pour calculer le résultant
de deux polynômes de $\mathbb{Q}[X]$~? Comparer le temps de calcul
avec le déterminant de la matrice de Sylvester.

{\bf TP Exercice 4, calcul du résultant par interpolation}\\
On se donne 
deux polynômes $P,Q \in \mathbb{Q}[X,Y]$, où la variable $X$ est
la variable principale et la variable $Y$ est vue comme un paramètre.
En utilisant l'interpolation polynomiale et le calcul du résultant en
une variable, programmer le calcul du résultant de $P$ et de $Q$.

{\bf TP Exercice 5, Bézout modulaire}\\
Programmer l'algorithme de l'exercice 7.

{\bf TP Exercice 6, points cocycliques}\\
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 On paramètre les 4 points du cercle par $R\frac{1+ia}{1-ia}$,
$R\frac{1+ib}{1-ib}$, ...
Exprimer les 6 coordonn\'ees $x_1,x_2,x_3,y_1,y_2,y_3$ en fonction de 
$R$ et $a,b,c,d$. 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}
