\documentclass{article}
\usepackage{graphicx,times}
\usepackage{psfig,epsfig}
\usepackage{amsfonts}

\newcommand{\no}{\noindent{\bf Notation:}}


\begin{document}

\hspace{-.6cm}Universit\'e Paris 7

\hspace{-.6cm}IUP 2

\hspace{-.6cm}Analyse de Performance et Simulation

\hspace{-.6cm}Ann\'ee 2003-2004

\begin{center}
\textbf{TD no 2}

\textbf{MSN, Arithm\'etique modulaire, R\'ecurrence lin\'eaire et M\'ethode congruentielle lin\'eaire}
\end{center}



\vspace{.6cm}\hspace{-.6cm}\textbf{Exercice 1 [ La m\'ethode MSN. ]}

Quel nombre suit 1010101010 (nombre d\'ecimal) en utilisant la m\'ethode MSN ? 


\vspace{.6cm}\hspace{-.6cm}\textbf{Exercice 2 [ Les probl\`emes de la m\'ethode MSN. ]}
\begin{itemize}
\item \emph{Etude de la MSN dans le cas des nombres d\'ecimaux de 2 chiffres :}

Calculer la suite si on commence par : 09, 43, 10, 29, 24.

Que peut-on deviner sur cette m\'ethode dans ce cas ?


\item \emph{D\'esavantage de la MSN sur un nombre \`a 2n chiffres} : 

Montrer
que si la suite a un \'el\'ement dont les n chiffres les plus
significatifs sont nuls, alors les \'el\'ements suivants seront de
plus en plus petits jusqu'\`a arriver \`a 0.
\end{itemize}


\vspace{.6cm}\hspace{-.6cm}\textbf{Exercice 3 [ Arithm\'etique
  modulaire. ]}

\begin{itemize}

\item 1) Prouvez que :

 - $((x \bmod n) + (y \bmod n)) \bmod n = (x + y) \bmod n$

 - $((x \bmod n) * (y \bmod n)) \bmod n = (x * y) \bmod n$

\item 2) Soit $n$ un entier et $S(n)$ la somme des chiffres $a_0,...a_N$ de
l'\'ecriture d\'ecimale de $n = a_N...a_0 = \Sigma_{0\leq k \leq N}a_k
10^k$.

a) Comparer $n \bmod 3$ et $S(n) \bmod 3$ ; en d\'eduire un crit\`ere de
divisibilit\'e par 3.

b)  Comparer $n mod 9$ et $S(n) \bmod 9$ ; en d\'eduire un crit\`ere de
divisibilit\'e par 9.

c) Donner un crit\`ere de divisibilit\'e par 11 en \'etudiant les
puissances de 10 modulo 11.

\end{itemize}



\vspace{.6cm}\hspace{-.6cm}\textbf{Exercice 4 [ R\'esoudre une r\'ecurrence lin\'eaire. ]}

D\'eterminer l'ensemble des solutions des relations de r\'ecurrence
suivantes :
\begin{itemize}
\item 1) $u_n = 4 u_{n-1}$
\item 2) $u_n = 2 u_{n-1} + 3 u_{n-2}$
\item 3) $u_n = u_{n-1} + 2 u_{n-2} + 3$
\item 4) $u_n = a u_{n-1} + b$ avec $a$ et $b$ r\'eels.
\end{itemize}

\vspace{.6cm}\hspace{-.6cm}\textbf{Exercice 5 [ La M\'ethode congruentielle lin\'eaire. ]}

Supposons que nous voulions g\'en\'erer une suite d'entiers $X_0$,
$X_1$, ..., tels que $0\leq X_n < m$. Soit $f(x)$ un fonction telle
que $0 \leq x < m$ implique $0 \leq f(x) < m$. Consid\'erons un suite
form\'ee selon la r\`egle $X_{n+1} = f(X_n)$. (Un exemple est MSN).

a) Montrer que cette suite est ultimement p\'eriodique, c'est-\`a-dire
qu'il existe des nombres $\lambda$ et $\mu$ pour lesquels
$X_0,X_1,...,X_{\mu},...,X_{\mu + \lambda - 1}$ sont distinctes, mais
$X_{n+\lambda} = X_n$ quand $n \geq \mu$.

Que signifie le cas o\`u $\mu = 0$ et $\lambda = m$ ?

Donner un exemple o\`u $\mu = m-1$ et $\lambda = 1$.

b) Montrer qu'il existe un $n > 0$ tel que $X_n = X_{2n}$ ; et que le
plus petit n qui convient est tel que $\mu \leq n \leq \mu +
\lambda$. Montrer de plus que cette valeur est unique, c'est-\`a-dire
que si $X_n = X_{2n}$ et $X_r = X_{2r}$, alors $X_r = X_n$.


\end{document}
