diff options
| -rw-r--r-- | rappels-maths.tex | 23 |
1 files changed, 13 insertions, 10 deletions
diff --git a/rappels-maths.tex b/rappels-maths.tex index 1d231fc..7c3312f 100644 --- a/rappels-maths.tex +++ b/rappels-maths.tex @@ -41,7 +41,7 @@ \maketitle {\footnotesize \begin{center} -CVS: \verb=$Id: rappels-maths.tex,v 1.11 2008-10-21 16:11:12 david Exp $= +CVS: \verb=$Id: rappels-maths.tex,v 1.12 2008-11-26 17:35:18 david Exp $= \end{center} \par} \pretolerance=10000 @@ -130,7 +130,7 @@ Sur leur répartition : Il y en a une infinité (Euclide). Pour tout $x>1$, il y a toujours un nombre premier $p$ tel que -$x\leq p < 2x$ (\v Ceby\v sëv : « postulat de Bertrand »). +$x < p < 2x$ (\v Ceby\v sëv : « postulat de Bertrand »). Le nombre $\pi(x)$ de nombres premiers $\leq x$ est équivalent à $\frac{x}{\ln x}$ lorsque $x\to +\infty$ (Hadamard \& de la Vallée @@ -571,8 +571,8 @@ verra plus loin comment la calculer. Note : on a deux involutions importantes sur $(\mathbb{Z}/m\mathbb{Z})^\times$ : l'une est $\bar a \mapsto -\bar a$, et l'autre est $\bar a \mapsto \bar a^{-1}$. Comme la première -n'a pas de point fixe, $\varphi(m)$ est toujours \emph{pair} (sauf -pour $m=2$). +n'a pas de point fixe (pour $m>2$), $\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 @@ -703,7 +703,7 @@ $(\mathbb{Z}/m\mathbb{Z})^\times$ (et de la question de savoir s'il y en a). Moralité : $\varphi(m)$ est aussi le nombre d'éléments d'un groupe -cyclique (quelconque) d'ordre $m$ qui en sont générateur. +cyclique (quelconque) d'ordre $m$ qui en sont un générateur. % \subsection{Théorème d'Euler} @@ -724,7 +724,8 @@ l'ordre de $2$ dans $\mathbb{Z}/7\mathbb{Z}$ ? dans $(\mathbb{Z}/7\mathbb{Z})^\times$ ? Cas particulier : « petit théorème de Fermat » : si $p$ est premier, -alors pour tout entier $a$ on a +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} \] @@ -1001,7 +1002,7 @@ après chaque opération. Élément très important : $\bar t$. C'est un espace vectoriel de dimension $\deg P$ sur $k$. Si $k$ est -fini alors $k[t]/(P)$ l'est. +fini alors $k[t]/(P)$ l'est (de cardinal $(\#k)^{\deg P}$). Théorème chinois : si $P$ et $Q$ sont premiers entre eux, on a $k[t]/(PQ) \cong (k[t]/(P)) \times (k[t]/(Q))$ (même démo qu'avant, @@ -1044,7 +1045,7 @@ s'appelle la caractéristique. \subsection{Unicité} Dans un corps $F$ à $q$ éléments, on a $a^{q-1} = 1$ pour tout $a \in -K^\times$ (par Lagrange) donc on a $a^q = a$ pour tout $a \in K$ +F^\times$ (par Lagrange) donc on a $a^q = a$ pour tout $a \in F$ (« petit théorème de Fermat » généralisé). Comme le polynôme $t^q-t$, de degré $q$, ne peut avoir que $q$ @@ -1200,7 +1201,9 @@ les deux conditions suivantes sont vérifiées : \begin{itemize} \item $f$ divise $t^{q^e}-t$, et \item $f$ est premier avec $t^{q^{e_1}}-t$ pour tout diviseur strict -$e_1$ de $e$. + $e_1$ de $e$ (en fait, on peut se contenter de tester pour les + diviseurs stricts \emph{immédiats}, c'est-à-dire les $e_1 = e/\ell$ + avec $\ell$ premier). \end{itemize} (Remarque : le premier s'écrit $t^{q^e}\equiv t \pmod{f}$, et pour le vérifier on applique un algorithme d'exponentiation @@ -1278,7 +1281,7 @@ alors tous ses conjugués sur le corps premier $g^p, g^{p^2}, g^{p^3}, \ldots, g^{p^{d-1}}$ le sont aussi. On peut donc aussi dire que leur polynôme minimal (commun) est primitif ; il est nécessairement de degré $d$. Le nombre de polynômes irréductibles primitifs de -degré $d$ sur $\mathbb{F}_p$ est donc $\frac{1}{d} \varphi(d)$. +degré $d$ sur $\mathbb{F}_p$ est donc $\frac{1}{d} \varphi(p^d-1)$. Exemple : si $g \in \mathbb{F}_{16}^\times$ est primitif, alors $\{g,g^2,g^4,g^8\}$ est un ensemble complet de conjugués |