\documentclass[12pt]{article}
\usepackage[frenchb]{babel}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[table]{xcolor}
\usepackage{pas-algo}
\usepackage[everytoc,ant]{pas-cours}
\usepackage{pas-math}
\usepackage{pas-tableur}
\usepackage{amssymb,amsmath}
\usepackage{numprint}
\usepackage[hmargin=2cm,vmargin=1.5cm]{geometry}
\usepackage[colorlinks=true]{hyperref}
\usepackage{multicol,cellspace,tabularx}
\usepackage{listings}
\setlength{\parindent}{0pt}
\setlength{\cellspacetoplimit}{4pt}
\setlength{\cellspacebottomlimit}{4pt}
\begin{document}
\chap[num=C,pos=right,color=purple]{Arithmétique}{\emph{Stéphane PASQUET, \today}}

%--------------- TOC
\renewcommand{\contentsname}{\color{purple}\titreFONT\huge Sommaire}
{\color{purple}\hrulefill}
{\tocFONT\tableofcontents}
{\color{purple}\hrulefill}

\vspace*{1cm} %---------- PREREQUIS

\begin{prerequis}
\item Raisonnement par récurrence
\item Fonction logarithme népérien
\end{prerequis}

\newpage %----------------- DEBUT

\begin{pasbox}[style=defi,name={Divisibilité},degrade,pluriel]
Soient $a$ et $b$ deux nombres relatifs.\\
On dit que $a$ \definmot{divise} $b$, et on note $a\vert b$, ou que $b$ est un \definmot{multiple} de $a$, s'il existe un entier naturel $q$ tel que $b=qa$. $q$ est alors appelé le \definmot{quotient} de $b$ par $a$.
\end{pasbox}

\begin{pasbox}[degrade,style=prop]
Soient $a$ et $b$ deux nombres relatifs.\\
Si un nombre $c$ divise $a$ et $b$, alors il divise tout nombre de la forme $au+bv$, où $\coord{u}{v}\in\Z\times\Z$.\\
En particulier, $c\vert(a-b)$ et $c\vert(a+b)$.
\end{pasbox}

\begin{pasbox}[style=demo,degrade,endsymb]
$\left.
\begin{array}{l}
c\vert a \Rightarrow \exists q\in\Z,\ a=qc\\
c\vert b \Rightarrow \exists q'\in\Z,\ b=q'c
\end{array}\right\}\Rightarrow \forall\coord{u}{v}\in\Z\times\Z,\ au+bv=c(qu+q'v)
$. Donc $c\vert(au+bv)$.
\end{pasbox}

Les propriétés suivantes seront admises :

\medskip

\begin{pasbox}[style=prop,degrade,pluriel]
Quels que soient les nombres relatifs $a$, $b$ et $c$,

\begin{enumerate}
\begin{multicols}{3}
\item $a\vert a$
\item $c\vert b$ et $b\vert a$ $\Rightarrow$ $c\vert a$
\item $a\vert b$ et $b\vert a$ $\Rightarrow$ $\vert a\vert=\vert b\vert$
\item $ac\vert ab$ et $a\neq 0$ $\Rightarrow$ $c\vert b$
\item $1\vert a$
\item $a\vert 0$
\item $0\vert a \Rightarrow a=0$
\item $b\vert a$ et $a\neq 0$ $\Rightarrow$ $0<\vert b\vert\leqslant\vert a\vert$
\end{multicols}
\end{enumerate}
\end{pasbox}

\begin{pasbox}[style=thm,degrade,name={Division euclidienne}]
Soient $\coord{a}{b}\in\Z\times\Z^*$.\\
Il existe un unique couple $\coord{q}{r}\in\Z\times\Z$ tel que :
\[ a=bq+r\qquad,\qquad 0\leqslant r<\vert b\vert\]
\end{pasbox}

\begin{pasbox}[style=demo,degrade,endsymb]
\begin{itemize}
\item \textbf{Existence d'un tel couple.}\\
Supposons que $\coord{a}{b}\in\Z\times\N^*$.\\
Alors, il existe un entier relatif $q$ tel que :
\[ q\leqslant\frac{a}{b}<q+1. \]
Ainsi, comme $b>0$ :
\begin{align} 
bq\leqslant a < bq+b. 
\end{align}
\end{itemize}
\breakbox
\begin{itemize}
\item[] Posons alors :
\begin{align}
r=a-bq.
\end{align}
Alors, 
\begin{align*}
\begin{array}{ccl}
(1) & \Rightarrow&  0\leqslant r<b\\
(2) & \Rightarrow &a=bq+r
\end{array}
\end{align*}
Il existe donc bien un couple $\coord{q}{r}\in\Z\times\Z$ tel que $a=bq+r$, $0\leqslant r<b$.\\
Pour généraliser au cas où $b\in\Z^*$, on pose $b=\vert b\vert$ dans ce qui précède.

\item \textbf{Unicité du couple.}\\
Supposons qu'il existe deux couples \coord{q}{r} et \coord{q'}{r'} tels que :
\[ 
\left\lbrace
\begin{array}{lcl}
a=bq+r & , & 0\leqslant r<b\\
a=bq'+r' & , & 0\leqslant r'<b
\end{array}\right.
\]
Si $0\leqslant r<b$ et $0\leqslant r'<b$, alors, par soustraction, $r-r'=0$, soit $r=r'$. Et donc, par suite, $q=q'$.
\end{itemize}
\end{pasbox}

\begin{pasbox}[style=thm,degrade,name={Algorithme d'Euclide}]
Soient $a$ et $b$ deux entiers naturels tels que $a=bq+r$, $0\leqslant r<b$.\\
On considère alors les suites \suite{a}{n}{},\suite{b}{n}{}, \suite{q}{n}{} et \suite{r}{n}{} définies par :
\[
\left\lbrace
\begin{array}{l}
a_0=a\\
b_0=b\\
q_0=q\\
r_0=r
\end{array}
\right.\qquad,\qquad
\left\lbrace
\begin{array}{l}
a_{n+1}=b_n\\
b_{n+1}=r_n\\
a_{n+1}=b_{n+1}q_{n+1}+r_{n+1}
\end{array}
\right., \forall n\in\N
\]
Alors, \suite{r}{n}{} est une suite finie dont le dernier terme est nul. L'avant dernier terme est égal à \pgcd{a}{b}.
\end{pasbox}

\begin{pasbox}[style=demo,degrade,endsymb]
Par définition, la suite \suite{r}{n}{} est strictement décroissante. En effet, pour tout entier naturel $n$, $r_n$ représente le reste de la division euclidienne de $a_n$ par $b_n$. Ainsi, $0<r_n<b_n$. Or, $b_n=r_{n-1}$ donc $0\leqslant r_n<r_{n-1}$. Ainsi, $0\leqslant r_n<r_{n-1}<r_{n-2}<\cdots<r_1<r_0$.\\
Or, $r_n\in\N$. Ainsi, la suite \suite{r}{n}{} est finie et son dernier terme est 0.\\
D'après la première propriété du cours, si $a=bq+r$ et si $d\vert a$ et $d\vert b$, alors $d\vert(a-bq)$, donc $d\vert r$.
\breakbox
Ainsi, en convenant d'écrire $a_{n+1}=r_nq_n+r_{n+1}$, 
\begin{align*}
\pgcd{a}{b} & = \pgcd{a_0}{b_0}\\
& = \pgcd{b_0}{r_0}\\
& = \pgcd{r_0}{r_1}\\
& \vdots\\
& = \pgcd{r_{N-1}}{r_{N}}
\end{align*}

en convenant de noter $r_N$ le dernier terme NON NUL de \suite{r}{n}{}.\\
Nous avons :
\begin{align*}
a_N & = r_{N-1}q_N+r_N\\
r_{N-1} & = r_Nq_{N+1}+0
\end{align*}

Alors, d'après la dernière égalité, $r_{N}\vert r_{N-1}$. Donc $\pgcd{r_{N-1}}{r_N}=r_N$.\\
Ainsi, $\pgcd{a}{b}=r_N$.
\end{pasbox}

\begin{pasbox}[style=prop,degrade,name={\'Egalité de Bézout}]
Soient $\coord{a}{b}\in\Z*\times\Z*$.\\
Il existe un couple $\coord{u}{v}\in\Z\times\Z$ tel que $au+bv=\pgcd{a}{b}$.
\end{pasbox}

\begin{pasbox}[style=demo,endsymb,degrade,name={Démonstration 1},notoc]
Soient $U$ et $V$ deux entiers relatifs tels que $c=au+bv$ soit minimal.\\
Notons $d=\pgcd{a}{b}$.\\
$d\vert a$ et $d\vert b$ donc $d\vert c$ ; ainsi, 
\begin{align}
d\leqslant c
\end{align}
La division euclidienne de $a$ par $c$ s'écrit :
\[ a = cq+r\quad,\quad 0\leqslant r<c.\]
Alors, 
\[ r=a-cq.\]
$r$ étant une combinaison linéaire de $a$ et $c$. Or, $c$ est une combinaison linéaire de $a$ et $b$, donc $r$ est une combinaison linéaire de $a$ et $b$, tout comme $c$. Mais $c$ est sensé être la plus petite combinaison linéaire de $a$ et $b$ possible. Donc $r$ est nécessairement égal à 0.\\
Ainsi, $a=cq$ et donc $c\vert a$ ; ainsi, 
\begin{align}
c\leqslant d
\end{align}

De (3) et (4), on déduit : $au+bv=d$.
\end{pasbox}

\begin{pasbox}[style=demo,endsymb,degrade,name={Démonstration 2},notoc]
Montrons par récurrence que dans l'algorithme d'Euclide, tous les restes s'écrivent sous la forme $r_k=au_k+bv_k$.

\begin{itemize}
\item \textbf{Initialisation.}\\
$a=bq_0+r_0$, $0\leqslant r_0<b$. Donc $r_0=a\times1-bq_0$.\\
$r_0$ s'écrit donc comme combinaison linéaire de $a$ et $b$. L'initialisation est alors faite.

\medskip

\item \textbf{Hérédité.}\\
Supposons que pour tout $i\leqslant k$, $r_k=au_k+bv_k$.\\
\begin{align*}
r_{k+1} & = a_{k+1} - b_{k+1}q_{k+1}\\
& = \textcolor{blue}{r_{k-1}}-\textcolor{red}{r_k}q_{k+1}\\
& = \textcolor{blue}{au_{k-1}+bv_{k-1}}-\textcolor{red}{(au_k+bv_k)}q_{k+1}\\
& = \left(u_{k-1}-u_kq_{k+1}\right)a+\left(v_{k-1}-v_kq_{k+1}\right)b
\end{align*}

Ainsi, $r_{k+1}$ est une combinaison linéaire de $a$ et $b$.\\
L'hérédité est alors vérifiée.

\medskip

Ainsi, tout reste est combinaison linéaire de $a$ et $b$. \\
Or, $\pgcd{a}{b}$ est le dernier reste non nul. Il est donc combinaison linéaire de $a$ et $b$.
\end{itemize}
\end{pasbox}

\begin{pasbox}[style=meth,degrade,name={Méthode (résoudre une équation de Bézout)}]
La dernière démonstration nous aide à trouver une méthode pour trouver le couple \coord{u}{v}.

\medskip

Prenons $a=\numprint{10246}$ et $b=514$. L'algorithme d'Euclide nous donne :
\begin{align*}
\numprint{10246} & = 19\times514+480\\
514 & = 1\times480+34\\
480 & =14\times34+4\\
34 & = 8\times4+2\\
4 & =2\times2+0
\end{align*}
En remontant, on a :
\begin{align*}
2 & = 34-8\times4 \\
 & = 514-480-8(480-14\times34)\\
 & = 514 - 9\times480+112\times 34\\
 & = 514-9\times(\numprint{10246}-19\times514)+112(514-480)\\
 & = -9\times\numprint{10246}+284\times514 -112(\numprint{10246}-19\times514)\\
 & = -121\times\numprint{10246}+\numprint{2412}\times514
\end{align*}

On obtient alors $\coord{u}{v}=\coord{-121}{\numprint{2412}}$.
\end{pasbox}

\begin{pasbox}[style=thm,degrade,name=Théorème de Bézout]
Soient $a$ et $b$ deux entiers naturels non nuls.\\
$a$ et $b$ sont premiers entre eux équivaut à dire qu'il existe un couple $\coord{u}{v}\in\Z\times\Z$ tel que $au+bv=1$.
\end{pasbox}

\begin{pasbox}[style=demo,degrade,endsymb]
Dire que $a$ et $b$ sont premiers entre eux signifie que $\pgcd{a}{b}=1$.\\
Donc, d'après l'égalité de Bézout,
\[ \pgcd{a}{b}=1 \Rightarrow \exists\coord{u}{v}\in\Z\times\Z,\ au+bv=1.\]
Réciproquement, supposons qu'il existe un couple $\coord{u}{v}\in\Z\times\Z$ tel que $au+bv=1$. Notons alors $\pgcd{a}{b}=d$.\\
$d\vert a$ et $d\vert b$ donc $d\vert(au+bv)$, soit $d\vert 1$. Ainsi, $d=1$.
\end{pasbox}

\begin{pasbox}[style=thm,degrade,name={Théorème de Gauss}]
Soient $a$, $b$ et $c$ trois entiers naturels non nuls.\\
Si $a\vert(bc)$ et si $\pgcd{a}{b}=1$, alors $a\vert c$.
\end{pasbox}

\begin{pasbox}[style=demo,degrade,endsymb]
$a\vert(bc)\Leftrightarrow\exists k\in\N,\ bc=ka$.

$\begin{aligned}[t]
\pgcd{a}{b}=1 & \Leftrightarrow \exists\coord{u}{v}\in\Z\times\Z,\ au+bv=1\\
& \Leftrightarrow \exists\coord{u}{v}\in\Z\times\Z,\ acu+bcv=c\\
& \Leftrightarrow \exists\coord{u}{v}\in\Z\times\Z,\ acu+kav=c\\
& \Leftrightarrow \exists\coord{u}{v}\in\Z\times\Z,\ a\underbrace{(cu+kv)}_{\in\N}=c\\
& \Rightarrow a\vert c
\end{aligned}$\\\phantom{-}
\end{pasbox}

\begin{pasbox}[style=prop,pluriel,degrade]
Soient $a$ et $b$ deux entiers naturels non nuls. On note $d=\pgcd{a}{b}$ et $m=\ppcm{a}{b}$.

\begin{enumerate}
\item $\exists\coord{a'}{b'}\in\N\times\N,\ \left\lbrace\begin{array}{l}
a=da'\\b=db'
\end{array}\right.$
\item Un multiple commun à $a$ et $b$ est un multiple de $da'b'$.
\item $m=da'b'$
\item $md=ab$
\end{enumerate}
\end{pasbox}

\begin{pasbox}[style=demo,degrade,endsymb]
\begin{enumerate}
\item $d\vert a$ et $d\vert b$ donc on peut écrire $a=da'$ et $b=db'$.\\
D'après l'égalité de Bézout, 
\begin{align*}
\exists\coord{u}{v}\in\Z\times\Z,\ au+bv=d & \Leftrightarrow da'u+da'v=d\\
& \Leftrightarrow a'u+b'v=1\\
& \Leftrightarrow \pgcd{a'}{b'}=1
\end{align*}

\item Posons $M$ un multiple commun à $a$ et $b$.\\
Alors, $M=\lambda a=\lambda da'=\mu b=\mu db'$.\\
On en déduit que $\lambda a'\vert \mu b'$.et donc que $b'\vert \lambda a'$.\\
$\pgcd{a'}{b'}=1 \Rightarrow b'\vert \lambda$ (théorème de Gauss) et donc $\lambda=kb'$, où $k\in\N$.\\
On a alors $M=kb'a=kda'b'$. Donc $M$ est un multiple de $da'b'$.

\item Considérons maintenant le nombre $da'b'=ab'=ba'$ : il s'agit d'un multiple commun à $a$ et à $b$. Donc, $da'b'\geqslant m$.\\
Puisque $m$ est multiple strictement positif de $a$ et de $b$, on a
$m\geqslant da'b'$ et on peut donc conclure $m=da'b'$.

\item En multipliant par $d$ l'égalité de l'item 3, on obtient $md=da'db'$, soit $md=ab$.
\end{enumerate}
\end{pasbox}

\begin{pasbox}[style=defi,name={Congruences},degrade]
Soient $a$ et $b$ deux entiers naturels non nuls.\\
Si $a=bq+r$, $q\in\Z$ et $r\in\N$, alors on note :
\[ a \equiv r \mod b \qquad\text{ou}\qquad a\equiv r~[b]\]
On lit : \emph{$a$ est \definmot{congru} à $r$ \definmot{modulo} $b$}.
\end{pasbox}

\begin{pasbox}[style=ex,pluriel,degrade]
\begin{enumerate}
\item $7=3\times2+1$ donc $7\equiv 1\mod 2$.
\item $205=20\times10+5$ donc $205\equiv 5\mod 10$.
\end{enumerate}
\end{pasbox}

\begin{pasbox}[style=prop,degrade]
Soient $a$, $b$, $c$, $d$ et $n$ des entiers naturels non nuls.

\begin{enumerate}
\item $a\equiv a\mod n$.
\item Si $a\equiv b\mod n$, alors $b\equiv a\mod n$.
\item Si $a\equiv b\mod n$ et $b\equiv c\mod n$, alors $a\equiv c\mod n$.
\item Si $a\equiv b\mod n$, alors $a+c\equiv b+c\mod n$.
\item Si $a\equiv b\mod n$ et $c\equiv d\mod n$, alors $a+c\equiv b+d\mod n$.
\item Si $a\equiv b\mod n$, alors $ac\equiv bc\mod n$.
\item Si $a\equiv b\mod n$ et $c\equiv d\mod n$, alors $ac\equiv bd\mod n$.
\item Si $a\equiv b\mod n$, alors $a^k\equiv b^k\mod n$, $k\in\N$.
\end{enumerate}
\end{pasbox}

\begin{pasbox}[style=demo,degrade,endsymb,notitlebreak]
\begin{enumerate}
\item $a=0\times n+a$ donc on a bien $a\equiv a\mod n$.
\item $\begin{aligned}[t]
a\equiv b\mod n & \Rightarrow a-b=kn,\ k\in\N\\
& \Rightarrow b=-kn+a,\ k\in\N\\
& \Rightarrow b\equiv a\mod n.
\end{aligned}$

\item $a\equiv b\mod n \Rightarrow a=kn+b,\ k\in\N$ et $b\equiv c\mod n \Rightarrow b=k'n+c,\ k\in\N$.\\
Donc, $a=(k+k')n+c$, d'où $a\equiv c\mod n$.

\item Si $a\equiv b\mod n$, alors $a=kn+b$ et donc $a+c=kn+(b+c)$. D'où $a+c\equiv b+c\mod n$.

\item $a\equiv b\mod n\Rightarrow a=kn+b$ et $c\equiv d\mod n\Rightarrow c=k'n+d$.\\
Ainsi, $a+c=(k+k')n+(b+d)$ et donc $a+c\equiv b+d\mod n$.

\item $a\equiv b\mod n\Rightarrow a=kn+b$, donc $ac=kcn+bc$ d'où $ac\equiv bc\mod n$.

\item $a\equiv b\mod n\Rightarrow a=kn+b$ et $c\equiv d\mod n\Rightarrow c=k'n+d$.\\
Ainsi, $ac=(kn+b)(k'n+d)=[kk'n+(kd+k'b)]n+bd$ d'où $ac\equiv bd\mod n$.

\item $a\equiv b\mod n\Rightarrow a=pn+b$ donc :
\begin{align*}
a^k & =(pn+b)^k\\
& =\displaystyle\sum_{i=0}^k\dbinom{k}{i}\left(pn\right)^ib^{k-i} \text{ (formule du binôme de Newton)}\\
& = b^k+n\displaystyle\sum_{i=1}^k\dbinom{k}{i}\left(pn\right)^{i-1}b^{k-i}
\end{align*}
Ainsi, $a^k\equiv b^k\mod n$.
\end{enumerate}
\end{pasbox}

\begin{pasbox}[style=defi,name={Nombres premiers},degrade]
Soit $p$ un entier naturel.\\
On dit que $p$ est \definmot{premier} s'il n'est divisible que par 1 et lui-même.
\end{pasbox}

\begin{pasbox}[style=prop,degrade]
Soit $N$ un entier naturel non nul et différent de 1.\\
Alors, soit $N$ est un nombre premier, soit $N$ est un produit de nombres premiers.
\end{pasbox}

\begin{pasbox}[style=demo,endsymb,degrade]
Démontrons cela par récurrence forte.
\begin{itemize}
\item \textbf{Initialisation.}\\
Le résultat est vrai pour $N=2$.

\item \textbf{Hérédité.}\\
Supposons que le résultat soit vrai pour tout entier naturel strictement inférieur à $N$.\\
Alors, pour $N$, soit il est premier, soit il ne l'est pas et donc $N=kd$, $2\leqslant k<N$ et $2\leqslant d< N$. Par hypothèse de récurrence, $k$ et $d$ sont soit premiers, soit des produits de nombres premiers. Ainsi, $N$ est un produit de nombres premiers.\\
L'hérédité est alors vérifiée.
\end{itemize}
Le résultat est alors vraie.
\end{pasbox}


\begin{pasbox}[style=prop,degrade,name={Infinitude des nombres premiers}]
Soit $\mathbb{P}$ l'ensemble des nombres premiers.\\
Alors, $\mathbb{P}$ est infini.
\end{pasbox}

\begin{pasbox}[style=demo,endsymb,degrade]
Supposons que $\mathbb{P}$ est un ensemble fini et que :
\[\mathbb{P}=\{p_k,\ 1\leqslant k\leqslant n \},\qquad p_1=2,\ p_2=3,\ p_3=5,\ \ldots \]
Posons alors $N=p_1p_2p_3\cdots p_n+1$. Alors, $N>p_n$ donc il n'appartient pas à $\mathbb{P}$. Or, il n'est divisible par aucun des $p_k$, ce qui signifie qu'il est premier, ce qui est contradictoire avec l'hypothèse selon laquelle $\mathbb{P}$ est fini.\\
Ainsi, $\mathbb{P}$ est infini.
\end{pasbox}

\begin{pasbox}[style=thm,name={Théorème de décomposition en produits de facteurs premiers [admis]},degrade]
Soit $n$ un entier naturel non nul différent de 1.\\
Alors, $n$ s'écrit de façon unique sous la forme :
\[
n=\prod_{i=1}^k p_i^{\alpha_i}\qquad,\qquad\alpha_i\in\N*,\ p_i\in\mathbb{P},\ i\neq j\Rightarrow p_i\neq p_j
\]
\end{pasbox}

\begin{pasbox}[style=rem,degrade]
On peut aussi utiliser une notation plus pratique :
\[ n=\prod_{p\in\mathbb{P}} p^{\alpha_p}\]
\end{pasbox}

\begin{pasbox}[style=prop,degrade]
Soient $a=\displaystyle\prod_{p\in\mathbb{P}}p^{\alpha_p}$ et $b=\displaystyle\prod_{p\in\mathbb{P}}p^{\beta_p}$ deux entiers naturels.\\
Alors,
\[
\pgcd{a}{b}=\prod_{p\in\mathbb{P}}p^{\min\left(\alpha_p,\beta_p\right)}\qquad\text{et}\qquad\ppcm{a}{b}=\prod_{p\in\mathbb{P}}p^{\max\left(\alpha_p,\beta_p\right)}
\]
\end{pasbox}

\begin{pasbox}[style=demo,endsymb,degrade]
$d=\displaystyle\prod_{p\in\mathbb{P}}p^{\min\left(\alpha_p,\beta_p\right)}$ divise nécessairement $a$ et $b$.\\
De plus, $\dfrac{a}{d}$ et $\dfrac{b}{d}$ sont premiers entre eux. Donc, $d=\pgcd{a}{b}$.

\medskip

D'après une propriété vue précédemment, $\ppcm{a}{b}=\dfrac{ab}{\pgcd{a}{b}}$. Compte tenu de l'expression précédemment démontrée, on arrive à l'expression souhaitée.
\end{pasbox}

\begin{pasbox}[style=ex,degrade]
Prenons $a=2^3\times5^7$ et $b=2^2\times3^2\times5^8$.
Alors,
\[ \pgcd{a}{b}=2^2\times5^7\qquad\text{et}\qquad\ppcm{a}{b}=2^3\times3^2\times5^8\]
\end{pasbox}

\begin{pasbox}[style=prop,degrade]
Soient $n\in\N*\setminus\left(\mathbb{P}\cup\{1\}\right)$ et $d$ un diviseur de $n$. Alors,
\[ d\leqslant\sqrt{n} \]
\end{pasbox}

\begin{pasbox}[style=demo,endsymb,degrade]
Si $d$ est un diviseur de $n$, alors il existe un entier $k$ tel que $n=kd$.
Supposons que $d>\sqrt{n}$ et $k>\sqrt{n}$. Alors, $kd>n$, ce qui est impossible. Donc $d\leqslant\sqrt{n}$.
\end{pasbox}

\medskip

\begin{pasbox}[degrade,style=defi,name={Nombre de nombres premiers}]
Le nombre de nombres premiers inférieurs ou égaux à $n$, $n>1$, est noté $\pi(n)$.
\end{pasbox}

Ainsi, $\pi(n)-\pi(m)$ représente le nombre de nombre premiers compris entre $m$ et $n$, $m<n$. \`A l'aide du crible d'\'Eratosthène (voir page suivante), on établit que :

\begin{multicols}{3}
\[ \pi(10)=4\]
\[ \pi(20)-\pi(10)=4\]
\[ \pi(30)-\pi(20)=2\]
\[ \pi(40)-\pi(30)=2\]
\[ \pi(50)-\pi(40)=3\]
\[ \pi(60)-\pi(50)=2\]
\[ \pi(70)-\pi(60)=2\]
\[ \pi(80)-\pi(70)=3\]
\[ \pi(90)-\pi(80)=2\]
\[ \pi(100)-\pi(90)=1\]
\end{multicols}

On voit que la répartition des nombres premiers est irrégulière. De plus, on a :

\begin{multicols}{2}
\begin{tabular}{|*4{Sc|}}
\hline\rowcolor{blue!20}
$\pmb{n}$ & $\pmb{\pi(n)}$ & $\pmb{\dfrac{n}{\ln n}}$ & $\pmb{\left\vert\pi(n)-\dfrac{n}{\ln n}\right\vert}$\\
\hline
10 & 4 & 4 & \pourcent{0}\\
\hline
100 & 25 & 22 & \pourcent{12}\\
\hline
$10^3$ & 168 & 145 & \pourcent{15,86}\\
\hline
$10^4$ & \numprint{1229} & \numprint{1086} & \pourcent{11,64}\\
\hline
$10^5$ & \numprint{9592} & \numprint{8686} & \pourcent{9,45}\\
\hline
$10^6$ & \numprint{78498} & \numprint{72382} & \pourcent{7,79}\\
\hline
$10^7$ & \numprint{664579} & \numprint{620421} & \pourcent{6,64}\\
\hline
$10^8$ & \numprint{5761455} & \numprint{5428681} & \pourcent{5,78}\\
\hline
$10^9$ & \numprint{50847534} & \numprint{48254942} & \pourcent{5,1}\\
\hline
\end{tabular}

On peut alors remarquer que la différence entre $\pi(n)$ et $\dfrac{n}{\ln n}$ tend à se réduire lorsque $n$ tend vers l'infini.

\medskip

On pourra alors conjecturer que :
\[ \pi(n) \underset{+\infty}{\sim} \frac{n}{\ln n}\]
\end{multicols}
\newpage
\itemclass{red}
\bonus{Crible d'\'Eratosthène} %---------------------------------------

Le crible d'\'Eratosthène est un moyen de trouver tous les nombres premiers (en théorie).
\begin{enumerate}
\item On dispose dans une grille tous les nombres entiers (ici, nous allons prendre les entiers inférieurs ou égaux à 100).
\item On exclut \og 1 \fg, qui ne fait pas partie de $\mathbb{P}$.
\item On marque \og 2 \fg{} comme un élément de $\mathbb{P}$, puis on noircit toutes les cases contenant les multiples de 2.
\item On marque le nombre suivant qui n'est pas noirci (ici, \og 3 \fg) comme un élément de $\mathbb{P}$, puis on noircit toutes les cases contenant ses multiples.
\item On continue ainsi jusqu'à ce qu'il n'y ait plus de nombres non marqués.
\end{enumerate}

\medskip

Cela nous donne :

\begin{center}
\begin{tikzpicture}%[scale=0.75,every node/.style={scale=0.75}]
\foreach\i in {2,3,...,100}
{
	\pgfmathparse{mod((\i-1),10)}\let\x\pgfmathresult
	\pgfmathparse{-floor((\i-1)/10)}\let\y\pgfmathresult
	\node[ball color=black,minimum size=1cm,text=white] at (\x,\y) {\i};
}
\foreach\i in {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97}
{
	\pgfmathparse{mod(\i,10)-1}\let\x\pgfmathresult
	\pgfmathparse{-floor((\i/10))*1}\let\y\pgfmathresult
	\node[ball color=green!20,minimum size=1cm] at (\x,\y) {\i};
}
\foreach\x in {0.5,...,9.5}
{
	\draw[white] (\x,0.5) -- (\x,-9.5);
}
\foreach\y in {-0.5,-1.5,...,-9.5}
{
	\draw[white] (-0.5,\y) -- (9.5,\y);
}
\end{tikzpicture}
\end{center}

\newpage

\bonus{Nombres de Fermat}

Tout part du théorème suivant :

\medskip

\begin{pasbox}[style=prop,degrade]
Si $a^m+1$ est un nombre premier, avec $a>1$ et $m>1$, alors $m$ est une puissance de 2.
\end{pasbox}

\begin{pasbox}[style=demo,endsymb,degrade]
Raisonnons par l'absurde : supposons que $m$ ne soit pas une puissance de 2. Alors, $m$ admet un diviseur impair $d\geqslant 3$. Dans ce cas, on peut écrire :
\begin{align*}
a^m+1 & = a^{d^k}+1 \text{ où }k\in\N*\\
& = \left(a^k\right)^d-(-1)^d\\
& = \left(a^k+1\right)f(a) \text{ (d'après la formule du binôme de Newton)}
\end{align*}

Ainsi, $a^m+1$ n'est pas premier (puisqu'il est divisible par $a^k+1$, qui n'est ni égal à 1, ni à $a^m+1$), ce qui contredit notre hypothèse selon laquelle $m$ n'est pas une puissance de 2.
\end{pasbox}

Si $a^m+1$ est premier, alors il est impair ; ainsi, $a^m$ est pair. On en déduit alors que $a$ est pair.\\
Ainsi, si on veut trouver des nombres premiers, il nous faut calculer les différentes valeurs de $a^m+1$ où $a$ est pair et tester leur primalité.\\
Or, il s'avère qu'en prenant $a=2$, les premières valeurs sont toutes premières.

\begin{center}
\begin{tabular}{|Sc|Sc|}
\hline\rowcolor{blue!20}
$n$ & $2^{2^n}+1$\\
\hline
0 & 3\\
\hline
1 & 5\\
\hline
2 & 17\\
\hline
3 & 257\\
\hline
4 & \numprint{65537}\\
\hline
\end{tabular}
\end{center}

Les \definmot{nombres de Fermat} sont les nombres $F_n=2^{2^n}+1$.\\
La conjecture de Fermat stipule que $F_n\in\mathbb{P}$. Malheureusement, ne serait-ce qu'en regardant $F_5=\numprint{4294967297}$, on s'aperçoit que la suite $\suite{F}{n}{n\geqslant0}$ croît très rapidement et qu'il est réellement difficile de tester la primalité des termes pour $n\geqslant5$.\\
Mais difficile ne veut pas dire impossible car Euler a démontré que $F_5$ admettait un diviseur autre que 1 et lui-même.

\newpage

\bonus{Nombres premiers de Mersenne}

Ici, tout part de l'étude des nombres parfaits, nombres égaux à la somme de leurs diviseurs propres. Euclide a démontré que si $M=2^p-1$ est un nombre premier, alors $\dfrac{M(M+1)}{2}=2^{p}-1\left(2^p-1\right)$ est un nombre parfait.\\
Plus tard, Euler a démontré que tous les nombres parfaits pairs ont cette forme (N.B. : aucun nombre parfait impair n'est connu à ce jour).

\medskip

Un \definmot{nombre premier de Mersenne} est un nombre premier s'écrivant sous la forme $2^p-1$, où $p$ est premier.

\begin{center}
\begin{tabular}{|Sc|Sc|}
\hline\rowcolor{blue!20}
$p$ & $2^p-1$\\
\hline
2 & 3\\
\hline
3 & 7\\
\hline
5 & 31\\
\hline
7 & 127\\
\hline
\end{tabular}
\end{center}

Attention : pour $p=11$, on a : $2^{11}-1=\numprint{2047}=23\times89$, donc il n'est pas un nombre premier de Mersenne.

\bigskip

\bonus{Nombres de Carmichaël}

Pour ces nombres, tout vient du \emph{Petit théorème de Fermat} :

\bigskip

\begin{pasbox}[style=prop,name={Petit théorème de Fermat},degrade]
Si $p$ est un nombre premier et $a$ un entier non divisible par $p$, alors :
\[ a^{p-1}\equiv 1\mod p\]
\end{pasbox}

\begin{pasbox}[style=demo,endsymb,degrade,notitlebreak]
\begin{itemize}
\item \textbf{Montrons d'abord que les restes des divisions euclidiennes par $\pmb{p}$ de \linebreak$\pmb{a}$, $\pmb{2a}$, ... , $\pmb{(p-1)a}$ sont tous distincts.}\\
Nous allons raisonner par l'absurde. Supposons donc qu'il existe deux entiers $k$ et $k'$ dans l'intervalle \entInterv{1}{p-1} tels que les restes de $ka$ et $k'a$ soient égaux.\\
On a alors :
\[ 
\left\lbrace
\begin{array}{l}
ka=pq+r\\
k'a=pq'+r
\end{array}
\right.\qquad,\qquad \coord{q}{q'}\in\Z\times\Z,\ r\in\entInterv{0}{p-1}
\]
Alors, \[ (k-k')a=p(q-q')\]
et donc $p\vert(k-k')a$.\\
Or, $k-k'<p$ donc $p\vert a$, ce qui contredit le fait que $a$ n'est pas divisible par $p$. Notre hypothèse selon laquelle il existe deux restes égaux est donc fausse.\\
Donc tous les restes sont distincts.

\item \textbf{Fin de la démonstration.}\\
De ce qui précède, on en déduit :
\begin{align*}
a & \equiv r_1\mod p\\
2a & \equiv r_2\mod p\\
\vdots&\\
(p-1)a & \equiv r_{p-1}\mod p
\end{align*}
Ainsi,
\begin{equation}
\fact{(p-1)}a^{p-1} \equiv r_1r_2\cdots r_{p-1}\mod p
\end{equation}
Or, pour $1\leqslant i\leqslant p-1$, $r_i\in\entInterv{0}{p-1}$ et ils sont tous distincts.\\
Donc $r_1r_2\cdots r_{p-1}=\fact{(p-1)}$.\\
De plus, $\pgcd{p}{\fact{(p-1)}}=1$ donc la congruence (5) nous donne :
\[ a^{p-1}\equiv 1\mod p\]
\vspace*{-2.5em}
\end{itemize}
\end{pasbox}

Un \definmot{nombre de Carmichaël} est un entier composé (entier non premier différent de 0 et 1) $n$ tel que :
\[ \mathcal{P}\; :\; \forall a\in\N,\ \pgcd{a}{n}=1\Rightarrow n\vert(a^{n-1}-1). \]

Le \emph{petit théorème de Fermat} nous dit que si $a$ est un nombre premier, alors il satisfait $\mathcal{P}$, mais la réciproque est fausse.\\
Les nombres de Carmichaël sont les entiers naturels qui satisfont $\mathcal{P}$ sans être premiers.

\bigskip

\begin{pasbox}[style=prop,name={Théorème de Korselt},degrade]
Un entier positif composé $n$ est un nombre de Carmichaël si et seulement si aucun carré de nombre premier ne divise $n$ (on dit que $n$ est \emph{quadratfrei} (sans carré)) et pour chaque diviseur premier $p$ de $n$, le nombre $p-1$ divise $n-1$. De plus, un tel $n$ divise tous les $a^n-a$ (même pour $a$ non premier à $n$).
\end{pasbox}

Il découle de ce théorème que tous les nombres de Carmichaël sont des produits d'au moins trois nombres premiers différents.

\medskip

En fait, Korselt fut le premier à observer ces propriétés, mais il n'a pas pu trouver d'exemples de nombre de Carmichaël. En 1909, Robert Daniel Carmichaël trouva le plus petit de ces nombres, 561, et ceux-ci furent nommés en son honneur.

\newpage

\bonus{Cryptographie RSA}

Soit $n=pq$ un entier où $\coord{p}{q}\in\mathbb{P}\times\mathbb{P}$.\\
On pose alors $m=(p-1)(q-1)$ et on considère un nombre $c$ premier avec $m$.\\
Enfin, on note $x$ un entier naturel quelconque.

\begin{itemize}
\item \textcolor{red!50!black}{\textbf{Il existe un entier $\pmb{d}$ tel que $\pmb{cd\equiv 1\mod m}$.}}\\
$\pgcd{c}{m}=1$ donc, d'après le théorème de Bézout, il existe un couple \coord{d}{k} d'entiers tel que $cd+km=1$, et donc tel que $cd\equiv 1\mod m$.

\medskip

\item \textcolor{red!50!black}{\textbf{On en déduit alors que $\pmb{x^{cd}\equiv x\mod p}$ et $\pmb{x^{cd}\equiv x\mod q}$.}}
\begin{itemize}
\item \textbf{Si $\pmb{x}$ est non divisible par $\pmb{p}$}, d'après le petit théorème de Fermat, $x^{p-1}\equiv 1\mod p$.\\
Or, \begin{align*}
x^m & =x^{(p-1)(q-1)}\\
x^m& = \left(x^{p-1}\right)^{q-1}\\
x^m& \equiv 1^{q-1}\mod p\\
x^m& \equiv 1 \mod p\\
x^{km} &\equiv 1 \mod p\\
x^{km+1}&\equiv x \mod p\\
x^{cd}& \equiv x\mod p
\end{align*}

\item \textbf{Si $\pmb{x}$ est divisible par $\pmb{p}$}, alors $x\equiv 0\mod p$, et donc $x^{cd}\equiv 0\mod p$.\\
On peut donc bien écrire $x^{cd}\equiv x\mod p$.
\end{itemize}

Comme $p$ et $q$ jouent des rôles identiques, la seconde congruence est aussi démontrée.

\medskip

\item \textcolor{red!50!black}{\textbf{On en déduit alors que $\pmb{x^{cd}\equiv x\mod n}$.}}\\
D'après le point précédent, $x^{cd}-x$ est divisible par $p$ et $q$, donc divisible par $pq$ (car $\pgcd{p}{q}=1$), soit par $n$. D'où la congruence.
\end{itemize}

Ce résultat nous permet alors d'établir un principe de cryptage, que l'on va appelé le \definmot{cryptage RSA} (initiales de Rivest, Shamir et Adleman qui l'ont mis au point) en 1977, utilisé notamment pour les transactions confidentielles sur Internet.

\begin{enumerate}
\item Pour chiffrer un message, on choisit deux nombres premiers $p$ et $q$ très grands, puis on calcule $n=pq$.\\
On pose alors $m=(p-1)(q-1)$ et on cherche deux entiers $c$ et $d$ tels que $cd\equiv 1\mod m$.
\item Les messages $x$ seront des entiers naturels dans \entInterv{0}{n-1}.\\
Le codage de $x$ consiste à calculer $C(x)\equiv x^c\mod n$.\\
Le décodage de $x$ consiste à calculer $D(y)\equiv y^d\mod n$.\\
On a bien : $D(C(x))\equiv x^{cd} \equiv x \mod n$.
\item Pour chiffrer $x$, on a besoin de connaître $c$ et $n$.\\
Le couple \coord{c}{n} est appelé la \definmot{clé publique} car elle est connue de tous et répertoriée dans un annuaire.
\item Pour déchiffrer le message, il vaut connaître $d$ et $n$.\\
$d$ est appelé la \definmot{clé privée} car elle n'est connue que de la personne qui reçoit le message codé.
\item Les nombres $p$ et $q$ doivent rester confidentiels car leur connaissance entraîne celle de $m$, puis celle de $d$ en résolvant l'équation de Bézout : $cd-km=1$ (ce qui est possible car $c$ est dans l'annuaire).
\end{enumerate}

Le système RSA \numprint{1024} bits correspond à un nombre $n$ de l'ordre de $2^{\numprint{1024}}$, s'écrivant avec 309 chiffres.

\bigskip

\begin{pasbox}[degrade,style=ex,notitlebreak]
Pour simplifier les calculs, on prendra $p$ et $q$ petits, contrairement à la réalité.

On prend $p=5$ et $q=11$, donc $n=55$.

Alors, $m=(5-1)(11-1)=40$. Il nous faut trouver $c$ et $d$ tels que $cd\equiv 1\mod 40$, \mbox{$\pgcd{c}{m}=1$}.

Le premier nombre $c$ possible est $c=3$ (car 3 et 40 sont premiers entre eux). \`A l'aide d'un tableur, on calcule tous les nombres $3d$ possibles et on prend le premier qui vérifie \mbox{$3d\equiv 1\mod 40$} : on trouve $d=27$.

Les lettres de l'alphabet sont représentées par des nombres selon la règle suivante :
\[ A\rightarrow 1\quad;\quad B\rightarrow 2\quad;\quad C\rightarrow 3\quad;\quad\ldots\quad;\quad Z\rightarrow 26\]
Nous allons coder le mot : \og MOT \fg.
\begin{center}
\begin{tabular}{|*4{Sc|}}
\hline\rowcolor{blue!20}
\bfseries Lettre & \bfseries Nombre correspondant & \bfseries Congruence & \bfseries Nombre final\\
\hline
M & 13 & $13^3\equiv 52\mod 55$ & 52\\
\hline
O & 15 & $15^3\equiv 20\mod 55$ & 20\\
\hline
T & 20 & $20^3\equiv 25\mod 55$ & 25\\
\hline
\end{tabular}
\end{center}

Bien entendu, nous allons nous servir d'un tableur (par exemple) pour automatiser le cryptage :

\begin{center}
\begin{tikzpicture}[every node/.style={xscale=0.7}]
\tableur[6]{A-H}
\celtxt[c]{A}{1}{p}\celtxt[c]{B}{1}{5}
\celtxt[c]{A}{2}{q}\celtxt[c]{B}{2}{11}
\celtxt[c]{D}{1}{c}\celtxt[c]{E}{1}{3}
\celtxt[c]{D}{2}{d}\celtxt[c]{E}{2}{27}
\celtxt[c]{G}{1}{Vérif.}\celtxt[c]{H}{1}{OK}
\celtxt[c]{A}{4}{Lettres :}
\celtxt[c]{B}{4}{M}\celtxt[c]{B}{5}{13}\celtxt[c]{B}{6}{52}
\celtxt[c]{C}{4}{O}\celtxt[c]{C}{5}{15}\celtxt[c]{C}{6}{20}
\celtxt[c]{D}{4}{T}\celtxt[c]{D}{5}{20}\celtxt[c]{D}{6}{25}
\celtxt[c]{A}{6}{Code :}
\end{tikzpicture}
\end{center}
\begin{itemize}
\item Dans la cellule \texttt{H1} :\\
On entre la formule : \texttt{=SI(MOD(E1*E2;(B1-1)*(B2-1))=1;"OK";"KO")}.\\
Cela permet de vérifier que les valeurs de $c$ et $d$ conviennent.
\item Dans la cellule \texttt{B5} :\\
On entre la formule : \texttt{=CODE(B4)-64}.\\
Ensuite, on copie la formule sur toute la ligne 5.
\item Dans la cellule \texttt{B6} :\\
On entre la formule : \texttt{=MOD(PUISSANCE(B5;\$E\$1);\$B\$1*\$B\$2)}.\\
Ensuite, on la copie sur toute la ligne 6.
\end{itemize}

Pour déchiffrer \og 52 \fg, il faudrait théoriquement mettre dans la cellule \texttt{B7} la formule :

\begin{quote}
\texttt{=MOD(PUISSANCE(B6;\$E\$2);\$B\$1*\$B\$2)}
\end{quote}
\breakbox
puis dans la cellule \texttt{B8} la formule :
\begin{quote}
\texttt{=CAR(B7+64)}
\end{quote}

Cependant, $52^{27}$ étant trop grand pour la tableur, cela donnerait un résultat erroné.\\
Un tableur est donc approprié lorsque $c$ et $d$ ne sont pas trop grands. Sinon, il faut contourner le problème à l'aide d'un programme que l'on fera tourner en un langage quelconque.
\end{pasbox}

\medskip


\begin{algo}[cryptRSA]{Algorithme de cryptage RSA} 

\begin{algoentries}
n,c : entiers (pour la clé RAS)\\
i,j : entiers (pour les boucles)\\
r : entier\\
LettreCodee, msg, msgCrypte : chaînes alphanumériques
\end{algoentries}

\begin{algobody}

\begin{algofor}{i}{1}{longueur(msg)}

r $\leftarrow$ 1

\begin{algofor}{j}{1}{c}
LettreCodee $\leftarrow$ ascii(msg[j])-64\\
r $\leftarrow$ mod(r$\times$LettreCodee;n)
\end{algofor}

msgCrypte[i] $\leftarrow$ r

\end{algofor}

\end{algobody}

\begin{algoend}

Afficher msgCrypte

\end{algoend}
\end{algo}

\begin{algo}[decryptRSA]{Algorithme de décryptage RSA} 

\begin{algoentries}
n,d : entiers (pour la clé RAS)\\
i,j : entiers (pour les boucles)\\
r : entier\\
msg, msgDecrypte : chaînes alphanumériques
\end{algoentries}

\begin{algobody}

\begin{algofor}{i}{1}{longueur(msg)}
r $\leftarrow$ 1
\begin{algofor}{j}{1}{d}

r $\leftarrow$ mod(r$\times$msg[j];n)
\end{algofor}

msgDecrypte[i] $\leftarrow$ lettreAscii(r+64)
\end{algofor}

\end{algobody}

\begin{algoend}
Afficher msgDecrypte
\end{algoend}
\end{algo}

\bonus{Problèmes de codage : calcul de clés}

Que ce soit dans un R.I.B. (Relevé d'Identité Bancaire), dans un numéro de sécurité sociale, dans les codes barres ou les codes ISBN (International Standard Book Number), il y a toujours un dernier nombre qui sert de \og clé de contrôle \fg{} et qui permet de vérifier que le codage n'est pas erroné.

\begin{enumerate}
\item \textcolor{red!50!black}{\textbf{Dans un R.I.B.}}\\
Un R.I.B. est constitué de la manière suivante :
\begin{center}
\begin{tabular}{|*4{Sc|}}
\hline\rowcolor{blue!20}
\bfseries Code Banque & \bfseries Code guichet & \bfseries N° compte & \bfseries Clé\\
\hline
12345 & 25896 & 35715942681 & ?\\
\hline
\end{tabular}
\end{center}
La clé de contrôle est le reste de la division euclidienne de $N=100a$ par 97, où $a$ est le nombre constitué est 21 chiffres précédents.\\
Ici, $N=\numprint{452588963571594268100}$. Nous pourrions effectuer la division euclidienne de $N$ par 97 à la main, mais on peut aussi utiliser les congruences en remarquant que :

\medskip

\begin{tabularx}{\textwidth}{*3{>{\centering\arraybackslash}X}}
$10^0\equiv 1 \mod 97$ & $10^1\equiv 10\mod 97$ & $10^2\equiv 3\mod 97$\\
$10^3\equiv 10^1\times10^2\equiv 30\mod 97$ & $10^4\equiv 9\mod 97$ & $10^6\equiv 27\mod 97$
\end{tabularx}

\medskip

On pourrait raisonner de la même façon pour les puissances suivantes de 10. On a alors, par exemple :
\begin{align*}
N & = \numprint{1234}\times10^{19}+\numprint{525896}\times10^{13}+ \numprint{357159426}\times10^4+81\times10^2\\
N & \equiv \numprint{1234}\times17+\numprint{525896}\times15+\numprint{357159426}\times9 +81\times3 \mod 97\\
N & \equiv \numprint{3222344495} \mod 97\\
N & \equiv 33 \mod 97
\end{align*}

Et comme $97-33=64$, la clé du R.I.B. est donc 64.

\medskip

\item \textcolor{red!50!black}{\textbf{Dans un code ISBN-13 et code barre EAN-13.}}\\
Un ISBN-13 ou un code barre EAN-13 est constitué de 13 chiffres suivis d'une clé.\\
Considérons le code ISBN suivant : 978-2-10-054640-x, où \og x \fg{} est la clé de contrôle.\\
Pour calculer cette clé, on commence par calculer :
\begin{align*}
N & = (9+8+1+0+4+4) + 3\times(7+2+0+5+6+0)\\
& = 26+3\times20\\
& = 26+60\\
& = 86\\
&\equiv 6 \mod 10
\end{align*}
Ensuite, on calcule :
\begin{align*}
& 10-6 \mod 10\\
\equiv & 4 \mod 10
\end{align*}
On obtient ainsi la clé : 4.
\pagebreak
\item \textcolor{red!50!black}{\textbf{Dans un numéro de sécurité sociale.}}\\
Considérons le numéro suivant : 1 73 07 33 063 033 [clé].\\
On considère le nombre $N=\numprint{1730733063033}$. Alors, à l'aide d'un tableur, en tapant dans une cellule la formule \texttt{=MOD(1730733063033;97)}, on trouve :
\[ N \equiv 24 \mod 97.\]\\
De plus, $97-24=73$. Donc, la clé est égale à 97.

\medskip

\item \textcolor{red!50!black}{\textbf{Sur un billet de banque en euros.}}\\
Sur les billets de banque (en euros), il y a une série de 12 chiffres précédés d'une lettre. Il existe un moyen rudimentaire de vérifier que ce \og code \fg{} est valable.\\
Considérons un billet où est écrit : X27385267637.\\
Dans un premier temps, on remplace la lettre par son rang dans l'alphabet (1 pour A, 2 pour B, etc.) puis on forme un nombre $N$ en remplaçant la lettre par ce rang. Ici, on aurait $N=\numprint{2427385267637}$.\\
Ensuite, on calcule le reste de la division euclidienne de $N$ par 9. Ici, il vaut 8.\\
Si ce reste n'est pas égal à 8, alors le billet est faux.
\end{enumerate}

\bigskip

\bonus{Critères de divisibilité.}

\begin{enumerate}
\item \textcolor{red!50!black}{\textbf{Critère de divisibilité par 11.}}\\
Considérons un nombre $N=\overline{abcd}$ écrit en base 10. Donc, $N=a\times10^4+b\times10^3+c\times10^1+d\times10^0$.\\
Or, $\numprint{1000}\equiv-1\mod 11$, $100\equiv1\mod 11$, $10\equiv-1\mod 11$ et $1\equiv1\mod 11$ donc : \[ N \equiv -a+b-c+d\mod 11.\]
Ainsi, $11\vert N \Leftrightarrow 11\vert(-a+b-c+d)$.\\
Par exemple, si $N=\numprint{9845}$, alors $-a+b-c+d=-(9+4)+(8+5)=-13+13=0$ donc $N$ est divisible par 11.\\
\textbf{N.B.} Pour un nombre plus grand, le principe est le même. Si $N=\numprint{98536295}$, on calcule $-(9+5+6+9)+(8+3+2+5)=-29+18=-11$, divisible par 11. Donc $N$ est divisible par 11.

\medskip

\item \textcolor{red!50!black}{\textbf{Critère de divisibilité par 7.}}\\
Considérons un nombre à au moins 3 chiffres. Alors, on peut l'écrire $N=10p+u$.\\
Considérons alors le nombre $N'=p-2u$. Alors, $N-10N'=10p+u-10(p-2u)=21u$. Donc $N-10N'$ est divisible par 7 :
\begin{align*}
& N-10N' \equiv 0 \mod 7\\
\Leftrightarrow & N\equiv 10N' \mod 7\\
\Leftrightarrow & N\equiv N' \mod 7\text{ car }\pgcd{10}{7}=1.
\end{align*}
Et donc :
\[ N'\equiv 0 \mod 7 \Leftrightarrow N\equiv 0\mod 7.\]
Prenons par exemple $N=\numprint{3983}$. Alors, $N'=398-2\times3=392$. En répétant l'algorithme sur $N'$, on a : $N''=39-2\times2=35$. Or, $7\vert N''$ donc $N$ est divisible par 7.

\pagebreak

\item \textcolor{red!50!black}{\textbf{Critère de divisibilité par $\pmb{p,\ p\in\mathbb{P}}$.}}\\
On peut s'inspirer du point précédent pour trouver un critère de divisibilité  par $p\in\mathbb{P}$.
Considérons $N=10p+u$ et $N'=p-ku$, $k\in\N*$.\\
Alors, $N-10N'=(10k+1)u$. Comme $\pgcd{10}{10k+1}=1$, si $10k+1\equiv 0\mod p$, alors $N\equiv 0\mod p$.\\
On trouve à l'aide d'un tableur (par exemple) :

\begin{multicols}{3}
\begin{center}
\begin{tabular}{|Sc|Sc|}
\hline\rowcolor{blue!20}
$p$ & $k$\\
\hline
7 & 2\\
\hline
11 & 1\\
\hline
13 & 9\\
\hline
17 & 5\\
\hline
19 & 17\\
\hline
23 & 16\\
\hline
29 & 26\\
\hline
31 & 3\\
\hline
\end{tabular}

\begin{tabular}{|Sc|Sc|}
\hline\rowcolor{blue!20}
$p$ & $k$\\
\hline
37 & 11\\
\hline
41 & 4\\
\hline
43 & 30\\
\hline
47 & 14\\
\hline
53 & 37\\
\hline
59 & 53\\
\hline
61 & 6\\
\hline
67 & 20\\
\hline
\end{tabular}

\begin{tabular}{|Sc|Sc|}
\hline\rowcolor{blue!20}
$p$ & $k$\\
\hline
71 & 7\\
\hline
73 & 51\\
\hline
79 & 71\\
\hline
83 & 58\\
\hline
89 & 80\\
\hline
97 & 29\\
\hline
\end{tabular}
\end{center}
\end{multicols}

\`A part pour 7, 11, 17, 31 et 41 (éventuellement pour 61 et 71), les autres valeurs de $k$ ne nous servent pas réellement pour vérifier mentalement si un nombre est divisible par $p$. Cependant, ces valeurs peuvent servir dans des programmes informatiques.

\medskip

\textbf{N.B.} Il existe plus d'un critère de divisibilité pour un certain nombre $p$. Il n'y a qu'à regarder ce que nous avons trouvé pour 11 : nous en avons déjà trouvé 2 aux points 2 et 3. Le dernier critère trouvé pour 11 étant, pour $N=\numprint{9845}$ : $984-5=979\rightarrow 97-9=88$ et $11\vert 88$ donc $11\vert\numprint{9845}$.
\end{enumerate}

\bigskip

\bonus{Nombres en base $\pmb{a}$}

Dans la vie de tous les jours, nous comptons en base 10 : cela signifie que tout nombre $N$ se décompose selon l'écriture :
\[
N=\sum_{i=0}^n 10^nx_i
\]
On utilise la notation suivante :
\[
N=\numprint{459015}_{(10)}\qquad\text{ou}\qquad N=\numprint{45905}_{10}
\]
pour désigner le nombre en base 10.\\
Mais tout nombre peut s'exprimer en base autre que décimale. Par exemple, en informatique, on utilise la base 2 (le binaire). En base $a$, $N$ s'exprime de la façon suivante :
\[
N=\sum_{i=0}^n a^ny_i\;.
\]
Les $y_i$ s'obtiennent en faisant des divisions euclidiennes par $a$.\\
Prenons par exemple $N=\numprint{45905}_{(10)}$. On a alors :

\begin{align*}
\numprint{45905} & = 2\times\numprint{22952}+1\\
\numprint{22952} & =2\times\numprint{11476}+0\\
\numprint{11476} & = 2\times\numprint{5738}+0\\
\numprint{5738} & = 2\times\numprint{2869}+0\\
\numprint{2869} & =2\times\numprint{1434}+1\\
\numprint{1434} & =2\times\numprint{717}+0\\
717 & = 2\times358+1\\
358&=2\times179+0\\
179&=2\times89+1\\
89&=2\times44+1\\
44&=2\times22+0\\
22&=2\times11+0\\
11&=2\times5+1\\
5&=2\times2+1\\
2&=2\times1+0\\
1&=2\times0+1
\end{align*}

On a alors :
\[ 
\numprint{45905}_{(10)}=1011001101010001_{(2)}
\]

\newpage

\begin{algo}{Algorithme de conversion en base $a$}
\begin{algoentries}
N : entier (en base 10)\\
M : chaîne numérique (contenant la conversion en base a)\\
a : base dans laquelle on veut convertir a\\
u : liste\\
n : entier de boucle
\end{algoentries}
\begin{algobody}
u[0] $\leftarrow$ N\\
n $\leftarrow$ 1\\
M $\leftarrow$ MOD(N;a)
\begin{algowhile}{n<ln(N)/ln(a)}
u[n] $\leftarrow$ (u[n-1]-y[n-1])/a\\
M $\leftarrow$ MOD(u[n];a)+"M"\\
n $\leftarrow$ n+1
\end{algowhile}
\end{algobody}
\begin{algoend}
Afficher M
\end{algoend}
\end{algo}

%Voici (page suivante) un programme en PHP qui permet de convertir n'importe quel nombre décimal en base $a$.
%\newpage
\lstset{
	numbers=left, 
	numberstyle=\tiny, 
	stepnumber=1, 
	showtabs=false,
	showspaces=false,
	showstringspaces=false,
	numbersep=3pt, 
	language=PHP, 
	backgroundcolor=\color{blue!5},
	frame=shadowbox,
	rulesepcolor=\color{blue!50!black},
	rulecolor=\color{blue!50!black},
	framexleftmargin=10pt,
	keywordstyle=\color{blue!50!black}\bfseries,
	basicstyle=\ttfamily,
    columns=flexible,
    keepspaces=false,
    commentstyle=\color{green!50!black},
    moredelim={[s][\color{red}]{<?}{php}},
    moredelim={[s][\color{red}]{?}{>}}
}
\begin{lstlisting}
<?php // Permet de convertir n'importe quel nombre décimal en base a.
	if (!isset($_POST['N']) && !isset($_POST['a']))
	{ // quand les valeurs de N et a ne sont pas données ...
	echo "<form action='".basename( __FILE__ )."' method='post'>";
	echo "N=<input type='text' size='10' name='N'> (nombre à convertir)<br>";
	echo "a=<input type='text' size='10' name='a'> (base en laquelle N 
	sera converti)<br>";
	echo "<input type='submit' value='valider'>";
	echo "</form>";
	}
	else
	{ // si N et a sont donnés ... 
	$N = $_POST['N'];
	$a = $_POST['a'];
	$n = 1;
	$u[0]=$N;
	$M=$N%$a;
	while ($n<log($N,$a))
	{ // n est nécessairement inférieur au log en base a de N
		$u[$n] = ($u[$n-1]-$y[$n-1])/$a;
		$M = $u[$n]%$a.$M;
		$n++;
	}
	echo $M;
	}
?>
\end{lstlisting}

\bigskip

\bonus{Chiffrement de Hill (Pré-requis : calcul matriciel)}

On considère un mot constitué de lettres : $L_1L_2\cdots L_n$, $n$ étant pair.\\
Soient 4 nombres $a$, $b$, $c$ et $d$ qui vont constituer la clé du chiffrement.\\
On remplace $L_i$ par sa position dans l'alphabet en convenant d'avoir 0 pour A, 1 pour B, etc. On obtient alors une suite de nombres : $u_1,\ u_2,\ \cdots,\ u_n$.
On pose alors :
\[
\forall k\in\entInterv{1}{\frac{n}{2}},\ 
\begin{pmatrix}
c_{2k-1}\\
c_{2k}
\end{pmatrix}
\equiv
\begin{pmatrix}
a & b\\
c & d
\end{pmatrix}
\begin{pmatrix}
u_{2k-1}\\
u_{2k}
\end{pmatrix} \mod 26
\]
On obtient une suite de nombres $c_1,\ c_2,\ \cdots,\ c_n$ qui correspond à une suite de lettres.

\medskip

Prenons par exemple le mot : CRYPTOGRAPHE et choisissons la clé $a=3$, $b=7$, $c=2$ et $d=13$. On a alors :
\begin{center}
\begin{tabular}{|>{\columncolor{blue!20}}Sl|*{12}{Sc|}}
\hline
\bfseries Lettres $\pmb{L_i}$ & C & R& Y& P &T &O &G &R &A &P &H &E\\
\hline
\bfseries Rang $\pmb{u_i}$ & 2 & 17 & 24 & 15 & 19 & 14 & 6 & 17 & 0 & 15 &7 & 4 \\
\hline
\end{tabular}
\end{center}

On a alors :

\begin{multicols}{2}
\begin{align*}
\begin{pmatrix}c_1\\c_2\end{pmatrix} &
=
\begin{pmatrix}3&7\\2&13\end{pmatrix}\begin{pmatrix}2\\17\end{pmatrix}\\
& = \begin{pmatrix}125\\225\end{pmatrix}\\
& \equiv \begin{pmatrix}21\\17\end{pmatrix}\mod 26\\
& \rightsquigarrow \begin{pmatrix}V\\R\end{pmatrix}
\end{align*}

\begin{align*}
\begin{pmatrix}c_3\\c_4\end{pmatrix} &
=
\begin{pmatrix}3&7\\2&13\end{pmatrix}\begin{pmatrix}24\\15\end{pmatrix}\\
& = \begin{pmatrix}177\\243\end{pmatrix}\\
& \equiv \begin{pmatrix}21\\9\end{pmatrix}\mod 26\\
& \rightsquigarrow \begin{pmatrix}V\\J\end{pmatrix}
\end{align*}
\end{multicols}

\'Ecrivons un algorithme pour éviter de tout faire à la main :

\medskip

\begin{algo}{Algorithme de chiffrement de Hill}
\begin{algoentries}
a, b, c, d : clé du chiffrement\\
L : liste contenant les lettres du message à crypter\\
u : liste de nombres correspondant à la position des lettres
\end{algoentries}
\begin{algobody}
\begin{algofor}{i}{0}{NbLettres(L)-1 avec un pas de 2}
u[i] $\leftarrow$ position(L[i])\\
u[i+1] $\leftarrow$ position(L[i+1])\\
c[i] $\leftarrow$ MOD(a$\times$u[i]+b$\times$u[i+1];26)\\
c[i+1] $\leftarrow$ MOD(c$\times$u[i]+d$\times$u[i+1];26)\\
Afficher Lettre(c[i])Lettre(c[i+1])
\end{algofor}
\end{algobody}
\end{algo}

\newpage

En PHP, cela donne :

\medskip

\begin{lstlisting}
<?php
if (!isset($_POST['message']) && !isset($_POST['a']) &&
 !isset($_POST['b'])&& !isset($_POST['c'])&& !isset($_POST['d']))
{
	echo "<form action='".basename( __FILE__ )."' method='post'>";
	echo "Message : <input type='text' size='50' name='message'><br>";
	echo "a=<input type='text' size='4' name='a'>&nbsp;
	b=<input type='text' size='4' name='b'>&nbsp;
	c=<input type='text' size='4' name='c'>&nbsp;
	d=<input type='text' size='4' name='d'><br>";
	echo "<input type='submit' value='valider'>";
	echo "<form>";
}
else
{
	if ( strlen($_POST['message'])%2 ==0 )
	{ 
		$msg = strtoupper($_POST['message']);
		for ($i=0 ; $i<strlen($msg) ; $i=$i+2)
		{
			// On commence par convertir la lettre en son code numérique
			$u[$i] = ord($msg[$i])-65;
			$u[$i+1] = ord($msg[$i+1])-65;
			// On calcule maintenant le code
			$c[$i] = ($_POST['a']*$u[$i]+$_POST['b']*$u[$i+1])%26;
			$c[$i+1] = ($_POST['c']*$u[$i]+$_POST['d']*$u[$i+1])%26;
			// On affiche les lettres correspondantes
			echo chr($c[$i]+65).chr($c[$i+1]+65);			
		}
	}
	else
		echo "Il faut un nombre pair de lettres.";
}
?>
\end{lstlisting}

\medskip

Cela nous donne, pour notre exemple, le code : VRVJZMHZBNXO.

\medskip

\textbf{N.B.} Dans le programme PHP, j'ai ajouté un test afin de vérifier si le nombre de lettre du message à coder est un nombre pair.

\bigskip

Le déchiffrement consiste à trouver les $u_k$ avec la relation :
\[
\forall k\in\entInterv{1}{\frac{n}{2}},\ 
\begin{pmatrix}
u_{2k-1}\\
u_{2k}
\end{pmatrix}
\equiv
\begin{pmatrix}
a & b\\
c & d
\end{pmatrix}^{-1}
\begin{pmatrix}
c_{2k-1}\\
c_{2k}
\end{pmatrix} \mod 26
\]
\`A l'aide d'un logiciel, on trouve que $\begin{pmatrix}3 & 7\\2 & 13\end{pmatrix}^{-1}=\dfrac{1}{25}\begin{pmatrix}13&-7\\-2&3\end{pmatrix}$.\\
Il nous faut trouver la valeur de $\dfrac{1}{25}$ modulo 26, c'est-à-dire le nombre $x$ tel que $25\times x \equiv 1\mod 26$. Or, $25\equiv -1\mod 26$ donc $25\times25\equiv 1\mod 26$. Ainsi, l'inverse de 25 modulo 26 est égal à 25 (ou $-1$ si on veut ... ce qui va nous arranger pour le calcul suivant).\\
On a alors :
\begin{align*}
\begin{pmatrix}3 & 7\\2 & 13\end{pmatrix}^{-1} & \equiv 25\begin{pmatrix}
13&-7\\-2&3\end{pmatrix}\mod 26\\
& \equiv -1\begin{pmatrix}13&-7\\-2&3\end{pmatrix}\mod 26\\
& \equiv \begin{pmatrix}-13&7\\2&-3\end{pmatrix}\mod 26\\
&\equiv \begin{pmatrix}13 & 7\\2&23\end{pmatrix}\mod 26
\end{align*}

En faisant tourner le programme précédent avec le mot crypté comme premier mot, puis en prenant $a=13$, $b=7$, $c=2$ et $d=23$, on arrive au mot décrypté.

\newpage

\bonus{Chiffrement affine}

On attribue à chaque lettre de l'alphabet un nombre (sa position) en convenant d'avoir 0 pour A, 1 pour B, etc.\\
On choisit deux nombres $a$ et $b$. On note $x$ le rang d'une lettre et $r(x)$ tel que \mbox{$ax+b\equiv r(x) \mod 26$}. La lettre correspondant à $r(x)$ est la lettre codée.

\begin{itemize}
\item \textcolor{red!50!black}{\textbf{Condition pour que ce chiffrement soit valable (pour que l'on puisse décoder tout message).}}
\begin{itemize}
\item Si $\pgcd{a}{26}\neq 1$, notons $x$ et $x'$ deux rangs différents. alors,
\begin{align*}
r(x)-r(x') & = 26(q-q')+a(x-x')\\
& = 26(q-q')+a\dfrac{26}{\pgcd{a}{26}}\quad\text{en prenant }x\text{ et }x' \text{ tels que }x-x'=\dfrac{26}{\pgcd{a}{26}}\\
& = 26\left(q-q'+\dfrac{a}{\pgcd{a}{26}}\right)\\
& \equiv 0\mod 26
\end{align*}

Il est donc possible de trouver deux $x$ et $x'$ différents tels que $r(x)\equiv r(x')\mod 26$.\\
Dans ce cas, le décryptage est impossible.

\medskip

\item Si $\pgcd{a}{26}=1$, soient deux nombres $x$ et $x'$ tels que $r(x)=r(x')$. Alors,
\[ a(x-x')=26(q-q').\]
Or, $\pgcd{a}{26}=1$, donc d'après le théorème de Gauss, 26 divise $(x-x')$. Ainsi, $x=x'$ car $-25\leqslant r(x)-r(x')\leqslant 25$.\\
Dans ce cas, on est assuré que le décryptage est possible (à une lettre codée ne correspond qu'une solution décodée).
\end{itemize}

\medskip

\textbf{Il est donc nécessaire que $\pmb{a}$ et 26 soient premiers entre eux.}

\medskip

\textbf{Exemple :} On prend $a=17$ et $b=2$ puis on cherche à coder la lettre K. Son rang dans l'alphabet vaut 10 et $17\times10+2\equiv16\mod 26$. La lettre de rang 16 est Q donc la lettre codée est Q.

\bigskip

\item \textcolor{red!50!black}{\textbf{Comment décoder une lettre ?}}\\
On part du principe que $y\equiv ax+b\mod 26$ est le rang de la lettre codée. Alors, en convenant de noter $a'$ l'inverse de $a$ modulo 26, on a :
\begin{align*}
ax+b\equiv y\mod 26 & \Leftrightarrow aa'x+ba'\equiv a'y\mod 26\\
& \Leftrightarrow x\equiv a'(y-b)\mod 26
\end{align*}

\textbf{Exemple :} pour décoder notre lettre Q, dont le rang est $y=16$, on fait :
\begin{align*}
x & \equiv 23(16-2)\mod 26\\
& \equiv 322 \mod 26\\
& \equiv 12\times26+10\mod 26\\
&\equiv 10 \mod 26
\end{align*}

On retrouve bien le rang de la lettre K.
\end{itemize}

\bonus{Chiffrement de Vigénère} %-----------------------------------------

Dans un premier temps, on associe à chaque lettre de l'alphabet sa position (0 pour A, 1 pour B, etc.).\\
Prenons par exemple le mot MATHEMATIQUES à coder. Le chiffrement de Vigénère nécessite un mot clé ou une phrase clé. Prenons le mot \og SYMPA \fg. Pour chiffrer notre message, on fera :
\begin{center}
\fontsize{9}{11}\selectfont
\begin{tabular}{|*{13}{Sc|}}
\hline\rowcolor{blue!10}
M & A & T & H & E & M & A & T & I & Q & U & E & S\\
\hline
12 & 0 & 19 & 7 & 4 & 12 & 0 & 19 & 8 & 16 & 20 & 4 & 18\\
\hline\rowcolor{green!10}
S & Y & M & P & A & S & Y & M & P & A & S & Y & M\\
\hline
18 & 24 & 12 & 15 & 0 & 18 & 24 & 12 & 15 & 0 & 18 & 24 & 12\\
\hline
$12+18$ & $0+24$ & $19+12$ & $7+15$ & $4+0$ & $12+18$ & $0+24$ & $19+12$ & $8+15$ & $16+0$ & $20+18$ & $4+24$ & $18+12$\\
$=30$ & $=24$ & $=31$ & $=22$ & $=4$ & $=30$ & $=24$ & $=31$ & $=23$ & $=16$ & $=38$ & $=28$ & $=30$\\
$\equiv 4$ & $\equiv 24$ & $\equiv 5$ & $\equiv 22$ & $\equiv 4$ & $\equiv 4$ & $\equiv 24$ & $\equiv 5$ & $\equiv 23$ & $\equiv 16$ & $\equiv 12$ & $\equiv 2$ & $\equiv 4$\\
\hline\rowcolor{yellow!10}
E & Y & F & W & E & E & Y & F & X & Q & M & C & E\\
\hline
$4-18$ & $24-24$ & $5-12$ & $22-15$ & $4-0$ & $4-18$ & $24-24$ & $5-12$ & $23-15$ & $16-0$ & $12-18$ & $2-24$ & $4-12$\\
$\equiv 12$ & $\equiv 0$ & $\equiv 19$ & $\equiv 7$ & $\equiv 4$ & $\equiv 12$ & $\equiv 0$ & $\equiv 19$ & $\equiv 8$ & $\equiv 16$ & $\equiv 20$ & $\equiv 4$ & $\equiv 18$\\
\hline\rowcolor{blue!10}
M & A & T & H & E & M & A & T & I & Q & U & E & S\\
\hline
\end{tabular}
\end{center}

\begin{minipage}{0.33\textwidth}
\textbf{Légende :}
\begin{quote}
\begin{tabular}{|Sl|}
\hline\rowcolor{blue!10}
Message décodé\\
\hline\rowcolor{green!10}
Clé\\
\hline\rowcolor{yellow!10}
Message codé\\
\hline
\end{tabular}
\end{quote}
\end{minipage}
\begin{minipage}{0.66\textwidth}
Toutes les congruences sont modulo 26.
\end{minipage}

\bigskip

\begin{algo}{Algorithme de chiffrement de Vigénère}
\begin{algoentries}
message : liste (message à coder)\\
cle : liste (clé du chiffrement)\\
i : entier de boucle
\end{algoentries}
\begin{algobody}
cle $\leftarrow$ ($\lfloor$NbLettres(message)/NbLettres(cle)$\rfloor$+1)$\times$cle\\
\emph{On forme ici une clé dont la longueur sera au moins égale à celle du message}
\begin{algofor}{i}{0}{NbLettres(message)-1}
Afficher Lettre(MOD(position(message[i])+position(cle[i]);26))
\end{algofor}
\end{algobody}
\end{algo}

\medskip

Voici un programme en PHP :

\medskip

\begin{lstlisting}
<?php
 if (!isset($_POST['message']) && !isset($_POST['cle']))
 {
  echo "<form action='".basename( __FILE__ )."' method='post'>";
  echo "Phrase à chiffrer : <input type='text' size='100' name='message'><br>";
  echo "Clé : <input type='text' size='100' name='cle'><br>";
  echo "<input type='submit' value='valider'>";
  echo "</form>";
  }
  else
  {
    $message = $_POST['message'];
    $cle = str_repeat($_POST['cle'], ceil(strlen($message)/strlen($_POST['cle'])));
    echo "Message codé : ";
    for ($i=0 ; $i<strlen($message) ; $i++)
    {
      echo chr((ord($message[$i])-65+ord($cle[$i])-65)%26+65);
    }
  }
?>
\end{lstlisting}
\end{document}	
