<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[10pt,a4paper]{article}
\usepackage{t1enc}
\usepackage{amsmath,amssymb,amsthm,amscd,graphicx}
\pagestyle{empty}
\usepackage[frenchb]{babel}
\usepackage[utf8]{inputenc}

\newcommand{\N}{\mathbb{N}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\def\ds{\displaystyle}
\newcommand{\mathframe}[1]{\fbox{$#1$}}
\def\ima{\mathrm{Im}}

\topmargin-2.8cm
\oddsidemargin-2.4mm
\textwidth17.5cm
\textheight27cm
\parskip=3pt
\parindent=0pt

\pagestyle{empty}

\def\soluce#1{} % n'affiche pas les indications de solutions

\begin{document}



\noindent
M1 alg\`ebre effective  \hfill PGCD et applications \hfill UGA


\section{TD}
{\bf Exercice 1}
Calculez le pgcd de $x^{202}+x^{101}+1$
et sa dÃ©rivÃ©e modulo 3 et modulo 5. Conclusion?

{\bf Exercice 2} Soit
$P=51x^3-35x^2+39x-115$ et $Q=17x^4-23x^3+34x^2+39x-115$ dans $\mathbb{Q}[X]$.
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. Que se
passe-t-il modulo 17?


{\bf Exercice 3}
DÃ©terminer le PGCD de $x^4+x+1$ et $x^3+7x^2+7x+1$ dans $\mathbb{Q}[X]$.

{\bf Exercice 4}
Soit $P$ le polyn\^ome $x^4+13x+1$. $P$ est-il squarefree
modulo $p$ pour $p=7$~? $p=11$~? $P$ est-il squarefree dans 
$\mathbb{Q}[X]$~?

{\bf Exercice 5}
D\'eterminer la factorisation square-free de $x^7+x^6+x+1$ modulo 2.

{\bf Exercice 6}
Factoriser $x^5-x^4+x^3-x^2-1$ modulo 3 et modulo 5 en utilisant
uniquement le PGCD. En dÃ©duire
la factorisation sur $\mathbb{Q}[X]$.

%% \item TD RÃ©duction du calcul d'une intÃ©grale de fractions rationnelles
%% \[ \int \frac{x^6+2}{(x^3+1)^2} \ dx \]
%% On se ramÃ¨ne d'abord Ã&nbsp; 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.

\section{TP}

{\bf Exercice 1}
\'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)


{\bf Exercice 2}
\'Ecrire une fonction renvoyant 1 si un polyn\^ome est squarefree
modulo $p$. Prolongement: renvoyer une factorisation partielle du polyn\^ome
(algorithme de Musser ou de Yun pour une factorisation squarefree).

{\bf Exercice 3}
\'Ecrire une fonction testant si un polyn\^ome est irr\'eductible
modulo $p$. Utiliser cette fonction pour construire un polyn\^ome
irr\'eductible de degr\'e $n$ modulo $p$ 
puis une repr\'esentation du corps fini GF$(p,n)$

{\bf Exercice 4}
D\'eterminer les degrÃ©s des facteurs de $x^7+x^5+2x^4+x^3+x^2+2x+1$ modulo 5
et 7 (sans utiliser la commande factor). Quelle est la factorisation
sur $\Q$ de ce polyn\^ome~?

{\bf Exercice 5}
\'Ecrire une fonction renvoyant la factorisation ddf (distinct degree
factorization) d'un polyn\^ome squarefree modulo $p$. Tester sur
l'exemple de l'exercice pr\'ec\'edent.

{\bf Exercice 6}
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 \in \mathbb{Q}[x]$
RÃ©aliser ensuite une factorisation partielle de ce polynÃ´me.

{\bf Exercice 7}
Impl\'ementer l'algorithme de H\"orner pour \'evaluer un polynome
en un point. 
%Modifier l'algorithme pour calculer le quotient. 
\'Ecrire
une fonction qui renvoie les facteurs de degr\'e 1
d'un polyn\^ome $P$ dans $\Z/p$ pour $p$ premier (pas trop grand)
en testant.\\
AmÃ©lioration~: on pourra calculer $x^p \pmod{ p,P}$ puis
le pgcd de $x^p-x$ et $P$ modulo $p$ pour diminuer
le degrÃ© du polynÃ´me Ã&nbsp; tester.

\end{document}
</pre></body></html>