diff options
| author | david <david> | 2008-10-14 11:04:11 +0000 |
|---|---|---|
| committer | david <david> | 2008-10-14 11:04:11 +0000 |
| commit | 167de08e525536886ef4354e869932add44828b2 (patch) | |
| tree | 5687f7f56498506be477d5730773c9f43e11fe6a | |
| parent | 1f5844826dcfd73d2f78153df1cf2537333c1851 (diff) | |
| download | infmdi720-167de08e525536886ef4354e869932add44828b2.tar.gz infmdi720-167de08e525536886ef4354e869932add44828b2.tar.bz2 infmdi720-167de08e525536886ef4354e869932add44828b2.zip | |
More on Z/nZ, polynomials.
| -rw-r--r-- | rappels-maths.tex | 203 |
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. + % % % |