talk/gclth2demo.tex

   1 % \only<1>{
   2 % \begin{theorem}[Théorème 1: Hull \& Dobell 1962]
   3 % La période de la suite produite par le générateur congruentiel linéaire est $m$ si %et seulement si
   4 % \begin{enumerate}
   5 % \item\label{item:gcl:c1} $c$ et $m$: premiers entre eux,
   6 % \item\label{item:gcl:c2}  $a \equiv 1 \mod p$ pour chaque facteur premier $p$ de $m$ et
   7 % \item\label{item:gcl:c3} $a \equiv 1 \mod 4$ si  $4$ divise $m$.
   8 % \end{enumerate}
   9 % \end{theorem}
  10 % }
  11
  12 \begin{theorem}[Théorème 3]
  13 Soit $m$ un nombre premier. On peut toujours trouver $a$ d'ordre $m-1$,
  14 $1 \le a \le m-1$.
  15 \end{theorem}
  16
  17
  18
  19 \begin{enumerate}
  20 \item {\sc Lemme}~1 $\Rightarrow$ recherche de l'entier $n$ minimum qui établit
  21 \begin{equation}
  22 \tag{4}
  23 \frac{a^n-1}{a-1}\equiv 0 \mod m.
  24 \end{equation}
  25
  26 \item \textbf{Cas $n=m = p^{\alpha}$, $p$ premier et $\alpha \geq 2$} ({\sc Lemme}~2):
  27 \begin{enumerate}
  28 \item binôme de Newton pour réécrire $a^n$;
  29 \item analyse de $\frac{p^{\alpha}}{j}$ dans $(6)$ $\leadsto$ (4) établie.
  30 \end{enumerate}
  31 \item \textbf{Cas $n<m = p^{\alpha}$, $p$ premier et $\alpha \geq 2$} ({\sc Lemme}~3):
  32 \begin{enumerate}
  33 \item (4) établie $\Rightarrow$  $n$   puissance de $p$,
  34 \item or (4) pas établie pour $n=p^{\alpha-1}$.
  35 \end{enumerate}
  36 \item \textbf{Cas $m=p_1^{\alpha1}p_2^{\alpha2}\dots p_s^{\alpha_s}$  et
  37 $a = 1 + kp_1^{\beta_1}p_2^{\beta_2}\dots p_s^{\beta_s}$}:
  38 \begin{enumerate}
  39 \item preuve similaire (cas 2. puis  3.).
  40 \end{enumerate}
  41
  42 \end{enumerate}
  43