%!TEX encoding = UTF-8 Unicode
\documentclass[10pt,a4paper]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{fourier}
\usepackage[scaled=0.875]{helvet}
\renewcommand{\ttdefault}{lmtt}
\usepackage{makeidx}
\makeindex
\usepackage{amsmath,amssymb}
\usepackage{fancybox}
\usepackage[normalem]{ulem}
\usepackage{pifont}
\usepackage{lscape}
\usepackage{multicol}
\usepackage{mathrsfs}
\usepackage{tabularx,array}
\usepackage{colortbl}
\usepackage{multirow}
\usepackage{textcomp}
\usepackage{enumitem}  
\newcommand{\euro}{\eurologo{}}
%Tapuscrit : Denis Vergès 
\usepackage{graphicx}
\usepackage{pst-plot,pst-tree,pstricks,pst-node,pst-func,pstricks-add}
\usepackage{pst-eucl}
\usepackage{pstricks-add}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\D}{\mathbb{D}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\usepackage{diagbox}
\usepackage[left=3.5cm, right=3.5cm, top=2cm, bottom=3cm]{geometry}
\def\e{\text{e}}
\def\i{\text{i}}
\newcommand{\ds}{\displaystyle}%   displaystyle
\newcommand{\cg}{\texttt{]}}% crochet gauche
\newcommand{\cd}{\texttt{[}}% crochet droit
\newcommand{\pg}{\geqslant}%  plus grand ou égal
\newcommand{\pp}{\leqslant}%  plus petit ou égal
\newcommand{\vect}[1]{\overrightarrow{\,\mathstrut#1\,}}
\newcommand{\barre}[1]{\overline{\,\mathstrut#1\,}}
\renewcommand{\theenumi}{\textbf{\arabic{enumi}}}
\renewcommand{\labelenumi}{\textbf{\theenumi.}}
\renewcommand{\theenumii}{\textbf{\alph{enumii}}}
\renewcommand{\labelenumii}{\textbf{\theenumii.}}
\def\Oij{$\left(\text{O},~\vect{\imath},~\vect{\jmath}\right)$}
\def\Oijk{$\left(\text{O},~\vect{\imath},~\vect{\jmath},~\vect{k}\right)$}
\def\Ouv{$\left(\text{O},~\vect{u},~\vect{v}\right)$}
\usepackage{fancyhdr}
\usepackage[dvips,colorlinks=true,pdfstartview=FitV,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\hypersetup{%
pdfauthor = {APMEP},
pdfsubject = {Baccalauréat S},
pdftitle = {Baccalauréat S -  2018},
allbordercolors = white,
pdfstartview=FitH} 
\usepackage[frenchb]{babel}
\usepackage[np]{numprint}
\begin{document}
\setlength\parindent{0mm}
\rhead{\textbf{A. P{}. M. E. P{}.}}
\lhead{\small{Baccalauréat S }}
\rfoot{\small{année 2018}}
\lfoot{\small{Exercices de spécialité}}
\pagestyle{fancy}
\thispagestyle{empty} 
\begin{center}
{\huge\textbf{\decofourleft~Baccalauréat S  
2018~\decofourright\\ \vspace{1cm} L'intégrale des exercices de spécialité de mai à novembre 2018}}

\vspace{1cm}

Pour un accès direct cliquez sur les liens {\Large 
\textcolor{blue}{bleus}}
\end{center}

\vspace{1cm}
 
\begin{tabularx}{\linewidth}{>{\Large}X} 
\Large \hyperlink{Pondichery}{Pondichéry  4 mai 2018} \dotfill \pageref{Pondichery}\\
\hyperlink{Liban}{Liban  29 mai 2018} \dotfill \pageref{Liban}\\
\hyperlink{AmeriqueNord}{Amérique du Nord 29 mai 2018} \dotfill \pageref{AmeriqueNord}\\
\hyperlink{Centresetrangers}{Centres étrangers 11  juin 2018} \dotfill \pageref{Centresetrangers}\\
\hyperlink{Antilles}{Antilles-Guyane 19 juin 2018} \dotfill \pageref{Antilles}\\
\hyperlink{Polynesie}{Polynésie 20 juin 2018} \dotfill \pageref{Polynesie}\\
\hyperlink{Asie}{Asie 21 juin 2018} \dotfill \pageref{Asie}\\
\hyperlink{Metropole}{Métropole  22 juin 2018} \dotfill \pageref{Metropole}\\
%\hyperlink{Polynesiesep}{Polynésie 5  septembre 2018} \dotfill \pageref{Polynesiesep}\\
\hyperlink{Antillessep}{Antilles-Guyane  6 septembre 2018} \dotfill \pageref{Antillessep}\\
\hyperlink{Metropolesep}{Métropole  12 septembre 2018} \dotfill \pageref{Metropolesep}\\
\hyperlink{AmeriSud}{Amérique du Sud  13 novembre 2018}\dotfill \pageref{AmeriSud}\\
\hyperlink{Caledonienov}{Nouvelle-Calédonie   27 novembre 2018} \dotfill \pageref{Caledonienov}\\
%\hyperlink{Caledoniemars}{Nouvelle-Calédonie  mars 2019} \dotfill \pageref{Caledoniemars}
\end{tabularx}
 
\vspace{1cm}\hyperlink{Index}{À la fin index des notions abordées}

%À la fin de chaque exercice cliquer sur {\blue *} pour aller à l'index
\newpage ~
\newpage
%%%%%%%%%%% Pondichéry 4 mai 2018
\hypertarget{Pondichery}{}

\label{Pondichery}
\textbf{\large Pondichéry 4 mai 2018}

\medskip

À toute lettre de l'alphabet on associe un nombre entier $x$ compris entre 0 et 25 comme
indiqué dans le tableau ci-dessous:

\begin{center}
\begin{tabularx}{\linewidth}{|c|*{13}{>{\centering \arraybackslash}X|}}\hline
Lettre 	&A &B &C &D &E &F &G &H &I &J &K 	&L 	&M\\ \hline
$x$ 	&0 &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 	&11 &12\\ \hline\hline
Lettre 	&N &O &P &Q &R &S &T &U &V &W &X 	&Y 	&Z\\ \hline
$x$ 	&13&14&15&16&17&18&19&20&21&22&23 	&24 &25\\ \hline
\end{tabularx}
\end{center}

\medskip

Le \og chiffre de RABIN \fg{} est un dispositif de cryptage asymétrique inventé en 1979 par
l'informaticien Michael Rabin.

\smallskip

Alice veut communiquer de manière sécurisée en utilisant ce cryptosystème. Elle choisit deux
nombres premiers distincts $p$ et $q$. Ce couple de nombres est sa clé privée qu'elle garde
secrète.

Elle calcule ensuite $n = p \times q$ et elle choisit un nombre entier naturel $B$ tel que $0 \leqslant B \leqslant n -1$.

Si Bob veut envoyer un message secret à Alice, il le code lettre par lettre.

Le codage d'une lettre représentée par le nombre entier $x$ est le nombre $y$ tel que :

\[y \equiv  x(x + B)\:\: [n] \:\text{ avec }\: 0 \leqslant y \leqslant n.\]

Dans tout l'exercice on prend $p = 3,\: q = 11$ donc $n = p \times q = 33$ et $B = 13$.

\bigskip

\textbf{Partie A : Cryptage}

\medskip

Bob veut envoyer le mot \og  NO \fg{} à Alice.

\medskip
\begin{enumerate}
\item Montrer que Bob code la lettre \og N \fg{} avec le nombre 8.
\item Déterminer le nombre qui code la lettre \og O \fg.
\end{enumerate}

\bigskip

\textbf{Partie B : Décryptage}

\medskip

Alice a reçu un message crypté qui commence par le nombre 3.

Pour décoder ce premier nombre, elle doit déterminer le nombre entier $x$ tel que :

\[x(x + 13) \equiv  3 \:\: [33]\:  \text{ avec }\: 0 \leqslant  x < 26.\]

\medskip

\begin{enumerate}
\item Montrer que $x(x + 13) \equiv 3\:\: [33]$ équivaut à $(x + 23)^2 \equiv 4\:\: [33]$.
\item
	\begin{enumerate}
		\item Montrer que si $(x + 23)^2 \equiv 4\:\: [33]$ alors le système d'équations $\left\{\begin{array}{l c l}
(x + 23)^2 &\equiv &4 \:\: [3]\\ 
(x + 23)^2 &\equiv &4 \:\: [11]
\end{array}\right.$ est vérifié.
		\item Réciproquement, montrer que si  $\left\{\begin{array}{l c l}
(x + 23)^2 &\equiv &4\:\: [3]\\ 
(x + 23)^2 &\equiv &4 \:\: [11]
\end{array}\right.$ alors $(x + 23)^2 \equiv 4\:\: [33]$.
		\item En déduire que $x(x + 13) \equiv 3\:\: [33] \iff  \left\{\begin{array}{l c l}
(x + 23)^2 &\equiv&1 \:\: [3]\\
(x + 23)^2 &\equiv& 4 \:\: [11]
\end{array}\right.$
	\end{enumerate}
\item
	\begin{enumerate}
		\item Déterminer les nombres entiers naturels $a$ tels que $0 \leqslant a < 3$ et $a^2 \equiv 1 \:\:  [3]$.
		\item Déterminer les nombres entiers naturels $b$ tels que $0 \leqslant b < 11$ et $b^2 \equiv 4\:\: [11]$.
 	\end{enumerate}
\item
	\begin{enumerate}
		\item En déduire que $x(x + 13) \equiv 3 \quad[33]$ équivaut aux quatre systèmes suivants :
		
\[\left\{\begin{array}{l c l}
x &\equiv&2\quad [3]\\
x&\equiv &8\quad[11]
\end{array}\right. \: \text{ ou } \left\{\begin{array}{l c l}
 x &\equiv& 0\quad[3]\\
 x &\equiv& 1 \quad[11]
 \end{array}\right.\: \text{ ou } \left\{\begin{array}{l c l}
x  &\equiv& 2\quad[3]\\
x &\equiv&1 \quad[11]
\end{array}\right.\: \text{ ou } \left\{\begin{array}{l c l}
x &\equiv& 0\quad [3]\\
x &\equiv& 8 \quad [11]
\end{array}\right.\]

		\item On admet que chacun de ces systèmes admet une unique solution entière $x$ telle que

$0 \leqslant x < 33$.

Déterminer, sans justification, chacune de ces solutions.
	\end{enumerate}
\item Compléter l'algorithme en \textbf{Annexe} pour qu'il affiche les quatre solutions trouvées dans la
question précédente.\index{algorithme}
\item Alice peut-elle connaître la première lettre du message envoyé par Bob ? 
	
Le \og chiffre de RABIN \fg{} est-il utilisable pour décoder un message lettre par lettre ?
\end{enumerate}

\newpage
\begin{center}

\textbf{\Large ANNEXE}

\bigskip

\textbf{\Large À COMPLÉTER ET À REMETTRE AVEC LA COPIE}

\begin{flushleft}
\textbf{\large EXERCICE 4  (spécialité)}
\end{flushleft}

\vspace{1.5cm}

\begin{tabularx}{0.7\linewidth}{|X|}\hline
Pour ...... allant de ...... à .......\\
\quad Si le reste de la division de ....... par ....... est égal à ....... alors\\
\qquad Afficher .......\\
\quad Fin Si\\
Fin Pour\\ \hline
\end{tabularx}
\end{center}

%%%%%%%%%  Liban 28 mai 2018
\newpage

\hypertarget{Liban}{}

\label{Liban}
\textbf{\large Liban 28 mai 2018}

\medskip

On définit la suite de réels $\left(a_n\right)$ par :

\[\left\{\begin{array}{l c l}
a_0 &= &0\\
a_1 &= &1\\
a_{n+1} &=& a_n + a_{n-1}\: \text{ pour }\: n \geqslant 1.
\end{array}\right.\]

On appelle cette suite la suite de Fibonacci.\index{suite}

\medskip

\begin{enumerate}
\item Recopier et compléter l'algorithme ci-dessous pour qu'à la fin de son exécution la variable $A$
contienne le terme $a_n$.\index{algorithme}

\begin{center}
\begin{tabularx}{0.4\linewidth}{|c X|}\hline
1&$A \gets 0$\\
2& $B \gets 1$\\
3& Pour $i$ allant de 2 à $n$ :\\
4& \multicolumn{1}{|l|}{\hspace{0.4cm} $C \gets A + B$}\\
5& \multicolumn{1}{|l|}{\hspace{0.4cm} $A \gets \ldots$}\\
6& \multicolumn{1}{|l|}{\hspace{0.4cm} $B \gets \ldots$}\\
7& Fin Pour\\ \hline
\end{tabularx}
\end{center}

On obtient ainsi les premières valeurs de la suite $a_n$ :

\begin{center}
\begin{tabularx}{\linewidth}{|c|*{11}{>{\centering \arraybackslash}X|}}\hline
$n$		&0 	&1 	&2 	&3 	&4 	&5 &6 	&7 		&8 	&9 &10\\ \hline
$a_n$	&0	& 1 &1	&2 	&3	&5 &8 	&13 	&21 &34 &55\\ \hline
\end{tabularx}
\end{center}
\item  Soit la matrice $A = \begin{pmatrix}1&1\\1&0\end{pmatrix}$.\index{matrice}

Calculer $A^2$, $A^3$ et $A^4$. 

Vérifier que $A^5 = \begin{pmatrix}8&5\\5&3\end{pmatrix}$.
\item On peut démontrer, et nous admettrons, que pour tout entier naturel $n$ non nul,

\[A^n = \begin{pmatrix}a_{n+1}&a_n\\a_n&a_{n-1}\end{pmatrix}.\]

	\begin{enumerate}
		\item Soit $p$ et $q$ deux entiers naturels non nuls. Calculer le produit $A^p \times A^q$ et en déduire que
		
		\[a_{p+q} = a_p \times a_{q+1} + a_{p-1} \times a_q.\]
		
		\item  En déduire que si un entier $r$ divise les entiers $a_p$ et $a_q$, alors $r$ divise également $a_{p+q}$.
		\item  Soit $p$ un entier naturel non nul.
		
Démontrer, en utilisant un raisonnement par récurrence sur $n$, que pour tout entier naturel $n$ non nul, $a_p$ divise $a_{np}$.\index{démonstration par récurrence}
	\end{enumerate}
\item 
	\begin{enumerate}
		\item Soit $n$ un entier supérieur ou égal à 5. Montrer que si $n$ est un entier naturel qui n'est pas premier, alors $a_n$ n'est pas un nombre premier.\index{nombre premier}
		\item On peut calculer $a_{19} = \np{4181} = 37 \times 113$.
		
Que penser de la réciproque de la propriété obtenue dans la question 4. a. ?
	\end{enumerate}
\end{enumerate}
%%%%%%%%%%%%   fin Liban 29 mai 2018
\newpage
%%%%%%%%%%%%   Amérique du Nord 29 mai 2018
\hypertarget{AmeriqueNord}{}

\label{AmeriqueNord}
\textbf{\large Amérique du Nord 29 mai 2018}

\medskip

Dans une région, on s'intéresse à la cohabitation de deux espèces animales : les campagnols et les
renards, les renards étant les prédateurs des campagnols. 

Au 1\up{er} juillet 2012, on estime qu'il y a dans cette région approximativement deux millions de campagnols et cent-vingt renards.

On note $u_n$ le nombre de campagnols et $v_n$ le nombre de renards au 1\up{er} juillet de l'année $2012+ n$.\index{suite}

\bigskip

\textbf{Partie A - Un modèle simple}

\medskip

On modélise l'évolution des populations par les relations suivantes :

\[\left\{\begin{array}{l c r}
u_{n+1}& =& 1,1u_n - \np{2000}v_n\\
v_{n+1} &=& 2 \times 10^{-5}u_n + 0,6v_n
\end{array}\right. \quad \text{pour tout entier }\:n \geqslant 0,\: \text{avec } \:u_0 = \np{2000000}\:  \text{ et} \: v_0 = 120.\]\index{suite}

\medskip

\begin{enumerate}
\item 
	\begin{enumerate}
		\item On considère la matrice colonne $U_n = \begin{pmatrix}u_n\\v_n\end{pmatrix}$ pour tout entier $n \geqslant 0$.\index{matrice}
		
Déterminer la matrice $A$ telle que $U_{n+1} = A \times U_n$ pour tout entier $n$ et donner la matrice $U_0$.
		\item Calculer le nombre de campagnols et de renards estimés grâce à ce modèle au 1\up{er} juillet
2018.
	\end{enumerate}
\item Soit les matrices $P = \begin{pmatrix}\np{20000}&\np{5000}\\1&1\end{pmatrix}$, \:$D = \begin{pmatrix}1&0\\0&0,7\end{pmatrix}$ et $P^{-1} = \dfrac{1}{\np{15000}}\begin{pmatrix}1& \np{-5000}\\- 1&\np{20000}\end{pmatrix}$.
	
On admet que $P^{- 1}$ est la matrice inverse de la matrice $P$ et que $A = P \times D \times P^{- 1}$.\index{matrice inverse}
	\begin{enumerate}
		\item Montrer que pour tout entier naturel $n$,\: $U_n = P \times D^n \times P^{- 1} \times U_0$.
		\item Donner sans justification l'expression de la matrice $D^n$ en fonction de $n$.
		\item On admet que, pour tout entier naturel $n$ :
	
\renewcommand\arraystretch{1.8}	
\[\left\{\begin{array}{l c r}
u_n &=& \dfrac{2,8 \times 10^7 + 2 \times 10^6 \times 0,7^n}{15}\\

v_n &=&\dfrac{\np{1400} + 400 \times 0,7^n}{15}
		\end{array}\right.\]
\renewcommand\arraystretch{1}	
Décrire l'évolution des deux populations.
	\end{enumerate}
\end{enumerate}

\bigskip

\textbf{Partie B - Un modèle plus conforme à la réalité}

\medskip

Dans la réalité, on observe que si le nombre de renards a suffisamment baissé, alors le nombre de
campagnols augmente à nouveau, ce qui n'est pas le cas avec le modèle précédent. 

On construit donc un autre modèle, plus précis, qui tient compte de ce type d'observations à l'aide des relations suivantes :\index{suite}

\[\left\{\begin{array}{l c r}
u_{n+1} &=& 1,1u_n - 0,001u_n \times v_n\\
v_{n+1} &=& 2 \times 10^{-7} u_n \times v_n + 0,6v_n
\end{array}\right.\quad \text{pour tout entier }\:n \geqslant 0,\: \text{avec }\:u_0 = \np{2000000}\: \text{et }\: v_0 = 120.\]

\medskip

Le tableau ci-dessous présente ce nouveau modèle sur les $25$ premières années en donnant les
effectifs des populations arrondis à l'unité :
\begin{center}
\begin{tabularx}{0.7\linewidth}{|>{\columncolor[gray]{0.7}}c|*{3}{>{\centering \arraybackslash}X|}}\hline
\rowcolor[gray]{0.7}&A &B &C\\ \hline
1& \multicolumn{3}{c|}{Modèle de la \textbf{partie B}}\\ \hline
2& $n$ 	&$u_n$ 			&$v_n$\\ \hline
3&0		& \np{2000000} 	&120\\ \hline
4&1		& \np{1960000} 	&120\\ \hline
5&2		& \np{1920800} 	&119\\ \hline
6&3		& \np{1884228} 	&117\\ \hline
7&4		& \np{1851905} 	&114\\ \hline
8&5		& \np{1825160} 	&111\\ \hline
9&6		& \np{1804988} 	&107\\ \hline
10&7	& \np{1792049} 	&103\\ \hline
11&8	& \np{1786692} 	&99\\ \hline
12&9	& \np{1789005} 	&94\\ \hline
13&10	& \np{1798854} 	&91\\ \hline
14&11	& \np{1815930} 	&87\\ \hline
15&12	& \np{1839780} 	&84\\ \hline
16&13	& \np{1869827} 	&81\\ \hline
17&14	& \np{1905378} 	&79\\ \hline
18&15	& \np{1945622} 	&77\\ \hline
19&16	& \np{1989620} 	&77\\ \hline
20&17	& \np{2036288} 	&76\\ \hline
21&18	& \np{2084374} 	&77\\ \hline
22&19	& \np{2132440} 	&78\\ \hline
23&20	& \np{2178846} 	&80\\ \hline
24&21	& \np{2221746} 	&83\\ \hline
25&22	& \np{2259109} 	&87\\ \hline
26&23	& \np{2288766} 	&91\\ \hline
27&24	& \np{2308508} 	&97\\ \hline
\end{tabularx}
\end{center}

\medskip

\begin{enumerate}
\item Quelles formules faut-il écrire dans les cellules B4 et C4 et recopier vers le bas pour remplir
les colonnes B et C ?\index{tableur}
\item  Avec le deuxième modèle, à partir de quelle année observe-t-on le phénomène décrit (baisse
des renards et hausse des campagnols) ?
\end{enumerate}

\bigskip

\textbf{Partie C}

\medskip

Dans cette partie on utilise le modèle de la partie B.

Est - il possible de donner à $u_0$ et $v_0$ des valeurs afin que les deux populations restent stables d'une
année sur l'autre, c'est-à-dire telles que pour tout entier naturel $n$ on ait $u_{n+1} = u_n$ et $v_{n+1} = v_n$ ? (On parle alors d'état stable.)
%%%%%%%%%%%%   fin Amérique du Nord 29 mai 2018
\newpage
%%%%%%%%%%%%   Centres étrangers 11 juin 2018
\hypertarget{Centresetrangers}{}

\label{Centresetrangers}
\textbf{\large Centres étrangers 11 juin 2018}

\medskip
Le but de cet exercice est d'envisager une méthode de cryptage à clé publique d'une information
numérique, appelée système RSA, en l'honneur des mathématiciens Ronald Rivest, Adi Shamir et
Leonard Adleman, qui ont inventé cette méthode de cryptage en 1977 et l'ont publiée en 1978.

\smallskip

Les questions 1 et 2 sont des questions préparatoires, la question 3 aborde le cryptage, la question 4
le décryptage.

\bigskip

\begin{enumerate}
\item Cette question envisage de calculer le reste dans la division euclidienne par $55$ de certaines
puissances de l'entier $8$.
	\begin{enumerate}
		\item Vérifier que $8^7 \equiv 2 \mod 55$.\index{division euclidienne}
		
En déduire le reste dans la division euclidienne par $55$ du nombre $8^{21}$.
		\item Vérifier que $8^2 \equiv 9 \mod 55$, puis déduire de la question \textbf{a.} le reste dans la division
euclidienne par $55$ de $8^{23}$.
 	\end{enumerate}
\item  Dans cette question, on considère l'équation $(E)$\: $23 x - 40 y = 1$, dont les solutions sont des
couples $(x~;~y)$ d'entiers relatifs.\index{equation diophantienne@équation diophantienne}
	\begin{enumerate}
		\item Justifier le fait que l'équation $(E)$ admet au moins un couple solution.
		\item Donner un couple, solution particulière de l'équation $(E)$.
		\item Déterminer tous les couples d'entiers relatifs solutions de l'équation $(E)$.
		\item En déduire qu'il existe un unique entier $d$ vérifiant les conditions $0 \leqslant d < 40$ et $23 d \equiv  1 \mod 40$.
 	\end{enumerate}
\item  Cryptage dans le système RSA
	
Une personne A choisit deux nombres premiers $p$ et $q$, puis calcule les produits $N = p q$ et
$n = (p - 1)(q - 1)$. Elle choisit également un entier naturel $c$ premier avec $n$.\index{nombre premier}
	
La personne A publie le couple $(N~;~c)$, qui est une clé publique permettant à quiconque de lui
envoyer un nombre crypté.
	
Les messages sont numérisés et transformés en une suite d'entiers compris entre $0$ et $N -1$.
	
Pour crypter un entier $a$ de cette suite, on procède ainsi : on calcule le reste $b$ dans la division
euclidienne par $N$ du nombre $a^c$, et le nombre crypté est l'entier $b$.

\smallskip

Dans la pratique, cette méthode est sûre si la personne A choisit des nombres premiers $p$ et $q$
très grands, s'écrivant avec plusieurs dizaines de chiffres.\index{nombre premier}

On va l'envisager ici avec des nombres plus simples : $p = 5$ et $q = 11$.

La personne A choisit également $c = 23$.
	\begin{enumerate}
		\item Calculer les nombres $N$ et $n$, puis justifier que la valeur de $c$ vérifie la condition voulue.
		\item Un émetteur souhaite envoyer à la personne A le nombre $a = 8$.
		
Déterminer la valeur du nombre crypté $b$.
	\end{enumerate}
\item  Décryptage dans le système RSA

La personne A calcule dans un premier temps l'unique entier naturel $d$ vérifiant les conditions
$0 \leqslant d < n$ et $cd \equiv 1 \mod n$.

Elle garde secret ce nombre $d$ qui lui permet, et à elle seule, de
décrypter les nombres qui lui ont été envoyés cryptés avec sa clé publique.

Pour décrypter un nombre crypté $b$, la personne A calcule le reste $a$ dans la division euclidienne
par $N$ du nombre $b^d$, et le nombre en clair -- c'est-à-dire le nombre avant cryptage -- est le
nombre $a$.

On admet l'existence et l'unicité de l'entier $d$, et le fait que le décryptage fonctionne.

Les nombres choisis par A sont encore $p = 5$, $q = 11$ et $c = 23$.
	\begin{enumerate}
		\item Quelle est la valeur de $d$ ?
		\item En appliquant la règle de décryptage, retrouver le nombre en clair lorsque le nombre crypté
est $b = 17$.
	\end{enumerate}
\end{enumerate}
%%%%%%%%%%%%   fin Centres étrangers 11 juin 2018
\newpage
%%%%%%%%%%%%   Antilles--Guyane 19 juin 2018
\hypertarget{Antilles}{}

\label{Antilles}
\textbf{\large Antilles--Guyane 19 juin 2018}

\medskip

Le droit de pêche dans une réserve marine est réglementé : chaque pêcheur doit posséder une carte d'accréditation annuelle. Il existe deux types de cartes :

\begin{itemize}
\item une carte de pêche dite \og libre \fg{} (le pêcheur n'est pas limité en nombre de poissons pêchés);
\item une carte de pêche dite \og avec quota \fg{} (le pêcheur ne doit pas dépasser une certaine quantité hebdomadaire de poisson).
\end{itemize}

\smallskip

On suppose que le nombre total de pêcheurs reste constant d'année en année.

On note, pour l'année $2017+n$:
\begin{itemize}
\item $\ell_n$ la proportion de pêcheurs possédant la carte de pêche libre ;
\item $q_n$ la proportion de pêcheurs possédant la carte de pêche avec quota.
\end{itemize}

On observe que:
\begin{itemize}
\item chaque année, 65~\% des possesseurs de la carte de pêche libres achètent de nouveau une carte de pêche libre l'année suivante;
\item Chaque année, 45~\% des possesseurs de la carte de pêche avec quota achètent une carte de pêche libre l'année suivante ;
\item En 2017, 40~\% des pêcheurs ont acheté une carte de pêche libre. On a donc $\ell_0 =\np{0,4}$ et $q_0=\np{0,6}$.
\end{itemize}

On note, pour tout entier naturel $n$, $P_n=\begin{pmatrix}
\ell_n\\q_n
\end{pmatrix}$.\index{matrice}

\medskip

\begin{enumerate}
\item Démontrer que, pour tout entier naturel $n$, $P_{n+1}= MP_n$, où $M$ est la matrice carrée $\begin{pmatrix}
\np{0,65}&\np{0,45}\\
\np{0,35}&\np{0,55}
\end{pmatrix}$.\index{suite}
\item Calculer la proportion de pêcheurs achetant une carte de pêche avec quota en 2019.
\item Un logiciel de calcul formel donne les résultats ci-dessous :
\begin{center}
\begin{tabular}{cc}
\begin{tabular}{|c|l|}
\hline
\cellcolor{lightgray!50}\begin{tabular}{c}1\\$\circ$\end{tabular} & 
\begin{tabular}{l}
$M:=\{\{\np{0.65},\np{0,45}\},\{\np{0.35},\np{0.55}\}\}$\\
$\checkmark~~ M:=\begin{pmatrix}
0,65&0,45\\0,35&0,55
\end{pmatrix}$
\end{tabular}
\\
\hline
\cellcolor{lightgray!50}\begin{tabular}{c}2\\$\circ$\end{tabular} & 
\begin{tabular}{l}
$P_0:=\{\{ 0,4 \},\{ 0,6 \}\}$\\
$\checkmark~~ P_0:=\begin{pmatrix}
0,4\\0,6
\end{pmatrix}$
\end{tabular}
\\
\hline
\cellcolor{lightgray!50}\begin{tabular}{c}3\\$\circ$\end{tabular} & 
\begin{tabular}{l}
$Q:=\{\{ 9,1 \},\{ 7,$- 1$ \}\}$\\
$\checkmark~~ Q:=\begin{pmatrix}
9&1\\7&-1
\end{pmatrix}$
\end{tabular}
\\
\hline
\cellcolor{lightgray!50}\begin{tabular}{c}4\\$\circ$\end{tabular} & 
\begin{tabular}{l}
$T:=\{\{ 1/16,1/16 \},\{ 7/16,- 9/16 \}\}$\\
$\checkmark~~ T:=\begin{pmatrix}
\frac{1}{16}&\frac{1}{16}\\\frac{7}{16}&-\frac{9}{16}
\end{pmatrix}$\\[-0.5ex]\quad
\end{tabular}
\\
\hline
\end{tabular}
&
\begin{tabular}{|c|l|}
\hline
\cellcolor{lightgray!50}\begin{tabular}{c}5\\$\circ$\end{tabular} & 
\begin{tabular}{l}
$TQ$\\
$\rightarrow~~ \begin{pmatrix}
1&0\\0&1
\end{pmatrix}$
\end{tabular}
\\
\hline
\cellcolor{lightgray!50}\begin{tabular}{c}6\\$\circ$\end{tabular} & 
\begin{tabular}{l}
$QT$\\
$\rightarrow~~ \begin{pmatrix}
1&0\\0&1
\end{pmatrix}$
\end{tabular}
\\
\hline
\cellcolor{lightgray!50}\begin{tabular}{c}7\\$\circ$\end{tabular} & 
\begin{tabular}{l}
$D:=TMQ$\\
$\rightarrow~~ D:=\begin{pmatrix}
1&0\\0&\frac15
\end{pmatrix}$
\\[-0.5ex]\quad
\end{tabular}
\\
\hline
\end{tabular}
\end{tabular}
\end{center}

En vous appuyant sur les résultats précédents, répondre aux deux questions suivantes :
\begin{enumerate}
\item Justifier que $Q$ est une matrice inversible et préciser sa matrice inverse.\index{matrice inverse}

On notera $Q^{-1}$ la matrice inverse de $Q$.
\item Justifier que $M = QDQ^{-1}$ et démontrer que, pour tout entier naturel $n$ non nul :
\[M^n=QD^nQ^{-1}.\]
\end{enumerate}
\item On admet que, pour tout entier naturel $n$ non nul,
\[
M^n=\frac{1}{16}\begin{pmatrix}
9+7\times\np{0,2}^n&9-9\times\np{0,2}^n\\
7-7\times\np{0,2}^n&7+9\times\np{0,2}^n
\end{pmatrix}.
\]
\begin{enumerate}
\item
Démontrer que pour tout entier naturel $n$, $P_n = M^nP_0$.
\item Justifier que, pour tout entier naturel $n$:
\[
\ell_n =\frac{9}{16}-\frac{13}{80}\times\np{0,2}^n.
\]
\end{enumerate}
\item La proportion de pêcheurs achetant la carte de pêche libre dépassera-t-elle 60~\%~?
\end{enumerate}
%%%%%%%%%%%%   fin Antilles--Guyane 19 juin 2018
\newpage
%%%%%%%%%%%%   Polynésie 20 juin 2018
\hypertarget{Polynesie}{}

\label{Polynesie}

\textbf{\large Polynésie 20 juin 2018}

\medskip

Un atome d'hydrogène peut se trouver dans deux états différents, l'état stable et l'état excité. À chaque nanoseconde, l'atome peut changer d'état.

\bigskip

\textbf{Partie A - Étude d'un premier milieu}

\medskip

Dans cette partie, on se place dans un premier milieu (milieu 1) où, à chaque nanoseconde, la probabilité qu'un atome passe de l'état stable à l'état excité est $0,005$, et la probabilité qu'il passe de l'état excité à l'état stable est $0,6$.\index{probabilité}

On observe un atome d'hydrogène initialement à l'état stable.

On note $a_n$ la probabilité que l'atome soit dans un état stable et $b_n$ la probabilité qu'il se trouve dans un état excité, $n$ nanosecondes après le début de l'observation.

On a donc $a_0 = 1$ et $b_0 = 0$.

On appelle $X_n$ la matrice ligne $X_n = \begin{pmatrix}a_n& b_n\end{pmatrix}$.\index{matrice}

L'objectif est de savoir dans quel état se trouvera l'atome d'hydrogène à long terme.

\medskip

\begin{enumerate}
\item Calculer $a_1$ puis $b_1$ et montrer que $a_2 = \np{0,993025}$ et $b_2 = \np{0,006975}$.
\item Déterminer la matrice $A$ telle que, pour tout entier naturel $n$,\: $X_{n+1} = X_n A$.

$A$ est appelée matrice de transition dans le milieu 1.\index{matrice de transition}

On admet alors que, pour tout entier naturel $n$,\: $X_n = X_0A^n$.

\item On définit la matrice $P$ par $P = \begin{pmatrix}1&-1\\ 1&120\end{pmatrix}$.

On admet que $P$ est inversible et que
\[P^{-1} = \dfrac{1}{121}\begin{pmatrix}120&1\\- 1&1\end{pmatrix}.\]

Déterminer la matrice $D$ définie par $D = P^{-1} AP$.
\item Démontrer que, pour tout entier naturel $n$,\: $A^n = P D^n P^{-1}$.
\item On admet par la suite que, pour tout entier naturel $n$,

\[A^n = \dfrac{1}{121}\begin{pmatrix}120 + 0,395^n&1 - 0,395^n\\120\left(1 - 0,395^n\right)&1 + 120 \times 0,395^n\end{pmatrix}.\]

En déduire une expression de $a_n$ en fonction de $n$.
\item Déterminer la limite de la suite $\left(a_n\right)$. Conclure.\index{limite de suite}
\end{enumerate}

\bigskip

\textbf{Partie B - Étude d'un second milieu}

\medskip

Dans cette partie, on se place dans un second milieu (milieu 2), dans lequel on ne connaît pas la probabilité que l'atome passe de l'état excité à l'état stable. On note $a$ cette probabilité supposée constante. On sait, en revanche, qu'à chaque nanoseconde, la probabilité qu'un atome passe de l'état stable à l'état excité est $0,01$.

\medskip

\begin{enumerate}
\item Donner, en fonction de $a$, la matrice de transition $M$ dans le milieu 2.\index{matrice de transition}
\item Après un temps très long, dans le milieu 2, la proportion d'atomes excités se stabilise autour de 2\,\%.

On admet qu'il existe un unique vecteur $X$, appelé état stationnaire, tel que $XM = X$, et que $X = \begin{pmatrix}0,98& 0,02\end{pmatrix}$.

Déterminer la valeur de $a$.
\end{enumerate}
%%%%%%%%%%%%   fin Polynésie 20 juin 2018
\newpage
%%%%%%%%%%%%   Asie 21 juin 2018
\hypertarget{Asie}{}

\label{Asie}

\textbf{\large Asie 21 juin 2018}

\medskip

On s'intéresse à la figure suivante, dans laquelle $a$, $b$ et $c$ désignent les longueurs des hypoténuses des trois triangles rectangles en O dessinés ci-dessous.\index{géométrie plane}

\begin{center}
\psset{unit=3cm}
\begin{pspicture}(-0.2,-0.8)(3.4,1)
\pspolygon(0,0)(1,0)(0,1)
\psline(1,0)(1.3,0)\psline(1.7,0)(2.1,0)\psline(2.1,0)(2.4,0)
\psline(2.7,0)(3.2,0)
\psline(0,1)(2.1,0)\psline(0,1)(3.2,0)
\psframe(0.1,0.1)
\psline[linestyle=dashed](1,0)(1,-0.2)\psline{<->}(0,-0.2)(1,-0.2)\uput[u](0.5,-0.2){1}
\psline[linestyle=dashed](2.1,0)(2.1,-0.4)\psline{<->}(0,-0.4)(2.1,-0.4)\uput[u](1.05,-0.4){$u$}
\psline[linestyle=dashed](3.2,0)(3.2,-0.6)\psline{<->}(0,-0.6)(3.2,-0.6)\uput[u](1.6,-0.6){$v$}
\uput[ur](0.5,0.5){$a$}\uput[ur](1.3,0.45){$b$}\uput[ur](1.85,0.5){$c$}
\psline[linestyle=dashed](0,0)(-0.2,0)\psline[linestyle=dashed](0,1)(-0.2,1)
\psline{<->}(-0.2,0)(-0.2,1)\uput[l](-0.2,0.5){1}
\psline[linestyle=dashed](1.2,0)(1.7,0)
\psline[linestyle=dashed](2.4,0)(2.7,0)
\psline[linestyle=dashed](0,0)(0,-0.6)
\end{pspicture}
\end{center}

\textbf{Problème :} on cherche les couples de \textbf{nombres entiers naturels non nuls} $(u,~v)$ tels que $ab = c$.

\medskip

\begin{enumerate}
\item Modélisation

Démontrer que les solutions du problème sont des solutions de l'équation :

\[(E) :\quad  v^2 - 2u^2 = 1\quad  (v \text{ et }\: u \: \text{ étant des entiers naturels non nuls}).\]

\item  Recherche systématique de solutions de l'équation $(E)$

Recopier et compléter l'algorithme suivant pour qu'il affiche au cours de son exécution tous les couples solutions de l'équation pour lesquels $1 \leqslant u \leqslant \np{1000}$ et $1 \leqslant v \leqslant \np{1000}$.

\begin{center}
\begin{tabularx}{\linewidth}{|X|m{4.5cm}|}\hline
Pour $u$ allant de 1 à \ldots faire&Au cours de son exécution,\\
\hspace{0.5cm}Pour \ldots&l'algorithme affiche :\\
\hspace{1cm}Si \ldots&2 \quad 3\\
\hspace{1.5cm}Afficher $u$ et $v$&12 \quad 17\\
\hspace{1cm}Fin Si&70 \quad 99\\
\hspace{0.5cm}Fin Pour&408 \quad 577\\
Fin Pour&\\ \hline
\end{tabularx}
\end{center}

\item Analyse des solutions éventuelles de l'équation $(E)$

On suppose que le couple $(u,~v)$ est une solution de l'équation $(E)$.
	\begin{enumerate}
		\item Établir que $u < v$.
		\item  Démontrer que $n$ et $n^2$ ont la même parité pour tout entier naturel $n$.

		\item  Démontrer que $v$ est un nombre impair.
		\item  Établir que $2u^2 =(v-1)(v+1)$.
		
En déduire que $u$ est un nombre pair.
	\end{enumerate}
\item  Une famille de solutions
	
On assimile un couple de nombres entiers $(u,~v)$ à la matrice colonne $X = \begin{pmatrix}u\\v\end{pmatrix}$.
	
On définit également la matrice $A = \begin{pmatrix}3&2\\4&3\end{pmatrix}$.\index{matrice}
	\begin{enumerate}
		\item Démontrer que si une matrice colonne $X$ est une solution de l'équation $(E)$, alors $AX$ est aussi une solution de l'équation $(E)$.
		\item Démontrer que si une matrice colonne $X$ est une solution de l'équation $(E)$, alors pour tout entier naturel $n$,\: $A^n X$ est aussi une solution de l'équation $(E)$.
		\item À l'aide de la calculatrice, donner un couple $(u,~v)$ solution de l'équation $(E)$ tel que
		
 $v > \np{10000}$.
	\end{enumerate}
\end{enumerate}
%%%%%%%%%%%%   fin Asie 21 juin 2018
\newpage
%%%%%%%%%%%%   Métropole--La Réunion 22 juin 2018
\hypertarget{Metropole}{}

\label{Metropole}
\textbf{\large Métropole--La Réunion 22 juin 2018}

\medskip

\textbf{Partie A}

\medskip

On considère l'équation suivante dont les inconnues $x$ et $y$ sont des entiers naturels :

\[x^2 - 8y^2 = 1 . \quad(E)\]

\medskip

\begin{enumerate}
\item Déterminer un couple solution $(x~;~y)$ où $x$ et $y$ sont deux entiers naturels.
\item On considère la matrice $A = \begin{pmatrix}3&8\\1&3\end{pmatrix}$.\index{matrice}

On définit les suites d'entiers naturels $\left(x_n\right)$ et $\left(y_n\right)$ par :

\[x_0 = 1,\: y_0 = 0,\: \text{et pour tout entier naturel }\:n,\: \begin{pmatrix}x_{n+1}\\y_{n+1}\end{pmatrix} = A\begin{pmatrix}x_{n}\\y_{n}\end{pmatrix}.\]
	\begin{enumerate}
		\item Démontrer par récurrence que pour tout entier naturel $n$, le couple 
		$\left(x_n~;~y_n\right)$ est solution de l'équation $(E)$.\index{démonstration par récurrence}
		\item En admettant que la suite $\left(x_n\right)$ est à valeurs strictement positives, démontrer que pour tout entier naturel $n$, on a : $x_{n+1} > x_n$.
 	\end{enumerate}
\item  En déduire que l'équation $(E)$ admet une infinité de couples solutions.
\end{enumerate}

\bigskip

\textbf{Partie B}

\medskip

Un entier naturel $n$ est appelé un nombre puissant lorsque, pour tout diviseur premier $p$ de $n$,\: $p^2$ divise $n$.\index{nombre premier}

\medskip

\begin{enumerate}
\item Vérifier qu'il existe deux nombres entiers consécutifs inférieurs à $10$ qui sont puissants.
\end{enumerate}
\medskip

L'objectif de cette partie est de démontrer, à l'aide des résultats de la partie A, qu'il existe une infinité de couples de nombres entiers naturels consécutifs puissants et d'en trouver quelques exemples.

\medskip

\begin{enumerate}[resume]
\item  Soient $a$ et $b$ deux entiers naturels.

Montrer que l'entier naturel $n = a^2 b^3$ est un nombre puissant.
\item  Montrer que si $(x~;~y)$ est un couple solution de l'équation $(E)$ définie dans la partie A, alors $x^2 - 1$ et $x^2$ sont des entiers consécutifs puissants.
\item  Conclure quant à l'objectif fixé pour cette partie, en démontrant qu'il existe une infinité de couples de nombres entiers consécutifs puissants.

Déterminer deux nombres entiers consécutifs puissants supérieurs à $2018$.
\end{enumerate}
%%%%%%%%%%%%   fin Métropole--La Réunion 22 juin 2018
\newpage
%%%%%%%%%%%%   Antilles-Guyane 6 septembre 2018
\hypertarget{Antillessep}{}

\label{Antillessep}
\textbf{\large Antilles--Guyane  6 septembre 2018}

\medskip

\begin{enumerate}
\item Démontrer que, pour tout entier naturel $n$ non nul, $u_n$ et $u_{n+1}$ sont premiers entre eux.\index{nombre premier}
\item Démontrer que les termes de la suite $\left(u_n\right)$ sont alternativement pairs et impairs.
\item L'affirmation suivante est-elle vraie ? Justifier.

Affirmation: \og Si $p$ est un nombre premier impair, alors $u_p$ est premier. \fg
\item 
	\begin{enumerate}
		\item Démontrer par récurrence que, pour tout entier naturel $n$,\: $2u_n = 3^n - 1$.\index{démonstration par récurrence}
		\item Déterminer le plus petit entier naturel non nul $n$ tel que $3^n$ est congru à 1 modulo 7.\index{congruence}
		\item En déduire que $u_{\np{2022}}$ est divisible par $7$.
 	\end{enumerate}
\item 
	\begin{enumerate}
		\item Calculer le reste de la division euclidienne par 5 de chacun des cinq premiers
termes de la suite $\left(u_n\right)$.\index{division euclidienne}
		\item Sans justification, recopier et compléter le tableau suivant :
		
\begin{center}
\begin{tabularx}{\linewidth}{|l|*{5}{>{\centering\arraybackslash}X|}}\hline	
Reste de la division euclidienne de $m$ par 5 	&0 	&1 	&2 	&3 	&4\\ \hline
Reste de la division euclidienne de $3m + 1$ par 5&	&	&	&	&\\ \hline
\end{tabularx}
\end{center}

		\item En déduire que, pour tout entier naturel $n$, si $u_n$ est congru à 4 modulo 5, alors $u_{n+4}$ est congru à 4 modulo 5.
		\item Existe-t-il un entier naturel $n$ tel que le reste de la division euclidienne de $u_n$ par 5 soit égal à 2 ?
	\end{enumerate}
\end{enumerate}
%%%%%%%%%%%%   fin Antilles-Guyane 6 septembre 2018
\newpage
%%%%%%%%%%%%   Métropole--La Réunion 13 septembre 2018
\hypertarget{Metropolesep}{}

\label{Metropolesep}
\textbf{\large Métropole--La Réunion  13 septembre 2018}

\medskip
\begin{center}
\textbf{Partie A}
\end{center}

\smallskip

On considère la suite $\left(u_n\right)$ définie par : $u_0 = 1$,\: $u_1 = 6$ et, pour tout entier naturel $n$ :

\[u_{n+2} = 6u_{n+1} - 8u_n.\]\index{suite}

\begin{enumerate}
\item Calculer $u_2$ et $u_3$ .
\item On considère la matrice $A = \begin{pmatrix}0&1\\-8&6\end{pmatrix}$ et la matrice colonne $U_n = \begin{pmatrix}u_n\\u_{n+1}\end{pmatrix}$.\index{matrice}

Montrer que, pour tout entier naturel $n$, on a : $U_{n+1} = AU_n$.
\item On considère de plus les matrices $B = \begin{pmatrix}2&-0,5\\4&- 1\end{pmatrix}$ et $C = \begin{pmatrix}- 1&0,5\\- 4&2\end{pmatrix}$.
	\begin{enumerate}
		\item Montrer par récurrence que, pour tout entier naturel $n$, on a : $A^n = 2^nB + 4^nC$.\index{démonstration par récurrence}
		\item On admet que, pour tout entier naturel $n$, on a : $U_n = A^nU_0$.
		
Montrer que, pour tout entier naturel $n$, on a : $u_n = 2 \times 4^n - 2^n$.
 	\end{enumerate}
\end{enumerate}

\begin{center}
\textbf{Partie B}
\end{center}

\smallskip

On dit qu'un entier naturel $N$ est parfait lorsque la somme de ses diviseurs (positifs) est égale à $2N$.

Par exemple, 6 est un nombre parfait car ses diviseurs sont 1, 2, 3 et 6 et on a : $1 + 2 + 3 + 6 = 12 = 2 \times 6$.

Dans cette partie, on cherche des nombres parfaits parmi les termes de la suite $\left(u_n\right)$ étudiée dans la partie A.

\medskip

\begin{enumerate}
\item Vérifier que, pour tout entier naturel $n$, on a : $u_n = 2^np_n$ avec $p_n = 2^{n+1} - 1$.
\item On considère l'algorithme suivant où $N$, $S$, $U$, $P$ et $K$ sont des entiers naturels.

\begin{center}
\begin{tabularx}{0.6\linewidth}{|X|}\hline
$S \gets 0$\\
~\\
Demander à l'utilisateur la valeur de $N$\\
$P \gets 2^{N+1} - 1$\\
$U \gets 2^N P$\\
~\\
Pour $K$ variant de $1$ à $U$\\
\hspace{0.6cm}Si $\frac{U}{K}$ est un nombre entier\\
\hspace{1.1cm}$S \gets S + K$\\
\hspace{0.6cm}Fin Si\\
Fin Pour\\
~\\
Si $S = 2U$\\
\hspace{0.6cm}Afficher \og oui \fg\\
Sinon\\
\hspace{0.6cm}Afficher \og non \fg\\
Fin Si\\ \hline
\end{tabularx}
\end{center}\index{algorithme}

	\begin{enumerate}
		\item À quelle question permet de répondre cet algorithme ?
		
Compléter, sans justification, les cases vides du tableau donné en annexe. Il n'est pas demandé au candidat de programmer l'algorithme.
		\item Faire une conjecture donnant une condition suffisante sur $P$ pour que l'algorithme affiche \og oui \fg.
 	\end{enumerate}
\item  Dans cette question, on suppose que $p_n$ est un nombre premier. On note $S_n$ la somme des diviseurs de $u_n$.\index{nombre premier}
	\begin{enumerate}
		\item Montrer que $S_n = \left(1 + p_n\right)p_n$.
		\item En déduire que $u_n$ est un nombre parfait.
	\end{enumerate}
\end{enumerate}

\newpage

\begin{center}
\textbf{\large  Annexe à remettre avec la copie}

\vspace{3cm}


\textbf{Exercice 4}

\vspace{1cm}

\textbf{Affichage de l'algorithme pour les premières valeurs de $N$}

\vspace{1cm}

\begin{tabularx}{\linewidth}{|*{5}{>{\centering \arraybackslash}X|}}\hline
$N$	&$P$	&$U$		&$S$		&Affichage final\\ \hline
0 	&1 		&1 			&1 			&non\\ \hline
1 	&3 		&6 			&12 		&oui\\ \hline
2 	&7 		&			&			&\\ \hline
3 	&15 	&			&360		&\\ \hline
4 	&31		&			&992		& oui\\ \hline
5 	&63 	&			&\np{6552}	& non\\ \hline
6 	&127	&\np{8128}	&\np{16256}	&\\ \hline
\end{tabularx}
\end{center}
%%%%%%%%%%%%   fin Métropole--La Réunion 13 septembre 2018
\newpage
%%%%%%%%%%%%   Amérique du Sud 12 novembre 2018
\hypertarget{AmeriSud}{}

\label{AmeriSud}
\textbf{\large Amérique du Sud 12  novembre 2018}

\medskip

Pour tout entier naturel $n$ , on note $F_n$ le $n$-ième nombre de Fermat. Il est défini par

\[F_n = 2^{2^n} + 1.\]

\smallskip

\textbf{Partie A :}

\medskip

Pierre de Fermat, leur inventeur, a conjecturé que :
\begin{center}
\og Tous les nombres de Fermat sont premiers \fg,\end{center}\index{nombre premier}

L'objectif est de tester cette conjecture.

\medskip

\begin{enumerate}
\item 
	\begin{enumerate}
		\item Calculer $F_0$, $F_1$, $F_2$ et $F_3$.
		\item Peut-on en déduire que tous les nombres de Fermat sont premiers ?
	\end{enumerate}
\item On considère l'algorithme ci-dessous:\index{algorithme}

\parbox{0.48\linewidth}{
\begin{center}
\begin{tabularx}{0.8\linewidth}{|X|}\hline	
$F \gets  2^{2^5} + 1$\rule[-3mm]{0mm}{8mm}\\
$N \gets 2$\\
Tant que $F\%N \ne 0$\\
\hspace{0,5cm}$N \gets N + 1$\\
Fin Tant que\\
Afficher $N$\\ \hline
\end{tabularx}
\end{center}}\hfill
\parbox{0.48\linewidth}{
\psset{unit=1cm}
\begin{pspicture}(6,2)
\psframe[linestyle=dashed,linewidth=1pt](0.25,0.25)(6,1.35)
\rput(3,1){$F\%N$ désigne le reste de la division}
\rput(3,0.5){euclidienne de $F$ par $N$.}
\end{pspicture}
%\begin{tabular}{c}\hdashline
%$F\%N$ désigne le reste de la division\\
%euclidienne de $F$ par $N$.\\ \hdashline
%\end{tabular}
}

La valeur affichée à la fin de l'exécution est 641.

Que peut-on en déduire ?
\end{enumerate}

\medskip

\textbf{Partie B :}

\medskip

L'objectif est de prouver que deux nombres de Fermat distincts sont toujours premiers entre eux.

\medskip

\begin{enumerate}
\item Démontrer que pour tout entier naturel $n$ non nul on a $F_n = \left(F_{n-1}  - 1\right)^2  + 1$.
\item Pour tout entier naturel $n$ on note :

\[\displaystyle\prod_{i=0}^n F_i = F_0 \times F_1 \times F_2 \times \ldots \times F_{n-1} \times F_n.\]

On a donc $\displaystyle\prod_{i=0}^{n} F_i = \left(\prod_{i=0}^{n-1} F_i\right) \times F_n$.

Montrer par récurrence et en utilisant le résultat de la question précédente que pour tout entier naturel $n$ non nul on a :\index{démonstration par récurrence}

\[\displaystyle\prod_{i=0}^{n-1} F_i = F_n - 2.\]

\item Justifier que, pour tous entiers naturels $n$ et $m$ tels que $n > m$, il existe un entier naturel $q$ tel que $F_n - qF_m = 2$.
\item En déduire que deux nombres de Fermat sont toujours premiers entre eux.
\end{enumerate}
%%%%%%%%%%%%   fin Amérique du Sud 12 novembre 2018
\newpage
%%%%%%%%%%%%   Nouvelle Calédonie 27 novembre 2018
\hypertarget{Caledonienov}{}

\label{Caledonienov}
\textbf{\large Nouvelle Calédonie 27 novembre 2018}

\medskip
On appelle suite de Fibonacci la suite $\left(u_n\right)$ définie par $u_0=0$, $u_1=1$ et, pour tout entier naturel $n$,

\[u_{n+2} = u_{n+1} + u_{n}.\]

On admet que, pour tout entier naturel $n$, $u_n$ est un entier naturel.

\smallskip

\emph{Les parties \emph{A} et \emph{B} peuvent être traitées de façon indépendante.}

\bigskip

\textbf{Partie A}

\medskip

\begin{enumerate}
\item 
	\begin{enumerate}
		\item Calculer les termes de la suite de Fibonacci jusqu'à $u_{10}$.
		\item Que peut-on conjecturer sur le PGCD de $u_{n}$ et $u_{n+1}$ pour tout entier naturel $n$?\index{PGCD}
	\end{enumerate}

\item On définit la suite $\left(v_n\right)$ par $v_n = u_n^2 - u_{n+1}\times u_{n-1}$ pour tout entier naturel $n$ non nul.
	\begin{enumerate}
		\item Démontrer que, pour tout entier naturel $n$ non nul, $v_{n+1} = -v_n$.
		\item En déduire que, pour tout entier naturel $n$ non nul,

\[u_n^2 - u_{n+1}\times u_{n-1} = \left (-1\right )^{n-1}.\]

		\item Démontrer alors la conjecture émise à la question \textbf{1. b.}
	\end{enumerate}
\end{enumerate}

\bigskip

\textbf{Partie B}

\medskip

On considère la matrice
$F=\begin{pmatrix} 1 & 1 \\ 1 & 0\end{pmatrix}$.\index{matrice}

\begin{enumerate}
\item Calculer $F^2$ et $F^3$. On pourra utiliser la calculatrice.
\item Démontrer par récurrence que, pour tout entier naturel $n$ non nul,

\[F^n = \begin{pmatrix} u_{n+1} & u_n \\ u_n & u_{n-1} \end{pmatrix}\]\index{matrice}

\item 
\begin{enumerate}
\item Soit $n$ un entier naturel non nul. En remarquant que
$F^{2n+2} = F^{n+2}\times F^{n}$, démontrer que

\[u_{2n+2} =u_{n+2}\times u_{n+1}+ u_{n+1}\times u_n.\]

\item En déduire que, pour tout entier naturel $n$ non nul,

\[u_{2n+2} = u_{n+2}^2 - u_n^2.\]
\end{enumerate}

\item On donne $u_{12}=144$.

Démontrer en utilisant la question \textbf{3.} qu'il existe un triangle rectangle dont les longueurs des côtés sont toutes des nombres entiers, l'une étant égale à 12.

Donner la longueur des deux autres côtés.
\end{enumerate}
%%%%%%%%%%%%   fin Nouvelle Calédonie 27 novembre 2018
\hypertarget{Index}{}
\setlength{\columnsep}{1.5cm}
\printindex
\end{document}