More on Z/nZ, polynomials.

1 files changed, 202 insertions, 1 deletions

diff --git a/rappels-maths.tex b/rappels-maths.tex
index 13cb112..ed3d328 100644
--- a/rappels-maths.tex
+++ b/rappels-maths.tex
@@ -40,7 +40,7 @@
 \maketitle
 {\footnotesize
 \begin{center}
-CVS: \verb=$Id: rappels-maths.tex,v 1.4 2008-10-07 10:04:22 david Exp $=
+CVS: \verb=$Id: rappels-maths.tex,v 1.5 2008-10-14 11:04:11 david Exp $=
 \end{center}
 \par}
 \pretolerance=10000
@@ -783,10 +783,211 @@ cyclique (auquel cas ses générateurs s'appellent éléments
 %
 \subsection{Exercices}
 
+\thingy Que vaut $10^{1000}$ modulo $7$ ?  (Réponse : $4$.)  Que vaut
+$10^{1000}$ modulo $6$ ?  (Réponse : $4$.)  Que vaut $10^{10^{1000}}$
+modulo $7$ ?  (Réponse : toujours $4$.)
+
+\thingy Quels sont les deux derniers chiffres (en base $10$) de
+$2^{1000!}$ ?
+
 \thingy Montrer que pour tout $a\in \mathbb{Z}$ on a $a^{1729} \equiv
 a \pmod{1729}$ (indication : $1729 = 7\times 13 \times 19$ ; utiliser
 le théorème chinois).
 
+\thingy À quoi est isomorphe le groupe
+$(\mathbb{Z}/56\mathbb{Z})^\times$ ?  Quel est le plus grand ordre
+possible d'un élément de ce groupe ?
+
+\thingy \textbf{Théorème de Wilson :} $p$ est premier si, et seulement
+si, $(p-1)! \equiv -1 \pmod{p}$.
+
+\thingy \textbf{Théorème de Wolstenholme :} si $p\geq 5$ est premier,
+le numérateur de
+$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1}$ est
+divisible par $p^2$.  (Indications : on pourra regrouper $\frac{1}{k}$
+et $\frac{1}{p-k}$, diviser par $p$, et chercher à étudier une
+congruence modulo $p$ ; on pourra faire usage du fait que
+$1^2+2^2+3^2+\cdots+(p-1)^2 = \frac{1}{6}p(p-1)(2p-1)$.)
+
+%
+\section{Polynômes}
+
+\subsection{Définition, structure d'anneau et degré}
+
+Soit $k$ un anneau commutatif quelconque, typiquement un corps
+(exemples importants : $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$ ou bien
+$\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$).
+
+Un \textbf{polynôme} en $t$ à coefficients dans $k$ est une somme
+formelle $f = a_0 + a_1 t + a_2 t^2 + \cdots$ avec $a_i \in k$ où
+\emph{seul un nombre fini} des $a_i$ est non nul (sinon on parle de
+\textbf{série formelle}).
+
+\textbf{Opérations :}
+\begin{itemize}
+\item Addition : terme à terme ($c_i = a_i+b_i$).
+\item Multiplication : « produit de Cauchy » en développant
+formellement ($c_i = \sum_{j=0}^{j=i} a_j b_{i-j}$).
+\end{itemize}
+
+Si $k$ est un anneau commutatif, alors $k[t]$ aussi.
+
+\textbf{Degré} d'un polynôme : $\deg f =$ le plus grand $i$ tel que
+$a_i \neq 0$ (le degré du polynôme nul est question de convention).
+On peut donc écrire un polynôme de degré $\leq N$ comme $a_0 + \cdots
++ a_N t^N$ ; si $a_N = 1$ on dit que $f$ est \textbf{unitaire}.
+
+\textbf{Propriétés} du degré :
+\begin{itemize}
+\item $\deg (f+g) \leq \max(\deg f, \deg g)$ (avec égalité si $\deg f
+\neq \deg g$)
+\item $\deg (fg) = \deg f + \deg g$ (dès que $k$ est \emph{intègre},
+  en particulier sur un corps)
+\end{itemize}
+
+Si $k$ est un anneau commutatif intègre, alors $k[t]$ aussi.
+
+Attention, $k[t]$ n'est jamais un corps !  (Car $t$ n'a pas d'inverse
+pour la multiplication.)
+
+\medbreak
+
+À souligner : \emph{analogie} importante entre les polyômes, notamment
+dans $\mathbb{F}_p[t]$, et l'écriture en base $p$ des entiers.
+Différence importante : pas de retenue pour les polynômes.
+
+Complexité des opérations : cf. entiers.
+
+%
+\subsection{Opérations spécifiques aux polynômes}
+
+\textbf{Évaluation} de polynômes : si $f = a_0 + \cdots + a_N t^N$ et
+$x \in A$ (une $k$-algèbre, par exemple $k$ ou $k[t]$), on définit
+$f(x) = a_0 + \cdots + a_N x^N$.
+
+Cas particulier : \textbf{composition} : si $g \in k[t]$, on note
+$f\circ g$ plutôt que $f(g)$.
+
+\medbreak
+\textbf{Dérivée :} si $f = a_0 + a_1 t + \cdots + a_N t^N$ alors $f' =
+a_1 + 2 a_2 t + \cdots + N a_N t^{N-1}$.
+
+\textbf{Attention :} On peut avoir $f'=0$ sans avoir $f$ constant
+(e.g., $f = t^p$ dans $\mathbb{F}_p[t]$).
+
+\textbf{Dérivées successives :} $f^{(i+1)} = (f^{(i)})'$ pour $i \in
+\mathbb{N}$.
+
+%
+\subsection{Polynôme interpolateur, formule de Taylor}
+
+Dans cette section, soit $k$ un \emph{corps} et $f \in k[t]$.
+
+\medskip
+
+Soient $a_0,\ldots,a_N
+\in k$ deux à deux distincts, où $N \geq \deg f$, et $b_i = f(a_i)$,
+alors
+\[
+f = \sum_{i=0}^N b_i \frac{\prod_{j\neq i}(t-a_j)}{\prod_{j\neq i}(a_i-a_j)}
+\]
+
+Permet de reconstruire un polynôme à partir de ses valeurs en
+suffisamment de points.
+
+\medbreak
+
+Si $N \geq \deg f$ et $N!$ n'est pas nul dans $k$, alors pour tout
+$a\in k$ :
+\[
+f = f(a) + (t-a)\,f'(a) + \frac{(t-a)^2}{2}\,f''(a) +
+\cdots + \frac{(t-a)^N}{N!}\,f^{(N)}(a)
+\]
+
+Permet de reconstruire un polynôme à partir de ses dérivées
+successives en un point.
+
+%
+\subsection{Division euclidienne de polynômes}
+
+Sauf mention du contraire, $k$ est maintenant un \textbf{corps}.
+
+\smallskip
+
+\textbf{Division euclidienne} analogue à celle des entiers :
+
+Si $f\in k[t]$ et $g\in k[t]$ est \emph{non nul},
+il existe un unique couple $(q,r)$ tel que :
+\begin{itemize}
+\item $q \in k[t]$,
+\item $r \in k[t]$ est (nul ou) de degré $\deg r < \deg g$ et
+\item $f = gq + r$.
+\end{itemize}
+
+\medbreak
+
+\textbf{Algorithme « naïf »} de division euclidienne : procéder par
+puissances \emph{décroissantes} :
+
+Soit $f = a_N t^N + \cdots + a_0$ et $g = b_D t^D + \cdots + b_0$ où
+$b_D \neq 0$ (donc $\deg g = D$) :
+\begin{itemize}
+\item si $N<D$ on renvoie $q = 0$ et $r = f$ ;
+\item sinon, on pose $c = a_N/b_D$, on définit $f^* = f - c t^{N-D}
+g$, donc $\deg(f^*) < N$, on applique l'algorithme pour diviser $f^*$
+par $g$, soit $f^* = gq^* + r$ et on a $f = gq + r$ où $q = c t^{N-D}
++ q^*$.
+\end{itemize}
+
+\smallbreak
+
+\textbf{Cas très important :} Le reste de la division euclidienne de
+$f$ par $t-a$ (où $a \in k$ est une constante) est $f(a)$.
+(Pourquoi ?)
+
+\smallbreak
+
+\textbf{Exercice :} Effectuer la division euclidienne de $t^7$ par $2
+t^3+1$ dans $\mathbb{F}_7[t]$.  (Réponse : $t^7 = (2 t^3+1) (4 t^4 + 5
+t) + 2 t$.)
+
+%
+\subsection{Arithmétique des polynômes}
+
+Relation de \textbf{divisibilité} : exactement analogue aux entiers.
+Les \textbf{unités} de $k[t]$ sont les éléments de $k^\times$
+(polynômes constants non nuls).
+
+Polynômes \textbf{irréductibles} : définition analogue aux nombres
+premiers.  On les choisira normalement \emph{unitaires} ; par
+convention, $0$ et les constantes ne sont pas irréductibles.  Les
+polynômes $t-a$ (unitaires de degré $1$) sont \emph{toujours}
+irréductibles.  Lorsque ce sont les seuls, le corps $k$ est dit
+\emph{algébriquement clos}.
+
+Le corps $\mathbb{C}$ est algébriquement clos.  Le corps $\mathbb{R}$
+ne l'est pas : les polynômes irréductibles sur $\mathbb{R}$ sont les
+$t-a$ et les $t^2-2bt+c$ où $b^2-c<0$.  Les corps finis (notamment
+$\mathbb{F}_p$ déjà vu) ne sont pas algébriquement clos (« encore
+  moins » que $\mathbb{R}$).
+
+\medbreak
+
+\textbf{Décomposition en facteurs irréductibles :} Écriture unique de
+tout $f\in k[t]$ non nul comme $c \prod_P P^{v_P(f)}$ où $c \in
+k^\times$ est le coefficient dominant de $f$ et $v_P(f)\in \mathbb{N}$
+pour tout $P$ irréductible (presque tous nuls).
+
+Cas où $k$ est algébriquement clos : tout $f \in k[t]$ non nul s'écrit
+de façon unique comme $c \prod_{a\in k} (t-a)^{v_a(f)}$ où $c \in
+k^\times$ est le coefficient dominant de $f$ et $v_a(f)\in \mathbb{N}$
+est l'ordre du zéro de $f$ en $a$.
+
+\medbreak
+
+PGCD, algorithme d'Euclide, relations de Bézout, Euclide étendu :
+exactement analogue aux entiers.
+
 %
 %
 %