\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

\section{Le PGCD}
Les instructions arithm\'etiques sont en g\'en\'eral dans
la librairie standard. Toutefois certaines de ces instructions
sont dans la librairie \verb|numtheory| (en maple) ou \verb|numlib| 
(en MuPAD)
(utilisez \verb|?numtheory| ou \verb|?numlib| pour avoir la liste 
des fonctions de ces librairies), 
pour \'eviter de taper \verb|numlib::| ou \verb|numtheory::|
\`a chaque fois, on peut lancer la commande 
\verb|with(numtheory)| (maple) ou 
\verb|export(numlib);| (MuPAD). Avec \verb|xcas|,
on peut les trouver dans les menus
Math->Integer et Alg->Polynomes/Arit.polynomiale.

Pour travailler dans $\Z/n\Z[X]$~:
\begin{itemize}
\item avec Maple,
on utilise les formes inertes des instructions (qui renvoient l'instruction
non \'evalu\'ee), dont le nom est le m\^eme que le nom de commande
habituel mais pr\'ec\'ed\'e par une majuscule, puis on indique
\verb|mod n|, par exemple \verb|Gcd(P,Q) mod 11|.
\item avec MuPAD, on d\'esigne le type des coefficients par exemple par 
\verb|IntMod(13)| puis on construit des objets ayant des coefficients
de ce type (par exemple des polyn\^omes, cf. infra).
Pour travailler efficacement en MuPAD avec les polynômes, on utilisera
\verb|poly|, en pr\'ecisant le type de coefficients si on travaille
dans $\Z/n\Z$, par exemple \verb|poly(x^2+1,[x],IntMod(13))|. 
\item avec \verb|xcas| on utilise la notation \% comme en C, par
exemple {\tt gcd(P \% 3, Q \% 3)}.
\end{itemize}

\subsection{Entiers}
\begin{itemize}
\item \verb|gcd|~: PGCD
\item \verb|chrem| (en MuPAD \verb|numlib::ichrem|)~:
restes chinois (entier)
\item \verb|igcdex|: Bézout pour des entiers
\item \verb|genpoly| (en MuPAD \verb|numlib::genpoly|): 
crée un polynôme à partir de la
représentation $z$-adique d'un entier (utile pour le PGCD heuristique) 
\item \verb|iquo| et \verb|irem| quotient et reste de la division euclidienne
de deux entiers
\item \verb|isprime| test de (pseudo-)primalit\'e
\item \verb|mods|: reste euclidien symétrique
\item \verb|nextprime| et \verb|prevprime| 
(en MuPAD \verb|numlib::prevprime|): nombre premier suivant ou pr\'ec\'edent
\item \verb|divisors|
(en maple \verb|numtheory::divisors|, en MuPAD \verb|numlib::divisors|)~:
liste des diviseurs d'un entier
\end{itemize}

\subsection{Polyn\^omes}
\begin{itemize}
\item \verb|coeff| coefficient(s) d'un polyn\^ome, 
\item \verb|coeffs| liste des coefficients d'un polyn\^ome
(\`a d\'evelopper auparavant, en mupad on utilise \verb|coeff|)
\item \verb|content| contenu (pgcd des coefficients)
\item \verb|degree| degré
\item \verb|divide| division euclidienne, 
\item \verb|gcd| PGCD,
\item \verb|gcdex| B\'ezout, 
\item \verb|icontent|: contenu entier pour un polyn\^ome \`a plusieurs
variables
\item \verb|indets|: 
liste des noms de variables d'une expression
\item \verb|lcoeff|: coefficient dominant d'un polyn\^ome
\item \verb|ldegree|: valuation
\item (MuPAD) \verb|multcoeffs| 
multiplie les coefficients d'un polynômes
\item (MuPAD) \verb|pdivide| pseudo-division
\item (MuPAD) \verb|poly(expr,[var],coeff)| crée un polynôme à partir de
l'expression symbolique \verb|expr| par rapport une variable ou
à une liste de variables \verb|var|, on peut indiquer dans quel anneau 
vivent les coefficients (par exemple dans $\Z/13\Z$ avec comme 3ème argument
\verb|IntMod(13)|)
\item \verb|primpart|: partie primitive d'un polyn\^ome
\item \verb|quo|, \verb|rem| (xcas et Maple) quotient et reste euclidien
(en MuPAD utiliser les options Quo et Rem de \verb|divide|)
\item \verb|tcoeff|: coefficient de plus bas degr\'e d'un polyn\^ome
\end{itemize}

\subsection{Exercices}
\begin{enumerate}

\item Calculez le pgcd de $x^{202}+x^{101}+1$
et sa dérivée modulo 3 et modulo 5. Conclusion?

\item $P=51x^3-35x^2+39x-115$ et $Q=17x^4-23x^3+34x^2+39x-115$.
Calculez le pgcd de $P$ et $Q$ modulo 5, 7 et 11. En déduire
le pgcd de $P$ et $Q$ par le théorème des restes chinois. Pourquoi
ne doit-on pas essayer modulo 17?

\item \'Ecrire un programme qui d\'etermine le degr\'e probable
du pgcd de 2 polyn\^omes en une variable en utilisant le pgcd modulaire 
(on consid\`ere le degr\'e probable d\'etermin\'e lorsqu'on trouve
deux nombres premiers r\'ealisant le minimum des degr\'es trouv\'es)

\item Détaillez l'algorithme du PGCD heuristique pour les
polynômes  $P=(x+1)^7-(x-1)^6$ et sa dérivée. Comparez avec l'algorithme
d'Euclide naïf.

\item \'Ecrire un programme mettant en oeuvre le pgcd heuristique
pour des polyn\^omes \`a une variable.

\item On veut comprendre comment un logiciel de calcul formel calcule
\[ \int \frac{x^6+2}{(x^3+1)^2} \ dx \]
On se ramène d'abord à une fraction propre (num\'erateur $N$ de degr\'e 
inf\'erieur au d\'enominateur),
Soit $P=X^3+1$, calculez le PGCD de $P$ et $P'$, puis
deux polyn\^omes $U$ et $V$ tels que:
\[ N=UP+VP' \]
On d\'ecompose alors l'int\'egrale en deux morceaux~:\\
\[ \int \frac{N}{P^2}=\int \frac{U}{P}  + \int V \frac{P'}{P^2}  \]
Faites une int\'egration par parties sur le deuxi\`eme terme
et en d\'eduire la valeur de l'int\'egrale du d\'epart.

\item \'Ecrire un programme qui d\'etermine le degr\'e probable du PGCD 
par rapport \`a toutes les
variables de 2 polyn\^ome \`a plusieurs variables
en utilisant l'\'evaluation en toutes les variables
sauf une.

\item Calculer le pgcd par une m\'ethode modulaire de
$(xy-x+1)(xy+x^2+1)$ et $(xy-x-y)(xy-x+1)$

\item Que se passe-t-il lorsqu'on ex\'ecute l'algorithme de Yun
dans $\Z/n\Z$?

%\item 
%Retrouvez les racines rationnelles de $(2x-999)\*(3x-1000)\*(5x-1001)$
%par une m\'ethode modulaire/p-adique (avec $p=11$)

\end{enumerate}
\end{document}