\documentclass[11pt]{article} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc}%ATTENTION codage en utf8 ! \usepackage{fourier} \usepackage[scaled=0.875]{helvet} \renewcommand{\ttdefault}{lmtt}\usepackage{amsmath,amssymb,makeidx} \usepackage{fancybox} \usepackage{amsmath, amssymb, amsthm} \usepackage[normalem]{ulem} \usepackage{pifont} \usepackage{textcomp} \usepackage{array} \usepackage{booktabs} \newcommand{\euro}{\eurologo{}} %Tapuscrit : Denis Vergès \usepackage{pst-plot,pst-text,pst-tree} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\D}{\mathbb{D}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\C}{\mathbb{C}} % Raccourcis \newcommand{\ZnZ}{\Z/n\Z} \newcommand{\ZpZ}{\Z/p\Z} \newcommand{\pgcd}{\mathrm{PGCD}} \usepackage[left=3.5cm, right=3.5cm, top=2cm, bottom=3cm]{geometry} \newcommand{\vect}[1]{\overrightarrow{\,\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{enumitem} \newcommand{\e}{\text{e}} \usepackage[french]{babel} \usepackage[np]{numprint} \begin{document} \setlength\parindent{0mm} \rhead{\small A. P. M. E. P.} \lhead{\small CAPES externe} \lfoot{\small{épreuve 2}} \rfoot{\small{CAPES 2003}} \pagestyle{fancy} \thispagestyle{empty} \begin{center} \vspace{0,5cm} {\Large \textbf{\decofourleft~CAPES externe 2003 ~\decofourright}} \medskip \textbf{\large Deuxième épreuve écrite} %-------------------------------------------------------------- % Page de garde %-------------------------------------------------------------- {\large \textbf{section : mathématiques}} \vspace{0.5cm} {\large \textbf{Durée : 5 heures}} \end{center} \vspace{0.5cm} \noindent\fbox{\begin{minipage}{0.97\textwidth} \textit{Calculatrice électronique de poche -- y compris programmable, alphanumérique ou à écran graphique -- à fonctionnement autonome, non imprimante, autorisée conformément à la circulaire n°\,99-186 du 16 novembre 1999.}\\ \textit{Tout document et tout autre matériel électronique sont interdits.} \end{minipage}} \vspace{0.7cm} \noindent\textit{La qualité de la rédaction, la clarté et la précision des raisonnements interviendront pour une part importante dans l'appréciation des copies. Les résultats indiqués dans l'énoncé peuvent être utilisés par les candidats pour la suite du problème.} \noindent\textit{Les candidats doivent reporter sur leur copie, devant leurs réponses, la numérotation complète des questions de l'énoncé.} \noindent\textit{Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il le signale dans sa copie et poursuit sa composition en indiquant les initiatives qu'il est amené à prendre de ce fait.} %-------------------------------------------------------------- % Notations %-------------------------------------------------------------- \newpage \section*{Notations, rappels et présentation du problème.} L'ensemble des entiers naturels sera noté $\N$, celui des entiers relatifs $\Z$. On notera $(\ZnZ)^*$ l'ensemble des éléments de $\ZnZ$ inversibles pour la multiplication. Etant donnés deux entiers relatifs $a$ et $b$, le plus grand diviseur commun de $a$ et $b$ sera noté $\pgcd(a,b)$ ou $a \wedge b$. On rappelle que $a \wedge 0 = a$. $a$ est dit premier avec $b$ si $a \wedge b = 1$. $a \equiv b \bmod n$ signifie que $a$ est congru à $b$ modulo $n$, c'est-à-dire que $n$ divise $(b-a)$. Un groupe $(G, \times)$ est dit cyclique s'il existe un élément $a$ de $G$ et un entier naturel $p$ tel que $G = \{1, a, a^2, a^3, \ldots, a^p\}$, où $a^k = a \times a \times \cdots \times a$ ($k$ termes) ; $a$ est alors un générateur de $(G, \times)$. Pour un entier naturel $n$ supérieur ou égal à 2, on notera respectivement : \begin{itemize} \item $S_n$ l'ensemble des entiers strictement positifs, inférieurs ou égaux à $n$, et premiers avec $n$. \item $D_n$ l'ensemble des diviseurs de $n$, entiers positifs (en particulier, 1 appartient à $D_n$). \end{itemize} La notation $\displaystyle\sum_{d \in D_n}$ désignera une somme étendue à tous les éléments $d$ de $D_n$. Enfin on notera $\phi(n)$ le cardinal de $S_n$. \bigskip La première partie du problème a pour but d'établir une identité due à Euler concernant la fonction $\phi$, à l'aide d'un raisonnement probabiliste. Dans la deuxième partie, on étudie le groupe des éléments inversibles pour la multiplication dans $\ZnZ$, et on montre que, si $n$ n'a qu'un seul diviseur premier, alors ce groupe est cyclique. La troisième partie introduit la notion de nombres pseudo-premiers forts et se propose d'en donner une caractérisation algorithmique sur une calculatrice programmable. Enfin, la quatrième partie a pour objet l'étude de nombres appelés nombres de Carmichaël, présentant des similarités avec les nombres premiers, et se termine par la présentation d'un test probabiliste pour la détection de nombres premiers. %-------------------------------------------------------------- % Partie I %-------------------------------------------------------------- \newpage \section*{Partie I} \begin{enumerate} \item On considère dans cette question un univers probabilisé $(\Omega, B, P)$. L'évènement contraire d'un évènement $E$ sera noté $\overline{E}$. \begin{enumerate}[label=(\alph*)] \item Soient $A_1$ et $A_2$ deux évènements indépendants de cet univers : montrer que $\overline{A_1}$ et $A_2$ sont indépendants. \item Généralisation : soit $k$ un entier naturel non nul et $A_1, A_2, \ldots A_k$ $k$ évènements mutuellement indépendants de $\Omega$. \begin{enumerate}[label=(\roman*)] \item Montrer que $\overline{A_1}, A_2, \ldots A_k$ sont indépendants. \item Montrer par récurrence que $\overline{A_1}, \overline{A_2}, \ldots \overline{A_k}$ sont indépendants. \end{enumerate} \end{enumerate} \bigskip Dans toute la suite de cette partie, $n$ désigne un entier naturel supérieur ou égal à 2 et $X$ une variable aléatoire sur $\Omega$, prenant ses valeurs dans l'ensemble $\{1, \ldots, n\}$ de manière équiprobable, c'est-à-dire telle que pour tout $i = 1, \ldots, n$ on a $P(X = i) = \dfrac{1}{n}$. \item On considère l'évènement $A_1$ : \og $X$ est multiple de 2 \fg{} et l'évènement $A_2$ : \og $X$ est multiple de 5 \fg. \begin{enumerate}[label=(\alph*)] \item On suppose que $n = 100$. Calculer les probabilités des évènements $A_1$ et $A_2$. $A_1$ et $A_2$ sont-ils indépendants ? \item On suppose maintenant que $n = 101$. Reprendre les questions du (a) dans ce cas. \end{enumerate} \item On suppose que la décomposition en facteurs premiers de $n$ s'écrit $n = \displaystyle\prod_{i=1}^{k} p_i^{\alpha_i}$, où les $\alpha_i$ sont des entiers supérieurs ou égaux à 1.\\ Enfin, pour $i$ entier naturel, $1 \leqslant i \leqslant k$, $A_i$ désigne l'évènement \og $X$ est divisible par $p_i$\fg. \begin{enumerate}[label=(\alph*)] \item Soit $A$ l'évènement : \og $X$ est premier avec $n$\fg{} ; exprimer $P(A)$ à l'aide de $n$ et de $\phi(n)$. \item Montrer que $P(A_i) = \dfrac{1}{p_i}$ pour tout entier $i$, $1 \leqslant i \leqslant k$. \item Montrer que les $(A_i)_{1 \leqslant i \leqslant k}$ sont mutuellement indépendants. \item Exprimer $A$ à l'aide des $\overline{A_i}$. \item En déduire que \[\phi(n) = n \prod_{i=1}^{k} \left(1 - \frac{1}{p_i}\right) \tag{E}\] \end{enumerate} \item On se propose de retrouver l'égalité précédente (E) par une autre méthode : soient $p$ et $q$ deux entiers naturels premiers entre eux ; On considère l'application \[h : \begin{cases} S_{pq} \to \{0, \ldots, p-1\} \times \{0, \ldots, q-1\} \\ r \mapsto (a, b) \end{cases}\] où $a$ (resp. $b$) est le reste de la division de $r$ par $p$ (resp. par $q$). \begin{enumerate}[label=(\alph*)] \item Montrer que $h(S_{pq})$ est inclus dans $S_p \times S_q$. \item Montrer que $h$ est injective. \item Justifier l'existence de deux entiers $\alpha$ et $\beta$ de $\Z$ tels que $\alpha p + \beta q = 1$. Soit $(a,b)$ un couple de $S_p \times S_q$. On note $x = \alpha p b + \beta q a$ ; montrer que $x \equiv a \bmod p$ et que $x \equiv b \bmod q$. En déduire que l'image de $h$ est $S_p \times S_q$, puis que $\phi(pq) = \phi(p)\phi(q)$. \item À l'aide d'une récurrence sur le nombre de diviseurs premiers de $n$, retrouver alors l'égalité (E). \end{enumerate} \item Identité d'Euler : \begin{enumerate}[label=(\alph*)] \item Soit $d$ un diviseur de $n$ et $a$ un entier naturel non nul ; montrer que $\pgcd(a, n) = d$ si, et seulement si, il existe un entier $k$ premier avec $\dfrac{n}{d}$ tel que $a = kd$. En déduire le nombre des entiers $a$ tels que $1 \leqslant a \leqslant n$ et $\pgcd(a, n) = d$. \item Pour tout entier $d$ diviseur de $n$, on note $C_d$ l'évènement ``$\pgcd(X,n)=d$''. Exprimer $P(C_d)$ à l'aide de $n$, $d$ et de la fonction $\phi$. \item En déduire que $\displaystyle\sum_{d \in D_n} \frac{1}{n}\,\phi\!\left(\frac{n}{d}\right) = 1$ \quad (rappel : $D_n$ note l'ensemble des diviseurs de $n$ dans $\N$). \item Montrer que l'application $u$ qui, à tout diviseur $d$ de $n$ associe $u(d)=\dfrac{n}{d}$ est une bijection de $D_n$ dans lui-même. Montrer que $\displaystyle\sum_{d \in D_n} \phi(d) = n$ \quad (identité d'Euler). \end{enumerate} \end{enumerate} %-------------------------------------------------------------- % Partie II %-------------------------------------------------------------- \newpage \section*{Partie II} $n$ étant toujours un entier supérieur ou égal à 2, l'objet de cette partie est l'étude du groupe noté $\bigl((\ZnZ)^*, \times\bigr)$ des éléments de $\ZnZ$ inversibles pour la multiplication. On rappelle que cet ensemble est composé des classes modulo $n$ des nombres premiers avec $n$. On pourra donc remarquer que $\phi(n) = \mathrm{card}\bigl((\ZnZ)^*\bigr)$. La classe d'un entier $a$ sera notée $\dot{a}$. \subsection*{A) Des résultats généraux sur les groupes et les anneaux.} \begin{enumerate} \item Soient $a$ et $b$ deux éléments d'un anneau commutatif $(A,+,\times)$ et $n$ un entier naturel non nul. Montrer que $b^n - a^n$ est divisible par $b - a$.\\ Donner le quotient de $b^n - a^n$ par $b-a$ sous forme de somme. \item Montrer que $(\ZnZ, +, \times)$ est un corps si, et seulement si, $n$ est premier. \item Factorisation de polynômes. \begin{enumerate}[label=(\alph*)] \item Soit $P$ un polynôme de degré $k$ supérieur ou égal à 1, à coefficients dans $\ZnZ$, où $n$ est un entier premier. Montrer que $P$ admet au plus $k$ racines (on pourra raisonner par récurrence sur $k$). \item Déterminer, dans $\Z/6\Z$, les racines du polynôme $P(X)=X^2-X$. Que peut-on en conclure ? \item Trouver, dans $\Z/6\Z\,[X]$, deux factorisations distinctes de $X^2-X$ sous la forme $(X-\dot{a})(X-\dot{b})$. \end{enumerate} \item On rappelle que si $x$ est élément d'un groupe fini $G$, l'ordre de $x$ est le plus petit entier naturel $k$ non nul tel que $x^k = 1$, où $1$ désigne l'élément neutre de $G$. \begin{enumerate}[label=(\alph*)] \item Soit $x$ un élément de $G$, groupe fini de cardinal $n$ ; montrer que, si $k$ est l'ordre de $x$, alors l'ensemble $\{1, x, \ldots, x^{k-1}\}$ est un sous-groupe de $G$. En déduire que l'ordre de $x$ divise le cardinal de $G$, et que $x^n = 1$. \item Si $p$ est un entier naturel premier et $x$ un entier naturel non divisible par $p$, montrer que $x^{p-1} - 1$ est divisible par $p$. \end{enumerate} \end{enumerate} \subsection*{B) Étude du groupe $\bigl((\ZnZ)^*, \times\bigr)$ quand $n$ est premier.} On suppose dans cette sous-partie que $n$ est un entier premier supérieur ou égal à 3. Si $d$ est un entier naturel non nul et strictement inférieur à $n$, on note $\zeta(d)$ le nombre des éléments de $\bigl((\ZnZ)^*, \times\bigr)$ d'ordre $d$. \medskip \begin{enumerate} \item Montrer que $\displaystyle\sum_{d \in D_{n-1}} \zeta(d) = n-1$. \item Soit $d$ un diviseur de $n-1$ et soit $\dot{a}$ un élément de $\bigl((\ZnZ)^*, \times\bigr)$ d'ordre $d$, s'il existe. $\dot{a}$ vérifie ainsi $\dot{a}^d = \dot{1}$. \begin{enumerate}[label=(\alph*)] \item Montrer que l'ensemble des racines du polynôme $X^d - \dot{1}$ est, dans $(\ZnZ)^*$, $\bigl\{\dot{1}, \dot{a}, \dot{a}^2, \dot{a}^3, \ldots, \dot{a}^{d-1}\bigr\}$. \item On suppose que $k$ est un entier naturel inférieur ou égal à $d$, non premier avec $d$. Montrer que $\dot{a}^k$ a un ordre strictement inférieur à $d$. \item En déduire que $\zeta(d) \leqslant \phi(d)$. Déduire des questions précédentes et de la première partie que $\zeta(d) = \phi(d)$ pour tout diviseur $d$ de $n-1$. Montrer en particulier qu'il existe au moins un élément $\dot{b}$ d'ordre $n-1$ dans $\bigl((\ZnZ)^*, \times\bigr)$ et que \[(\ZnZ)^* = \bigl\{\dot{1}, \dot{b}, \dot{b}^2, \ldots \dot{b}^{n-2}\bigr\}.\] \end{enumerate} \end{enumerate} \subsection*{C) Cas $n = p^\alpha$.} On suppose maintenant que $n$ s'écrit sous la forme $n = p^\alpha$, où $p$ est un entier premier, et $\alpha$ un entier naturel supérieur ou égal à 2. D'après la partie II B), il existe donc un entier $b$, dont la classe $\dot{b}$ est d'ordre $p-1$ dans $\bigl((\Z/p\Z)^*, \times\bigr)$. \medskip \begin{enumerate} \item Montrer que l'un au moins des deux entiers $b^{p-1}$ ou $(b+p)^{p-1}$ n'est pas congru à 1 modulo $p^2$ ; on notera $c$ l'un des nombres $b$ ou $b+p$ de façon à ce que $c^{p-1}$ ne soit pas congru à 1 modulo $p^2$. \item Montrer par récurrence que, pour tout entier naturel $r$, il existe un entier $k_r$ premier avec $p$ tel que \[c^{p^r(p-1)} = 1 + k_r \times p^{r+1}.\] En déduire que $\dot{c}$ appartient à $(\ZnZ)^*$. \item Soit $r$ l'ordre de $\dot{c}$ dans $\bigl((\ZnZ)^*, \times\bigr)$. \begin{enumerate}[label=(\alph*)] \item Expliquer pourquoi $r$ divise $p^{\alpha-1}(p-1)$ et pourquoi $(p-1)$ divise $r$. \item En déduire qu'il existe un entier naturel $\beta$ inférieur ou égal à $\alpha - 1$ tel que $r = p^\beta(p-1)$. \item Montrer finalement que $\beta = \alpha - 1$ et que $\dot{c}$ est un générateur de $\bigl((\ZnZ)^*, \times\bigr)$. \end{enumerate} \item Application : Déterminer un générateur de $\bigl((\Z/7\Z)^*, \times\bigr)$ puis un générateur de $\bigl((\Z/49\Z)^*, \times\bigr)$. \end{enumerate} %-------------------------------------------------------------- % Partie III %-------------------------------------------------------------- \newpage \section*{Partie III} \subsection*{Nombres pseudo-premiers forts} Dans toute cette partie, $p$ désigne un entier impair supérieur ou égal à 3, et on notera $(p-1) = q \times 2^s$, où $q$ est un entier naturel impair et $s$ un entier naturel supérieur ou égal à 1. \medskip \begin{enumerate} \item Dans cette question, on suppose $p$ premier. \begin{enumerate}[label=(\alph*)] \item Soit $a$ un entier premier avec $p$. Montrer que $a^{\frac{p-1}{2}}$ est congru à 1 ou à $p-1$ modulo $p$. \item On dit qu'un entier naturel $a$ vérifie la propriété $H_a(p)$ si : \[\bigl(a^q \equiv 1 \bmod p\bigr) \quad \text{ou} \quad \bigl(\exists\, r \text{ entier},\ 0 \leqslant r < s \text{ tel que } a^{q \times 2^r} \equiv p-1 \bmod p\bigr)\tag{$H_a(p)$}\] Montrer que tout entier naturel $a$ premier avec $p$ vérifie $H_a(p)$. \end{enumerate} \item On dit qu'un nombre $p$ impair, non nécessairement premier, est pseudo-premier fort en base $a$ si la propriété $H_a(p)$ est vérifiée ; on écrira en abrégé que $p$ est $a$-ppf. Par exemple, 25 est 7-ppf car $24 = 3 \cdot 2^3$ et $7^{3 \times 2^2} = 117649 \equiv 24 \equiv -1 \bmod 25$. Montrer que si $a$ est un entier tel que le pgcd de $a$ et $p$ est strictement plus grand que 1, alors $p$ ne peut pas être $a$-ppf. \item Construction d'un algorithme : \begin{enumerate}[label=(\alph*)] \item Un entier $p$ impair et un entier $a$ étant donnés, écrire un algorithme permettant de tester si $p$ est $a$-ppf. \textbf{N.B.} : On ne cherchera pas à écrire, pour le calcul de $a^q$ modulo $p$ un algorithme rapide de puissance, mais on pourra se contenter d'une boucle calculant $a^2$ modulo $p$, $a^3$ modulo $p$, \ldots, $a^q$ modulo $p$. Vous retranscrirez cet algorithme sur votre copie en langage algorithmique (français) ou dans le langage de votre machine, en spécifiant le modèle que vous employez. Implanter cet algorithme sur votre machine ; on peut le tester en contrôlant que tout nombre $p$ premier est $a$-ppf pour tout $a$ premier avec $p$. \item Reportez le tableau suivant sur votre copie et complétez les cases vides par \og oui\fg{} ou \og non \fg à l'aide du programme précédent. \begin{center} \begin{tabular}{|c|c|c|c|c|c|c|}\hline $p$ & 49 & 91 & 111 & 121 & 135 & 1225 \\ \hline $a$ & 30 & 74 & 28 & 94 & 43 & 999 \\ \hline $p$ est $a$-ppf & & & & & & \\ \hline \end{tabular} \end{center} \item On peut vérifier (la vérification n'est pas demandée) que l'ensemble des entiers $a$, compris au sens large entre 1 et 560 tels que 561 soit $a$-ppf, est $\{1, 50, 101, 103, 256, 305, 458, 460, 511, 560\}$. Montrer que l'ensemble des classes modulo 561 de ces entiers constitue un sous-groupe cyclique de $\bigl((\Z/561\Z)^*, \times\bigr)$. \end{enumerate} \end{enumerate} %-------------------------------------------------------------- % Partie IV %-------------------------------------------------------------- \newpage \section*{Partie IV} \subsection*{A) Nombres de Carmichaël} L'objet de cette partie est la caractérisation de certains nombres, appelés nombres de Carmichaël.\\ On rappelle que pour tout entier naturel premier $p$, et tout $a$ entier premier avec $p$, $a^{p-1} \equiv 1 \bmod p$. La réciproque n'est pas vraie ; un nombre $n$ est appelé nombre de Carmichaël si : \begin{itemize} \item[a)] $n$ n'est pas premier \item[b)] pour tout nombre $a$ premier avec $n$, $a^{n-1}$ est congru à 1 modulo $n$. \end{itemize} \begin{enumerate} \item Montrer que si $n = p_1 \times p_2 \times \cdots \times p_k$ où $p_1, p_2, \ldots, p_k$ sont des nombres premiers deux à deux distincts tels que $(p_i - 1)$ divise $(n-1)$ pour tout $i \in \{1, 2, \ldots, k\}$, alors $n$ est un nombre de Carmichaël. Montrer en particulier que 561, 10585 sont des nombres de Carmichaël. \item Dans toute cette question, on suppose que $n$ est un nombre de Carmichaël et l'on désire établir la réciproque du résultat obtenu en question 1. \begin{enumerate}[label=(\alph*)] \item On suppose tout d'abord que $n$ est une puissance de 2, $n = 2^\alpha$, où $\alpha$ est un entier $\geqslant 2$. Quel est le cardinal de $(\ZnZ)^*$ ? En déduire que pour tout entier $a$ impair $a^{(2^{\alpha}-1)}$ ne peut pas être congru à 1 modulo $n$ sauf si $a$ est congru à 1 modulo $n$ ; que peut-on conclure ? \item On suppose désormais que $n$ admet au moins un facteur premier impair $p_1$ et l'on note $p_1, p_2, \ldots, p_k$ les facteurs premiers de $n$ ; la décomposition de $n$ est alors $n = \displaystyle\prod_{i=1}^{k} p_i^{\alpha_i}$. \begin{enumerate}[label=(\roman*)] \item Soit $\omega$ un entier dont la classe modulo $p_1^{\alpha_1}$ est un générateur de $\bigl((\Z/p_1^{\alpha_1}\Z)^*, \times\bigr)$ ; $\omega$ existe d'après la partie II. A l'aide de la bijection définie dans la question I\,4, montrer qu'on peut trouver un entier $t$ tel que : $t \equiv \omega \bmod p_1^{\alpha_1}$ et, pour tout $i$ (s'il en existe) tel que $2 \leqslant i \leqslant k$, $t \equiv 1 \bmod p_i^{\alpha_i}$. Montrer qu'alors $t^{n-1} \equiv 1 \bmod n$. \item En déduire que $p_1^{\alpha_1-1}(p_1-1)$ divise $(n-1)$, puis que $\alpha_1 = 1$, et enfin que $(p_1-1)$ divise $(n-1)$. \item Montrer que $n$ est nécessairement impair et que $n$ peut s'écrire sous la forme $n = p_1 \times p_2 \times \cdots \times p_k$ où $p_1, p_2, \ldots, p_k$ sont des nombres premiers deux à deux distincts tels que $(p_i - 1)$ divise $(n-1)$ pour tout $i \in \{1, 2, \ldots, k\}$. Conclure. \end{enumerate} \end{enumerate} \item Montrer qu'un nombre de Carmichaël admet au moins trois facteurs premiers. \item Résoudre l'équation $85p - 16k = 1$, où $(k, p)$ appartient à $\Z^2$. Déterminer le plus petit nombre de Carmichaël divisible par 5 et 17. \end{enumerate} \subsection*{B) Le test de Miller-Rabin} \begin{enumerate} \item Soit $n$ un nombre non premier et qui ne soit pas non plus un nombre de Carmichaël. Montrer qu'il existe au moins un entier $a$ inférieur à $n$ et premier avec $n$ tel que $n$ ne soit pas $a$-ppf. \item En fait, on peut démontrer et l'on admettra que, pour tout nombre $n$ non premier, l'ensemble des classes des entiers naturels $a$ strictement inférieurs à $n$ tels que $n$ soit $a$-ppf est inclus dans un sous-groupe strict de $\bigl((\ZnZ)^*, \times\bigr)$. Le test de Miller-Rabin est alors le suivant : étant donnés un nombre impair $n$ et un entier $k$, on effectue $k$ épreuves indépendantes ; l'épreuve $n^\circ i$ ($i = 1, \ldots, k$) consistant à choisir un entier $a_i$ de manière équiprobable parmi $\{1, 2, 3, \ldots, n-1\}$ et à tester la propriété \og $n$ est $a_i$-ppf \fg. \begin{itemize} \item Si, pour l'un des $a_i$, $n$ n'est pas $a_i$-ppf, $n$ est composé. \item Si $n$ est pseudo-premier fort pour tous les $a_i$, alors $n$ est déclaré premier. \end{itemize} On suppose que $n$ est composé (c'est-à-dire non premier) ; par quelle valeur (en fonction de $k$), peut-on majorer la probabilité de déclarer $n$ premier ? \end{enumerate} \end{document}