\documentclass[11pt]{article}
\usepackage[french]{babel}
\setlength{\textwidth}{18 cm}
\setlength{\textheight}{24 cm}
\setlength{\topmargin}{-17 mm}
\setlength{\oddsidemargin}{-15 mm}
\usepackage{amsfonts,amsmath,amssymb}
\begin{document}


%Macros perso
\renewcommand{\leq}{\,\leqslant\,}
\renewcommand{\geq}{\,\geqslant\,}
\newcommand{\N}{\mathbb{N}}
\newcommand{\PGCD}[2]{\mathop{\rm PGCD}\left(#1, #2\right)}
\newcommand{\somme}[3]{\sum_{#1}^{#2}\limits{#3}}


%Num{\'e}rotation
\renewcommand{\labelenumi}{\textbf{\arabic{enumi}\r{})} }
\renewcommand{\labelenumii}{\alph{enumii}) }


\begin{center}\framebox{{\'E}PREUVE OPTIONNELLE de MATH{\'E}MATIQUES}\end{center}


\bigskip
Dans ce probl{\`e}me, on note $D(a, b)$ l'ensemble des diviseurs communs {\`a} deux entiers naturels $a$, $b$ o{\`u} $(a, b) {\neq} (0, 0)$, et le plus grand {\'e}l{\'e}ment de cet ensemble $D(a, b)$ est donc le PGCD de $a$ et $b$.
Le probl{\`e}me a pour but l'{\'e}tude de la complexit{\'e} du calcul du PGCD des entiers naturels $a$ et $b$ par l'algorithme d'Euclide d{\'e}crit ci-dessous.
On {\'e}tudie {\`a} titre pr{\'e}liminaire la suite de Fibonacci, qui est d{\'e}finie par $F_{0} = 0$, $F_{1} = 1$, et $F_{n+2} = F_{n+1} + F_{n}$ pour $n \in \N$.

\bigskip
\begin{enumerate}
\item %Question 1
Dans cette question, on {\'e}tudie le calcul de la suite de Fibonacci $(F_{n})$.
\begin{enumerate}
\item {\'E}crire un algorithme de calcul de $F_{n}$ lorsque le nombre entier $n$ est donn{\'e}.
\item Pr{\'e}ciser $F_{n}$ pour $n {\leq} 12$.
\end{enumerate}

\item %Question 2
Dans cette question, on {\'e}tudie les propri{\'e}t{\'e}s de la suite de Fibonacci $(F_{n})$.
\begin{enumerate}
\item Prouver que $(F_{n})$ est une suite de nombres entiers naturels, strictement croissante pour $n {\geq} 2$.
\item D{\'e}terminer les suites g{\'e}om{\'e}triques $(u_{n})$ v{\'e}rifiant la relation $u_{n+2} = u_{n+1} +u_{n}$.
\item D{\'e}terminer l'expression du terme g{\'e}n{\'e}ral $F_{n}$ de la suite de Fibonacci en fonction de $n$.
\item En d{\'e}duire l'encadrement suivant de $F_{n}$, puis un {\'e}quivalent de $F_{n}$ lorsque $n$ tend vers $+{\infty}$ :
$$\dfrac{1}{\sqrt{5}} \left( \left(\dfrac{\sqrt{5}+1}{2}\right)^{n} - 1\right) {\leq} F_{n} {\leq} \dfrac{1}{\sqrt{5}} \left( \left(\dfrac{\sqrt{5} + 1}{2}\right)^{n} + 1\right).$$
\item D{\'e}terminer le domaine de d{\'e}finition et la somme de la fonction g{\'e}n{\'e}ratrice :

\centerline{$F(x) = \somme{n=0}{+{\infty}}{F_{n} x^{n}}$.}
\end{enumerate}

\item %Question 3
Dans cette question, on {\'e}tudie quelques propri{\'e}t{\'e}s de l'ensemble $D(a, b)$.
\begin{enumerate}
\item Quels sont les {\'e}l{\'e}ments de $D(a, 0)$ et le PGCD de $a$ et de $0$ pour $a {\geq} 1$ ?
\item Montrer, si $a = bq + r$, que $D(a, b) = D(b, r)$ et $\PGCD{a}{b} = \PGCD{b}{r}$.
\item En remarquant que $F_{k+2} = F_{k+1} + F_{k}$, en d{\'e}duire le PGCD de $F_{n+1}$ et de $F_{n}$ pour $n \in \N$.
\end{enumerate}

\bigskip
On consid{\`e}re deux nombres entiers naturels $a$ et $b$ tels que $a > b > 0$.
On rappelle qu'une {\'e}galit{\'e} de la forme $a = bq + r$ est la division euclidienne de $a$ par $b$ si $q$ et $r$ sont deux entiers naturels v{\'e}rifiant $0 {\leq} r < b$, et que l'algorithme d'Euclide est la suite des divisions euclidiennes suivantes, poursuivies jusqu'{\`a} l'obtention d'un premier reste nul, et dans lesquelles $a_{0} = a$ et $a_{1} = b$ :
$$\begin{array}{rcl}
a_{0} = q_{1} a_{1} + a_{2}\quad\mbox{ avec }\quad &0 < a_{2} < a_{1} \\
a_{1} = q_{2} a_{2} + a_{3}\quad\mbox{ avec }\quad &0 < a_{3} < a_{2} \\
......................................\\
a_{n-1} = q_{n} a_{n} + a_{n+1}\quad\mbox{ avec }\quad &0 < a_{n+1} < a_{n} \\
a_{n} = q_{n+1} a_{n+1} + a_{n+2}\quad\mbox{ avec }\quad &a_{n+2} = 0
\end{array}$$

On dit alors, plus pr{\'e}cis{\'e}ment, que l'algorithme d'Euclide pour $a$ et $b$ s'effectue en $n+1$ divisions.
L'ensemble de ces notations est d{\'e}sormais conserv{\'e} jusqu'{\`a} la fin du probl{\`e}me.

\bigskip
\item %Question 4
Dans cette question, on {\'e}tudie un exemple d'application de l'algorithme d'Euclide.
\begin{enumerate}
\item {\'E}crire l'algorithme d'Euclide pour $F_{3}$ et $F_{2}$, pour $F_{4}$ et $F_{3}$, pour $F_{5}$ et $F_{4}$.
\item Prouver que l'{\'e}galit{\'e} $F_{k+2} = F_{k+1} + F_{k}$ est la division euclidienne de $F_{k+2}$ par $F_{k+1}$ pour $k {\geq} 2$.

En d{\'e}duire que l'algorithme d'Euclide pour $F_{n+2}$ et $F_{n+1}$ s'effectue en $n$ divisions pour $n {\geq} 1$.
\end{enumerate}

\item %Question 5
Dans cette question, on {\'e}tudie enfin la complexit{\'e} de l'algorithme d'Euclide (Th{\'e}or{\`e}me de Lam{\'e}).
\begin{enumerate}
\item Prouver que le PGCD de $a$ et $b$ est {\'e}gal au dernier reste non nul $a_{n+1}$.
\item Prouver par r{\'e}currence les in{\'e}galit{\'e}s $q_{k} {\geq} 1$ pour $1 {\leq} k {\leq} n+1$ et $a_{k} {\geq} F_{n+2-k}$ pour $0 {\leq} k {\leq} n+2$.
\item En d{\'e}duire, si l'algorithme d'Euclide s'effectue en $n+1$ divisions, que $a {\geq} F_{n+2}$, $b {\geq} F_{n+1}$, et :
$$\dfrac{1}{\sqrt{5}} \left( \left(\dfrac{\sqrt{5} + 1}{2}\right)^{n+1} - 1\right) {\leq} b.$$
\item En d{\'e}duire, si l'{\'e}criture d{\'e}cimale de $b$ compte $p$ chiffres, autrement dit si $10^{p-1} {\leq} b < 10^{p}$, que le nombre $n+1$ de divisions de l'algorithme d'Euclide est major{\'e} par $5p+2$.
\end{enumerate}

\item %Question 6
{\'E}crire un algorithme it{\'e}ratif ou r{\'e}cursif calculant le PGCD de deux nombres entiers donn{\'e}s $a$ et $b$ par cette m{\'e}thode.
\end{enumerate}
\end{document}
