summaryrefslogtreecommitdiffstats
path: root/rappels-maths.tex
diff options
context:
space:
mode:
authordavid <david>2008-11-26 17:35:18 +0000
committerdavid <david>2008-11-26 17:35:18 +0000
commitd7c301214ccf4679e4e816a232a3e75c657ecb9a (patch)
tree9d424875caa32a3ee60359acdcb4722516485a42 /rappels-maths.tex
parentbb28c6a7f9500b4c61847845da32ca70416d52cc (diff)
downloadinfmdi720-d7c301214ccf4679e4e816a232a3e75c657ecb9a.tar.gz
infmdi720-d7c301214ccf4679e4e816a232a3e75c657ecb9a.tar.bz2
infmdi720-d7c301214ccf4679e4e816a232a3e75c657ecb9a.zip
Correct various mistakes.
Diffstat (limited to 'rappels-maths.tex')
-rw-r--r--rappels-maths.tex23
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