\documentclass[12pt,a4paper]{article}
\usepackage{multicol}
\usepackage[french]{babel}
\newfont{\mini}{cmssi10 scaled 480}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\euro{\mbox{\textsf{C}\kern -2.33em{\raise0.24ex\vbox{\small\it =}}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\fin{\nolinebreak \raise-0.1em\hbox{$\Box$}}
\def\stackunder#1#2{\mathrel{\mathop{#2}\limits_{#1}}}
\def\dual{ ^{\rm v}}
\def\bidual{ ^{\rm vv}}
\def\primedual{ ^{\prime \rm v}}
\def\ideal{{\cal J}}
\def\LL{{\cal L}}
\def\max{{\cal M}}
\def\quot#1#2{\mbox{\raise 0.1cm\hbox{$#1$}{\big /}\raise -0.1cm\hbox{$#2$}}}
\def\danger{{\Large \bf
    $\bigtriangleup$}\kern-0.32cm\raise0.05cm\hbox{\small
    !}\kern0.32cm\lower0.05cm\hbox{}}
%%%%%%%
\newlength{\largeurtmp}
\def\rela{\settoheight{\largeurtmp}{Z}{\rm Z} \kern -0.6\largeurtmp
  \raise 0.05cm\hbox{\tiny{\it /}}\kern 0.6\largeurtmp}
\def\petitrela{\settoheight{\largeurtmp}{Z}{\rm Z} \kern -0.4\largeurtmp
  \raise 0.05cm\hbox{\tiny{\it /}}\kern 0.4\largeurtmp}
\def\petitcomplex{{
    \settoheight{\largeurtmp}{$_C$}{\rm C}\kern -\largeurtmp
    \rule{0.25pt}{1.3\largeurtmp}\kern \largeurtmp}}
\def\complex{{
    \settoheight{\largeurtmp}{Q}{\rm C}\kern -0.66\largeurtmp
    \rule{0.25pt}{0.9\largeurtmp}\kern 0.66\largeurtmp}}
\def\ratio{{
    \settoheight{\largeurtmp}{C}{\rm Q}\kern -0.75\largeurtmp
    \rule{0.25pt}{0.9\largeurtmp}\kern 0.75\largeurtmp}}
\def\petitratio{{
    \settoheight{\largeurtmp}{C}{\rm Q}\kern -0.6\largeurtmp
    \rule{0.25pt}{0.6\largeurtmp}\kern 0.6\largeurtmp}}
\newcommand{\proj}{{\rm I} \! {\rm P}}
\newcommand{\reel}{{\rm I} \! {\rm R}}
\newcommand{\Fp}{{\rm I} \! {\rm F}_p}
\newcommand{\nat}{{\rm I} \! {\rm N}}
%%%%%%%%%%%%%%%Debut de macros de fiches d'exos
%%les macros sont \exo, \qu, \quskip \squ \qusqu \qusquskip
\newcounter{exo}
\newcounter{question}
\newlength{\lng}
\newcounter{sousquestion}
\setcounter{exo}{1}
\def\exo{

  \bigskip
  \noindent{\bf Exercice
    \Roman{exo}:}\addtocounter{exo}{1}\setcounter{question}{0}\nopagebreak 

  }
\def\exotitre#1{

  \bigskip
  \noindent{\bf Exercice
    \Roman{exo}: #1}\addtocounter{exo}{1}\setcounter{question}{0}\nopagebreak 

  }
\def\qu{

  \addtocounter{question}{1}\arabic{question})
  \setcounter{sousquestion}{1} }
\def\quskip{

  \bigskip
  \qu}
\def\squ{

  \settowidth{\lng}{\arabic{question})
  }\hspace{\the\lng}\alph{sousquestion}) \addtocounter{sousquestion}{1}} 
\def\qusqu{\qu\nopagebreak \vskip -1\baselineskip \squ}
\def\qusquskip{\quskip\nopagebreak \vskip -1\baselineskip \squ}

%%reference pour exos,squ \`a placer avant la question, qu est a placer apres
\def\labelexo#1{\expandafter\edef\csname refexo#1\endcsname {\Roman{exo}}}
\def\refexo#1{\csname refexo#1\endcsname}
\def\labelqu#1{\expandafter\edef\csname refqu#1\endcsname {\arabic{question})}}
\def\refqu#1{\csname refqu#1\endcsname}
\def\labelsqu#1{\expandafter\edef\csname refsqu#1\endcsname
  {\arabic{question}\alph{sousquestion})}} 
\def\refsqu#1{\csname refsqu#1\endcsname}  

%%%%%%%%%%fin de macros fiche d'exos
%%macros taille page
\newlength{\elargir}
\setlength{\elargir}{2.5cm}
\addtolength{\leftmargin}{-\elargir}
%%\addtolength{\hoffset}{-\elargir}
\addtolength{\oddsidemargin}{-\elargir}
\addtolength{\evensidemargin}{-\elargir}
\addtolength{\elargir}{\elargir}
\addtolength{\textwidth}{\elargir}
\addtolength{\textheight}{13\baselineskip}
\topmargin=-5\baselineskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        
\everymath={\displaystyle}
\begin{document}
\noindent{\bf Universit\'e de Paris 7 \hfill \framebox{\Large \bf
    \hspace{ 1cm} TP17 Polyn\^omes 2 \hspace{1cm}}\hfill   agreg 2008 (F.Han\footnote{http://www.math.jussieu.fr/$\sim$han/agreg})}\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\code#1{{\tt #1}}
%% 
\columnsep 0.7cm
\begin{multicols}{2}
% restart;maple_mode(1);cas_setup(0,0,0,1,0,1e-10,10,[1,50,0,25],0,0,0); #radians,pas de cmplx, pas de  Sqrt
\exotitre{sous r\'esultant}
(Cf Cohen, ou Knuth, ou doc xcas)
Soit $A$ un anneau factoriel, et $k$ son corps des fractions. Pour deux \'el\'ements
de  $A[x]$, $P$ et $Q$, on souhaite effectuer l'algorithme d'Euclide pour $P$ et
$Q$ en restant dans $A[x]$. Il nous faut pour cel\`a multiplier \`a chaque \'etape les
deux polyn\^omes par une constante.
\qu Cr\'eer une proc\'edure \code{pseudiv(P,Q)} de pseudo division, qui retourne 
$P$ si $\deg P< \deg Q$  et le reste de $l(Q)^{\deg P -  \deg Q +1}.P$ par $Q$
sinon. (o\`u $l(Q)$ d\'esigne le coefficient dominant de $Q$).
%!s!<c>
%a priori il faudra degree(P)-degree(Q)+1 divisions par le coeff dominant de Q,
%ce qui explique le coefficient multiplicateur.
%!s!
% pseudiv:=(P,Q)->rem(lcoeff(Q)^(max(degree(P)-degree(Q)+1,0))*P,Q);
\qu Cr\'eer une proc\'edure \code{eucl1(P,Q)} qui affiche les \'etapes d'un
algorithme d'euclide   qui utilise la pseudo-division \`a la place de la
division. Illustrer\footnote{On pourra \'eventuellement regarder la documentation
  de xcas sur le sous-r\'esultant} le probl\`eme de croissance des coefficients avec
un calcul de pgcd d'un polyn\^ome et de sa d\'eriv\'ee.
%!s!<p>
%eucl1:=proc(P,Q)
%local R1,R2,R3;
%R1:=P;R2:=Q;
%while (R2 <>0) do R3:=pseudiv(R1,R2);
%print(R1);
%R1:=R2;R2:=R3;od;
%R1;
%end;
%!s!
%P:=(x+1)^7-(x-1)^6;
%eucl1(P,diff(P,x));
\qu Calculer le contenu des polyn\^omes \`a chaque \'etape pour simplifier de mani\`ere
optimale r\'esoudrait le probl\`eme de la taille des coefficients, mais serait en
revanche couteux. Nous allons d\'ecrire ici un algorithme avec, \`a chaque \'etape,
une simplification connue \`a priori. (ie la simplification n'est pas optimale, mais on
simplifie  par un coefficient connu d'avance).

On commence d'abord par calculer les contenus de $P$ et $Q$, et l'on sauve $d$
le pgcd de ces contenus. Nous allons donner un algorithme qui retourne un PGCD
$D$ de $P$ et $Q$  tel que le contenu de $D$ soit $d$. Ainsi lorsque $P$ et $Q$
sont des polyn\^omes constants, $D$ co\"\i ncidera avec le PGCD de $P$ et $Q$ en tant
qu'\'el\'ements de $A$.

On simplifie ensuite $P$ et $Q$ par leur contenus, et l'on initialise des
variables auxilaires $g$ et $h$ \`a $1$.

Ensuite, on pose $\delta=\deg P -\deg Q$ (que l'on suppose positif d\`es le
d\'epart), et l'on note $R$ le reste de la pseudo 
division de $P$ par $Q$. Tant que $R$ 
n'est pas constant, on remplace $P$ par $Q$ et $Q$ par $\frac{R}{g.h^\delta}$,
$g$ par le coefficient dominant de $P$ et $h$ par $h^{1-\delta}g^\delta$, et
l'on recalcule $\delta$ et $R$.

Lorsque $R$ est constant non nul on retourne $d$ et si $R$ est nul on retourne
$d.Q/cont(Q)$.
\squ Cr\'eer une proc\'edure \code{subpgcd} utilisant cet algorithme.
% !s!<p>
% subpgcd:=proc(P,Q)
% local R1,R2,R3,g,d,delta,p,q;
% p:=content(P);q:=content(Q);d:=igcd(p,q);
% if degree(P)< degree(Q)
% then R1:=normal(Q/q);R2:=normal(P/p);
% else R1:=normal(P/p);R2:=normal(Q/q);
%  fi;
%  R3:=pseudiv(R1,R2);delta:=degree(R1)-degree(R2);
% h:=1;g:=1;
%  while degree(R3)>0 do
% print(R1);
%  R1:=R2; R2:=normal(R3/g/h^delta);
%  g:=lcoeff(R1);h:=g^delta/h^(delta-1);
%  R3:=pseudiv(R1,R2);delta:=degree(R1)-degree(R2);
%  od;
%  if R3==0 then normal(d*R2/content(R2)) else d fi;
%  end;
% !s!
\squ Illustrer la taille des coefficients en imprimant tous les restes sur un
bon exemple.
%subpgcd(P,diff(P,x));
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exotitre{Expos\'e-R\'evision}
Exposer l'algorithme de Gauss-Bareiss, expliquer le parall\`ele avec l'exercice
pr\'ec\'edent.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\end{multicols}

\end{document}

\qu Etudier les d\'eterminants $(u_{i+j})_{0\leq i,j\leq n}$ pour les
d\'eveloppement en s\'erie de:
\begin{center}
${1\over {x+{1 \over {2.x+5+{1 \over {x^2+x+1+{1\over
              {x}}}}}}}}$ et de${1\over {x+{1 \over {x+1+{1 \over {2.x+3+{1\over
{x^2+2+{1\over x}}}}}}}}}$
\end{center}
%%Quel est le lien entre l'annulation d'un de ces d\'eterminants et les degr\'es dans
%%le d\'eveloppement en fraction continue?
