\documentclass[a4paper,11pt]{article}

\input macrodwicky.tex
\geometry{verbose,letterpaper,hmargin=2cm,vmargin=2cm}
\usepackage{calligra}



\newcommand{\ch}{Chapitre 1}
\newcommand{\Ch}{Arithmétiques et  \linebreak[2]  problèmes de codage}	
\newcommand{\Cl}{TS-spé}	
\newcommand{\Annee}{2013-2014}	
\newcommand{\Profs}{D.Zancanaro}

\definecolor{trustcolor}{rgb}{0.71,0.14,0.07}

\newcommand{\Couleur}{trustcolor}


\begin{document}

\pagestyle{empty}
\calligra
\begin{pspicture}(-1,-3)(3,1)
   \psset{linewidth=0.2}
   %\psline[linecolor=dablue](-1,0)(3,0)
   \rput(7,0){\psdiabox*[fillcolor=\Couleur]{\bfseries\huge\textsc{\textcolor{white!20}{2013-2014}}}}
  {\color{\Couleur}{\rput(-2,-2){\rule{5cm}{3pt}} }}
  \rput(7,-2){\bfseries\Huge\textsc{\textbf{Les cours du Lycée J.Durand}}}
  {\color{\Couleur}{\rput(16,-2){\rule{5cm}{3pt}} }}
    {\color{\Couleur}{\rput(-2,-8.5){\rule{2cm}{150pt}} }}
 {\color{\Couleur}{\rput(-2.2,-16.2){\rule{2cm}{80pt}} }}
\end{pspicture}
\rm
\vfill
\hfill \huge{ \textbf{Mathématiques}} \hspace*{3cm} \newline

\hfill \huge{ \textbf{Terminale S}} \hspace*{3cm} \newline

\hfill \huge{ \textbf{Enseignement de spécialité}} \hspace*{3cm} \newline

\vfill

\hfill \Large{ \textbf{Rédaction :}} \hspace*{3cm} \newline

\hfill \Large{ David Zancanaro \hspace*{3cm} \newline


\vfill


\hfill \large{ \textbf{Réalisé à l'aide de : }\hspace*{3cm} \newline

\hfill \large{ \LaTeX \hspace*{3cm} 

\definecolor{BlanchedAlmond}{rgb}{1,0.92,0.80}


\pagebreak


\tableofcontents
\pagebreak



\fancypagestyle{styleLyc}{%
\fancyhf{} 
\fancyhead{\href{http://www.wicky-math.fr.nf}{wicky-math.fr.nf}}
	\fancyfoot[LE,LO]{{\scriptsize\textsl{ \Profs \\ Lycée \LyDav }}}
	\fancyfoot[C]{\scriptsize\textsl{\Cl \\ \Annee}}
\fancyfoot[LE,RO]{\bfseries\thepage / \pageref{LastPage}}
}
\pagestyle{styleLyc}

\lhead{\Ch}
\rhead{\ch}
\setcounter{NumLecon}{1}


\TITRE{ascii.eps}{0.4}

\section{Divisibilité dans $\Z$}

\subsection{Définition}

\begin{exoi}Les codes-barres sont omniprésents dans la vie courante. Ils trouvent leurs applications dans des domaines aussi variés que la gestion des prêts d'une bibliothèque, les caisses enregistreuses à lecture optique ou le contrôle de la production dans l'industrie.\\
Les codes-barres.\\
Les codes EAN 13 (European Article Numbering à 13 chiffres) sont des codes-barres utilisés dans le monde entier sur l'ensemble des produits de grande consommation. Ils comportent 13 chiffres :
\begin{itemize}
 \item les deux premiers chiffres correspondent au pays  de provenance du produit ou à une classe normalisée de produits ;
 \item les quatre chiffres suivants correspondent au codage du fabriquant ;
 \item les six suivants forment le numéro d'article ;
 \item le treizième chiffre est une clé de contrôle calculée en fonction des douze précédents. 
 \end{itemize} 
 La clé de contrôle sert à la vérification de la bonne saisie du code. Nous allons nous intéresser à son calcul.\\
\textbf{Calcul de la clé de contrôle}\\
 Un code-barres est symbolisé par le tableau suivant :
  \begin{center}
\begin{tabular}{|*{13}{c|}}
    \hline
     $C_1$  & $C_2$  & $C_3$  & $C_4$  & $C_5$  & $C_6$  & $C_7$  & $C_8$  & $C_9$  & $C_{10}$ & $C_{11}$ & $C_{12}$ & R\\
    \hline
\end{tabular}
 \end{center}
 où $C_1$, $C_2$, $\dots$, $C_{12}$ et $R$ sont les 13 chiffres constituant le code-barres ; $R$ est donc la clé.\\
 Les chiffres $C_1$, $C_3$, $\dots$, $C_{11}$ sont ceux de rangs impairs et $C_2$, $C_4$, $\dots$, $C_{12}$ sont les chiffres de rangs pairs.\\
 La clé $R$ est calculée de telle sorte que :
 $$[(\textbf{somme des chiffres de rang impair})+3(\textbf{somme des chiffres de rang pair)}+R] \text{ est un multiple de 10} $$
 \pagebreak
 \begin{enumerate}
 \item Vérifier que l'on ne détecte pas d'erreur dans le code-barres ci-dessous.
  \begin{center}
\includegraphics[scale=0.3]{code2.eps}
\end{center}
 \item Déterminer la clé associée au code-barres suivant :
 \begin{center}
\includegraphics[scale=0.3]{code1.eps}
\end{center}
 \item Le système de lecture optique d'une caisse enregistreuse étant défectueux, un employé doit saisir les codes à la main. Parmi les codes saisis, lesquels comportent à coup sûr une erreur ?
 $$ 9782940199617$$
 $$ 9782940199167$$
 $$ 3782940199617$$
 \item Calculer la clé des deux codes suivants :
 $$ 1672345678900$$
 $$ 7612345678900$$
 Toutes les erreurs de saisie peuvent-elles être détectée grâce à la clé de contrôle ?
\item Déterminer $x$ sachant que le code est le suivant :
$$ 374284x179317$$
 \end{enumerate}\end{exoi}
 
 \Rqs{\item La clé de contrôle permet de détecter des erreurs de saisie d'un code-barres (l'inversion de deux chiffres consécutifs ou un chiffre erroné par exemple) mais elle ne permet pas de détecter toutes les erreurs.
 \item Le calcule de la clé de contrôle fait appel à la notion de divisibilité, objet d'étude de ce premier chapitre.}

 \begin{defi}
 Soient $a$ et $b$ deux entiers relatifs quelconques. (On note $a\in \Z$ et $b\in\Z$). \\
 On dit que $a$ est un multiple de $b$, ou que $b$ divise $a$ ou encore que $b$ est un diviseur de $a$ si et seulement si il existe un entier relatif $k$ tel que :
 $$ a=b\times k$$
 On note $b | a$
 \end{defi}
 
 \Rqs{\item $1$ et $-1$ divisent tous les entiers relatifs.
 \item Un nombre $a$ admet au minimum $4$ diviseurs : $\{-a;-1;1;a\}$. Dans le cas où $a$ a exactement $4$ diviseurs, $a$ est un nombre premier.
 \item La relation de divisibilité est \textit{réflexive} i.e $a$ divise $a$.
 \item L'ensemble des multiples de $a$ se notent $\{ak, \text{ où } k\in\Z\}$ ; par exemple l'ensemble des multiples de $7$ se note donc $\{7k, \text{ où } k\in\Z\}=\{\dots, -21;-14;-7;0;7;14;21;\dots \}$
 \item $0$ est  un multiple de tous les nombres ce qui revient à dire que tous les entiers relatifs divisent $0$.}


\begin{exoi}
\begin{center}
\textbf{\underline{Partie A}}
\end{center}
Un triangle rectangle a des côtés de longueurs entières. L'un des côtés de l'angle droit a pour longueur $6$. On aimerait déterminer les longueurs des deux autres côtés.
\begin{enumerate}
\item En notant $x$ et $y$ les longueurs cherchées (avec $x>y$), vérifier que le problème se traduit par : $$(x-y)(x+y)=36$$
\item Quels sont les diviseurs positifs de $36$?
\item Quels sont les couples d'entiers naturels $(a;b)$ tels que $ab=36$?
\item En déduire les différentes solutions du problème.
\end{enumerate}
\begin{center}
\textbf{\underline{Partie B}}
\end{center}
Ayant à traiter un grand nombre de tels triangles, on cherche à systématiser la recherche des couples $(a;b)$ tels que $ab=n$ où $n$ est un entier naturel.
\\On propose l'algorithme suivant :
\begin{center}
\Algo{8cm}{
\Entree{ 
 $n$  est un entier naturel, $n>2$.\\}
{
Entrer $n$ \\
  \For{j allant de 1 à $E(\sqrt{n})$}
{\Rq{La fonction $E$ utilisée ici est la fonction \og partie entière \fg.}
\If{$j$ est un diviseur de $n$}
{Afficher $j$\\Afficher $\dfrac{n}{j}$}
}
}
}
\end{center}
\begin{enumerate}
\item Quels sont les affichages obtenus en faisant tourner cet algorithme pour $n=36$? $n=38$?
\item On veut programmer cet algorithme sur un ordinateur.
\begin{enumerate}
\item Comment traduire la condition \og $j$ est un diviseur de $n$ \fg ?
\item Programmer cet algorithme.
\item Vérifier vos réponses à la question $2.$
\end{enumerate} 
\item Soient $a$ et $b$ deux entiers naturels tels que $ab=n$ avec $a\leq b$.\\Montrer que l'on a $a\leq \sqrt{n}\leq b$.
En déduire que le programme proposé affiche bien tous les couples d'entiers naturels $(a;b)$ tels que $ab=n$.
\end{enumerate} 
\end{exoi}

\begin{center}
\includegraphics[scale=1]{python1.eps}
\end{center}

\begin{exoi}Un cube est constitué de $n^3$ petits cubes identiques, où $n$ est un entier supérieur ou égal à $2$. \\On lui en enlève un petit cube et on souhaite regrouper les petits cubes restants en plusieurs paquets identiques.
\begin{enumerate}
\item Vérifier qu'un tel regroupement n'est pas possible pour $n=2$.
\item On suppose $n>2$
\begin{enumerate}
\item Vérifier que $8^3-1$ est divisible par $7$.
\item Vérifier que $23^3-1$ est divisible par $22$.
\item Conjecturer un diviseur de $n^3-1$ pour un entier $n$ quelconque.
\item Prouver votre conjecture.
\item proposer une solution au problème.
\end{enumerate}
\end{enumerate}
\end{exoi}


\begin{exoi}Déterminer les entiers naturels $n$ tels que $6$ divise $n+17$\end{exoi}

\begin{exoi}Déterminer les entiers naturels $n$ tels que $2n-5$ divise $6$\end{exoi}


\subsection{Propriétés}

Bien que ces propriétés soient relativement simples on portera une attention toute particulière à leurs démonstrations, qui donneront de bons réflexes pour les exercices.

\begin{prop}
Si $b$ divise $a$ alors $-b$ divise $a$, et réciproquement.
\end{prop}

\Dem{En effet si $b|a$ alors $\exists k\in\Z \text{ tel que } a=bk\Longleftrightarrow a=(-b)\times (-k)$. $-k$ est un entier relatif par conséquent $-b|a$. }

\Rqs{\item $a$ et $-a$ ont donc les mêmes diviseurs dans $\Z$ et les diviseurs négatifs de $a$ sont les opposés des diviseurs positifs de $a$.
\\Ainsi on se restreindra pour la recherche des diviseurs dans $\Z$ à la recherche des diviseurs dans $\N$ et on complètera par les opposés.
\item Tout nombre $a\in \Z$  admet un nombre fini de diviseur, compris $-a$ et $a$.}

\Expl{On a vu que les diviseurs positifs de $36$ sont $\{1;2;3;4;6;9;12;18;36\}$ donc les diviseurs de $36$ dans $\Z$ sont $\{-36;-18;-12;-9;-6;-4;-3;-2;-1;1;2;3;4:6;9;12;18;36\}$
}
\begin{exoi}Déterminer l'ensemble des diviseurs de $42$\end{exoi}

\begin{prop}
Si $b$ divise $a\neq 0$ alors $|b|\leq |a|$.
\end{prop}

\Dem{$b|a \Longleftrightarrow  \exists k\in \Z/ a=bk \Longrightarrow |a|=|b|\times |k|$. Puisque $a$ est non nul, il est en de même pour $k$ donc $|k|\geq 1$ d'où :
$$ |a|\geq |b|$$}

\begin{prop}
Si $a|b$ et $b|a$ alors $a=b$ ou $a=-b$
\end{prop}

\Dem{D'après la propriété précèdente, si $a|b$ alors $|a|\leq |b|$. De même puisque $b|a$ alors $|a|=|b|$ ce qui permet de conclure que $a=\pm b$.}

\begin{prop}
Si $a|b$ et $b|c$ alors $a|c$.\\
La relation de divisibilité est \textit{transitive}.
\end{prop}

\Dem{
$a|b\Longleftrightarrow \exists k\in\Z \text{ tel que } b=ak$, de même $b|c\Longleftrightarrow \exists k'\in\Z \text{ tel que } c=bk' $ 
\\
Ces deux égalités impliquent que :
$$ c=akk'$$
$kk'\in Z$ en tant que produit de deux entiers relatifs donc $a|c$.
 }

\begin{prop}
Si $a|b$ alors $a$ divise tout multiple de $b$ i.e $a|bc$ pour tout entier $c$.
\end{prop}


\Dem{$a|b\Longleftrightarrow \exists k\in\Z \text{ tel que } b=ak \Longrightarrow bc=akc$, puisque $kc\in \Z$ $a|bc$.}

\begin{prop}
Si $a|b$ alors $ac|bc$ pour tout entier $c$.
\end{prop}

\Dem{$a|b\Longleftrightarrow \exists k\in\Z \text{ tel que } b=ak\Longrightarrow bc=ack$, puisque $k\in \Z$ alors $ac|bc$}

\begin{prop}
Si $a|b$ et $a|c$ alors quelque soit les entiers $u$ et $v$ on a :
$$ a|ub+vc$$
\end{prop}

\Dem{$a|b\Longleftrightarrow \exists k\in\Z \text{ tel que } b=ak$, de même :
\\$a|c\Longleftrightarrow \exists k'\in\Z \text{ tel que }c=ak'$, d'où :\\
$ub=auk$ et $ vc=ak'v$ ce qui implique que :
$$ ub+vc=auk+ak'v=a(uk+k'v)$$
Puisque $uk+k'v\in\Z$ on a $a|ub+vc$.}


\begin{exoi}Déterminer les entiers $n$ tels que $2n+3$ divise $n-2$\end{exoi}

\begin{exoi}Soit $n$ un entier naturel, montrer que les diviseurs communs de $10n+3$ et $6n+1$ sont des diviseurs de $4$\end{exoi}

\begin{exoi}Démontrer par récurrence que pour $n\in \N*$, $3^{2n}-2^n$ est divisible par $7$.\end{exoi}

\begin{exoi}En choisissant le raisonnement qui vous semble le plus judicieux(raisonnement par l'absurde, par disjonction de cas, par contraposée, par la recherche d'un contre-exemple), répondre aux questions suivantes:
\begin{enumerate}
\item Montrer que $3n+7$ n'est pas divisible par $3$ pour tout entier naturel $n$
\item Pour tout entier $n$, si $n^2$ est impair alors $n$ est impair.
\item Pour tout entier $n$, l'entier $n(n+1)$ est pair
\item L'entier $n^2-n+3$ est-il divisible par $3$ pour tout entier naturel $n$?
\end{enumerate}
\end{exoi}

\begin{exoi}Un entier naturel est parfait s'il est égal à la somme de ses diviseurs positifs autres que lui-même.\\
Parmi les entiers suivants déterminer ceux qui sont parfaits : $20$, $28$ et $104$.\end{exoi}

\begin{exoi}On veut déterminer les entiers relatifs $n\neq -2$ tels que $\dfrac{2n-29}{n+2}$ soit un entier. 
\begin{enumerate}
\item Montrer que si $n$ esy solution alors $n+2$ divise $33$.\footnote{Utiliser la propriété 7}
\item Etablir la liste des diviseurs de $33$ dans $\Z$.\\
En déduire les valeurs possibles de $n$.
\item Conclure.
\end{enumerate}\end{exoi}
\pagebreak
\section{Division euclidienne}

\begin{exoi}Le relevé d'identité bancaire (RIB) est formé :
\begin{itemize}
\item d'un nombre de $21$ chiffres :
\begin{itemize}
\item cinq chiffres identifiant la banque,
\item cinq chiffres identifiant le guichet et,
\item onze chiffres représentant le numéro du compte.
\end{itemize}
\item suivi d'un nombre de $2$ chiffres qui est une clé de détection d'erreur dans l'un des $21$ précédents.
\end{itemize}
La clé est définie ainsi :\\
On note $A$ le nombre constitué des $21$ chiffres on calcule le reste $r$ de la division euclidienne de $100A$ par $97$ ; la clé $K$ est alors définie par $K=97-r$.\\
Soit $A=200410101278340238431$.
\begin{enumerate}
\item Ecrire $100A$ sous la forme $a\times 10^{12}+b\times 10^6+c$ avec $0\leq c< 10^6$ et dire combien de chiffres comporte $100A$.
\item Identifier $a$, $b$ et $c$.
\item Calculer le reste de la division euclidienne de $10^6$ par $97$ puis de $10^{12}$ par $97$.
\item Calculer la clé du nombre $A$.
\end{enumerate}
\end{exoi}

\subsection{Division euclidienne dans $\N$}

\begin{theo}
Pour tout entier naturel $a$ et pour tout entier naturel $b$ non nul, il existe un unique couple $(q;r)$ d'entiers naturels tels que :
$$ a=bq+r\qquad \text{avec } 0\leq r<b$$
\end{theo}

\Dem{\begin{itemize}
\item \fbox{Existence du couple $(q;r)$}
Posons $q=E\left(\dfrac{a}{b}\right )$.
\\$q$ est donc un entier naturel tel que $q\leq \dfrac{a}{b}<q+1$
\\Puisque $b>0$ on a $bq\leq b\dfrac{a}{b}<b(q+1)$ c'est à dire $bq\leq a<bq+b\Longleftrightarrow 0\leq a-bq<b$
\\Posons $r=a-bq$, on a : $a=bq+r$ et $0\leq r<b$
\\Ainsi pour tout entier relatif $a$ et tout entier naturel $b$ non nul, on a trouvé deux entiers naturels $q$ et $r$ tels que $a=bq+r$ et $0\leq r<b$
\item \fbox{unicité du couple $(q;r)$}
Raisonnons par l'absurde et supposons qu'il existe deux couples d'entiers naturels $(q,r)$ et $(q',r')$ tels que:
$a=bq+r=bq'+r'$ et $0\leq r<b$ et $0\leq r'<b$
\\Par différence : $r-r'=b(q'-q)$ ainsi $r-r'$ est un multiple de $b$. Ce multiple est compris entre $-b$ et $b$ donc cela ne peut être que $0$. donc $r=r'$.\\Donc $b(q'-q)=0$ et $b\neq 0$ donc $q'=q$.
Les deux couples sont identiques.
\end{itemize}
}

\begin{defi}
Pour tout entier relatif $a$ et tout entier naturel $b$ non nul, les entiers relatifs $q$ et $r$ vérifiant $a=bq+r$ et $0\leq r< b$ sont respectivement appelés \textbf{quotient} et \textbf{reste} de la division euclidienne de $a$ par $b$. $a$ est le dividende et $b$ le diviseur.
\end{defi}

\begin{exoi}En athlétisme, le $3000$ mètres steeple se court sur une piste de $390$ mètres de long passant par le saut d'une rivière.
\\ A quelle distance avant la ligne d'arrivée doit-on positionner la ligne de départ?
\end{exoi}


\begin{exoi}\begin{enumerate}
\item Le reste de la division euclidienne de l'entier naturel $a$ par $18$ est $13$. \\
Quel est le reste de la division euclidienne de $a$ par $9$ ? par $6$ ? par $3$ ?
\item \begin{enumerate}
\item Montrer que tout entier naturel $n$ s'écrit nécessairement sous l'une des trois formes $3k$, $3k+1$, $3k+2$ avec $k\in \N$.
\item Montrer que dans la division euclidienne de $(n^2+n)$ (où $n$ est un entier quelconque) par $3$, le reste n'est jamais égal à $1$. 
\end{enumerate} 
\end{enumerate}
\end{exoi}
\subsection{Division euclidienne dans $\Z$}

Cela n'a qu'une importance toute relative (et théorique) mais on peut définir la division euclidienne dans $\Z$ :

\begin{theo}
Pour deux entiers relatifs $a$ et $b$ (avec $b\neq 0$), il existe un unique couple $(q;r)$ avec $q\in\Z$, $r\in \N$ ; tel que :
$$ a=bq+r\qquad \text{avec } 0\leq r<|b| $$
\end{theo}

\begin{defi}
$q$ est alors le quotient et $r$ le reste de la division euclidienne de $a$ par $b$.
\end{defi}

\Rq{$b|a$ si et seulement si, le reste de la division euclidienne de $a$ par $b$ est nul.}

\begin{exoi}Effectuer les divisions euclidiennes de $a$ par $b$ pour chacun des quatre cas suivants :
\begin{multicols}{2}
\begin{enumerate}
\item $a=2013$ et $b=7$ ;
\item $a=2013$ et $b=-7$ ;
\item $a=-2013$ et $b=7$ ;
\item $a=-2013$ et $b=-7$.
\end{enumerate}
\end{multicols}
\end{exoi}

\pagebreak

\Dem{
La démonstration du théorème précédent est quasiment identique à celle effectué dans le cas où $a$ et $b$ sont des entiers naturels ; en particulier l'unicité du couple $(q;r)$ se démontre comme précédemment. En ce qui concerne l'existence il convient de distinguer les cas suivants, et de vérifier que les couples proposées fonctionnent : 
\begin{itemize}
\item $a>0$ et $b>0$ alors $q=E\left(\dfrac{a}{b}\right)$ et $r=a-bq$.
\item $a<0$ et $b>0$ alors $q=E\left(\dfrac{a}{b}\right)$ et $r=|bq|-|a| $
\item $a>0$ et $b<0$ alors $q=E\left(\dfrac{a}{b}\right)+1$ et $r=a-bq$
\item $a<0$ et $b<0$ alors $q=E\left(\dfrac{a}{b}\right)$ et $r= |bq|-|a| $
\item si $a=0$ alors $q=0=r$
\end{itemize}
}

\begin{exoi}\begin{enumerate}
\item Montrer, en effectuant une division euclidienne posée, que le développement décimal d'un rationnel est périodique.
\item Réciproquement, montrer qu'un réel dont le développement décimal est périodique est un rationnel.
\item \begin{enumerate}
\item Quelle est la période du développement décimal de $\dfrac{3}{7}$ ?
\item Quelle fraction possède pour développement décimal $0,\overline{63}$ ? $34,\overline{63}$ ? $0,\overline{0,99}$ ? $31,123\overline{45}$ ? 
\end{enumerate}
\end{enumerate}
\end{exoi}

\begin{exoi}Que peut-on dire d'une suite d'entier naturel strictement décroissante ?\footnote{L'ensemble $\N$ est archimédien i.e que toute ensemble non vide de $\N$ possède un plus petit élément. Ce n'est pas le cas pour l'ensemble des réels positifs.}
\end{exoi}


\begin{exoi}\begin{enumerate}
\item Effectuer la div euclidienne de 3217 par 19, de -1273 par 17, de 228 par -15 et de -329 par -30.
\item Déterminer des entiers naturels a et b tels que leur somme soit égale à 283 et que dans la division de a par b, le quotient soit 5 et le reste 13.
\item $n$ désigne un entier naturel.
\begin{enumerate}
\item Réaliser la division de $n^2+2n+2$ par  $n+3$ pour montrer que $n^2+2n+2=(n+3)(n-1)+5$.
\item Déterminer les entiers naturels $n$ tels que $ \dfrac{n^2+2n+2}{n+3}\in\N$
\end{enumerate}
\item Soit $ n$un entier naturel non nul. Effectuer la division euclidienne de :
\begin{multicols}{3}
\begin{enumerate}
\item $2n^2 + n$ par $n + 1$ ;
\item $n^2 +2n+3$ par  $n+2$ ;
\item $ 3^n-2$ par $3^{n-1}$.
\end{enumerate}
\end{multicols}
\end{enumerate}\end{exoi} 



Page suivante l'exemple d'un programme en python basé sur cette démonstration :

\begin{center}
\includegraphics[scale=1]{python2.eps}
\includegraphics[scale=1]{python3.eps}
\end{center}



\section{Congruence}

\begin{exoi}
L'année $2012$ a débuté par un Dimanche.
\begin{enumerate}
\item Calculer $N$ le nombre de jours qui séparent sa propre naissance, du $1^\text{er}$ janvier 2012.
\\
\textit{Attention} : tous les 4 ans, il y a une année bissextile qui compte $366$ jours : $2000$ était une année bissextile.
\item Calculer le reste de la division euclidienne de $N$ par $7$. Expliquer le choix du nombre $7$.
\item En déduire le jour de sa propre naissance.
\end{enumerate}
\end{exoi}

\Expl{Mr.Z est né le  \begin{center}
\textit{25 avril 1982}\end{center}
Curieux il aimerait savoir à quel jour de la semaine cela correspond.\\
On sait que le premier jour de $2012$ était un dimanche.
\\
 Entre le 25 avril 1982 et le 1 janvier 2012 il s'est écoulé
$$ 2012-1982-1=29 \text{ années complètes}$$
Or, $29=4\times 7+1$, parmi ces $29$ années $7$ furent bissextiles et donc $22$ ne le furent pas, au total il y eut :
$$ 366\times 7+365\times 22=10592 \text{ journées}$$
Du $25$ avril jusqu'au terme de cette merveilleuse année $1982$ on dénombre pas moins de :
$$ 30-25+1+31+30+31+31+30+31+30+31=6+31\times 5+30\times 3=251 \text{ jours}$$
Notons que durant le mois d'avril pour le jeune bébé $6$ jours sont passés.\\
Ainsi nous concluons qu'entre le $25$ avril $1982$ et le $1$ janvier 2012 :
$$\text{ Monsieur Z. a vécu }251+10592=10843   \text{ journées paisibles.}$$
Enfin $10843\equiv 0[7]$, on en conclut que Mr. Z est né un dimanche, ce qui explique beaucoup de choses...
}

\begin{defi}
Soit $a$ et $b$ deux entiers relatifs.\\
Soit $n\in\N^*$, on dit que $a$ et $b$ sont congrus module $n$ si, et seulement si, $a$ et $b$ ont le même reste dans la division euclidienne par $n$. On écrit :
$$ a\equiv b(n)\qquad \text{ou}\qquad a\equiv b[n]$$
\end{defi}

\Expls{Puisque $145=13\times 11+2$ et $119=13\times 9+2$ on conclut que :
$$ 145\equiv 119[13]$$
}

\begin{exoi}
Vérifier que $29\equiv -121[5]$ et $-623\equiv 17[10]$.
\end{exoi}



\Rq{Si le reste de la division euclidienne de $a$ par $n$ est $r$ alors $a\equiv r[n]$. Dès lors que $0\leq r <n$ et $a\equiv r[n]$ alors $r$ est le reste de la division euclidienne de $a$ par $n$. }

Voici une propriété très pratique :

\begin{prop}
Pour tout entier naturel $n\geq 2$ on a :
$$ a\equiv b[n]\quad \text{si, et seulement si }\quad n\text{ divise } a-b$$
\end{prop}


\Dem{
$\Rightarrow $ : Si $a\equiv b \, [n]$ alors il existe un unique couple $(q,r)$ d'entiers tel que $a=qn+r$ avec 
$0\leq r < n$ et un unique couple $(q',r)$ d'entiers tels que $b=q'n+r$.\newline
Donc $a-b=qn-q'n=(q-q')n$ et $n|(a-b)$\newline
$\Leftarrow$ : Si $n|(a-b)$ alors il existe $k\in\N$ tel que $a-b=kn$.\newline
D'apr\`es la division euclidienne, il existe un unique couple $(q,r)$ avec $0\leq r <n$ tel que $a=qn+r$ 
et un unique couple $(q',r')$ avec $0\leq r' <n$ tel que $b=q'n+r'$. \newline
Donc $a-b=(q-q')n+r-r'$ avec $-n< r-r' < n$. Comme $a-b$ est un multiple de $n$ on a $r-r'$ est un multiple de $n$. \newline
Or $r-r'\in \N$ et le seul multiple de $n$ dans $]-n;n[$ est $0$. Donc $r=r'$ et $a\equiv b \, [n]$ 
}


\begin{exoi}
Vérifier à l'aide de cette propriété que $29\equiv -121[5]$ et $-623\equiv 17[10]$.
\end{exoi}



\begin{prop}
Si $a\equiv b \,[n]$ et $b\equiv c \,[n]$ alors $a\equiv c \,[n]$
\end{prop}

\Dem{Puisque $a\equiv b [n]$ et $b\equiv c \,[n]$ on en déduit que $n| a-b$ et que $n|b-c$, par conséquent $n|1\times (a-b)+1\times (b-c)$ i.e :
$$ n|a-c$$
Et donc $$ a\equiv c[n]$$}

\begin{prop}
$a\equiv 0 \,[n] \Longleftrightarrow n|a$
\end{prop}

\Dem{$a\equiv 0 \,[n]\Longleftrightarrow n|a-0\Longleftrightarrow n|a$}

\begin{prop}
Si $n'|n$ alors $a\equiv b \, [n] \Rightarrow a\equiv b \, [n']$
\end{prop}

\Dem{Puisque $a\equiv b[n]$ on a $n|a-b$ et comme de plus $n'|n$ on a encore $n'|a-b$ par conséquent :
$$ a\equiv b[n']$$
Notons que la réciproque, pour s'en convaincre observons l'exemple suivant :
$$ 10|20 \quad 12\equiv 2[10]$$
or, $12$ n'est pas congrue à $2$ modulo $20$ puisque $20$ ne divise pas $12-2=10$.}

\begin{theo}
On note $a$, $a'$, $b$ et $b'$ quatre entiers relatifs quelconques et $n\geq 2$ un entier naturel.
Si $a \equiv a' \, [n]  $ et $b \equiv b' \, [n]  $ alors :\newline
$$a+b \equiv a'+b' \, [n]  $$
$$a-b \equiv a'-b' \, [n]  $$
$$ab \equiv a'b' \, [n]  $$
$$\forall k\in\Z, \quad ka \equiv ka' \, [n]  $$
$$\forall p \in \N, \quad a^p \equiv a'^p \, [n]  $$
\end{theo}

\Rq{ $ka \equiv ka' \, [n] \nRightarrow a \equiv a' \, [n]  $
}

\Cexpl{$16 \equiv 20 \, [4]  $ mais $8$ et $10$ ne sont pas congrus modulo $4$
}


\Dem{
Si $a \equiv a' \, [n]  $ il existe $k_1\in\N$ tel que $a=a'+k_1n$
Si $b \equiv b' \, [n]  $ il existe $k_2\in\N$ tel que $b=b'+k_2n$
Donc : 
$$a+b=(a'+b') + n(k_1+k_2) \quad \textrm{ Donc } a+b\equiv a'+b' \, [n]$$
$$a-b=(a'-b') + n(k_1-k_2) \quad \textrm{ Donc } a-b\equiv a'-b' \, [n]$$
$$ab=(a'+k_1n)(b'+k_2n)= a'b'+n(a'k_2+b'k_1+k_1k_2n) \quad \textrm{ Donc } ab\equiv a'b' \, [n]$$
$$\forall k\in\Z, \quad ka=ka'+ nk_1 \quad \textrm{ Donc } ka\equiv ka' \, [n]$$
On d\'emontre cette partie par r\'ecurrence  : \newline
Initialisation : On a $a^1\equiv a'^1 \, [n]$\newline
H\'er\'edit\'e : On suppose que la propri\'et\'e est vraie au rang $k$, donc que $a^k \equiv a'^k \, [n] $\newline
Alors $a^{k+1}=a^k \times a  \equiv a'^k \, [n] $. Donc $ a^{k+1}\equiv a'^{k+1} \, [n]$.\newline
La propri\'et\'e est h\'er\'editaire et vraie au rang 1. Elle est vraie pour tout $p \in \N^*$
}


\begin{exoi}
\textbf{Une annale des temps très ancien - Asie 2002}\\
On considère les suites $\left(x_n\right)$ et $\left(y_n\right)$ définies par $x_0 = 1,~y_0 = 8$ et

\renewcommand\arraystretch{2}
\[ \left\{ \begin{array}{l c l}
x_{n+ 1} & = &  \dfrac{7}{3}x_n + \dfrac{1}{3} y_n + 1\\
y_{n + 1} &  =& \dfrac{20}{3}x_n + \dfrac{8}{3} y_n + 5\\
\end{array}\right., ~n \in \N \]
\renewcommand\arraystretch{1} 
\begin{enumerate} 
\item Montrer, par récurrence, que les points $M_n$ de
 coordonnées $\left(x_n~;~~y_n\right)$ sont sur la droite $(\Delta)$ dont une équation est $5x - y + 3 = 0$. En déduire que $x_{n+ 1} = 4x_n + 2.$ 
\item Montrer, par récurrence, que tous les $x_n$ sont des
 entiers naturels. En déduire que tous les $y_n$ sont aussi des entiers naturels.
\item Montrer que :
	\begin{enumerate} 
		\item $x_n$ est divisible par 3 si et seulement si $y_n$ est divisible par 3.
		\item Si $x_n$ et $y_n$ ne sont pas divisibles par 3, alors ils sont
 premiers entre eux. 
 	\end{enumerate}
\item 
	\begin{enumerate} 
		\item Montrer, par récurrence, que $x_n = \dfrac{1}{3} 
\left(4^n \times  5 - 2\right).$ 
		\item En déduire que $4^n \times  5 - 2$ est un multiple de 3, pour tout
 entier naturel $n$.  
	\end{enumerate} 
\end{enumerate}
\end{exoi}
\pagebreak  
\begin{exoi}
Le numéro \textbf{INSEE} (Institut National des Statistiques et des Etudes Economiques) d'un individu est constitué de $15$ chiffres.\\
Le premier chiffre est $1$ si le sujet est un homme, $2$ si le sujet est une femme ;\\
les deux suivants correspondent aux deux derniers chiffres de son année de naissance ;\\
les deux suivants correspondent au mois de sa naissance ;\\
les deux suivants correspondent au département de sa naissance ;\\
les trois suivants correspondent au numéro de la commune de sa naissance ;\\
les trois derniers correspondent au numéro d'inscription sur le registre d'état civil ;\\
les trois derniers correspondent au numéro d'inscription sur le registre d'état civil.\\
On accorde à ce numéro, une clé de 2 chiffres calculée à partir des 13 précédents.\\
Par exemple le numéro :2960622645001 est celui d'une femme, née en 1996, au mois de Juin dans le département des côtes d'Armor, dans la commune 645 ; elle est la première enregistrée au mois de Juin.\\
Le calcul de la clé suit l'algorithme suivant :
\begin{center}
\Algo{8cm}{
\Entree{ 
 $A$  est un entier constitué de $13$ chiffres.\\
$ r$ et $K$ sont des nombres entiers.\\
}
{
Entrer $A$ \\
$r$ est le reste de la division euclidienne de $A$ par $97$.
\\
$K$ vaut $97-r$.
\\Afficher $K$
}
}
\end{center}
\textbf{On appelle $A$ le numéro INSEE de l'exemple précédent.}
\begin{enumerate}
\item Calculer la clé $K$ de $A$
\item On écrit $A$ sous la forme $A=x\times 10^6+y$ avec $0\leq y<10^6$, montrer que $10^6\equiv 27 [97]$. En déduire que $r\equiv 27x+y[97]$.
\item Déterminer la clé de son propre numéro INSEE.
\end{enumerate}
\end{exoi}



\begin{exoi}D\'emontrer que $2^{3n}-1$ est divisible par 7 pour tout $n\in \N$. \end{exoi} 

\begin{exoi}D\'emontrer que $671^{800}-1$ est divisible par 6. \end{exoi}

\begin{exoi}Le but de cet exercice est de calcuer le reste de la division par 7 du nombre $247^{349}$
\begin{enumerate}
 \item V\'erifier que $247\equiv 2 \, [7]$
 \item V\'erifier que $2^{3k}\equiv 1$, $2^{3k+1}\equiv 2$,$2^{3k+2}\equiv 4$ $[7]$
 \item En d\'eduire le reste  de la division de $247^{349}$ par $7$.
\end{enumerate}
\end{exoi}


\begin{exoi}
\begin{enumerate}
\item Le nombre $A=1305^{1305}+900^{900}$ est-il divisible par $29$ ?
\item On considère un entier naturel $n$ supérieur ou égal à $2$.\\
Calculer le reste de la division euclidienne de $27^{2012}$ par $7$.
\\
On pourra utiliser le fait que :
$$ n-1\equiv -1[n]$$
\item \begin{enumerate}
\item Quel est le reste de la division euclidienne de $1000$ par $37$ ?
\item En déduire que pour tout entier naturel $n$, le reste de la division euclidienne de $10^{3n}$ par $37$ est égal à $1$.
\item Quel est le reste de la division euclidienne du nombre $N=10^{10}+10^{20}+10^{30}$ par $37$ ? 
\end{enumerate}
\end{enumerate}
\end{exoi}


\begin{exoi}
On considère un entier $n$ quelconque.
\begin{enumerate}
\item Quels sont les restes possibles de la division euclidienne de $n^2$ par $5$ ?
\item Quels sont les restes possibles de la division euclidienne de $n^3$ par $5$ ?
\end{enumerate}
\end{exoi}

\begin{exoi}
\begin{enumerate}
\item 
Déterminer le reste dans la division euclidienne de $25\times 2^{17}$ par $7$
\item Montrer que, pour tout entier $n$, $7^n+3^n+2$ est divisible par $4$.
\end{enumerate}
\end{exoi}

\begin{exoi}
\textbf{Une annale des temps anciens - Amérique du nord 2006}
\begin{enumerate}
\item  \emph{Cette question constitue une restitution organisée de connaissances}
	\begin{enumerate}
		\item  Soient $a,~ b,~ c$ et $d$ des entiers relatifs.\\
Démontrer que : si $a \equiv b \mod 7$ et $c  \equiv d \mod 7$ alors $ac \equiv  bd \mod 7$.
		\item En déduire que : pour $a$ et $b$ entiers relatifs non nuls\\
si $a \equiv b \mod 7$ alors pour tout entier naturel $n,~ a^n \equiv  b^n \mod 7$.
	\end{enumerate}
\item Pour $a = 2$ puis pour $a =  3$, déterminer un entier naturel $n$ non nul tel que $a^n \equiv  1 \mod 7$.
\item Soit $a$ un entier naturel non divisible par 7.
	\begin{enumerate}
		\item  Montrer que : $a^6 \equiv 1 \mod 7$.
		\item On appelle \emph{ordre} de $a \mod 7$, et on désigne par $k$, le plus petit entier naturel non nul tel que $a^k \equiv 1 \mod 7$. Montrer que le reste $r$ de la division euclidienne de 
$6$ par $k$ vérifie $a^r \equiv 	1 \mod 7$.\\
En déduire que $k$ divise $6$.\\
Quelles sont les valeurs possibles de $k$ ?
		\item Donner l'ordre modulo 7 de tous les entiers $a$ compris entre $2$ et $6$.
	\end{enumerate}
\item A tout entier naturel $n$, on associe le nombre
 
\[A_{n} = 2^n  + 3^n + 4^n + 5^n + 6^n.\]

Montrer que $A_{2006} \equiv  6 \mod 7.$
\end{enumerate}
\end{exoi}
\pagebreak

\section{Application aux codages}
\subsection{Les nombres premiers - définitions}


\begin{defi}On dit qu'un entier naturel $p$ est premier s'il poss\`ede exactement 2 diviseurs positifs : 1 et lui-m\^eme.\end{defi}



\Expls{
\begin{itemize}
 \item 0 n'est pas premier car il admet une infinit\'e de diviseurs
 \item 1 n'est pas premier car il n'admet qu'\textit{un seul} diviseur : lui-m\^eme.
 \item 2 est le seul nombre premier pair (les autres sont divisibles au moins par 1, eux-m\^emes et 2).
 \item 3, 5, 7, 11, 13 sont des nombres premiers.
 \item 6 n'est pas un nombre premier, car il est divisible par 1, 6, 2 et 3.
\end{itemize}
}

%\begin{theo}Soit $n\in \N$ sup\'erieur ou \'egal \`a 2. Alors :
%\begin{itemize}
%\item $n$ admet au moins un diviseur premier
%\item  Si $n$ n'est pas premier, alors il admet au moins un diviseur premier $p$ tel que $p \leq \sqrt{n}$. 
%\end{itemize}
%\end{theo}
%
%\Dem{Si $n$ est premier, alors il s'admet lui-m\^eme comme diviseur premier. \\
%Sinon, $n$ admet au moins un diviseur propre. Supposons tous les diviseurs de $n$ soient sup\'erieurs strictement \`a $\sqrt{n}$. Alors il existe $a>\sqrt{n}$ et $b>\sqrt{n}$ tels que $a\times b =n$ mais $a\times b >\sqrt{n}^2=n$. Ce qui est absurde.}
%
%\begin{coro}Soit $n\in \N$ sup\'erieur ou \'egal \`a 2. Alors si $n$ n'admet aucun diviseur inf\'erieur ou \'egal \`a sa racine carr\'e, alors $n$ est premier\end{coro}
%
%\Dem{C'est la contrapos\'ee du th\'eor\`eme.}
%
%
%\begin{theo}Il existe une infinit\'e de nombres premiers.\end{theo}
%
%\Dem{Supposons qu'il existe un nombre fini $n$ de nombres premiers, not\'es $p_1$, $p_2$, $\dots$, $p_n$. On pose $N=p_1\times p_2 \times \dots \times p_n + 1$. \newline
%Alors si $N$ est premier, on a trouv\'e un autre nombre premier, l'hypoth\`ese de d\'epart est donc absurde.\newline
%Si $N$ n'est pas premier, alors il admet un certain diviseur premier $k$. Si $k=p_i$ alors $k | p_1p_2 \dots p_n$ et $k|N$ donc $k|1$ (la diff\'erence). Donc $k=1$, mais $k$ est premier donc c'est impossible.\newline
%Par cons\'equent on a trouv\'e un autre nombre premier, l'hypoth\'ese est absurde.\newline
%Dans les deux cas possibles, l'hypoth\`ese est absurde, donc elle l'est toujours. }
\pagebreak
\begin{lem}
\hfill \textbf{Lemme d'euclide}\\
Si un nombre premier $p$ divise le produit $ab$ alors il divise $a$ ou il divise $b$.
\end{lem}

\Dem{
Raisonnons par l'absurde i.e supposons qu'il existe deux entiers naturels $a$ et $b$ tels que $p$ divise $ab$ mais ne divise ni $a$ ni $b$.Notons cette propriété $*$
\\
Pour $p$ et $a$ fixés, considérons le plus petit entier $b$ tel que $p$ divise $ab$ et $p$ ne divise ni $a$ ni $b$. 
\\
Notons $r$ le reste (qui ne vaut pas $0$ puisque $p$ ne divise pas $b$) de la division euclidienne de $b$ par $p$ alors $$ b\equiv r [p] \qquad \text{et} \qquad 1\leq r<p$$
Par conséquent, en multipliant par $a$ on a $ab\equiv ar [p]$. Puisque $p$ divise $ab$ alors il divise $ar$ mais ne divise ni $a$ ni $r$. Puisque $b$ est le plus entier satisfaisant $*$ que $r$ satisfait aussi $*$ alors $b\leq r$. Notons qu'il existe un entier naturel $q$ tel que $b=pq+r$, par conséquent $b\geq r$ donc $b=r$. Par conséquent :
$$ 1\leq b<p$$
Notons alors $b'$ le reste de la division euclidienne de $p$ par $b$, alors il existe un entier naturel $m$ tel que $$ p=mb+b'\qquad \text{avec } 0\leq b'<b $$
Si $b'=0$ alors $b$ divise $p$ qui est un nombre premier. Comme $b\in \N$ et $b<p$ alors $b=1$, ce qui contredit notre hypothèse de départ (en effet puisque $p|ab=a$ alors $p$ divise $a$). Par conséquent :
$$ 1\leq b'<b<p$$
Enfin $ab'=a(p-mb)=ap-abm$, puisque $ab$ est un multiple de $p$, alors $ab'$ est un multiple de $p$ aussi.\\
La situation est donc la suivante :
\begin{center}
$p$ divise $ab$ mais ne divise ni $a$, ni $b$ \qquad $*$.
\end{center}
\begin{enumerate}
\item $b$ est le plus petit des entiers naturels satisfaisant $*$.
\item $p$ divise $ab'$ mais ne divise ni $a$ ni $b'$ (en effet $1\leq b'<b<p$). Par conséquent $b'$ satisfait $*$.
\item Enfin $1\leq b'<b$. Ceci est en contradication avec le point $1$.
\end{enumerate}
Il n'existe donc pas de plus petit entier naturel $b$ satisfaisant $*$, on en déduit qu'il n'existe pas d'entier $b$ tel que $p|ab$ et $p$ ne divise ni $a$ ni $b$, quelque soit $a$ et $p$.
}

%\subsection{D\'ecomposition en nombres premiers}
%
%\begin{theo}
%Tout entier naturel sup\'erieur ou \'egal \`a deux est :
%\begin{itemize}
% \item Soit un nombre premier
% \item Soit un produit de puissance de nombres premiers.
%\end{itemize}
%Cette \'ecriture, appel\'ee \textit{d\'ecomposition en nombres premiers} est unique \`a l'ordre des facteurs pr\`es.
%\end{theo}
%
%\Dem{Supposons $n$ non premier. \newline
%Existence : \newline
%Soit $n\geq 2$. D'apr\`es le th\'eor\`eme pr\'ec\'edent, $n$ admet un diviseur premier $p_1$ et l'on a $n=p_1n_1$ 
%avec $2 \leq n_1 < n$ ($n$ n'est pas premier donc $n_1 \neq 1$). \newline
%Par le th\'eor\`eme pr\'ec\'edent, on a de m\^eme que $n_1$ admet un diviseur premier $p_2$ et que $n=p_1p_2n_2$ 
%avec $1\leq n_2 < n_1 < n$. Si $n_2=1$ alors $n_1$ est premier et le r\'esultat est d\'emontr\'e. Sinon on r\'eit\`ere le raisonnement tant que le quotient est diff\'erent de 1.
%La liste des quotients est une liste d\'ecroissante d'entiers naturels, elle admet donc un plus petit \'el\'ement $n_k$ et est finie. On a alors $n=p_1p_2 \dots p_k$\newline
%Unicit\'e : Admise pour l'instant (cf exo 24 p 81)}
%
%\Expls{ 
%On utilise les crit\`eres de divisibilit\'e.
%$105=3\times 5\times 7 \quad ; \quad 83 160 = 2^3 \times 3^3 \times 5 \times 7 \times 11$. 
%}
%
%
%\begin{theo}
%Soit $n$ un entier naturel sup\'erieur ou \'egal \`a 2 se d\'ecomposant en produit de facteurs premiers sous la forme $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$. \newline
%Les diviseurs positifs de $n$ sont les nombres de la forme $p_1^{\beta_1}p_2^{\beta_2}\dots p_k^{\beta_k}$, avec $0\leq \beta_i \leq \alpha_i$ pour tout $1 \leq i \leq k$.
%\end{theo}
%
%\Dem{Il est clair que les nombres de cette forme divisent $n$ car $\alpha_i-\beta_i \geq 0$ pour tout $1 \leq i \leq k$.\newline
%D\'emontrons maintenant que tout diviseur de $n$ est de cette forme.\newline
%Soit $d$ un diviseur de $n$. Alors il existe un entier $d'$ tel que $n=d\times d'$. Le produit des d\'ecompositions en facteurs premiers de $d$ et $d'$ est une d\'ecomposition en produit de facteurs premiers de $n$. \newline
%Comme elle est unique, c'est la m\^eme.\newline
%Les seuls diviseurs premiers intervenant dans les d\'ecompositions de $d$ et $d'$ sont donc les $p_i$ et leur exposant ne peuvent \^etre qu'inf\'erieurs ou \'egaux aux $\alpha_i$.\newline
%L'entier $d$ est donc forc\'ement de la forme indiqu\'ee.}
%
%\begin{coro}Soit un entier $n \leq 2$ se d\'ecomposant en produit de facteurs premiers sous la forme $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$. \newline
%Alors, $n$ poss\`ede $(\alpha_1+1)\times (\alpha_2 + 1) \times \dots \times (\alpha_k+1)$ diviseurs positifs.\end{coro}
%
%\Dem{D\'enombrement.}
%
%\Exo{\textbf{Antilles-Guyanne, Juin 2005} \hfill (5 points)\\
%\begin{enumerate}
%\item \begin{enumerate}
%      \item D\'eterminer suivant les valeurs de l'entier naturel non nul $n$ le reste dans la division euclidienne 
%	par 9 de $7^n$.
%       \item D\'emontrer alors que $2005^{2005}\equiv 7 \, [9]$
%      \end{enumerate}
%\item \begin{enumerate}
%      \item D\'emontrer que pour tout entier naturel non nul $n$ : $10^n \equiv 1 \, [9]$
%       \item On d\'esigne par $N$ un entier naturel \'ecrit en base 10, on appelle $S$ la somme de ses chiffres. \\
%      D\'emontrer la relation suivante : $N \equiv S \, [9]$
%      \item En d\'eduire que $N$ est divisible par 9 si et seulement si $S$ est divisible par $9$.
%      \end{enumerate}
%\item On suppose que $A=2005^{2005}$ ; on d\'esigne par : \begin{itemize}
%							  \item $B$ la somme des chiffres de $A$
%                                                          \item $C$ la somme des chiffres de $B$
%							  \item $D$ la somme des chiffres de $C$
%                                                          \end{itemize}
%      \begin{enumerate}
%      \item D\'emontrer la relation suivante : $A \equiv D \, [9]$
%      \item Sachant que $2005 <10000$, d\'emontrer que $A$ s'\'ecrit en num\'eration d\'ecimale avec au plus 8020 chiffres. \\
%      En d\'eduire que $B \leq 72180$.
%      \item D\'emontrer que $C \leq 45$
%      \item En \'etudiant la liste des entiers inf\'erieurs \`a 45, d\'eterminer un majorant de $D$ plus petit que 15.
%      \item Montrer que $D=7$.
%      \end{enumerate}
%\end{enumerate}
%}

\pagebreak
\subsection{Chiffrement Affine}

A chaque lettre de l'alphabet, on associe, gr\^ace au tableau ci-dessous, un nombre entier $m$ compris entre $0$ et $25$.

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


On définit un système de codage en associant à l'entier $m$ l'entier $p$ qui est le reste de la division euclidienne de $f(m)$ par $26$ où $f$ est une fonction affine.

Un tel codage est dit affine. On cherche la fonction $g$ de décodage.

\begin{exoi}
La fonction $f$ est définie par $f(m)=21m+11$.
\end{exoi}
\begin{enumerate}
\item Coder NOTE.
\item Trouver un entier $x$ tel que $21x\equiv 1[26]$.
\item Démontrer que $$ 105m+55\equiv m+3[26]$$
\item Démontrer que si $21m+11\equiv p[26]$ alors $m\equiv 5p-3[26]$.
\item Démontrer que si $m\equiv 5p-3[26]$ alors $21m+11\equiv p[26]$.
\item Donner alors la fonction $g$ de décodage et décoder GLB.
\end{enumerate}

\begin{exoi}
La fonction $f$ est définie par $f(m)=15m+14$
\begin{enumerate}
\item Coder le mot $BAC$.
\item Ecrire un algorithme permettant de trouver le plus petit entier $x$ tel que $15x\equiv 1[26]$. Donner $x$.
\item Démontrer que $$ 105m+98\equiv m+20[26]$$
\item Démontrer que si $15m+14\equiv p[26]$ alors $m\equiv 7p-20[26]$.
\item Démontrer que si $m\equiv 7p-20[26]$ alors $15m+14\equiv p[26]$.
\item Donner alors la fonction $g$ de décodage et décoder GLB.
\end{enumerate}
\end{exoi}

\subsection{Autre codage}

\begin{exoi}
On considère la fonction $f$ de codage définie par $f(x)$ est égal au reste de la division euclidienne de $x^5$ par $26$.
\begin{enumerate}
\item A l'aide d'un programme ou de votre calculatrice dresser le tableau de congruence des valeurs de $x^5$ modulo $26$.
\item Coder le mot TEST.
\item \begin{enumerate}
\item Compléter le tableau de congruence pour obtenir les valeurs de $x^{25}$ modulo $26$ et vérifier que pour tout entier $x$ :
$$ x^{25}\equiv x [26]$$
\item Décoder le mot STK.
\item En déduire que la fonction de décodage est $f$ elle-même. 
\end{enumerate}
\end{enumerate}
\end{exoi}

\subsection{Chiffrement de Vigenère}

On se fixe une clé sous la forme d'un mot (exemple : SINUS).

On veut coder le message \og{} VIVE LA SPE MATH \fg{}.

On écrit la phrase à coder et en dessous, la clé autant de fois que nécessaire.

Chaque lettre est codée par son rang entre 0 et 24. On additionne les nombres de chaque lettre avec celui de la lettre de la clé et on calcule les restes modulo 26 de chaque résultat. On obtient le message codé.

\begin{center}
\includegraphics[scale=0.5]{tab.eps}
\end{center}

Pour décrypter il suffit de soustraire la clé au texte chiffré.

\begin{exoi}
\begin{enumerate}
\item Crypter le mot SPECIALITE avec la clé BAC.
\item On suppose que la longueur de la clé est de $3$ lettres.
On donne un texte crypté avec cette clé dont le début est donné ci-dessous. Les lettres ont été regroupées par paquets de $3$.

NEK UVG DST CIC VWW SYP BVD SIR FVE IIV FRC JXG OWQ OFG DYP GVQ NEI F\dots

En étudiant les fréquences d'apparation des lettres sur l'ensemble du texte, on a les résultats suivants :
\begin{itemize}
\item La première lettre de chaque mot la plus fréquente est le F ;
\item la lettre centrale de chaque mot la plus fréquente est le I ;
\item la lettre finale de chaque mot la plus fréquente est le G.
\end{itemize}
\begin{enumerate}
\item En admettant que la lettre la plus fréquente d'un groupe de lettre assez grand est le E, déterminer la clé de ce chiffrement.
\item Décrypter le début du texte proposé.
\end{enumerate}
\end{enumerate}
\end{exoi}

\pagebreak

\subsection{Codage Affine par bigramme}

Tous les codes qui substituent une lettre à une autre lettre peuvent être assez facilement déchiffrés par une analyse fréquentielle. Pour éviter cela et rendre le code plus sûr on peut coder les mots par bloc de $2$ lettres. A chaque bloc de $2$ lettres, appelé bigramme, on associe un entier compris entre $0$ et $625$ à l'aide du tableau suivant. La première lettre correspond à la colonne et la deuxième lettre à la ligne.
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
 & A & B & C & D & E & F & G & H & I & \dots \\ \hline
 A & 0 & 1 & 2 & 3 & 4 & 5 & 6& 7 & 8 & \dots \\ \hline
 B & 26 & 27 & 28 & 29 & 30 & 31 & 32 & 33 & 34 & \dots \\ \hline
 C & 52 & 53 & 54 & 55 & 56 & 57 & 58 & 59 & 60 & \dots \\ \hline
 \dots &  &  &  &  &  &  &  &  &  &  \\ \hline
\end{tabular}
\end{center}
Par exemple le bigramme BC correspond à l'entier $53$ et le bigramme CB correspond à l'entier 28.
\begin{enumerate}
\item A quel entier correspond le bigramme FD ? et CG ?
\item Quel bigramme correspond à l'entier 440 ? à 108 ?
\\
\textit{Effectuer la division euclidienne par 26. A quoi correspondent q et r ?}
\\
On peut alors effectuer un chiffrement affine par la fonction $f$ de codage définie par $f(x)$ est égal au reste de la division euclidienne de $ax+b$ par $626$. Pour la suite de l'exercice on prendre les clés de codage $a=31$ et $b=10$.
\begin{enumerate}
\item Coder alors le message PATIENTE
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline 
& PA & TI & EN & CE\\ \hline
X & 15 & 227 & & \\ \hline
Y & 475 & & & \\ \hline
& HS & & & KG\\ \hline
\end{tabular}
\end{center}
\item Vérifier que $31\times 101 \equiv 1 [626]$.
\item En déduire que si $31x+10\equiv y [626]$ alors $x\equiv 101 y +242 [626]$.
\item Décoder le message RUEOUK.
\end{enumerate}
\end{enumerate}
\end{document}