From 2c0256cb192f4579ba7ae9c4d57886a5af93c043 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Mon, 24 Oct 2011 15:39:14 +0200 Subject: Re-encode as utf-8. --- rappels-maths.tex | 1543 +++++++++++++++++++++++++++-------------------------- 1 file changed, 772 insertions(+), 771 deletions(-) (limited to 'rappels-maths.tex') diff --git a/rappels-maths.tex b/rappels-maths.tex index 50168cf..8df213a 100644 --- a/rappels-maths.tex +++ b/rappels-maths.tex @@ -1,8 +1,8 @@ %% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? \documentclass[12pt]{article} \usepackage[francais]{babel} +\usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} -\usepackage[latin1]{inputenc} \usepackage{times} % A tribute to the worthy AMS: \usepackage{amsmath} @@ -18,10 +18,10 @@ \newtheorem{comcnt}{Tout}[subsection] \newcommand\thingy{% \refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} } -\newtheorem{defn}[comcnt]{Définition} +\newtheorem{defn}[comcnt]{Définition} \newtheorem{prop}[comcnt]{Proposition} \newtheorem{lem}[comcnt]{Lemme} -\newtheorem{thm}[comcnt]{Théorème} +\newtheorem{thm}[comcnt]{Théorème} \newtheorem{cor}[comcnt]{Corollaire} \newtheorem{rmk}[comcnt]{Remarque} \newtheorem{exmps}[comcnt]{Exemples} @@ -33,6 +33,7 @@ \newcommand{\tee}{\mathbin{\top}} \newcommand{\Frob}{\operatorname{Frob}} \renewcommand{\qedsymbol}{\smiley} +\DeclareUnicodeCharacter{00A0}{~} % % % @@ -60,185 +61,185 @@ On appelle $\mathbb{Z}=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$ l'ensemble des entiers relatifs. Il a pour sous-ensemble $\mathbb{N} = \{0,1,2,3,\ldots\}$ l'ensemble des entiers naturels (ou positifs). -Sur $\mathbb{Z}$ on a les opérations : $+$ (addition) et $\times$ -(multiplication) ; et les éléments remarquables : $0$, $1$. Ces -données vérifient les propriétés suivantes : +Sur $\mathbb{Z}$ on a les opérations : $+$ (addition) et $\times$ +(multiplication) ; et les éléments remarquables : $0$, $1$. Ces +données vérifient les propriétés suivantes : \begin{enumerate} -\item Associativité de l'addition : $x+(y+z) = (x+y)+z$ -\item Neutralité de zéro pour l'addition : $0+x = x+0 = x$ -\item Existence d'opposés (=symétriques pour l'addition) : (pour - chaque $x$, il existe un élément noté $-x$ tel que) $x + (-x) = (-x) +\item Associativité de l'addition : $x+(y+z) = (x+y)+z$ +\item Neutralité de zéro pour l'addition : $0+x = x+0 = x$ +\item Existence d'opposés (=symétriques pour l'addition) : (pour + chaque $x$, il existe un élément noté $-x$ tel que) $x + (-x) = (-x) + x = 0$ -\item Commutativité de l'addition : $y+x = x+y$ -\item Distributivité de la multiplication sur l'addition : $x(y+z) = +\item Commutativité de l'addition : $y+x = x+y$ +\item Distributivité de la multiplication sur l'addition : $x(y+z) = xy + xz$ et $(x+y)z=xz+yz$ -\item Associativité de la multiplication : $x(yz) = (xy)z$ -\item Neutralité de un pour la multiplication : $1x = x1 = x$ -\item Commutativité de la multiplication : $yx = xy$ +\item Associativité de la multiplication : $x(yz) = (xy)z$ +\item Neutralité de un pour la multiplication : $1x = x1 = x$ +\item Commutativité de la multiplication : $yx = xy$ \end{enumerate} -Les trois premières propriétés traduisent le fait que $\mathbb{Z}$ est -un \emph{groupe} pour l'addition ; les quatre premières, que -$\mathbb{Z}$ est un \emph{groupe abélien} pour l'addition ; les sept -premières propriétés traduisent le fait que $\mathbb{Z}$ est un -\emph{anneau} ; les huit propriétés réunies traduisent le fait que +Les trois premières propriétés traduisent le fait que $\mathbb{Z}$ est +un \emph{groupe} pour l'addition ; les quatre premières, que +$\mathbb{Z}$ est un \emph{groupe abélien} pour l'addition ; les sept +premières propriétés traduisent le fait que $\mathbb{Z}$ est un +\emph{anneau} ; les huit propriétés réunies traduisent le fait que $\mathbb{Z}$ est un \textbf{anneau commutatif}. -Mieux : c'est un \emph{anneau intègre} : si $uv=0$ alors $u=0$ ou -$v=0$ (la réciproque est vraie dans n'importe quel anneau : $0x = x0 = +Mieux : c'est un \emph{anneau intègre} : si $uv=0$ alors $u=0$ ou +$v=0$ (la réciproque est vraie dans n'importe quel anneau : $0x = x0 = 0$). -Éléments inversibles : un \textbf{inversible} ou une \textbf{unité} -(dans un anneau commutatif) est un élément $x$ tel qu'il existe $y$ +Éléments inversibles : un \textbf{inversible} ou une \textbf{unité} +(dans un anneau commutatif) est un élément $x$ tel qu'il existe $y$ tel que $xy = 1$. Dans $\mathbb{Z}$, les inversibles sont $1$ et $-1$. -On a aussi sur $\mathbb{Z}$ une relation d'ordre : c'est-à-dire une -relation réflexive (on a toujours $x\leq x$), antisymétrique (si +On a aussi sur $\mathbb{Z}$ une relation d'ordre : c'est-à-dire une +relation réflexive (on a toujours $x\leq x$), antisymétrique (si $x\leq y$ et $y\leq x$ alors $x=y$) et transitive (si $x\leq y$ et $y\leq z$ alors $x\leq z$). % -\subsection{Écriture $b$-adique} +\subsection{Écriture $b$-adique} -Si $b\geq 2$ est un entier naturel, tout entier naturel $A$ s'écrit de -façon unique $A = \sum_{i=0}^{+\infty} a_i b^i$ avec $0\leq a_i1$, il y a toujours un nombre premier $p$ tel que $x < p -< 2x$ (\v Ceby\v sëv : « postulat de Bertrand », démontré en 1850). -De façon équivalente : si $p$ est premier, alors le nombre premier qui -le suit immédiatement est $<2p$. - -Le nombre $\pi(x)$ de nombres premiers $\leq x$ est équivalent à -$\frac{x}{\ln x}$ lorsque $x\to +\infty$ (Hadamard \& de la Vallée -Poussin : « théorème des nombres premiers », démontré en 1896). -Moralement : la probabilité qu'un nombre de $n$ bits aléatoire soit +< 2x$ (\v Ceby\v sëv : « postulat de Bertrand », démontré en 1850). +De façon équivalente : si $p$ est premier, alors le nombre premier qui +le suit immédiatement est $<2p$. + +Le nombre $\pi(x)$ de nombres premiers $\leq x$ est équivalent à +$\frac{x}{\ln x}$ lorsque $x\to +\infty$ (Hadamard \& de la Vallée +Poussin : « théorème des nombres premiers », démontré en 1896). +Moralement : la probabilité qu'un nombre de $n$ bits aléatoire soit premier est environ $\frac{1}{n\,\ln 2}$. -Beaucoup de questions ouvertes. Par exemple : Conjecture des nombres -premiers jumeaux : existe-t-il une infinité de nombres premiers $p$ +Beaucoup de questions ouvertes. Par exemple : Conjecture des nombres +premiers jumeaux : existe-t-il une infinité de nombres premiers $p$ tels que $p+2$ soit aussi premier (tels que $3$, $5$, $11$, $17$, -$29$, $41$, $59$, $71$...) ? +$29$, $41$, $59$, $71$...) ? \smallbreak -\textbf{Lemme de Gauß :} pour $p$ premier, si $p$ divise $ab$ alors -$p$ divise $a$ ou $p$ divise $b$. +\textbf{Lemme de Gauß :} pour $p$ premier, si $p$ divise $ab$ alors +$p$ divise $a$ ou $p$ divise $b$. % -\subsection{Décomposition en facteurs premiers} +\subsection{Décomposition en facteurs premiers} -Pour tout entier $n$ \emph{non nul}, il existe une écriture -\emph{unique} (à l'ordre près) de $n$ comme produit d'une \emph{unité} -($1$ ou $-1$) et de nombres premiers : en regroupant les facteurs -premiers $p$, +Pour tout entier $n$ \emph{non nul}, il existe une écriture +\emph{unique} (à l'ordre près) de $n$ comme produit d'une \emph{unité} +($1$ ou $-1$) et de nombres premiers : en regroupant les facteurs +premiers $p$, \[ n = u\, 2^{v_2(n)} \, 3^{v_3(n)} \cdots p^{v_p(n)}\cdots \] Ici, $v_p(n)$ (un entier naturel) est l'exposant de la plus grande -puissance de $p$ qui divise $n$ : on l'appelle \emph{valuation -$p$-adique} de $n$. Presque tous ces nombres sont nuls, ce qui permet +puissance de $p$ qui divise $n$ : on l'appelle \emph{valuation +$p$-adique} de $n$. Presque tous ces nombres sont nuls, ce qui permet de donner un sens au produit infini. Dire que $b|a$ signifie $v_p(b) -\leq v_p(a)$ pour tout $p$. +\leq v_p(a)$ pour tout $p$. -Quant à $u$, c'est simplement le signe de $n$. +Quant à $u$, c'est simplement le signe de $n$. -Exemple : $7920 = 2^4\times 3^2\times 5\times 11$, c'est-à-dire que +Exemple : $7920 = 2^4\times 3^2\times 5\times 11$, c'est-à-dire que $v_2(7920)=4$, $v_3(7920)=2$, $v_5(7920)=1$, $v_7(7920)=0$, $v_{11}(7920)=1$, et $v_p(7920)=0$ pour n'importe quel nombre premier $p\geq 13$. % -\subsection{Remarques sur la complexité} +\subsection{Remarques sur la complexité} Toujours pour des nombres de $n$ bits. -\textbf{Tests de primalité :} \emph{polynomiaux}. Un test polynomial -\emph{déterministe} est connu depuis seulement récemment -(Agrawal-Kayal-Saxena), démontrablement en $O(n^{12})$, sans doute -meilleur ($O(n^3)$ ?). En pratique, des tests probabilistes sont -suffisants et plus efficaces (p.e., Miller-Rabin « pratiquement » en -$O(n^2)$) éventuellement complétés par des certificats de primalité +\textbf{Tests de primalité :} \emph{polynomiaux}. Un test polynomial +\emph{déterministe} est connu depuis seulement récemment +(Agrawal-Kayal-Saxena), démontrablement en $O(n^{12})$, sans doute +meilleur ($O(n^3)$ ?). En pratique, des tests probabilistes sont +suffisants et plus efficaces (p.e., Miller-Rabin « pratiquement » en +$O(n^2)$) éventuellement complétés par des certificats de primalité (p.e., test d'Atkin). -\textbf{Algorithmes de factorisation :} \emph{lents}. Font appel à -des résultats difficiles de théorie algébrique et analytique des -nombres. La meilleure méthode connue (« méthode du crible général de -corps de nombres ») a une complexité « attendue » (et heuristique) en +\textbf{Algorithmes de factorisation :} \emph{lents}. Font appel à +des résultats difficiles de théorie algébrique et analytique des +nombres. La meilleure méthode connue (« méthode du crible général de +corps de nombres ») a une complexité « attendue » (et heuristique) en $O(e^{n^{1/3}\,(\log n)^{2/3}\,(\textrm{cte}+o(1))})$ (avec $\textrm{cte} \approx 2$). -On ne pourra donc pas envisager d'utiliser la décomposition en +On ne pourra donc pas envisager d'utiliser la décomposition en facteurs premiers pour calculer les pgcd. % @@ -246,21 +247,21 @@ facteurs premiers pour calculer les pgcd. Si $n$ est un entier et $p$ un nombre premier, $v_p(n)$ est l'exposant de la plus grande puissance de $p$ qui divise $n$. Si $a/b$ est un -rationnel, on pose $v_p(a/b) = v_p(a)-v_p(b)$ (ne dépend pas de la -représentation $a/b$ choisie). Par convention, $v_p(0) = +\infty$. +rationnel, on pose $v_p(a/b) = v_p(a)-v_p(b)$ (ne dépend pas de la +représentation $a/b$ choisie). Par convention, $v_p(0) = +\infty$. -Quelle est la valuation $2$-adique de $192$ ? $3$-adique ? -$5$-adique ? Quelles sont les valuations $p$-adiques de -$-\frac{24}{11}$, pour tous les $p$ possibles ? +Quelle est la valuation $2$-adique de $192$ ? $3$-adique ? +$5$-adique ? Quelles sont les valuations $p$-adiques de +$-\frac{24}{11}$, pour tous les $p$ possibles ? -Propriétés de $v_p$ : produit (cf. lemme de Gauß) : on a $v_p(xy) = -v_p(x) + v_p(y)$ ; inégalité sur la somme : on a $v_p(x+y) \geq -\min(v_p(x), v_p(y))$ avec égalité si $v_p(x) \neq v_p(y)$. Dire que +Propriétés de $v_p$ : produit (cf. lemme de Gauß) : on a $v_p(xy) = +v_p(x) + v_p(y)$ ; inégalité sur la somme : on a $v_p(x+y) \geq +\min(v_p(x), v_p(y))$ avec égalité si $v_p(x) \neq v_p(y)$. Dire que $x \in \mathbb{Q}$ est entier signifie exactement $v_p(x) \geq 0$ pour -tout $p$. +tout $p$. -Remarque : calculer $v_p(n)$, pour un $n$ donné et un $p$ premier -donné, est facile. Ce qui est difficile dans la décomposition en +Remarque : calculer $v_p(n)$, pour un $n$ donné et un $p$ premier +donné, est facile. Ce qui est difficile dans la décomposition en facteurs premiers, c'est de trouver tous les $p$ tels que $v_p(n) > 0$ (ou en fait, en trouver \emph{un}). @@ -268,88 +269,88 @@ facteurs premiers, c'est de trouver tous les $p$ tels que $v_p(n) > 0$ \subsection{Division euclidienne} Si $a$ est un entier relatif et $b$ un entier naturel \emph{non nul}, -il existe un unique couple $(q,r)$ tel que : +il existe un unique couple $(q,r)$ tel que : \begin{itemize} \item $q$ est un entier relatif, \item $r$ est un entier naturel tel que $0\leq r2$), $\varphi(m)$ est toujours \emph{pair} (sauf pour $m=2$). Si $p$ est premier, alors tous les nombres entre $1$ et $p-1$ sont -premiers avec $p$ : $(\mathbb{Z}/p\mathbb{Z})^\times = \{\bar +premiers avec $p$ : $(\mathbb{Z}/p\mathbb{Z})^\times = \{\bar 1,\ldots, \overline{p-1}\}$ (et notamment $\varphi(p) = p-1$). Tous -les éléments de $\mathbb{Z}/p\mathbb{Z}$ sont inversibles sauf $\bar -0$ : on dit que l'anneau $\mathbb{Z}/p\mathbb{Z}$ est un \emph{corps} -et on le note $\mathbb{F}_p$. +les éléments de $\mathbb{Z}/p\mathbb{Z}$ sont inversibles sauf $\bar +0$ : on dit que l'anneau $\mathbb{Z}/p\mathbb{Z}$ est un \emph{corps} +et on le note $\mathbb{F}_p$. % -\subsection{Théorème chinois} +\subsection{Théorème chinois} Si $m$ et $n$ sont deux naturels non nuls \textbf{premiers entre eux}, -considérons l'application dont les composantes sont les deux -surjections canoniques : +considérons l'application dont les composantes sont les deux +surjections canoniques : \[ \mathbb{Z}/(mn)\mathbb{Z} \to (\mathbb{Z}/m\mathbb{Z}) \times (\mathbb{Z}/n\mathbb{Z}) \] Autrement dit, il s'agit de l'application qui envoie un entier $z$ -modulo $mn$ sur sa classe modulo $m$ et sa classe modulo $n$. +modulo $mn$ sur sa classe modulo $m$ et sa classe modulo $n$. Il s'agit d'un \emph{morphisme d'anneaux} (car les surjections -canoniques en sont !) : +canoniques en sont !) : \begin{itemize} \item il est injectif car un entier multiple de $m$ et de $n$ -est multiple de $mn$ (lemme de Gauß), -\item il est surjectif car les cardinaux coïncident ($mn$ au départ et -à l'arrivée), +est multiple de $mn$ (lemme de Gauß), +\item il est surjectif car les cardinaux coïncident ($mn$ au départ et +à l'arrivée), \end{itemize} c'est donc un \textbf{isomorphisme}. @@ -699,17 +700,17 @@ $(\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/5\mathbb{Z})$... \smallbreak -Concrètement, le théorème chinois signifie : lorsque $m$ et $n$ sont -premiers entre eux, se donner un entier modulo $mn$ revient au même -que se donner cet entier modulo $m$ et modulo $n$ séparément (et, de +Concrètement, le théorème chinois signifie : lorsque $m$ et $n$ sont +premiers entre eux, se donner un entier modulo $mn$ revient au même +que se donner cet entier modulo $m$ et modulo $n$ séparément (et, de plus, toutes les combinaisons d'une classe modulo $m$ et d'une classe -modulo $n$ sont possibles pour une unique classe modulo $mn$). +modulo $n$ sont possibles pour une unique classe modulo $mn$). % -\subsection{Théorème chinois explicite} +\subsection{Théorème chinois explicite} -Si on a une relation de Bézout $um+vn=1$, alors l'isomorphisme chinois -a pour réciproque +Si on a une relation de Bézout $um+vn=1$, alors l'isomorphisme chinois +a pour réciproque \[ \begin{array}{c} (\mathbb{Z}/m\mathbb{Z}) \times (\mathbb{Z}/n\mathbb{Z}) \to @@ -718,36 +719,36 @@ a pour r \end{array} \] -(Remarque : dans cette expression, on peut se contenter de calculer -$uy$ modulo $n$ avant de le multiplier par $m$, et de même $vx$ -modulo $m$ avant de le multiplier par $n$, ce qui est parfois plus -efficace que de faire tout le calcul modulo $mn$.) +(Remarque : dans cette expression, on peut se contenter de calculer +$uy$ modulo $n$ avant de le multiplier par $m$, et de même $vx$ +modulo $m$ avant de le multiplier par $n$, ce qui est parfois plus +efficace que de faire tout le calcul modulo $mn$.) -Exemple : trouver le nombre entre $0$ et $100$ congru à $9$ -modulo $11$ et à $3$ modulo $13$. (Relation de Bézout : $6\times 11 - -5 \times 13 = 1$ ; ensuite, $6 \times 11 \times 3 - 5 \times 13 \times +Exemple : trouver le nombre entre $0$ et $100$ congru à $9$ +modulo $11$ et à $3$ modulo $13$. (Relation de Bézout : $6\times 11 - +5 \times 13 = 1$ ; ensuite, $6 \times 11 \times 3 - 5 \times 13 \times 9 \equiv 5\times 11 - 1\times 13 \equiv 42 \pmod{11\times 13}$.) \medskip -Généralisations du théorème chinois : +Généralisations du théorème chinois : \begin{itemize} -\item Si $m$ et $n$ ne sont pas premiers entre eux, toute donnée d'une +\item Si $m$ et $n$ ne sont pas premiers entre eux, toute donnée d'une classe $x$ modulo $m$ et d'une classe $y$ modulo $n$ ne permet pas - forcément de retrouver une classe modulo $mn$ (il faut, et il - suffit, pour cela, que $x$ et $y$ soient « compatibles », - c'est-à-dire congrus modulo $d = \pgcd(m,n)$). Lorsque $x$ et $y$ + forcément de retrouver une classe modulo $mn$ (il faut, et il + suffit, pour cela, que $x$ et $y$ soient « compatibles », + c'est-à-dire congrus modulo $d = \pgcd(m,n)$). Lorsque $x$ et $y$ sont compatibles, alors on retrouve une unique classe modulo $\ppcm(m,n)$ (pour faire le calcul en pratique, diviser les nombres - $m,n$ par $d',d''$ tels que $d'd''=d$ pour se ramener à deux nombres + $m,n$ par $d',d''$ tels que $d'd''=d$ pour se ramener à deux nombres $m/d'$ et $n/d''$ premiers entre eux). -\item Si $m_1,\ldots,m_k$ sont premiers entre eux \emph{deux à deux}, - alors la donnée d'une classe modulo le produit $m_1\cdots m_k$ - équivaut à la donnée de classes modulo chacun des $m_i$ (pour faire +\item Si $m_1,\ldots,m_k$ sont premiers entre eux \emph{deux à deux}, + alors la donnée d'une classe modulo le produit $m_1\cdots m_k$ + équivaut à la donnée de classes modulo chacun des $m_i$ (pour faire le calcul en pratique, on utilise les classes modulo $m_1,m_2$ pour trouver une classe modulo $m_1 m_2$, puis celle-ci et la classe - modulo $m_3$ déterminent une classe modulo $m_1 m_2 m_3$, etc.). -\item En combinant ces deux généralisations : connaissant la classe + modulo $m_3$ déterminent une classe modulo $m_1 m_2 m_3$, etc.). +\item En combinant ces deux généralisations : connaissant la classe d'un entier modulo $m_1,\ldots,m_k$, on peut retrouver sa classe modulo $\ppcm(m_1,\ldots,m_k)$. \end{itemize} @@ -756,785 +757,785 @@ G \subsection{Calcul de l'indicatrice d'Euler} Si $m$ et $n$ (naturels non nuls) sont premiers entre eux, par le -théorème chinois on a $(\mathbb{Z}/(mn)\mathbb{Z})^\times \cong +théorème chinois on a $(\mathbb{Z}/(mn)\mathbb{Z})^\times \cong (\mathbb{Z}/m\mathbb{Z})^\times \times (\mathbb{Z}/n\mathbb{Z})^\times$, donc \[ \varphi(mn) = \varphi(m)\,\varphi(n) \] -Si $p$ est premier alors $\varphi(p^r) = (p-1)\,p^{r-1}$ (car être -premier avec $p^r$ équivaut à être premier à $p$, et c'est le cas de -$p-1$ entiers sur $p$). +Si $p$ est premier alors $\varphi(p^r) = (p-1)\,p^{r-1}$ (car être +premier avec $p^r$ équivaut à être premier à $p$, et c'est le cas de +$p-1$ entiers sur $p$). -On en déduit : +On en déduit : \[ \varphi(n) = n\,\prod_{p|n}\left(1-\frac{1}{p}\right) \] -où $p$ parcourt les premiers divisant $n$. +où $p$ parcourt les premiers divisant $n$. -Exemple : $\varphi(63) = \frac{2}{3}\times\frac{6}{7}\times 63 = 36$. +Exemple : $\varphi(63) = \frac{2}{3}\times\frac{6}{7}\times 63 = 36$. -(Intuitivement : parmi les $n$ entiers de $0$ à $n-1$, pour chacun des +(Intuitivement : parmi les $n$ entiers de $0$ à $n-1$, pour chacun des nombres premiers $p$ divisant $n$, il y a une proportion -$\frac{p-1}{p}$ des nombres qui ne sont pas multiples de $p$, et -toutes ces propriétés sont indépendantes --- c'est essentiellement le -théorème chinois --- donc la proportion des nombres qui ne sont -multiples d'aucun des $p$ divisant $n$ est le produit des +$\frac{p-1}{p}$ des nombres qui ne sont pas multiples de $p$, et +toutes ces propriétés sont indépendantes --- c'est essentiellement le +théorème chinois --- donc la proportion des nombres qui ne sont +multiples d'aucun des $p$ divisant $n$ est le produit des $\frac{p-1}{p}$.) -\textbf{Algorithmiquement :} \emph{lent} en général (demande de -connaître la d.f.p.). +\textbf{Algorithmiquement :} \emph{lent} en général (demande de +connaître la d.f.p.). % -\subsection{Notions de théorie des groupes} +\subsection{Notions de théorie des groupes} -Un \textbf{groupe} est un ensemble $G$ muni d'une opération binaire -$\star$ (c'est-à-dire une application $G\times G \to G$ dont on note -$g \star g'$ l'image d'un couple $(g,g')$) et d'un élément remarquable -$e$ tels que : +Un \textbf{groupe} est un ensemble $G$ muni d'une opération binaire +$\star$ (c'est-à-dire une application $G\times G \to G$ dont on note +$g \star g'$ l'image d'un couple $(g,g')$) et d'un élément remarquable +$e$ tels que : \begin{itemize} -\item Associativité de $\star$ : $x\star(y\star z) = (x\star y)\star z$ -\item Neutralité de $e$ pour $\star$ : $e\star x = x\star e = x$ -\item Existence de symétriques : pour chaque $x$, il existe un élément - noté $x'$ tel que) $x \star x' = x' \star x = e$ +\item Associativité de $\star$ : $x\star(y\star z) = (x\star y)\star z$ +\item Neutralité de $e$ pour $\star$ : $e\star x = x\star e = x$ +\item Existence de symétriques : pour chaque $x$, il existe un élément + noté $x'$ tel que) $x \star x' = x' \star x = e$ \end{itemize} Lorsque de plus la loi $\star$ est commutative ($y\star x = x\star -y$), on parle de \emph{groupe abélien} (ou commutatif). +y$), on parle de \emph{groupe abélien} (ou commutatif). -Exemples : l'addition sur les nombres réels (la loi $\star$ étant -l'addition et le neutre $e$ étant le nombre $0$), ou sur les -complexes, ou sur les entiers ; la multiplication sur les nombres -réels non nuls (la loi $\star$ étant la multiplication et le neutre -$e$ étant le nombre $1$), ou sur les réels strictement positifs, ou -sur les complexes non nuls ; la composition des isométries du plan (la -loi $\star$ étant la composition et le neutre $e$ étant l'identité). +Exemples : l'addition sur les nombres réels (la loi $\star$ étant +l'addition et le neutre $e$ étant le nombre $0$), ou sur les +complexes, ou sur les entiers ; la multiplication sur les nombres +réels non nuls (la loi $\star$ étant la multiplication et le neutre +$e$ étant le nombre $1$), ou sur les réels strictement positifs, ou +sur les complexes non nuls ; la composition des isométries du plan (la +loi $\star$ étant la composition et le neutre $e$ étant l'identité). -Contre-exemple : la multiplication sur les entiers (ou même sur les +Contre-exemple : la multiplication sur les entiers (ou même sur les entiers non nuls) \emph{ne forme pas} un groupe, faute d'inverses pour -les entiers autres que $\pm 1$. - -Généralement, un groupe est noté soit de façon multiplicative (on -écrit $xy$ au lieu de $x\star y$ et $1$ au lieu de $e$, et dans ce cas -on note $x^m$ l'élément $x\star x\star \cdots x$ avec $m$ fois $x$ et -$x^{-1}$ le symétrique de $x$, alors appelé « inverse »), soit de -façon additive (on écrit $x+y$ au lieu de $x\star y$ et $0$ au lieu -de $e$, et dans ce cas on note $mx$ l'élément $x + x + + \cdots + x$ -avec $m$ fois $x$, et $-x$ le symétrique de $x$, alors appelé -« opposé »). Très souvent on utilise une de ces deux notations de -façon implicite. La notation additive est en principe réservée aux -groupes abéliens (mais on n'en rencontrera pas de non-abéliens dans ce +les entiers autres que $\pm 1$. + +Généralement, un groupe est noté soit de façon multiplicative (on +écrit $xy$ au lieu de $x\star y$ et $1$ au lieu de $e$, et dans ce cas +on note $x^m$ l'élément $x\star x\star \cdots x$ avec $m$ fois $x$ et +$x^{-1}$ le symétrique de $x$, alors appelé « inverse »), soit de +façon additive (on écrit $x+y$ au lieu de $x\star y$ et $0$ au lieu +de $e$, et dans ce cas on note $mx$ l'élément $x + x + + \cdots + x$ +avec $m$ fois $x$, et $-x$ le symétrique de $x$, alors appelé +« opposé »). Très souvent on utilise une de ces deux notations de +façon implicite. La notation additive est en principe réservée aux +groupes abéliens (mais on n'en rencontrera pas de non-abéliens dans ce cours). \smallbreak Un \textbf{morphisme} de groupe $\psi\colon G \to G'$ est une -application qui préserve la composition ($\psi(x\star y) = \psi(x) -\star \psi(y)$), et du coupb forcément aussi l'élément neutre -($\psi(e) = e$) et les symétriques (le symétrique de $\psi(x)$ est -l'image du symétrique de $x$). Un \textbf{isomorphisme} de groupes -est un morphisme bijectif ; moralement : les groupes $G$ et $G'$ sont -abstraitement « le même » (mais éventuellement notés ou étiquetés -différemment). Attention ! On aura souvent affaire, par exemple, à -un morphisme entre un groupe noté additivement et un groupe noté -multiplicativement : dans ce cas, cela signifie $\psi(x+y) = -\psi(x)\,\psi(y)$. Exemple : l'exponentielle (de base $e$, disons) -constitue un isomorphisme entre le groupe additif des réels et le -groupe multiplicatif des réels non nuls. +application qui préserve la composition ($\psi(x\star y) = \psi(x) +\star \psi(y)$), et du coupb forcément aussi l'élément neutre +($\psi(e) = e$) et les symétriques (le symétrique de $\psi(x)$ est +l'image du symétrique de $x$). Un \textbf{isomorphisme} de groupes +est un morphisme bijectif ; moralement : les groupes $G$ et $G'$ sont +abstraitement « le même » (mais éventuellement notés ou étiquetés +différemment). Attention ! On aura souvent affaire, par exemple, à +un morphisme entre un groupe noté additivement et un groupe noté +multiplicativement : dans ce cas, cela signifie $\psi(x+y) = +\psi(x)\,\psi(y)$. Exemple : l'exponentielle (de base $e$, disons) +constitue un isomorphisme entre le groupe additif des réels et le +groupe multiplicatif des réels non nuls. L'\textbf{ordre d'un groupe} est simplement son cardinal, lorsque -celui-ci est fini. L'\textbf{ordre d'un élément} $g$ dans un groupe +celui-ci est fini. L'\textbf{ordre d'un élément} $g$ dans un groupe fini est le plus petit $m\geq 1$ tel que $g^m = 1$ (en notation -multiplicative ; en notation additive, cela s'écrirait : $mg = 0$, -i.e., un multiple de $g$) ; c'est aussi le nombre de puissances -distinctes (en notation additive : de multiples distincts) de -l'élément $g$. Lorsque $g$ est d'ordre $m$, on a $g^m = 1$ mais aussi -$g^{m'} = 1$ si et seulement si $m'$ est multiple de $m$. +multiplicative ; en notation additive, cela s'écrirait : $mg = 0$, +i.e., un multiple de $g$) ; c'est aussi le nombre de puissances +distinctes (en notation additive : de multiples distincts) de +l'élément $g$. Lorsque $g$ est d'ordre $m$, on a $g^m = 1$ mais aussi +$g^{m'} = 1$ si et seulement si $m'$ est multiple de $m$. Un \textbf{sous-groupe} $H$ d'un groupe $G$ est un sous-ensemble de -$G$ qui est lui-même un groupe pour la même opération et le même -élément neutre ; c'est-à-dire, c'est une partie $H$ de $G$ telle que +$G$ qui est lui-même un groupe pour la même opération et le même +élément neutre ; c'est-à-dire, c'est une partie $H$ de $G$ telle que $1 \in H$ et que $x,y \in H \limp xy \in H$ et que $x \in H \limp -x^{-1} \in H$ (cette dernière partie étant d'ailleurs automatique si -le groupe $G$ est fini). (Exemple : pour la multiplication, les -nombres réels strictement positifs forment un sous-groupe du groupe -des nombres réels non nuls.) - -Le sous-groupe engendré par une partie $E$ d'un groupe $G$ est le plus -petit sous-groupe contenant $E$ (c'est-à-dire l'intersection de tous -les sous-groupes de $G$ contenant $E$). On utilisera cette notion -seulement dans le cas suivant : le \emph{sous-groupe engendré par un - unique élément} $g$ de $G$ : c'est l'ensemble des puissances de $g$ -(en notation additive : multiples). L'ordre $m$ de ce sous-groupe est -l'ordre de $g$. Ce sous-groupe est isomorphe à +x^{-1} \in H$ (cette dernière partie étant d'ailleurs automatique si +le groupe $G$ est fini). (Exemple : pour la multiplication, les +nombres réels strictement positifs forment un sous-groupe du groupe +des nombres réels non nuls.) + +Le sous-groupe engendré par une partie $E$ d'un groupe $G$ est le plus +petit sous-groupe contenant $E$ (c'est-à-dire l'intersection de tous +les sous-groupes de $G$ contenant $E$). On utilisera cette notion +seulement dans le cas suivant : le \emph{sous-groupe engendré par un + unique élément} $g$ de $G$ : c'est l'ensemble des puissances de $g$ +(en notation additive : multiples). L'ordre $m$ de ce sous-groupe est +l'ordre de $g$. Ce sous-groupe est isomorphe à $\mathbb{Z}/m\mathbb{Z}$, avec $\bar k \mapsto g^k$. \smallbreak -\textbf{Théorème de Lagrange :} Dans un groupe fini, l'ordre de tout +\textbf{Théorème de Lagrange :} Dans un groupe fini, l'ordre de tout sous-groupe divise l'ordre du groupe. En particulier, l'ordre d'un -élément divise l'ordre du groupe : si $G$ est un groupe fini et $g \in +élément divise l'ordre du groupe : si $G$ est un groupe fini et $g \in G$ alors $g^{\#G} = 1$. % \subsection{Groupes cycliques} On dit qu'un groupe fini $G$ est \textbf{cyclique} lorsqu'il existe un -élément $g$ (appelé \emph{générateur} de $G$) tel que tout élément de +élément $g$ (appelé \emph{générateur} de $G$) tel que tout élément de $G$ soit de la forme $g^k$ (une puissance de $g$, en notation -multiplicative ; en notation additive, cela s'écrirait : $kg$, i.e., -un multiple de $g$), autrement dit : le sous-groupe engendré par $g$ -est $G$ tout entier. Ou encore : $G$ est cyclique de générateur $g$ -si et seulement si l'ordre de $g$ est égal à l'ordre de $G$. +multiplicative ; en notation additive, cela s'écrirait : $kg$, i.e., +un multiple de $g$), autrement dit : le sous-groupe engendré par $g$ +est $G$ tout entier. Ou encore : $G$ est cyclique de générateur $g$ +si et seulement si l'ordre de $g$ est égal à l'ordre de $G$. Le groupe \emph{additif} $\mathbb{Z}/m\mathbb{Z}$ est cyclique, avec -pour générateur $1$ (mais ce n'est pas le seul possible ! -cf. ci-dessous). Réciproquement, tout groupe cyclique est isomorphe à -$\mathbb{Z}/m\mathbb{Z}$, avec $m$ l'ordre d'un générateur $g$ (qui -est donc aussi l'ordre du groupe et ne dépend pas du générateur). -D'où une autre définition possible : un groupe cyclique $G$ [de - générateur $g$] est un groupe isomorphe à $\mathbb{Z}/m\mathbb{Z}$ -[avec $1$ correspondant à $g$]. - -Quels sont tous les générateurs de $\mathbb{Z}/m\mathbb{Z}$ (comme -groupe additif !) ? Réponse : ce sont précisément les classes modulo -$m$ des entiers premiers à $m$, c'est-à-dire les inversibles de -$\mathbb{Z}/m\mathbb{Z}$ (comme anneau !). (Démonstration : si $\bar +pour générateur $1$ (mais ce n'est pas le seul possible ! +cf. ci-dessous). Réciproquement, tout groupe cyclique est isomorphe à +$\mathbb{Z}/m\mathbb{Z}$, avec $m$ l'ordre d'un générateur $g$ (qui +est donc aussi l'ordre du groupe et ne dépend pas du générateur). +D'où une autre définition possible : un groupe cyclique $G$ [de + générateur $g$] est un groupe isomorphe à $\mathbb{Z}/m\mathbb{Z}$ +[avec $1$ correspondant à $g$]. + +Quels sont tous les générateurs de $\mathbb{Z}/m\mathbb{Z}$ (comme +groupe additif !) ? Réponse : ce sont précisément les classes modulo +$m$ des entiers premiers à $m$, c'est-à-dire les inversibles de +$\mathbb{Z}/m\mathbb{Z}$ (comme anneau !). (Démonstration : si $\bar a$ engendre le groupe additif $\mathbb{Z}/m\mathbb{Z}$, alors en -particulier il doit engendrer $\bar 1$, c'est-à-dire qu'on peut écrire +particulier il doit engendrer $\bar 1$, c'est-à-dire qu'on peut écrire $\bar 1 = \bar a + \bar a + \cdots + \bar a$, avec $u$ fois $\bar a$ disons, donc $\bar a \bar u = \bar 1$ dans l'anneau $\mathbb{Z}/m\mathbb{Z}$, et $\bar a$ y est bien inversible. -Réciproquement, si $\bar a \bar u = \bar 1$, et si $\bar a + \bar a + -\cdots + \bar a = 0$, avec $k$ fois $\bar a$, alors en multipliant par +Réciproquement, si $\bar a \bar u = \bar 1$, et si $\bar a + \bar a + +\cdots + \bar a = 0$, avec $k$ fois $\bar a$, alors en multipliant par $\bar u$ on a $\bar 1 + \bar 1 + \cdots + \bar 1 = 0$, soit $\bar k = -0$, donc $k$ est multiple de $m$ : ceci prouve que l'ordre de $\bar a$ -ne peut pas être plus petit que $m$.) +0$, donc $k$ est multiple de $m$ : ceci prouve que l'ordre de $\bar a$ +ne peut pas être plus petit que $m$.) Ainsi, pour $m$ entier naturel non nul et $a$ entier, il y a -équivalence entre : +équivalence entre : \begin{itemize} \item les entiers $a$ et $m$ sont premiers entre eux, -\item l'élément $\bar a$ a pour ordre (additif) $m$ dans le groupe +\item l'élément $\bar a$ a pour ordre (additif) $m$ dans le groupe $\mathbb{Z}/m\mathbb{Z}$, -\item l'élément $\bar a$ est générateur du groupe +\item l'élément $\bar a$ est générateur du groupe $\mathbb{Z}/m\mathbb{Z}$, -\item l'élément $\bar a$ est inversible dans l'anneau +\item l'élément $\bar a$ est inversible dans l'anneau $\mathbb{Z}/m\mathbb{Z}$, -\item l'élément $\bar a$ appartient au groupe +\item l'élément $\bar a$ appartient au groupe $(\mathbb{Z}/m\mathbb{Z})^\times$ des inversible de l'anneau $\mathbb{Z}/m\mathbb{Z}$. \end{itemize} En particulier, $\mathbb{Z}/m\mathbb{Z}$ admet $\varphi(m)$ -générateurs. Comme un groupe cyclique d'ordre $m$ est la même chose -que (un groupe isomorphe à) $\mathbb{Z}/m\mathbb{Z}$, on en déduit : -le nombre de générateurs de n'import quel groupe cyclique d'ordre $m$ +générateurs. Comme un groupe cyclique d'ordre $m$ est la même chose +que (un groupe isomorphe à) $\mathbb{Z}/m\mathbb{Z}$, on en déduit : +le nombre de générateurs de n'import quel groupe cyclique d'ordre $m$ est $\varphi(m)$. -Attention ! on parlera aussi, plus loin, des générateurs du groupe +Attention ! on parlera aussi, plus loin, des générateurs du groupe \emph{multiplicatif} $(\mathbb{Z}/m\mathbb{Z})^\times$ (et de la -question de savoir s'il y en a). Il ne faut pas confondre ! +question de savoir s'il y en a). Il ne faut pas confondre ! \medbreak -De façon générale, l'ordre additif de $\bar a$ dans +De façon générale, l'ordre additif de $\bar a$ dans $\mathbb{Z}/m\mathbb{Z}$ vaut exactement $m/\pgcd(a,m)$. % -\subsection{Théorème d'Euler} +\subsection{Théorème d'Euler} -Si $m$ est un entier naturel non nul et $a$ un entier premier à $m$, +Si $m$ est un entier naturel non nul et $a$ un entier premier à $m$, alors \[ a^{\varphi(m)} \equiv 1 \pmod{m} \] -Démonstration : l'élément $\bar a \in (\mathbb{Z}/m\mathbb{Z})^\times$ -a un ordre qui d'après Lagrange doit diviser l'ordre du groupe, -i.e. $\varphi(m)$. - -\textbf{Attention !} ne pas confondre l'ordre (« additif ») d'un -élément du groupe additif $\mathbb{Z}/m\mathbb{Z}$ et l'ordre -(« multiplicatif ») d'un élément du groupe multiplicatif -$(\mathbb{Z}/m\mathbb{Z})^\times$. Exemple : quel est l'ordre de $2$ -dans $\mathbb{Z}/7\mathbb{Z}$ ? (réponse : $7$ car $2+2+2+2+2+2+2 = -0$ dans $\mathbb{Z}/7\mathbb{Z}$ et qu'on ne trouve pas $0$ avant) ; -et dans $(\mathbb{Z}/7\mathbb{Z})^\times$ ? (réponse : $3$ car +Démonstration : l'élément $\bar a \in (\mathbb{Z}/m\mathbb{Z})^\times$ +a un ordre qui d'après Lagrange doit diviser l'ordre du groupe, +i.e. $\varphi(m)$. + +\textbf{Attention !} ne pas confondre l'ordre (« additif ») d'un +élément du groupe additif $\mathbb{Z}/m\mathbb{Z}$ et l'ordre +(« multiplicatif ») d'un élément du groupe multiplicatif +$(\mathbb{Z}/m\mathbb{Z})^\times$. Exemple : quel est l'ordre de $2$ +dans $\mathbb{Z}/7\mathbb{Z}$ ? (réponse : $7$ car $2+2+2+2+2+2+2 = +0$ dans $\mathbb{Z}/7\mathbb{Z}$ et qu'on ne trouve pas $0$ avant) ; +et dans $(\mathbb{Z}/7\mathbb{Z})^\times$ ? (réponse : $3$ car $2\times 2\times 2 = 1$ dans $(\mathbb{Z}/7\mathbb{Z})^\times$ et qu'on ne trouve pas $1$ avant). -Pour que l'ordre multiplicatif d'un élément $x$ dans -$\mathbb{Z}/m\mathbb{Z}$ soit défini, il faut (et il suffit) que cet -élément $x$ soit dans $(\mathbb{Z}/m\mathbb{Z})^\times$ (car c'est lui +Pour que l'ordre multiplicatif d'un élément $x$ dans +$\mathbb{Z}/m\mathbb{Z}$ soit défini, il faut (et il suffit) que cet +élément $x$ soit dans $(\mathbb{Z}/m\mathbb{Z})^\times$ (car c'est lui le groupe multiplicatif), et dans ce cas l'ordre additif vaut -forcément $m$ car $x$ est un générateur du groupe cyclique +forcément $m$ car $x$ est un générateur du groupe cyclique $\mathbb{Z}/m\mathbb{Z}$. \smallbreak -Cas particulier du théorème d'Euler : le « petit théorème de - Fermat » : si $p$ est premier, alors $a^{p-1} \equiv 1 \pmod{p}$ -lorsque $a$ n'est pas multiple de $p$ ; donc, pour tout entier $a$ on +Cas particulier du théorème d'Euler : le « petit théorème de + Fermat » : si $p$ est premier, alors $a^{p-1} \equiv 1 \pmod{p}$ +lorsque $a$ n'est pas multiple de $p$ ; donc, pour tout entier $a$ on a \[ a^p \equiv a \pmod{p} \] -Ceci fournit une condition \emph{nécessaire} mais non suffisante pour +Ceci fournit une condition \emph{nécessaire} mais non suffisante pour qu'un nombre soit premier. % -\subsection{Éléments primitifs} +\subsection{Éléments primitifs} Soit $m$ un entier naturel non nul. On dit que $g \in -(\mathbb{Z}/m\mathbb{Z})^\times$ est (un résidu) \textbf{primitif} +(\mathbb{Z}/m\mathbb{Z})^\times$ est (un résidu) \textbf{primitif} (modulo~$m$) lorsqu'il engendre $(\mathbb{Z}/m\mathbb{Z})^\times$ -(comme groupe abélien multiplicatif) --- ce qui entraîne que +(comme groupe abélien multiplicatif) --- ce qui entraîne que $(\mathbb{Z}/m\mathbb{Z})^\times$ est cyclique. -Autrement dit, $g^{\varphi(m)}=1$ est optimal : dire que $g$ est -primitif modulo $m$ signifie que son ordre multiplicatif est +Autrement dit, $g^{\varphi(m)}=1$ est optimal : dire que $g$ est +primitif modulo $m$ signifie que son ordre multiplicatif est exactement $\varphi(m)$ (et pas un autre diviseur de $\varphi(m)$). -Exemple : les puissances de $\bar 2$ modulo $9$ sont : $\bar 2,\bar -4,\bar 8,\bar 7,\bar 5,\bar 1$ ; il y en a bien $\varphi(9)=6$ donc -$2$ est primitif modulo $9$. +Exemple : les puissances de $\bar 2$ modulo $9$ sont : $\bar 2,\bar +4,\bar 8,\bar 7,\bar 5,\bar 1$ ; il y en a bien $\varphi(9)=6$ donc +$2$ est primitif modulo $9$. \smallbreak -\textbf{Attention !} Ne pas confondre : +\textbf{Attention !} Ne pas confondre : \begin{itemize} -\item $\mathbb{Z}/m\mathbb{Z}$ (groupe \emph{additif}, d'élément -neutre $0$) est d'ordre $m$ et est \emph{toujours} cyclique (avec pour -générateurs au moins $1$ et $-1$, et tous les éléments de +\item $\mathbb{Z}/m\mathbb{Z}$ (groupe \emph{additif}, d'élément +neutre $0$) est d'ordre $m$ et est \emph{toujours} cyclique (avec pour +générateurs au moins $1$ et $-1$, et tous les éléments de $(\mathbb{Z}/m\mathbb{Z})^\times$). \item $(\mathbb{Z}/m\mathbb{Z})^\times$ (groupe \emph{multiplicatif}, -d'élément neutre $1$) est d'ordre $\varphi(m)$ et est \emph{parfois} -cyclique (auquel cas ses générateurs s'appellent éléments +d'élément neutre $1$) est d'ordre $\varphi(m)$ et est \emph{parfois} +cyclique (auquel cas ses générateurs s'appellent éléments \emph{primitifs} et il y en a $\varphi(\varphi(m))$). \end{itemize} \medbreak -\textbf{Théorème :} +\textbf{Théorème :} \begin{itemize} \item Si $p$ est un nombre premier impair, alors $(\mathbb{Z}/p\mathbb{Z})^\times$ est cyclique, i.e., il existe des - éléments primitifs modulo $p$. (Il en existe exactement + éléments primitifs modulo $p$. (Il en existe exactement $\varphi(p-1)$.) \item Si $p$ est un nombre premier impair et $r\geq 2$, alors $(\mathbb{Z}/p^r\mathbb{Z})^\times$ est cyclique, i.e., il existe - des éléments primitifs modulo $p^r$. (Il en existe exactement - $\varphi(p^{r-1}(p-1))$.) \emph{Mieux} : $g$ est primitif modulo + des éléments primitifs modulo $p^r$. (Il en existe exactement + $\varphi(p^{r-1}(p-1))$.) \emph{Mieux} : $g$ est primitif modulo $p^r$ si et seulement si il l'est modulo $p^2$. \item Si $p=2$ et $1\leq r\leq 2$, alors $(\mathbb{Z}/2^r\mathbb{Z})^\times$ est trivialement cyclique. \item Si $p=2$ et $r \geq 3$, alors - $(\mathbb{Z}/2^r\mathbb{Z})^\times$ \emph{n'est pas} cyclique : il - est produit d'un groupe cyclique d'ordre $2$ engendré par $-1$ et - d'un groupe cyclique d'ordre $2^{r-2}$ engendré par $5$ (l'ordre - maximal possible d'un élément est $2^{r-2}$). + $(\mathbb{Z}/2^r\mathbb{Z})^\times$ \emph{n'est pas} cyclique : il + est produit d'un groupe cyclique d'ordre $2$ engendré par $-1$ et + d'un groupe cyclique d'ordre $2^{r-2}$ engendré par $5$ (l'ordre + maximal possible d'un élément est $2^{r-2}$). \end{itemize} % -\section{Polynômes} +\section{Polynômes} -\subsection{Définition, structure d'anneau et degré} +\subsection{Définition, structure d'anneau et degré} -Soit $k$ un anneau commutatif quelconque (par exemple : $\mathbb{Z}$), -typiquement un corps (exemples importants : $\mathbb{F}_p = +Soit $k$ un anneau commutatif quelconque (par exemple : $\mathbb{Z}$), +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}). Autrement dit, on peut écrire $f = a_0 + -a_1 t + \cdots + a_n t^n$ pour un certain $n$ (et si on impose $a_n -\neq 0$, ceci définit $n$, qui s'appellera alors le degré de $f$). +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}). Autrement dit, on peut écrire $f = a_0 + +a_1 t + \cdots + a_n t^n$ pour un certain $n$ (et si on impose $a_n +\neq 0$, ceci définit $n$, qui s'appellera alors le degré de $f$). -\textbf{Opérations :} +\textbf{Opérations :} \begin{itemize} -\item Addition : terme à terme ($c_i = a_i+b_i$). -\item Multiplication : « produit de Cauchy » en développant +\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}. Plus -généralement, le coefficient $a_{\deg f}$ s'appelle \emph{coefficient - dominant} de $f$. +\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}. Plus +généralement, le coefficient $a_{\deg f}$ s'appelle \emph{coefficient + dominant} de $f$. -\textbf{Propriétés} du degré : +\textbf{Propriétés} du degré : \begin{itemize} -\item $\deg (f+g) \leq \max(\deg f, \deg g)$ (avec égalité si $\deg f +\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}, +\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. +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 +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. +À 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. +Complexité des opérations : cf. entiers. % -\subsection{Opérations spécifiques aux polynômes} +\subsection{Opérations spécifiques aux polynômes} -\textbf{Évaluation} de polynômes : si $f = a_0 + \cdots + a_N t^N$ et -$x$ est dans $k$ ou $k[t]$ (ou plus généralement une « $k$-algèbre »), -on définit $f(x) = a_0 + \cdots + a_N x^N$. +\textbf{Évaluation} de polynômes : si $f = a_0 + \cdots + a_N t^N$ et +$x$ est dans $k$ ou $k[t]$ (ou plus généralement une « $k$-algèbre »), +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)$. +Cas particulier : \textbf{composition} : si $g \in k[t]$, on note +$f\circ g$ plutôt que $f(g)$. \medbreak -\textbf{Racines :} si $f(x) = 0$ avec $x \in k$, on dit que $x$ est -une \emph{racine} du polynôme $f$. +\textbf{Racines :} si $f(x) = 0$ avec $x \in k$, on dit que $x$ est +une \emph{racine} du polynôme $f$. -\textbf{Attention :} On peut très bien avoir $f(x) = 0$ pour tout $x +\textbf{Attention :} On peut très bien avoir $f(x) = 0$ pour tout $x \in k$ sans pour autant que $f$ soit nul (e.g., $f = t^p - t$ dans $\mathbb{F}_p[t]$). (Mais on va voir que si $k$ est un corps, le nombre de racines de $f$ -dans $k$ est inférieur ou égal au degré de $f$.) +dans $k$ est inférieur ou égal au degré de $f$.) \medbreak -\textbf{Dérivée :} si $f = a_0 + a_1 t + \cdots + a_N t^N$ alors $f' = +\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 +\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 +\textbf{Dérivées successives :} $f^{(i+1)} = (f^{(i)})'$ pour $i \in \mathbb{N}$. % -\subsection{Polynôme interpolateur} +\subsection{Polynôme interpolateur} Dans cette section, soit $k$ un \emph{corps} et $f \in k[t]$. \medskip -\textbf{Fait fondamental :} lorsque deux polynômes de degré $\leq N$ -coïncident en (au moins) $N+1$ points, ils sont égaux ; de façon -équivalente, si un polynôme de degré $\leq N$ s'annule en $\geq N+1$ -points, alors c'est le polynôme nul. +\textbf{Fait fondamental :} lorsque deux polynômes de degré $\leq N$ +coïncident en (au moins) $N+1$ points, ils sont égaux ; de façon +équivalente, si un polynôme de degré $\leq N$ s'annule en $\geq N+1$ +points, alors c'est le polynôme nul. -Réciproquement, si $a_0,\ldots,a_N \in k$ sont deux à deux distincts, +Réciproquement, si $a_0,\ldots,a_N \in k$ sont deux à deux distincts, et $b_0,\ldots,b_N\in k$ sont quelconques, alors \[ \sum_{i=0}^N b_i \frac{\prod_{j\neq i}(t-a_j)}{\prod_{j\neq i}(a_i-a_j)} \] -(\emph{polynôme interpolateur de Lagrange}) est un polynôme de -degré $\leq N$ prenant en $a_i$ la valeur $b_i$. D'après ce qu'on -vient de dire, c'est \emph{le} seul polynôme de degré $\leq N$ prenant -en chaque $a_i$ la valeur $b_i$. +(\emph{polynôme interpolateur de Lagrange}) est un polynôme de +degré $\leq N$ prenant en $a_i$ la valeur $b_i$. D'après ce qu'on +vient de dire, c'est \emph{le} seul polynôme de degré $\leq N$ prenant +en chaque $a_i$ la valeur $b_i$. -Ceci permet de reconstruire un polynôme à partir de ses valeurs en +Ceci permet de reconstruire un polynôme à partir de ses valeurs en suffisamment de points. % -\subsection{Division euclidienne de polynômes} +\subsection{Division euclidienne de polynômes} Sauf mention du contraire, $k$ est maintenant un \textbf{corps}. \smallskip -\textbf{Division euclidienne} analogue à celle des entiers : +\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 : +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 $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} : +\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$) : +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