diff options
| -rw-r--r-- | rappels-maths.tex | 33 |
1 files changed, 23 insertions, 10 deletions
diff --git a/rappels-maths.tex b/rappels-maths.tex index 57a421b..542bc7d 100644 --- a/rappels-maths.tex +++ b/rappels-maths.tex @@ -422,10 +422,9 @@ Si $au + bv = \pm 1$ on dit parfois que les rationnels $a/b$ et $-v/u$ \medbreak Plus généralement, si $\pgcd(a,b) = d$, on peut trouver $u$ et $v$ -tels que $au+bv = d$ (en fait, il existe $d',d''$ avec $d=d'd''$ tels -que $a/d'$ et $b/d''$ soient premiers entre eux, et si -$(a/d')u_0+(b/d'')v_0 = 1$ est une relation de Bézout entre eux, alors -on a $a(d''u_0)+b(d'v_0) = d$). +tels que $au+bv = d$ (en fait, $\pgcd(\frac{a}{d},\frac{b}{d}) = 1$, +et si $\frac{a}{d} u + \frac{b}{d} v = 1$ est une relation de Bézout +entre eux, alors on a $au + bv = d$). % \subsection{Algorithme d'Euclide} @@ -741,7 +740,8 @@ Généralisations du théorème chinois : 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/d'$ et $n/d''$ premiers entre eux). + $m/d'$ et $n/d''$ premiers entre eux et dont le produit vaut + $\frac{mn}{\pgcd(m,n)} = \ppcm(m,n)$). \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 @@ -853,6 +853,9 @@ 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$, et donc $g^i = g^j$ si $i \equiv j \pmod{m}$. +Attention : le fait d'avoir $g^m = 1$ signifie (exactement) que +l'ordre de $g$ \emph{divise} $m$, pas forcément qu'il est égal à $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 @@ -994,9 +997,10 @@ Soit $m$ un entier naturel non nul. On dit que $g \in (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 -exactement $\varphi(m)$ (et pas un autre diviseur de $\varphi(m)$). +Autrement dit, $g^{\varphi(m)}=1$ est \emph{optimal} : dire que $g$ +est primitif modulo $m$ signifie que son ordre multiplicatif est +\emph{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 @@ -1020,8 +1024,8 @@ cyclique (auquel cas ses générateurs s'appellent éléments \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 + $(\mathbb{Z}/p\mathbb{Z})^\times$ est cyclique, i.e., \emph{il + existe} des é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 @@ -1037,6 +1041,15 @@ cyclique (auquel cas ses générateurs s'appellent éléments maximal possible d'un élément est $2^{r-2}$). \end{itemize} +\smallbreak + +Attention à ne pas faire l'erreur suivante : si on a +$g^{\varphi(m)}=1$, cela \emph{ne signifie pas} que $g$ soit primitif, +et d'ailleurs c'est le cas pour tout élément inversible de +$\mathbb{Z}/m\mathbb{Z}$ d'après le théorème d'Euler : pour pouvoir +dire que $g$ est primitif, la condition importante est que $g^i \neq +1$ lorsque $0<i<\varphi(m)$. + % \section{Polynômes} |