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