\documentclass[10pt,a4paper]{report}
\usepackage[height=250mm,width=183mm]{geometry}
\usepackage{preambule}
\usepackage[upright]{fourier}

%\usepackage{listings}
\usepackage{algorithm}
\usepackage{algorithmic}
% \lstloadlanguages{XCAS}
% \lstset{numbers=none,language=XCAS,%
% keywordstyle =\color{blue}\bfseries,%basicstyle=\sffamily,%\small,
%     backgroundcolor=\color{green}}
   



%\usepackage[upright]{fourier}
\newcommand{\N}{\mathbb{N}}

\newcommand{\Z}{\mathbb{Z}}
%\input{/home/moi/Lycee/makalice}
\setlength{\parindent}{0pt}
\entete{\rightmark }{ \NoLecon\   leçon\   \NomLecon}{Lycée Jean Perrin - TS }
\usepackage{bbding,xlop,casio}


\graphicspath{{/home/moi/Photos/Tehessin/}{/home/moi/Figures/figuresAlice/}{/home/moi/Figures/FigSeconde/}{/home/moi/Photos/Maths/}}

\begin{document}
\thispagestyle{empty}
\setlength{\parindent}{0mm}
%\begin{minipage}[t]{0.75\textwidth}\vspace{0cm}
\LECOND{I}{Première}{ARITHM\'ETIQUE I }{}{ARITHM\'ETIQUE I}{Boulier.eps}
%\end{minipage}
%\begin{minipage}[t]{0.3\textwidth}\vspace{0cm}
%\hspace{-1.5cm}
%\includegraphics[width=\textwidth]{boulier.eps}
%\end{minipage}





% 
% 
% \begin{Abstract}
% {Téhessin avait choisi la spécialité math pour en découdre avec des
% exercices à sa hauteur et on commence par le faire compter sur ses
% doigts comme en maternelle~: Mathémator serait-il devenu sénile ou
% bien se moque-t-il de lui~?}
% \end{Abstract}

%\CHAP{DIVISION}{Division}


\section{EN GUISE D'\'ECHAUFFEMENT...}

\subsection{Savez-vous diviser~?}

\subsubsection{Divisons en dessinant}

Vous vous souvenez à peu près du mécanisme de la division que vous avez appris à l'école primaire : vous savez comment ça marche, mais savez-vous pourquoi ça marche~?

Pour vous raffraichir la mémoire, posez la division de 37 par 4.

Pour y voir plus clair, nous \og dessiner \fg cette division. L'idée de base vient du dessin suivant\footnote{C'est même le principe de la démonstration de l'existence de la division euclidienne que nous verrons plus tard.} : 

\begin{center}
\includegraphics{Nombres.1}
\end{center}


Commentez ce schéma.

Puisque nous voulons voir ce qui se passe \og après la virgule\fg, nous allons dessiner un segment de droite de 20~cm de long, la première graduation correspondra à 36, la dernière 40, l'unité valant 5~cm.

Placez-y 37. 

Divisez alors le segment $[36\pv 37]$ en 10. Que peut-on en déduire~? 

Divisez à nouveau en 10 le petit segment contenant 37. Si votre dessin est précis, que remarque-vous ? Qu'en concluez-vous~?


\subsubsection{Traduction du dessin en calcul}

Si vous tapez \CTrois \CSept \CDiv \CQuatre \ sur votre calculatrice, vous obtenez \textifsym{9.25} sur votre écran\footnote{C'est ce que vous aviez déjà obtenu en posant l'opération\dots}.

En pensant aux subdivisions que vous avez tracé sur votre schéma, essayez de  traduire le résultat lu à l'aide d'une égalité faisant intervenir 4, $\fr{4}{10}$ et $\fr{4}{100}$. 


\subsubsection{\og J'abaisse un zéro, je mets une virgule\fg}

Sans \og abaisser de zéro\fg, essayez de reposer votre division en utilisant les phrases \og en truc combien de fois quatre\fg, \og en truc combien de fois quatre dixièmes\fg, \og en truc combien de fois quatre centièmes\fg.


\subsection{Dessinons des racines}

Il aurait été plus correct d'intituler cette activité : \textbf{construisons des irrationnels à la règle et à l'équerre}.

Quelle est la longueur de la diagonale d'un carré de côté 1~? Déduisez-en une \textit{construction} de $\sqrt{2}$.

Construisez de même $\sqrt{5}$, $\sqrt{13}$, $\sqrt{11}$.


\sm

Casse-tête en forme d'escargot adepte du cubisme : quelle est la longueur du dixième segment gris de cette spirale\footnote{Je ne vous demande pas de prouver le résultat mais juste de le deviner} ?


\begin{center}
\includegraphics{Nombres.2}
\end{center}

%\break

\subsection{$\Mathbold{\sqrt{2}}$ est irrationnel}

\subsubsection{Qui se cache derrière l'écriture $\Mathbold{\sqrt{2}}$~?}

$\sqrt{2}$ : qu'est-ce que ça veut dire~? Vous rappelez-vous de la définition vue en collège\footnote{Vous pouvez rechercher comment nos voisins européens appellent ce nombre et comment on a pu l'appeler depuis l'Antiquité}~?

Pour les grecs, un nombre \og existait \fg si l'on pouvait le dessiner. Ayant à votre disposition une règle de longueur 1 et une équerre, pouvez-vous dessiner $\sqrt{2}$~?

\subsubsection{Rationnel or not rationnel?}

Comme son nom l'indique, un irrationnel est un nombre qui n'est pas rationnel\dots

Il serait donc utile de se souvenir de  ce qu'est un rationnel : rappelez la définition.

Ainsi, on ne sait pas vraiment ce qu'est un irrationnel, mais on sait ce qu'il n'est pas\footnote{C'est clair !}.

Une des premières questions qui surgit de votre esprit en ébullition est sûrement : est-ce que de tels nombres existent~?

Tapons \CShift\CRacine\CDeux sur notre machine. Nous obtenons \textifsym{1.414213562373}. On pourrait penser qu'en découpant le segment $[1\pv2]$ en fractions suffisamment petites, on puisse \og tomber\fg sur ce nombre, et donc l'exprimer en fractions d'unité. Que pourrait-on en déduire~?

Supposons donc que $\sqrt{2}$ soit un rationnel. Puisque je connais ma définition, je sais alors qu'il existe deux entiers - appelons-les $p$ et $q$ -  tels que $\sqrt{2}=\ofr{p}{q}$. Supposons que $p$ et $q$ sont choisis pour que la fraction soit la plus \og simple\fg possible : comment comprenez-vous cette formulation~?


\subsubsection{Où nous allons mettre au point un théorème sur la  parité}

Avant d'aller plus loin, faisons un petit aparté : comment traduire qu'un entier est pair~? Et tant qu'on y est qu'un entier est impair ? Essayer de donner une définition la plus générale possible mais qui permette de caluler\footnote{if you see what I mean\dots}.

À votre avis, $p$ et $q$ peuvent-ils être tous les deux pairs~?

Observez maintenant les liens entre la parité d'un nombre et celle de son carré sur quelques exemples. Cela vous donne des idées~? Essayez alors d'énoncer un théorème\dots puis de le prouver~! 


\subsubsection{Revenons à nos moutons}


Bon. On suppose donc que $\sqrt{2}$ s'écrit sous la forme $\ofr{p}{q}$, avec $p$ et $q$ les plus simples possibles. Pouvez-vous en déduire des choses sur la parité de $p^2$ puis sur celle de $p$~?

Comment peut alors s'écrire $p$ ? $p^2$ ? $q^2$ ? Qu'en déduisez-vous sur la parité de $q$ ? 

Méditez sur ce résultat. 


\subsubsection{Considérations sur le  raisonnement que nous venons d'utiliser}


Otto \textsc{Schzprwt}, chef des services secrets syldaves, interroge un homme que des agents des forces spéciales ont surpris en train de rôder autour d'une usine ultra-secrète d'aspirateurs.  Pour prouver son innocence, il lui demande de réciter  l'hymne à la gloire du Président syldave, mais le prévenu en est incapable. Otto \textsc{Schzprwt} en déduit donc qu'il n'est pas un patriote syldave, mais  un vil espion à la solde de la Bordurie et le condamne à avaler en moins de 10 minutes une quenelle de grande taille de 18 kg.

Arrivé à ce moment du récit, vous vous demandez si votre pauvre prof de maths à abusé de la Slivoviz, célèbre eau de vie syldave. 

Et bien non~! Car le bon Otto vient d'utiliser le même raisonnement qui nous a conduit à conclure que $\sqrt{2}$ n'était pas rationnel. 

Reprenons les faits : notre hypothèse de départ était que $\sqrt{2}$ était rationnel. Après une série de déductions logiques, nous sommes arrivés à une conclusion \textit{absurde}, à savoir que $p$ et $q$ devaient être tous deux pairs. 

Par un raisonnement juste, nous sommes arrivés à un résultat faux : c'est donc que notre hypothèse de départ était fausse.

Nous avons effectué un \textbf{raisonnement par l'absurde}, qui, malgré son nom, est un type de raisonnement extrêmement rigoureux et que nous utiliserons souvent. 

Son utilisation dépasse le cadre mathématique : il est utilisé par les chefs de services secrets mais aussi couramment par les garagistes, les plombiers, les médecins, les détectives privés, etc.

Nous venons de nous initier à la Logique, qui est une discipline qui occupe les esprits depuis des siècles mais qui a connu un véritable essor surtout à partir du début du XX\eme sous l'imulsion du britannique B. \textsc{Russel}. 


%\break


\subsection{Développement décimal illimité}

\subsubsection{Curiosité}

Observez ce qu'affiche une calculatrice quand vous effectuez les calculs suivants :

\[ \fr{324-32}{9}\qquad   \fr{3245-32}{99}\qquad   \fr{324510-32}{9999} \]

Sans preuve, essayez d'écrire 57,333333333333333333333\dots sous forme de fraction.

\subsubsection{Une histoire de \dots}

Par convention, les \dots veulent dire qu'il y a une infinité de 3 à droite de la virgule. C'est un peu vague, nous en reparlerons plus bas. 

À  votre avis, que vaut 1,333\dots $-1$,333 ? 1,333$-$ 1,333 ? $1,333\dots -1,33$ ?

Tout ça reste un peu empirique.

\subsubsection{L'algèbre au secours de la numération}

Nous aimerions prouver ce que nous avons observé tout à l'heure. Essayons donc d'écrire 32,444\dots sous forme de fraction, puisque la machine nous dit que \textit{ça a l'air} possible. 

Comme c'est embêtant d'écrire 32,444\dots, nous allons lui donner un petit surnom, par exemple \textit{Joe}.

Donc $Joe=32,444\dots$. 

\textbf{LA ruse} : que vaut $10\times Joe -Joe$ ? Déduisez-en  que \textit{Joe} est un nombre rationnel puis retrouvez les résultats précédents.

\subsubsection{On n'est pas des Mickey}

Contrairement à cette charmante souris, nous avons dix doigts et pas huit. Nous comptons donc en \textbf{base dix} : qu'est-ce que ça veut dire~?

Pour vous aider à avoir des idées, pensez à ce qui se passe après 9, 99, 999, etc. et surtout, pensez \textbf{puissances de 10}.

\subsubsection{Trinité}
 
Après des vacances près de Carnac, Plexigladz, le Grand Chef de Gare du peuple syldave\footnote{C'est à dire le président de Syldavie}
a eu une illumination : tout doit marcher par trois. Il a donc ordonné d'effacer de Syldavie tous les chiffres sauf 0, 1 et 2.

Les Syldaves vont donc devoir apprendre à compter en base 3. 

En vous inspirant de ce que nous avons dit au sujet de la base dix, essayez de nommer cet objet : {\LARGE\textcolor{green}{\FourClowerOpen}}


Plexigladz aime compter ses usines la nuit pour s'endormir : combien en a-t-il\footnote{en base trois, bien sûr} ?

\begin{center}
{\textcolor{bleu_m}{ \LARGE\Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\  \Industry\ \Industry\  \Industry\ \Industry\  \Industry\ \Industry\ }}
\end{center}


\subsubsection{Développement décimal périodique}

Posez la division de 1 par 3, vous obtenez sans cesse le reste 1 et le déloppement décimal est donc 0,33333333333\dots

En fait, il existe une écriture qui évite les \dots : $0,\underline{3}$ signifie de la même manière que le 3 se répète infiniment.

Voyez ce que donne 13/7.

\begin{center}
\opdiv{13}{7}
\end{center}

Donc on écrit \opdiv[period,style=text]{13}{7}

\subsubsection{Si, et seulement si}

\textbf{Si} je nage en maillot de bain dans un lac syldave \textbf{alors} je serai mouillé, mais est-ce que \textbf{si} je suis mouillé \textbf{alors} je nage en maillot de bain dans un lac syldave~?


La première proposition\footnote{\textbf{Si} je nage en maillot de bain dans un lac syldave \textbf{alors} je serai mouillé} est une \textbf{implication} vraie : nager en maillot de bain dans un lac syldave implique d'être mouillé.

On utilise le symbole  $\Longrightarrow$ pour matérialiser cette implication :

\[ \text{Nager en maillot dans un lac syldave}\Rightarrow\text{être mouillé}\]

La deuxième proposition\footnote{\textbf{Si} je suis mouillé \textbf{alors} je nage en maillot de bain dans un lac syldave} est l'\textbf{implication réciproque}. Dans le cas qui nous occupe, cette implication réciproque  est fausse

\[\text{être mouillé}\nRightarrow\text{nager en maillot dans un lac syldave}\]


On dit que ces deux propositions ne sont pas \textbf{équivalentes} :

\[ \text{Nager en maillot dans un lac syldave}\nLeftrightarrow\text{être mouillé}\]



\sm

Revenons à nos nombres.

En pensant à la division posée, expliquez pourquoi un nombre rationnel admet forcément un développement décimal périodique.

Inversement, expliquez pourquoi un nombre admettant un développement rationnel périodique est forcément rationnel.

Comment exprimer ces résultats en termes d'équivalence~?

\subsubsection{$\Mathbold{\sqrt{2}}$ admet-il un développement décimal périodique~?}

Si vous répondez correctement à cette question, alors vous commencerez à vous débrouiller en logique :-)


\subsubsection{Les limites du développement décimal}

\'Ecrivez sous forme de fraction le nombre 1,\underline{9}.

Des remarques~?




\section{SAVEZ-VOUS COMPTER SUR VOS
DOIGTS~?}
\subsection{Qu'est-ce qu'un entier~?}

\tsx C'est une blague ce chapitre~?

\pro Ne vous emballez pas mon petit Téhessin. Je suis persuadé que
vous savez compter sur vos doigts, tout comme je suis persuadé que
vous obtiendrez bientôt votre permis de conduire une 309 custom,
mais savez-vous comment est fabriqué votre carburateur~? vos
freins ABS~? Même si vous l'ignorez, vous pourrez décoller à
pleine vitesse sur les ralentisseurs de la rue du château. C'est
un peu la même chose avec ces entiers si familiers et qui pourtant
cachent tant de complexité. On les utilise depuis des millénaires,
mais il a fallu attendre les travaux de l'italien Peano à la fin
du XIX\eme siècle pour en avoir une présentation $axiomatique$,
c'est à dire qu'à partir d'un petit point de départ posé a priori
-~l'axiome~-, on déduit logiquement tout un ensemble de résultats
-~théorèmes~-.



\begin{Idee}

{\bf Comment on a fabriqué l'ensemble $\bbn$} 


Tout a commencé par quelques axiomes...
\been
\item Il existe une application $s\ :\ \bbn\to\bbn$, appelée
$succession$. L'image d'un entier $n$ par $s$ est appelé
$successeur$ de $n$.
\item Il existe un élément de $\bbn$ noté 0 qui n'a pas
d'antécédent par $s$ (il n'est le successeur de personne). On note
1 le successeur de 0, 2 celui de 1, etc.
\item Chaque entier $n$ admet un unique successeur $s(n)$ et chaque
entier non nul est le successeur d'un unique entier.
\item \textit{Axiome de récurrence}\\ Si une partie $A$ de $\bbn$
contient 0 et le successeur de chacun de ses éléments, alors $A$ est en fait égale à $\bbn$ tout entier. \een  \sm On peut alors
retrouver tout ce qu'on sait sur $\bbn$ et même plus.  \sm On peut par exemple définir une addition $+$ : pour tout couple d'entiers
$(m,n)$, $m+0=m$ et $m+s(n)=s(m+n)$. L'axiome de récurrence nous permet de vérifier que cette addition est définie pour tout couple
d'entiers et donc que cette définition en est bien une. On obtient ainsi que $s(n)=n+1$ 
\end{Idee}


Ce petit aparté présenté pour votre culture générale a  néanmoins
l'avantage d'introduire un raisonnement clé de notre année de
formation~:



\subsection{Raisonnement par récurrence}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%





\SUBSUBSECTION{Génétique syldave}

Les scientifiques syldaves viennent de mettre en évidence que la terrible maladie de Mathieu est en fait héréditaire : cette maladie frappe depuis des siècles les petits syldaves et les fait naître avec un unique mais énorme cheveu sur la tête.

C'est Vaclav \textsc{Grtschtsz} qui, le premier, contracta cette maladie en 1643 après être rentré en contact avec des vénusiens : ce fait peu connu marque la cause de l'apparition de la maladie en Syldavie. Depuis, tous ses descendants ont souffert de ce terrible mal et aucun médicament terrestre ne semble en mesure de stopper cette calamité.

Résumons les faits :

\begin{enumerate}
\item  la maladie de Mathieu fait naître les nouveaux nés avec un énorme et unique cheveu sur la tête. Notons $n$
la $n$\eme génération aprés Vaclav.

 Notons $\PR(n)$ la propriété~:~<<~la $n$\eme génération sera infectée par la maldie~>>
\item initialisation : un premier syldavien est infecté en 1643, donc $\PR(0)$ est vraie;
\item l'hérédité de la maladie a été prouvée : si un des parents de la $k$\eme génération est atteint, alors ses enfants de la $k+1$\eme génération seront également infectés, ce qui se traduit par \[ \PR(k)\ \text{vraie}\imp\PR(k+1)\ \text{vraie}\]
\item nous en déduisons que, quelque soit la génération $n$  des descendants de Vaclav, ceux-ci seront infectés, c'est à dire que $\PR(n)$ est vraie quelque soit l'entier naturel $n$. 
\end{enumerate}


\SUBSUBSECTION{Jouons aux cubes}

Voici un test de fin d'étude maternelle en Syldavie : prenez un cube, placez en-dessous deux autres cubes, et encore en-dessous trois cubes, etc. 

\des{limfonc.70}{4}



Combien y a-t-il de cubes bleus  au total sur le dessin ci-dessus ? On peut encore les compter à la main, mais que faire si je vous demande le nombre de cubes lorsqu'on a placé 100 rangées ? $n$ rangées ?

Le dessin nous donne une idée : si nous complétons la figure pour former un rectangle, il y a deux fois plus de cubes, mais maintenant nous pouvons les compter. Il y en a en effet $\fr{4\times (4+1)}{2}$, et donc \[1+2+3+4=\fr{4\times(4+1)}{2}\]

\smallskip

Reprenons la méthode adoptée pour étudier la génétique syldave :

\been

\item Nous allons  essayer de prouver que la propriété suivante est vraie pour tout entier naturel non nul $n$

\[\PR(n)~:~\text{<<}~ 1+2+3+\cdots+n=\fr{n(n+1)}{2}~\text{>>}\]

\item Il est facile de vérifier que  $1=\fr{1(1+1)}{2}$,  donc la deuxième étape de notre raisonnement est vérifiée
\[\PR(1)\ \text{ est vraie}\]

\item Supposons qu'une  <<~génération~>>, appelons-la par exemple la $k$ \eme, soit <<~infectée~>>. Plus sobrement on dira : soit $k$ un entier supérieur à 1. Supposons que $\PR(k)$ soit vraie et essayons alors de montrer que cela implique que la génération suivante , la $k+1$ \eme, sera elle aussi infectée, c'est à dire
\[\PR(k)\ \text{ vraie}\Longrightarrow \PR(k+1)\ \text{ vraie}\]

Il s'agit donc de calculer $1+2+3+\cdots+k+(k+1)$ sachant que $1+2+3+\cdots+k=\fr{k(k+1)}{2}$, or 
\begin{center}
\begin{tabular}{rccl}
$1+2+3+\cdots+k+(k+1)$ &=& $\ds\underbrace{1+2+3+\cdots+k}$&$+(k+1)$ \\
                                   &=&\vtabb $\fr{k(k+1)}{2}     $                     & $+(k+1)$\\
                                   &= &\vtabb $(k+1)\pa{\fr{k}{2}+1}$ & \\
                                   &=&\vtabb $(k+1)\pa{\fr{k+2}{2}}$  &\\
                                   &=&\vtabb $\fr{(k+1)(k+1+1)}{2}$

\end{tabular}
\end{center}

Nous en déduisons que $\PR(k+1)$ est  vraie elle aussi.

\item Nous avons vérifié que la propriété était vraie au rang 1 et qu'elle était héréditaire. Nous allons donc en déduire que la propriété sera toujours vraie, quelque soit l'entier naturel non nul $n$ grâce au théorème admis suivant 

\een

\SUBSECTION{Le théorème}

\ENC{\Thm\ \ (admis) Raisonnement par récurrence}{Soit $\PR$ une propriété
dépendant d'un rang $n$. Pour montrer que $\PR(n)$ est vraie pour
tous les entiers naturels $n$  supérieurs à un certan $n_0$ \been
\item On expose clairement la propriété $\PR(n)$.
\item On vérifie que $\PR(n_0)$ est vraie : c'est le \textbf{pas
initial}
de la récurrence.
\item On \textbf{suppose} ensuite que $\PR(k)$ est vraie pour un
certain entier $k$ : c'est \textbf{l'hypothèse de récurrence} et  on démontre alors que la propriété $\PR(k+1)$ est vraie :
c'est le passage du rang $k$ au rang $k+1$ qui exprime que la
propriété $\PR$ est \textbf{héréditaire}.
\item Il reste à \textbf{conclure} en annonçant que, par
récurrence, la propriété est vraie pour tout entier naturel $n$
\een }




\SUBSECTION{Applications}

\exot{Jouons encore...}

Prenons un cube, rajoutons trois autres cubes
pour former un carré, puis cinq autres cubes pour former un plus
grand carré, puis sept autres cubes pour former un carré encore
plus grand...

\sm

Nous voulons maintenant calculer la somme des $n$ premiers entiers
impairs.

\been \item Proposez une formule générale inspirée du résultat de
notre petite activité de \textit{maternelle}. \item Démontrez la formule par récurrence. \een

\exot{Récurrence chinoise}

Que vous inspire le petit dessin suivant (il est interdit de répondre : <<~rien !~>>)


\begin{center}
\includegraphics[height=10cm]{cubes.eps}
\end{center}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% \pro L'axiome de récurrence peut en fait s'écrire maintenant~:

% \sm

% \textit{Soit A une partie de $\bbn$ contenant 0. On suppose que
% pour tout entier n appartenant à A, on a aussi n+1 dans A. Alors
% A=$\bbn$}


% \sm

% \tsx J'voudrais pas dire, mais j'ai beau avoir choisi la
% spécialité math, je n'ai pas de tendance suicidaire et là vous me
% déprimez.

% \pro Changeons de tactique : attribuons à la génération de la
% brave Ève le numéro 0, à la génération de ses enfants le numéro 1,
% à la génération de ses petits-enfants le numéro 2 etc. Supposons
% qu'Ève soit hémophile. Il a été prouvé que cette maladie se
% transmet de génération en génération, c'est à dire que si une
% génération $n$ est infectée, la génération suivante $n+1$ le sera
% aussi. Appelons $H$ l'ensemble des générations atteinte
% d'hémophilie. Nous avons prouvé que $H$ contient 0 et que pour
% tout entier $n$ appartenant à $H$, on a aussi $n+1$ dans $H$ donc
% l'axiome de récurrence permet de conclure que $H=\bbn$ et donc que
% tout le monde sera affecté pour l'infinité à venir.

% \tsx Votre illustration est plutôt morbide et de mauvais goût,
% mais plus parlante que ce qui précède.

% \pro Vous pourrez donc appliquer le même raisonnement dans de
% nombreux cas. Voici la marche à suivre :

% \ENC{Raisonnement par récurrence}{Soit $\PR$ une propriété
% dépendant d'un rang $n$. Pour montrer que $\PR(n)$ est vraie pour
% tous les entiers naturels $n$ \been
% \item On expose clairement la propriété $\PR(n)$.
% \item On vérifie que $\PR(0)$ est vrai : c'est le \textbf{pas
% initial}
% de la récurrence.
% \item On \textbf{suppose} ensuite que $\PR(k)$ est vraie pour un
% certain entier $k$ : c'est \textbf{l'hypothèse de récurrence}.
% \item On démontre alors que la propriété $\PR(k+1)$ est vraie :
% c'est le passage du rang $k$ au rang $k+1$ qui exprime que la
% propriété $\PR$ est \textbf{héréditaire}.
% \item Il reste à \textbf{conclure} en annonçant que, par
% récurrence, la propriété est vraie pour tout entier naturel $n$
% \een }

% \sm

% \tsx Aurais-je droit à un petit exemple~?

% \pro Vous ai-je déjà refusé un tel plaisir~? Vous avez sûrement vu
% l'an passé le résultat suivant valable pour tout entier naturel
% $n$
% $$0+1+2+3+4+\cdots+n=\sum_{k=0}^nk=\fr{n(n+1)}{2}$$

% \tsx Oui, c'était au moment de l'étude des suites arithmétiques.

% \pro Et bien cette propriété peut être démontrée par récurrence.

% \tsx Suivons le guide. \been
% \item Soit $\PR(n)$ la propriété
% <<~$0+1+2+3+\cdots+n=\fr{n(n+1)}{2}$~>>
% \item $0=\fr{0(0+1)}{2}$, donc $\PR(0)$ est vraie.
% \item Soit $k$ un entier : supposons que $\PR(k)$ soit vraie.


% Notre hypothèse de récurrence est donc
% <<~$0+1+2+\cdots+k~=~\fr{k(k+1)}{2}$~>> \een

% À partir de là, je ne vois pas trop comment faire.

% \pro Vous voulez montrer que $\PR(k+1)$ est vraie, c'est à dire
% que $0+1+2+\cdots+k+k+1=\fr{(k+1)(k+2)}{2}$. Partir du membre de
% gauche et utiliser l'hypothèse de récurrence est souvent une bonne
% méthode.

% \tsx Essayons \begin{itemize}
% \item[4)] \begin{align*}
% (0+1+2+\cdots+k)+k+1&=\fr{k(k+1)}{2}+k+1 \text{ d'après
% l'hypothèse
% de récurrence}\\
% &=(k+1)\left(\fr{k}{2}+1\right)\\
% &=(k+1)\left(\fr{k+2}{2}\right)
% \end{align*}

% Donc $\PR(k)$ vraie $\Rightarrow$ $\PR(k+1)$ vraie : la propriété
% est héréditaire.

% \item[5)] Par récurrence, la propriété est donc vraie pour tout
% entier naturel.
% \end{itemize}

% \pro Eh ben voilà, c'est pas si compliqué. Il existe des variantes
% de ce raisonnement que nous verrons dans un autre chapitre. Pour
% vous détendre pendant vos loisirs, je vous propose de prouver par
% récurrence la propriété démontrée par le dessin suivant :
% 
% \begin{center}
% \includegraphics[height=10cm]{/home/moi/ancienordi/ts/cubes.eps}
% \end{center}

Et maintenant, avec tout ça on peut définir une multiplication
$\times$, une relation d'ordre $\ie$\footnote{Pour les curieux,
elle est définie par $m\ie n\ssi \text{il existe } p\in\bbn \text{
tel que } m+p=n$}, une exponentiation\footnote{Les puissances
quoi}, une soustraction. Le bonheur quoi. Tout ça pour en arriver
à la ...



 \subsection{Propriété fondamentale de $\bbn$}

\ENC{\Prop}{Toute partie non vide de $\bbn$ possède un plus petit
élément}

\tsx Je ne vois pas trop où est le scoop : c'est sûr que si on
prend un groupe de nombre, il y en a forcément un de plus petit.

\pro Eh, eh...Considérez l'intervalle de $\bbr$ $]32;92]$ : quel
est son plus petit élément~?

\tsx Ben 32.

\pro Sauf que le crochet gauche est ouvert : 32 n'appartient pas à
l'intervalle donc ne peut pas être son plus petit élément.

\tsx Bon ben 32,1 alors.

\pro Et pourquoi pas 32,0001 ou même 32,0000000000000000001 : vous
pouvez comprendre qu'on ne pourra pas trouver de plus petit
élément, donc cette propriété n'est pas si bête et va souvent nous
servir.



\section{DIVISIBILIT\'E, MULTIPLES, DIVISEURS}

 \pro Les mathématiques aiment souvent la symétrie : à chaque
entier naturel, on a donc associé un \textit{symétrique} tel que
la somme des deux fasse zéro\footnote{Derrière tout ça se cache la
notion de groupe que nous reverrons au moment d'étudier les
similitudes} et c'est comme ça qu'on a crée $\bbz$. Ensuite, on
s'est amusé à multiplier ces entiers entre eux et on a regardé ce
qui se passe : c'est l'objet de notre cours d'arithmétique.

\tsx Vous voulez me faire croire qu'il suffit de connaître ses
tables de multiplication pour assurer en spé math...

\pro À peu de choses près. Par exemple, vous êtes au courant que
45 est un \textit{multiple} de 3, donc que 45 est $divisible$ par
3 ou encore que 3 $divise$ 45. Les petites définitions qui suivent
ne vont donc pas vous faire peur :


\ENC{\Def}{Soit $m$ et $n$ deux entiers.\\ Dire que $n$
\textbf{divise} $m$ signifie qu'il existe un entier $k$ tel que
$m=kn$. On note $n|m$.\\ On dit alors que $n$ est un
\textbf{diviseur} de $m$, que $m$ est un \textbf{multiple} de $n$
ou encore que $m$ est \textbf{divisible} par $n$.}

\sm

Par exemple, on caractérisera un multiple de 3 en disant qu'il
s'écrit sous la forme 3$k$, avec $k$ un entier.

Comment caractériseriez-vous un entier pair~?

\tsx Un entier pair est un multiple de 2, donc il est de la forme
$2k$, avec $k$ un entier.

\pro De la même manière, un entier impair est un entier qui n'est
pas pair. C'est donc un entier coincé entre deux nombres pairs :
c'est le successeur ou le prédécesseur d'un nombre pair.

\tsx Donc on peut l'écrire sous la forme $2k+1$ ou $2k-1$ :
j'assure, non~?

\pro Alors occupez-vous de démontrer les propriétés suivantes :

\ENC{\Props}{Soit $a$, $b$ et $c$ des entiers non nuls. \been
\item Si $a$ divise $b$ et $b$ divise $c$, alors $a$ divise $c$.
\item Si $a$ divise $b$, alors $|a|\ie|b|$.
\item Si $c$ divise $a$ et $b$, alors $c$ divise toute combinaison
linéaire à coefficients entiers $u$ et $v$ du type $au+bv$.\een}

Un petit commentaire sur la troisième propriété :  comme 3 divise 6 et 15, alors 3 divise
$2\times6-7\times15$.

Ensuite, une fois que vous aurez démontré le
lemme suivant :

\ENC{\Prop}{Toute partie majorée de $\bbn$ est finie et admet un
plus grand élément}

\sm

vous aurez tout le loisir de démontrer

\ENC{\Prop}{Tout entier non nul admet un nombre fini de diviseurs}


\section{DIVISION EUCLIDIENNE}

\subsection{Le théorème}

\tsx Après la maternelle, on passe au CM1~?

\pro Donc nous progressons...Revenez quelques années en arrière.
La maîtresse vous demande de diviser 32 par 5 : que faîtes-vous~?

\tsx Je me dis : <<~en 32, combien de fois 5~?~>>

\pro Vous cherchez donc à encadrer 32 par deux multiples
consécutifs de 5

%\dessin{3}

\tsx Et je conclue par : <<~il y va six fois et il reste 2~>>.

\pro Donc on a $32=6\times5+2$, mais on aurait pu écrire aussi que
$32=4\times5+12$.

\tsx Ah non~! Je vous ai dit qu'il y allait six fois, pas quatre.

\pro Eh oui : le $reste$ proposé doit être inférieur au $quotient$
5 pour être sûr d'être entre deux multiples consécutifs de 5.


On peut <<~résumer~>> cette idée par le théorème suivant :

\ENC{\Thm}{Soit $a$ un entier relatif et $b$ un entier naturel non
nul (pourquoi~?).

Il existe un unique couple d'entiers $(q,r)$ tels que
$$a=bq+r\quad\text{avec}\quad0\ie r<b$$

Déterminer $q$ et $r$, c'est effectuer la division euclidienne de
$a$ par $b$.

On appelle $a$ le dividende, $b$ le diviseur, $q$ le quotient et
$r$ le reste.}

\sm

Qui dit théorème dit démonstration. Le principe de celle qui va
suivre est le schéma suivant

\begin{center}
\includegraphics{analyse2.8}
\end{center}


qui traduit qu'un entier $a$ est soit un multiple de $b$, soit est
encadré par deux multiples consécutifs de $b$.

L'énoncé contient deux termes importants : <<~il $existe$ un
$unique$ couple~>>. Il va donc falloir prouver deux choses :

- qu'un tel couple existe

- qu'il est unique.

\sm

Traitons d'abord le cas particulier où $a\in\bbn$.
\begin{itemize}

\item[\textbf{Existence}]

Le monde des multiples de $b$ se sépare en deux catégories : ceux
qui sont inférieurs (ou égaux) à $a$ et les autres.

 En d'autres termes, appelons $\MR_i$ l'ensemble des multiples de
 $b$ inférieurs ou égaux à $a$. Cet ensemble $\MR_i$ est non vide
 car il contient au moins 0. De plus $\MR_i$ est majoré par $a$
 puisqu'on l'a défini comme ça.

 L'ensemble $\MR_i$ est donc une partie de $\bbn$ non vide et
 majorée : $\MR_i$ admet donc un plus grand élément d'après une
 propriété que vous avez démontrée.

 Appelons $\mu$ ce plus grand  élément. C'est un multiple de $b$, donc il existe un entier $q$ tel que $\mu=qb$.

 Le multiple suivant est $\mu+b=qb+b=(q+1)b$ qui n'appartient pas à $\MR_i$
 car il est strictement supérieur au maximum $\mu$.

 On en déduit que $$bq\ie a<bq+b$$

 C'est ce que nous <<~montrait~>> le dessin. Il nous indique aussi
 que le reste correspond en fait à la différence $a-bq$.

 Posons donc $r=a-bq$ : on a alors $a=bq+r$ et donc $bq\ie
 bq+r<bq+b$, c'est à dire $0\ie r<b$

 \sm

 Nous avons donc démontré l'existence de deux entiers $q$ et $r$
 tels que $a=bq+r$ avec $0\ie r<b$, \textit{inspirés} que nous
 étions par un joli dessin.

 Il reste à démontrer l'unicité d'un tel couple d'entiers.

\item[\textbf{unicité}]

Une méthode habituelle pour démontrer une unicité est $supposer$
l'existence d'un second couple.

Supposons donc qu'il existe deux couples d'entiers $(b,q)$ et
$(b',q')$ vérifiant

\begin{align*}
a&=bq+r\quad\text{avec}\quad 0\ie r<b\\
a&=bq'+r'\quad\text{avec}\quad 0\ie r'<b
\end{align*}

Effectuons la différence membre à membre de ces égalités. On
obtient

$$0=b(q-q')+r-r'\quad\text{avec}\quad -b<r-r'<b$$

Vous en déduisez comme moi que $r-r'$ est un multiple de $b$, et
que ce multiple est strictement compris entre $-b$ et $b$.

%\dessin{3}

Le seul multiple qui convient est 0, donc $r-r'=0$ et par suite
$q-q'=0$, c'est à dire que $r=r'$ et $q=q'$. Dès lors il n'existe
qu'un seul couple solution.

\end{itemize}

\tsx Ça c'est de la démonstration~! Mais pourquoi dit-on qu'on ne
peut pas diviser par zéro~? Je ne crois pas avoir rencontré de
déduction utilisant le fait que $b$ est non nul.

\pro C'est que cela s'est passé vers la fin : vous deviez être
épuisé mentalement.

Je vous propose donc un petit jeu : vous répondez à votre propre
question et vous traitez le cas où $a$ est strictement négatif
connaissant bien sûr le résultat pour $a\in\bbn$.

\MATA{Voilà un gars qui sait s'amuser.}


\subsection{Notre premier algorithme XCAS}

Nous voudrions fabriquer <<~à la main~>> un algorithme donnant le quotient et le reste de la division euclidienne de $a$ par $b$. La preuve du théorème, comme souvent, peut nous donner des idées : en effet, il s'agit de coincer $a$ entre deux multiples consécutifs de $b$. Par commodité, nous considèrerons que $a$ et $b$ sont des entiers naturels.

On sent qu'un test <<~tant que~>> peut s'avérer utile : tant que le multiple de $b$ est inférieur à $a$, on prend le suivant. Cela donne pour le quotient :

\begin{lstlisting}
quotient(a,b):={
local k;
while(k*b<=a){k:=k+1;}
k-1;
}
}
\end{lstlisting}

et pour le reste 

\begin{lstlisting}
reste(a,b):={
local k;
while(k*b<=a){k:=k+1;}
a-b*(k-1);
}
}
\end{lstlisting}


Sachez tout de même que ces fonctions sontt pré-programmées de manière plus efficace sur XCAS 

\begin{lstlisting}
iquo(2354,67);
irem(2354,67);
\end{lstlisting}







%\vfill

%.

%\break



\section{UNE PREMIÈRE S\'ERIE D'EXERCICES}

\subsection{Divisibilité} 
\exot{} Soit $a$ et $b$ deux entiers.

\been
\item Montrez que pour tout entier naturel non nul, $a-b$ divise
$a^n-b^n$.
\env{Pour l'hérédité, écrivez l'hypothèse de récurrence sous la forme $a^k=b^k+p(a-b)$}
\item Montrez que pour tout entier naturel $impair$, $a+b$ divise
$a^n+b^n$. \een

\env{Une récurrence pourrait s'avérer utile en attendant le binôme
de Newton. Inspirez-vous de la récurrence précédente.}



\exot{VRAI OU FAUX~?}{

\been
\item Si $d$ divise $a+b$, alors $d$ divise $a$ et $b$.
\item Si $d$ divise $2a$, alors $d$ divise $a$.
\item Si $d$ divise $a$ ou  $b$, alors $d$ divise $ab$.
\item Si $d$ divise $ab$, alors $d$ divise $a$ ou $b$.
\item Le produit  de deux entiers naturels pairs est
pair.
\item La somme de deux entiers naturels pairs est
paire.
\item Le produit  de deux entiers naturels impairs est
impair.
\item La somme de deux entiers naturels impairs est
impaire.
\item Le produit d'un entier pair et d'un entier impair est pair.
\item Le produit et la différence de deux entiers relatifs ont
toujours la même parité.
\item Le produit de deux entiers consécutifs est pair.
\item La somme de deux entiers impairs consécutifs est divisible
par 4.
\item La somme de $k$ entiers consécutifs est divisible par $k$,
avec $k\in[\![2,+\infty[\![$
\item Le produit de $k$ entiers consécutifs est divisible par $k$,
avec $k\in\bbn^*$
\item $1251^{2p+1}+26^{2p+1}$ est divisible par 1277 pour tout $p\in\bbn$.
\item $4^{13127}+1$ est un entier naturel qui se termine par 5.
\een}


\exot{} Prouvez que les entiers suivants sont des multiples de 37 :

\been
\item les nombres de trois chiffres identiques (111, 222, 333,...)
\item les nombres de six chiffres identiques ($111\,111$,
$222\,222$, $333\,333$,...)
\item les nombres de six chiffres écrits en alternant deux mêmes
chiffres ($121\,212$,...) \een


\exot{} \been
\item Soit $x$ un réel différent de 1 et $n$ un entier
naturel. Calulez $S_n=\ds\sum_{k=0}^{n-1}x^k$ et retrouvez que
$a-b$ divise $a^n-b^n$.
\item Soit $n\in\bbn^*$ et $d$ un diviseur positif de $n$.

Montrez que, pour tout entier $a\se1$, $a^n-1$ est divisible par
$a^d-1$.

\env{Posez par exemple $n=kd$ et $x=a^d$}

\item Montrez que $2^{2004}-1$ est divisible par 3, 7, 63 et 65.

\een

\exot{Une équation dans $\bbz^2$}

Résolvez dans $\bbz\times \bbz$ \[x^2+2xy=15\]

\env{Pensez factorisation et diviseurs de 15}


\exot{Relation d'ordre}\label{ordre}

\begin{description}
\item [Relation reflexive ] 

On dit qu'une relation $\RR$ est reflexive sur un ensemble E si, et seulement si, pour tout élément $a$ de E on a $a\RR a$.

Montrez que la relation <<~divise~>> est reflexive sur $\bbn$. Donnez des exemples de relations reflexives et non-reflexives sur des ensembles divers.

\item [Relation transitive ] 

On dit qu'une relation $\RR$ est transitive sur un ensemble E si, et seulement si, pour tout élément $a$, $b$, $c$ de E on a $\begin{cases} a\RR b     \\ b\RR c \end{cases} \Longrightarrow a\RR c$.

Montrez que la relation <<~divise~>> est transitive sur $\bbn$. Donnez des exemples de relations transitives et non-transitives sur des ensembles divers.



\item [Relation antisymétrique ] 

On dit qu'une relation $\RR$ est antisymétrique sur un ensemble E si, et seulement si, pour tout élément $a$ et $b$  de E on a $\begin{cases} a\RR b     \\ b\RR a \end{cases} \Longrightarrow a= b$.

Montrez que la relation <<~divise~>> est antisymétrique  sur $\bbn$. L'est-elle sur $\bbz$~? Donnez d'autres exemples de relations antisymétriques sur des ensembles divers.

\item[Relation d'ordre]

On dit qu'une relation à la fois reflexive, transitive et antisymétrique sur un ensemble E est une relation d'ordre. Des commentaires ?

\end{description}




\section{CONGRUENCES DANS $\bbz$}


%\begin{center}
%\includegraphics[height=6cm]{/home/moi/ancienordi/ts/shadokMeu+Bu.eps}
%\end{center}






\subsection{En quoi la division euclidienne nous aide-t-elle à
classifier les entiers~?}

\pro La section précédente nous a fait découvrir une belle
démonstration, mais surtout elle a mis en évidence que, par
exemple, le monde des entiers se sépare en trois catégories~: les
nombres qui s'écrivent sous la forme $3k$, $3k+1$ ou encore
$3k+2$, avec $k$ un entier. Ça vous interpelle quelque part~?

\tsx Là je sens que vous allez être épaté~: quand on divise un
nombre par 3, le reste doit vérifier $0\ie r<3$, donc il ne peut
valoir que 0, 1 ou 2. Donc quand on effectue la division
euclidienne de n'importe quel entier $a$, on obtient au choix
$a~=3~q~+~0$ ou $a~=3~q~+~1$ ou encore $a~=3~q~+~2$.

\pro Imaginez le mathématicien, assez cossard de nature, devant un
tel résultat~: il jubile. Au lieu de considérer tous les entiers,
ce qui est fastidieux, il va pouvoir se contenter de trois
représentants si par exemple leur <<~position~>> par rapport à 3
l'intéresse. Ce principe de simplification par l'utilisation de
<<~délégués~>> est un outil mathématique extrêmement performant
qui est le fondement de ce qu'on nomme l'algèbre générale.

Le souci permanent de simplification ne s'arrête pas là :
puisqu'on va travailler avec des nombres <<~délégués~>>, on ne va
pas utiliser les règles de calculs des vulgaires nombres du
bas-peuple~: on va s'inventer un mécanisme de calcul plus
performant et élégant. C'est tout l'objet de cette section.

\subsection{Définition et propriétés des congruences}

\pro Nous venons de dire que nous allons regrouper les nombres
selon leur reste dans la division euclidienne par un entier
naturel $n$ quelconque cette fois-ci. Il faut donc définir un code
pour se reconnaître entre gens du même monde~:

\ENC{\Def}{Soient $a$ et $b$ deux entiers et $n$ un entier naturel
supérieur à 2.

Dire que $a$ est congru à $b$ modulo $n$ signifie que $a$ et $b$
ont le même reste dans la division euclidienne par $n$.

On note $$a\equiv b[n]$$}



\tsx Mais dites-moi, nous avions déjà rencontré cette notation en
trigonométrie. Par exemple $\theta\equiv\fr{\pi}{3}[2\pi]$.

\pro C'est que le problème est similaire~: tous les nombres
congrus à $\pi/3$ modulo $2\pi$ ont un air de famille : ils ont le
même représentant sur le cercle trigonométrique. Il n'est donc pas
utile de les considérer tous~:~un <<~délégué~>> suffit.



L'atout le plus important des congruences en Terminale, c'est la
puissance de calcul qu'elle permettent. Avant d'y venir,
faites-vous la main avec cette propriété importante :

\ENC{\Prop}{Soit $a$ et $b$ deux entiers et $n$ un entier naturel.

$a$ est congru à $b$ modulo $n$ si et seulement si $a-b$ est un
multiple de $n$}

\tsx Puisque les congruences sont liés au reste, il faut sûrement
utiliser les divisions euclidiennes par $n$.

Je pose donc $a=nq+r$ et $b=nq'+r'$ sans oublier que $r$ et $r'$
sont dans $[\![0,n[\![$.

Comme $a\equiv b[n]$, on a $r=r'$ par définition des congruences.

Alors $a-b=nq+r-nq'-r'=nq-nq'=n(q-q')$ et j'obtiens bien que $a-b$
est un multiple de $n$.

\pro Pas mal...mais vous n'avez fait que la moitié du boulot : le
<<~si et seulement si~>> signifie que les assertions sont
équivalentes, c'est à dire que

- \textbf{si} $a\equiv b[n]$, \textbf{alors} $a-b$ est un multiple
de $n$

\textbf{ET réciproquement}

- \textbf{si} $a-b$ est un multiple de $n$, \textbf{alors}
$a\equiv b[n]$

\tsx Autant pour moi. Cette fois-ci, nous supposons que $a-b$ est
un multiple de $n$, donc il existe un entier $k$ tel que $a-b=kn$.

Or $a-b=n(q-q')+r-r'$, donc $r-r'=n(k-q+q')$. Bon, $r-r'$ est donc
un multiple de $n$, mais de là à dire que $r=r'$...

\pro Ah lala lala...si seulement vous étudiez vos démonstrations
de cours, cela vous donnerait des idées. Revoyez donc ce que nous
avons fait pour prouver l'unicité de la division euclidienne.

\tsx Ah c'est sûr, tout s'éclaire : $r-r'$ est un multiple de $n$
qui vérifie $-n<r-r'<n$. Il n'en existe qu'un seul :zéro, donc
$r=r'$ et par définition, on obtient bien que $a\equiv b[n]$.

\pro Cette propriété nous permet en fait d'exploiter autrement les
congruences. En effet, si par exemple $x\equiv 5[32]$, cela
signifie qu'il existe un entier $k$ tel que  $x-5=32k$, soit
encore que $x=5+32k$.

\ENC{\Prop}{$$a\equiv b[n]\ssi \text{ il existe un entier } k
\text{ tel que } a=b+kn$$}

\tsx Ça ressemble à la division euclidienne de $a$ par $n$.

\pro Mais ça peut ne pas l'être : n'oubliez pas que le reste doit
obligatoirement être positif et strictement inférieur au diviseur.

Par exemple on a bien $33\equiv 97[32]$, mais 97 n'est certes pas
le reste de la division de 33 par 32.

\sm

Occupez-vous à présent de quelques propriétés extrêmement
intéressantes des congruences

\ENC{\Props}{Comme d'habitude, $n$ est un entier naturel supérieur
à 2 et tous les autres sont des entiers relatifs.

\been

\item $a\equiv a[n]$
\item Si $a\equiv b[n]$, alors $b\equiv a[n]$
\item Si $a\equiv b[n]$ et $b\equiv c[n]$, alors $a\equiv c[n]$
\item Si $a\equiv b[n]$ et $a'\equiv b'[n]$, alors $$a+a'\equiv
b+b'\ [n]\quad a-a'\equiv b-b'\ [n]\quad aa'\equiv bb'\ [n]$$
\item Si $a\equiv b[n]$, alors, pour tout $p\in\bbn$, $a^p\equiv
b^p[n]$

\een}

\sm

En fait, il faut retenir qu'on peut additionner, soustraire,
multiplier des congruences \textbf{de même module}.

\tsx Vous avez oublié la division.

\pro Et pour cause : c'est une opération à haut risque quand on
travaille avec des entiers.

Par exemple $12\equiv 0[6]$, mais $\fr{12}{3}\not\equiv
\fr{0}{3}[6]$.

L'utilisation des congruences nous ouvre les portes d'une
multitude d'exercices. Elle va également nous permettre de revenir
sur les bases de la numération que vous avez découvertes en
primaire.



\subsection{Les bases sur les bases}

\pro Vous utilisez depuis votre tendre enfance le système de
numération décimale. Si nous étions tous des Mickey, nous aurions
sûrement préféré compter en base 8. Les ordinateurs, eux,
préfèrent compter en base 2 et de plus en plus maintenant en base
16. Cela me rappelle mon jeune  temps : j'étais un
sage petit Mataïe en classe de CM1 et je jouais aux cubes : quand j'avais 3 cubes, je les remplaçais par une barre de 3, quand j'avais 3 barres je les remplaçais par une plaque, quand j'avais trois plaques je les remplaçais par un cube\dots ëtes-vous capable de commenter ces délirantes activités qui faisaient de mes journées à l'école un enchantement~?

\MATA{C'est dur de veillir...}

%\begin{center}
%\includegraphics[height=15cm]{/home/moi/ancienordi/ts/base1.eps}
%\end{center}

% \break
% 
% \pro Je me souviens encore du cours qui suivit
% 
% 
% %\begin{center}
% %\includegraphics[height=23cm]{/home/moi/ancienordi/ts/base2.eps}
% %\end{center}
% 
% 
% \break
% 
% \pro et ces charmants exercices qui stimulaient tant mon esprit en
% formation
% 
% 
% %\begin{center}
% %\includegraphics[height=23cm]{/home/moi/ancienordi/ts/base3.eps}
% %\end{center}
% 
% 
% 
% \break

%\pro 

\pro Mais j'ai grandi depuis, alors pour faire plus sérieux je
vous propose la propriété suivante

\ENC{Numération en base $b$}{Soit $b$ un entier supérieur à 2. On
peut écrire de manière unique tout entier naturel $a$ sous la
forme
$$a=a_n\times b^n+a_{n-1}\times b^{n-1}+\cdots+a_1\times b^1+a_0\quad
\text{avec} \ 0\ie a_i\ie b-1\ \text{ et }\ a_n\neq0$$ On note
$a=\overline{a_na_{n-1}\cdots a_1a_0}^{\ b}$}


\sm

Encore une fois, le problème se sépare en deux : existence puis
unicité d'une telle écriture. Vous vous en occuperez en exercice.
Vous prouverez également certains critères de divisibilité que
vous utilisez depuis le primaire.




\section{POUR DIRE LES CHOSES PLUS SIMPLEMENT\dots}





Avant de voir tous  vos neurones fondre  comme des fusibles 10 ampères dans une centrale atomique, il est temps d'adopter un plan
d'urgence. Si les congruences sont quasi inexistantes dans votre livre vieux de quatre ans, elles sont devenues les coqueluches des poseurs
de sujet comme vous le constaterez sr le recueil d'exercices de Bac. Je me suis donc replongé dans mon vieux livre de cm1...

Voici un classement des entiers naturels

\begin{center}
\begin{tabular}{ccccc}

0&1&2&3&4\\
5&6&7&8&9\\
10&11&12&13&14\\
15&16&17&18&19\\
20&...& & &

\end{tabular}
\end{center}

Vous pouvez aussi enrouler la droite des réels graduée par les entiers sur un cercle de périmètre 5 et retrouver les mêmes sensations qu'avec la congruence modulo $2\pi$ : il vous semble assez naturel de penser $\pi/3$, $7\pi/3$, $-5\pi/3$ <<~représentent~>> le même réel sur le cercle trigonométrique. Et bien 1, 6, 11, 16, ... représentent le même entier sur le <<~cercle modulo 5~>>

\des{limfonc.56}{5}


Cela nous permet de classer les entiers par équipes : l'équipe de ceux qui ont pour reste 0 dans la division euclidienne par 5, l'équipe
de ceux qui ont pour reste 1, etc.

Maintenant, si Roger, Bébert et Josette font partie de la même équipe, on pourra désigner cette équipe par <<~équipe de Roger~>> ou
<<~équipe de Bébert~>> ou bien <<~équipe de Josette~>>.

Pour nos nombres, l'équipe de ceux qui ont pour reste 3 pourra s'appeler l'équipe de 3 ou l'équipe de 8 ou l'équipe de $32\,318$. Point
de vue congruence, cela donne
$$3\equiv8[5]\quad3\equiv32\,318[5]\quad32\,318\equiv8[5]$$
On souhaite maintenant additionner ces équipes. Il ne s'agit pas de l'addition usuelle des entiers. Par exemple, si on note $\dot{3}$
l'équipe de 3, on obtient
$$\dot{3}\dot{+}\dot{2}=\dot{0}\quad\dot{4}\dot{+}\dot{4}=\dot{3}\quad\dot{4}\dot{+}\dot{4}=\dot{-2} $$
et comme la multiplication des entiers, c'est une suite d'additions, on a également
$$\dot{3}\dot{\times}\dot{2}=\dot{1}\quad\dot{7}\dot{\times}\dot{5}=\dot{0}\quad\dot{3}\dot{\times}\dot{8}=\dot{-1}$$







\section{DES EXERCICES UTILISANT LES CONGRUENCES.}






\exot{Tables d'addition et de multiplication} 

\begin{nliste}{2}

\item Complétez  le tableau  en n'utilisant que $\dot{0},\ \dot{1},\ \dot{2},\ \dot{3}$ et $\dot{4}$\dots
\begin{tabular}{|c|c|c|c|c|c|}
\hline
$\dot{+}$&$\dot{0}$&$\dot{1}$&$\dot{2}$&$\dot{3}$&$\dot{4}$\\
\hline $\dot{0}$& & & & & \\
\hline $\dot{1}$& & & & & \\
\hline $\dot{2}$& & & & & \\
\hline $\dot{3}$& & & & & \\
\hline $\dot{4}$& & & & & \\
\hline

\end{tabular}


\item \dots et pour rigoler, celui-ci aussi



\begin{tabular}{|c|c|c|c|c|c|}
\hline
$\dot{\times}$&$\dot{0}$&$\dot{1}$&$\dot{2}$&$\dot{3}$&$\dot{4}$\\
\hline $\dot{0}$& & & & & \\
\hline $\dot{1}$& & & & & \\
\hline $\dot{2}$& & & & & \\
\hline $\dot{3}$& & & & & \\
\hline $\dot{4}$& & & & & \\
\hline

\end{tabular}
\end{nliste}


\exot{} Vous pouvez même résoudre les équations suivantes dans $\bbz$

$$1+1\equiv0[x]\quad 3+x\equiv2[7]\quad 8+6\equiv 5[x]$$

\exot{} Allez, un dernier exercice tiré du livre de cm1

\sm

\textsl{Les nombres 13, 21, 32, 36, 40, 45 et 77 sont écrits en base dix. Si tu voulais les écrire en base trois, quels sont ceux qui
auraient pour chiffre des unités 0, 1, 2~? Quels sont ceux qui auraient pour chiffre des unités 0, 1, 2, 3, 4 si tu voulais les écrire en
base cinq~?}

\bigskip

 On essaie des formulations plus <<~terminale~>>

\sm

\exot{} Soit $x$ et $y$ deux entiers naturels tels que $x\equiv7[9]$ et $y\equiv4[9]$. Déterminez les restes dans la division par 9 de
$$a)\ 3x+4y\qquad b)\ x^2+y^2\qquad c)\ 2x^2-5y^2$$


\exot{Vrai ou Faux~?} \been
\item On suppose que $a\equiv 1[n]$, alors $a^n\equiv 1[n]$
\item On suppose que $a\equiv 3[n]$, alors $a^n\equiv 3[n]$
\een

\exot{} Trouvez le reste de la division par 5 du nombre $12^{1527}$. \env{$2^4\equiv1[5]$ et $1527\equiv3[4]$}

%\exot{} Résolvez dans $\bbz$ les équations $$(E_1)~:\ 2x\equiv3[5]\qquad (E_2)\ 3x^2\equiv4[8]$$

\exot{} Montrez que, pour tout naturel $n$,
$$3^{3n+2}+2^{n+4}\equiv0[5]$$

\exot{} Montrez que $$a)\ 34^{57}\equiv1[11]\qquad b)\ 328^{42}\equiv4[5]\qquad c)\ 3\,174^{249}\equiv2[11]$$

\exot{} Pour quelles valeurs de $n$ a-t-on $3^n\equiv0[2]$

 \exot{un exo de bac
pour finir sur une note optimiste}

\been
\item Montrez que pour tout naturel $n$, $24n^2+8n$ est divisible
par 16.
\item Déduisez-en que $(2n+1)^4\equiv1[16]$
\item Montrez que, si $a\in\bbn$, $a^4$ est congru à 0 ou 1 modulo
16.
\item Déduisez-en que, si le nombre $16n+15$, avec $n\in\bbn$, est
mis sous la forme d'une somme de $k$ puissances quatrièmes d'entiers, $i.e.$ $16n+15=x_1^4+x_2^4+\cdots+x_k^4$, alors nécessairement
$k\se15$\een



\sm











\exot{Relation d'équivalence}

On dit qu'une relation $\RR$ est \textbf{symétrique} sur un ensemble E si et seulement si, pour tout couple $(a,b)$ de $E\times E$
\[ a\RR b\Longrightarrow b\RR a\]

Une relation qui est à la fois reflexive, symétrique et transitive est une \textbf{relation d'équivalence} (cf exercice\ref{ordre} page\pageref{ordre}) 

La relation $\equiv$ est-elle une relation d'équivalence~?

\exot{} Dans tout l'exercice, on évitera de passer par la base
10.\been
\item Un entier s'écrit 1.011.111.101.000 en base deux. L'écrire en base
huit.
\item Un  entier s'écrit 572.634 en base huit. L'écrire en base deux.
\een


\exot{Critères de divisibilité à partir de l'écriture décimale}


Justifiez les critères de divisibilité suivants. Les chiffres dont
il est question dans les différents critères sont ceux de
l'écriture décimale de l'entier naturel $n$ que l'on teste. Si
besoin est, on notera ces chiffres $c_{p-1},\cdots,c_0$ de telle
sorte que $\ds n=\overline{c_{p-1}\cdots c_0}^{\,10}$, et on
posera $c_k=0$ pour $k\se p$.


\been
\item $n$ est divisible par 2 si et seulement si son chiffre des unités $c_0$ est égal
à 0,2,4,6 ou 8.
\item $n$ est divisible par 3 si et seulement si la somme de ses chiffres est
divisible par 3.
\item $n$ est divisible par 4 si et seulement si le nombre formé par ses deux
derniers chiffres (i.e. $\overline{c_{1}c_0}^{\,10}$) est lui-même
divisible par 4.
\item $n$ est divisible par 5 si et seulement si son chiffre des unités $c_0$ est égal
à 0 ou 5.
\item $n$ est divisible par 7 si et seulement si $\overline{c_2c_1c_0}^{\,10}-
\overline{c_5c_4c_3}^{\,10}+\overline{c_8c_7c_6}^{\,10}+\cdots$
est divisible par 7.
\item $n$ est divisible par 8 si et seulement si le nombre formé par ses trois
derniers chiffres (i.e. $\overline{c_2c_{1}c_0}^{\,10}$) est
lui-même divisible par 8.
\item $n$ est divisible par 9 si et seulement si la somme de ses chiffres est
divisible par 9.
\item $n$ est divisible par 10 si et seulement si son chiffre des unités $c_0$ est égal
à 0.
\item $n$ est divisible par 11 si et seulement si $c_0-c_1+c_2-c_3+\cdots$ est
divisible par 11.
\item $n$ est divisible par 13 si et seulement si
$\overline{c_2c_1c_0}^{\ 10}-\overline{c_5c_4c_3}^{\
10}+\overline{c_8c_7c_6}^{\ 10}+\cdots$ est divisible par 13. \een




\exot{Existence et unicité de l'écriture d'un nombre en base $b$}

On rappelle le théorème de cours


\ENC{Numération en base $b$}{Soit $b$ un entier supérieur à 2. On
peut écrire de manière unique tout entier naturel $a$ sous la
forme
$$a=a_n\times b^n+a_{n-1}\times b^{n-1}+\cdots+a_1\times b^1+a_0\quad
\text{avec} \ 0\ie a_i\ie b-1\ \text{ et }\ a_n\neq0$$ On note
$a=\overline{a_na_{n-1}\cdots a_1a_0}^{\ b}$}

\been
\item Existence.
   \been
   \item Justifiez que $a$ peut s'écrire $$a=bq_0+a_0\text{, où }0\ie
   a_0\ie b-1\text{ et }q_0<a$$
   Justifiez que si $q_0<b$, le problème est résolu.
   \item Si $q_0\se b$, réitérer le procédé.

   Justifiez que ce procédé s'arrête au bout d'un nombre fini
   d'itérations.
   \een
\item Démontrez l'unicité de l'écriture.
\een

\exot{Triangle rectangle à côtés entiers.}

Les mesures des côtés d'un triangle rectangle sont des nombres
entiers $a$, $b$ et $c$.

\been

\item Démontrez que l'un au moins des trois nombres est pair.

\item Démontrez que l'un au moins des trois nombres est divisible
par 3.

\item Démontrez que l'un au moins des trois nombres est divisible
par 4.

\item Démontrez que l'un au moins des trois nombres est divisible
par 5.

\een



\exot{Sommes de carrés}

\been
\item Montrer qu'un entier congru à 3 modulo 4 n'est pas somme de
deux carrés d'entiers.
\item Montrer qu'un entier congru à 7 modulo 8 n'est pas somme de
trois carrés d'entiers.

\sm

\textsl{Un peu de culture}

Au vu des deux résultats précédents, on pourrait croire qu'un
entier congru à 15 modulo 16 n'est pas somme de quatre carrés
d'entiers, mais c'est faux... car tout entier naturel est somme de
quatre carrés ! \een


\exot{} Montrez que, pour tous entiers $m$ et $n$, $m^2+n^2$ est
divisible par 7 si et seulement si $m$ et $n$ sont divisibles par
7. \env{Résumez dans un tableau les valeurs que peut prendre $k^2$
modulo 7, avec $k$ un entier quelconque.}

\exot{} Résolvez dans $\bbn^2$ l'équation $2^x-5^y\equiv3[24]$.
\env{Montrez par récurrence que $2^n$ ne prend que deux valeurs
modulo 24 à partir d'un certain rang. De même avec $5^n$.}



\exot{} Quel est le chiffre des unités des nombres suivants :
 $$a=2001^{2003^{2005}}\quad b=2003^{2004^{2005}}\quad c=2003^{2005^{2004}}\quad d=2007^{2008^{2009}}$$

 \exot{VRAI OU FAUX~?}

 \been
 \item Tout carré est congru à 0 ou 1 modulo 8.
 \item Si $(x^2-1)^2$ n'est pas multiple de 4, alors $x$ l'est.
 \een

 \exot{} \been
 \item Soit $n\in\bbn^*$. Montrez que 5 divise $n(n^4-1)$.
 \item Déduisez-en que, si $p\in\bbn^*$, $n^p$ et $n^{p+4}$ ont le
 même chiffre des unités.
 \een

 \exot{} Le plan est rapporté à un repère orthonormal $\ouv$.
 Existe-t-il des points à coordonnées entières sur le cercle de
 centre O et de rayon $5\sqrt{27\,723}$~?

 \env{Quels sont les restes possibles dans la division par 4 d'une
 somme de deux carrés~?}

\exot{$\sqrt{2}$ est irrationnel}

Supposons qu'il existe $a\in\bbn$ et $b\in\bbn^*$ tels que
$\sqrt{2}=a/b$. En étudiant les chiffres des unités de $a$, $a^2$,
$b$, $2b^2$, montrez qu'on arrive à une contradiction.

\exot{$\sqrt{2}$ est décidément irrationnel}

Le plan est rapporté à un repère $\ouv$. On considère la droite
$D$ d'équation $y=\sqrt{2}x$ et l'application $f$ qui, à tout
point $M(x,y)$ du plan, associe le point $M'(x',y')$ défini par
$$\bsys
x'=3x-2y\\y'=-4x+3y\esys$$

Nous ferons l'hypothèse suivante : <<~il existe un point $m_0$ de
$D$ dont les coordonnées $x_0$ et $y_0$ sont des entiers
strictement positifs~>>.

\sm

On considère le point $m_1=f(m_0)$ de coordonnées $(x_1,y_1)$ puis
on réitère le procédé pour obtenir une suite $(m_k)_{k\in\bbn}$ de
points de coordonnées $(x_k,y_k)$.

Montrez que tous les points $m_k$ appartiennent à $D$ et que les
suites $(x_k)$ et $(y_k)$ sont des suites strictement
décroissantes d'entiers strictement positifs.

Expliquez le choix du titre de cet exercice.

\sm

\textsl{Un peu de culture}

Cette méthode de démonstration, dite de \textit{descente infinie},
a été découverte par Fermat au XVII\eme siècle.

%\end{document}







%\section{CONGRUENCES : ON SORT LE PLAN B}





\vfill

.

\pagebreak


\section{PGCD}

\subsection{Définition}

Considérons un entier relatif $a$. On notera $\DR(a)$ l'ensemble de ses diviseurs dans $\bbz$.

Par exemple, $\DR(0)=\bbz$, $\DR(1)=\ac{-1,1}$, $\DR(12)=\ac{-12,-6,-4,-3,-2,-1,1,2,3,4,6,12}$ et plus généralement $$\DR(a)=\ac{-|a|,...,-1,1,...,|a|}$$

 \ENC{\Def\ \ PGCD}{Soit $a$ et $b$ deux entiers. On appelle PGCD de $a$ et $b$ et on note $a\wedge b$ l'entier défini de la manière suivante:
\bel
\item $0\wedge 0=0$
\item Si $a$ et $b$ ne sont pas simultanément nuls, $a\wedge b$ est le plus grand entier naturel qui divise simultanément $a$ et $b$.
\el}


Le PGCD de $a$ et $b$ est donc le plus grand élément de $\DR(a)\cap\DR(b)$ : la notation le rappelle.
Comme toute partie non vide et majorée de $\bbn$ admet un plus grand élément, cette définition en est bien une car $\DR(a)\cap\DR(b)$ contient au moins $1$.


\subsection{\'Egalité de Bézout}

\ill{Voici la clé de notre chapitre : nous allons montrer que notre PGCD est en fait une combinaison linéaire de $a$ et de $b$. \\
Cette idée est due au français \'Etienne Bézout(1730 - 1783) dont vous pouvez admirer le charmant portrait. \\
Considérons d'abord le cas où $a$ et $b$ sont non nuls et notons $$S=\ac{au+bv\ |\ (u,v)\in\bbz^2\ \text{ et } au+bv>0}$$
L'ensemble $S$ est constitué d'entiers naturels et est non vide car il contient au moins $a^2+b^2$ : il admet donc un unique \textbf{plus petit élément} que nous noterons $d$ qui s'écrit donc $d=au_0+bv_0$.\\
Notre mission va bien sûr consister à prouver que $d$ est en fait le PGCD de $a$ et $b$. }{Bezout}


Nous allons pour cela utiliser une ficelle classique : introduire le reste de la division euclidienne de $a$ par $d$ et utiliser le fait que  $d$  est le plus petit élément de $S$ puis raisonner par l'absurde.

La division de  $a$ par $d$ s'écrit

$$a=dq+r \quad\text{avec}\quad 0\ie r<d$$

\textbf{Supposons} que $r>0$, alors
$$r=a-dq=a-q(au_0+bv_0)=a(1-qu_0)+b(-qv_0)>0$$
et donc $r\in S$ or $r<d$. C'est impossible car $d$ est le plus petit élément de $S$ : \textbf{contradiction}.

Notre supposition de départ est donc fausse et $r=0$. Nous en déduisons que $d$ divise $a$.

On montre de manière similaire que $d$ divise $b$. Ainsi 
$$d \text{ est un diviseur commun de } a\text{ et } b$$

Il nous reste à montrer que c'est le plus grand. Soit $\delta$  un diviseur commun à $a$ et $b$  quelconque. On a montré   au début du cours (Propriété XX-2) qu'alors $\delta$ divisait toute combinaison linéaire de $a$ et de $b$, donc en particulier $\delta$ divise $au_0+bv_0$ donc $d$. Alors toujours d'après la propriété XX-2, $c\ie|d|=d$, donc $d$ est bien le plus grand des diviseurs. 

\sm


Il faut encore vérifier que le PGCD est \textbf{unique}. La méthode habituelle est de supposer qu'il existe un deuxième PGCD, disons $d'$. Alors $d\ie d'$ car $d'$ est le plus grand diviseur puis $d'\ie d$ car $d$ aussi et finalement $d=d'$ ce qui assure l'unicité.

\sm 

Comme $|a|=\pm1\times a+0\times 0$, l'égalité tient toujours si $b$ (ou $a$) est nul, donc

\ENC{\Thm\ \ \'Egalité de Bézout}{Soit $a$ et $b$ deux entiers relatifs.\\
Si $d=a\wedge b$, alors il existe deux entiers $u$ et $v$ tels que $$au+bv=d$$}

Ce résultat est beaucoup plus important qu'il n'y parait. Nous allons d'abord voir quelques conséquences immédiates.


\subsection{Premières propriétés}

Soit $\delta$ un diviseur commun à $a$ et $b$. Alors il divise aussi $au+bv$ donc $d$ comme nous l'avons déjà vus. Inversement, un diviseur de $d$ divise aussi $a$ et $b$, d'où

\ENC{\Prop}{ Les diviseurs communs à $a$ et $b$ sont les diviseurs de leur PGCD $$\DR(a)\cap\DR(b)=\DR(a\wedge b)$$}

De plus, $a\wedge b$ divisant toute combinaison linéaire de $a$ et $b$, donc toute combinaison linéaire de $a$ et $b$ est un multiple de $a\wedge b$.

Inversement, puisqu'il existe deux entiers $u$ et $v$  tels que $a\wedge b=au+bv$, on a $k(a\wedge b)=(ku)a+(kv)b$ et donc tout multiple de $a\wedge b$ est une combinaison linéire de $a$ et $b$

\ENC{\Prop}{L'ensemble $S=\ac{ax+by \ |\ (x,y)\in\bbz^2}$ constitue l'ensemble de tous les multiples de $d=a\wedge b$, c'est à dire $$S=d\bbz$$}

Par exemple, l'équation $15x+12y=5$ ne peut pas avoir de solution dans $\bbz$ car $15\wedge 12=3$ et 5 n'est pas un multiple de 3.

\sm

Donnons maintenant quelques propriétés évidentes

\ENC{\Prop}{\bel
\item $a\wedge b=b\wedge a$
\item $a\wedge a=a$
\item $a\wedge 1=1$
\item $a\wedge b=b \ssi b|a$
\el}


Nous nous restreindront dans la suite à des entiers naturels car

\ENC{\Prop}{$$a\wedge b=|a|\wedge|b|$$}

Voyons maintenant une propriété qui va être à la base de la construction algorithmique du PGCD

\ENC{\Prop}{Si $ab\neq 0$  et $k$ un entier quelconque $$a\wedge(b+ka)=a\wedge b$$ et en particulier $$a\wedge b=a\wedge(b-a)=a\wedge(a-b)$$}

La démonstration est classique et nous servira à de nombreuses occasions.

Notons $a\wedge b=d$ et $a\wedge(b+ka)=d'$. Alors \bel
\item $d$ divisant $a$ et $b$, $d$ divise $(ka+b)$  et $a$ donc divise $d'$ d'après une propriété précédente.
\item d'autre part, $d'$ divise $a$ et $b+ka$, donc divise $b+ka-ka$, donc $b$, donc $d'$ est un diviseur commun à $a$ et $b$ donc $d'$ divise $d$.
\el
Comme $d|d'$ et $d'|d$, on a donc $d=d'$.

\sm

Cette propriété va nous permettre de fabriquer un algorithme de calcul de $a\wedge b$. En effet, si $a\se b$, et comme $a\wedge b=b\wedge (a-b)$, on calcule le PGCD de deux entiers plus petits. Et on réitère. Par exemple :

$$15\wedge 12=12\wedge 3=9\wedge 3=6\wedge 3=3\wedge 3=3\wedge0=3$$

ce qui donne en xcas 

\begin{lstlisting}
pgcd1(a,b):={
if (b=0) return a;
if (a>=b) return(pgcd1(b,a-b)); 
else return(pgcd1(a,b-a));
}
\end{lstlisting}


Comment se persuader que cette descente aboutit ? Nous pouvons aisément nous convaincre sans se perdre dans trop de formalisme que 

\ENC{\Prop\ \ \ Suite décroissante d'entiers naturels}{ Toute suite strictement décroissante d'entiers naturels est finie.}

Et cette constante ne pouvant être par construction que 0, le PGCD de $a$ et $b$ sera la dernière valeur non nulle de cette suite car $k\wedge 0=k$ pour tout entier $k$.

Ce procédé semble  assez long : beaucoup d'opérations sont inutiles. Malgré tout il est assez efficace car il n'utilise que des sommes et des différences qu'un ordinateur traite extrêmement rapidement.




\subsection{Algorithme d'Euclide}

C'est  le même principe que ce que nous venons de faire, mais en plus rapide car nous remarquons que, en notant $$a=bq_0+r_0\quad  \text{avec }0\ie r_0<b$$ la division euclidienne de $a$ par $b$, on obtient que 
$$a\wedge b = b\wedge (a-bq_0)=b\wedge r_0$$

Puis en notant $$b=r_0q_1+r_1\quad \text{avec }0\ie r_1<r_0$$

on obtient de même que $$a\wedge b=b\wedge r_0=r_0\wedge r_1$$

et on continue ainsi à fabriquer une suite strictement décroissante d'entiers naturels~:~elle est donc finie et son dernier terme $r_p= 0$.

Alors $$a\wedge b=r_{p-1}\wedge r_p=r_{p-1}\wedge 0=r_{p-1}=\text{ le dernier reste non nul}$$
 
Donnons deux algorithmes XCAS donnant le pgcd : l'un itératif, l'autre récursif et utilisant tous deux la fonction \Coms{irem}{a,b} vue précédemment qui donne le reste de la division euclidienne de a par b :

\begin{lstlisting}
pgcd2(a,b):={
local r;
while(b!=0){
r:=irem(a,b);
a:=b;
b:=r;
}
return(a);
}
\end{lstlisting}






et une version récursive~:

\begin{lstlisting}
pgcd3(a,b):={
if (b==0)
return(a);
else
return(pgcd3(b,irem(a,b)));
}
\end{lstlisting}



Nous pouvons traduire pgcd2 en langage ti89~:

\begin{lstlisting}
:pgcd2(a,b)
:Func
:Local r
:  While b<>0
:    irem(a,b) => r
:    b => a
:    r => b;
:   EndWhile
:  Return a
:EndFunc
\end{lstlisting}

ou en langage ti<89~:

\begin{lstlisting}
Prompt a
Prompt b
  While b!=0
     a-b*Int(a/b)-> r
    b -> a
    r -> b;
  End
Disp  a
\end{lstlisting}

ou en langage Casio~:

\begin{lstlisting}
"a" : ? -> a
"b" : ? -> b
  While b!=0
     a-b*Int(a/b)-> r
    b -> a
    r -> b;
  WhileEnd
a
\end{lstlisting}


\begin{figure}
              \begin{Idee}
              XCAS a une fonction très éfficace pour calculer les PGCD : \Coms{igcd}{a,b}. Pourtant, il est \emph{pédagogiquement} important de voir différents algorithmes de calcul, histoire de n'être pas seulement des consommateurs...
               \end{Idee}
               \end{figure}




Sans ordinateur, on peut présenter les calculs sous forme de tableau.







Il nous reste un dernier algorithme à découvrir, qui nous donnera des coefficients des égalités de Bézout.

\subsection{Algorithme d'Euclide étendu}

L'algorithme d'Euclide nous assure que le PGCD de $a$ et $b$ est le dernier reste non nul de la suite $(r_k)$ construite au paragraphe précédent. L'égalité de Bézout nous assure de l'existence de deux entiers $u$ et $v$ tels que $au+bv=a\wedge b$.

Nous allons essayer de combiner les deux en construisant deux suites $(u_k)$ et $(v_k)$ telles que $$r_k=au_k+bv_k$$

Voici le départ \bel
\item $r_0=a=1\times a+0\times b$
\item $r_1=b=0\times a+1\times b$
\item $r_2=$\texttt{reste}$(r_0,r_1)$\\
$\vdots$
\item $r_{i+1}=$\texttt{reste}$(r_{i-1},r_i)$\\
$\vdots$
\item $r_{p-1}=a\wedge b$
\item $r_p=0$
\el

Or par définition, comme $r_2=$\texttt{reste}$(r_0,r_1)$, on a $r_0=q_2r_1+r_2$, donc $r_2=1\times r_0-q_2\times r_1$, c'est à dire 
$$u_2=1 \ \text{ et } \ v_2=-q_2$$

On réitère le mécanisme. Supposons que $r_{k-1}=u_{k-1}\times a+v_{k-1}\times b$ et $r_{k}=u_{k}\times a+v_{k}\times b$

Comme $r_{k+1}=$\texttt{reste}$(r_k,r_{k-1})$, on a $r_{k-1}=q_{k+1}r_k+r_{k+1}$, donc $r_{k+1}=1\times r_{k-1}-q_{k+1}\times r_k$, c'est à dire $$r_{k+1}=1\times(u_{k-1}\times a+v_{k-1}\times b)-q_{k+1}\times(u_{k}\times a+v_{k}\times b)$$

Finalement

$$u_{k+1}=u_{k-1}-u_k\times q_{k+1} \ \text{ et } \ v_{k+1}=v_{k-1}-v_k\times q_{k+1}$$

\c Ca a l'air un peu brut comme ça, au premier coup d'\oe il, mais en fait il y a une disposition pratique qui permet de mieux voir ce qui se passe. D'abord, dans algorithme d'Euclide étendu il y a algorithme d'Euclide, donc on commence par rechercher le PGCD de $a$ et $b$ par l'algorithme d'Euclide en n'oubliant pas cette fois de noter les quotients en remplissant le tableau suivant

\begin{center}
\begin{tabular}{|c||c|c|c||c|}
\hline $k$ & $u_k$ & $v_k$ & $r_k$ & $q_k$ \\ 
\hhline{=====} 0 & 1 & 0 &a& /  \\ 
\hline 1 & 0 & 1 &b& $q_1$  \\ 
\hline 2 &  &  &$r_2$& $q_2$  \\ 
\hline 3 &  &  & $r_3$&$q_3$  \\ 
\hline $\vdots$ &  &  & $\vdots$ & $\vdots$ \\ 
\hline $p-1$ &  &  & $r_{p-1}=a\wedge b$ & $q_{p-1}$ \\ 
\hline $p$ &  &  &   $r_p=0$ &\\ 
\hline 
\end{tabular} 
\end{center}

Et le secret tient dans le schéma 

\begin{center}
\begin{tabular}{ccccc}
 & \psframebox[fillstyle=solid,fillcolor=bleu_ciel]{$u_k$} & {\Large{\textbf{$-$}}} &  &    \\
 & & & &  \\ 
{\Large{\textbf{(}}} & \psframebox[fillstyle=solid,fillcolor=bleu_ciel]{$u_{k+1}$} & {\Large{\textbf{$\times$}}} & \psframebox[fillstyle=solid,fillcolor=vert_e]{$q_{k+1}$} & {\Large{\textbf{)}}}   \\
 & & & &  \\ 
{\Large{\textbf{$=$}}} & \psframebox{$u_{k+2}$} &  &  &    \\ 
\end{tabular} 
\end{center}


et pareil pour les $v_k$.

Voyons tout de suite sur un exemple simple : cherchons $u$ et $v$ tels que $$19u+15v=19\wedge 15$$

\begin{center}
\begin{tabular}{|c||c|c|c||c|l}
\hhline{-----} $k$ & $u_k$ & $v_k$ & $r_k$ & $q_k$ &  \\ 
\hhline{=====} 0 & \psframebox[fillstyle=solid,fillcolor=bleu_ciel]{ 1} & \psframebox[fillstyle=solid,fillcolor=bleu_ciel]{ 0} & \psframebox[fillstyle=solid,fillcolor=bleu_ciel]{ 19} & / & $L_0$ \\ 
\hhline{-----} 1 & \psframebox[fillstyle=solid,fillcolor=bleu_ciel]{ 0} & \psframebox[fillstyle=solid,fillcolor=bleu_ciel]{ 1} & \psframebox[fillstyle=solid,fillcolor=bleu_ciel]{ 15} & \psframebox[fillstyle=solid,fillcolor=vert_e]{1} & $L_1$ \\ 
\hhline{-----} 2 & 1 & $-1$ & 4 & 3 & $L_2\leftarrow L_0-\psframebox[fillstyle=solid,fillcolor=vert_e]{1}\times L_1$ \\ 
\hhline{-----} 3 & $-3$ & 4 & 3 & 1 & $L_3\leftarrow L_1-3\times L_2$ \\ 
\hhline{-----} 4 & 4 & $-5$ & 1 & 3 & $L_4\leftarrow L_2-1\times L_3$ \\ 
\hhline{-----} 5 &  &  & 0 &  & $L_5\leftarrow L_3-3\times L_4$ \\ 
\hhline{-----} 6 &  &  &  & 0 &  \\ 
\hhline{-----} 
\end{tabular} 
\end{center}


Le dernier reste non nul est 1 donc $19\wedge 15=1$ et $4\times19-5\times 15=1 $

On  peut naturellement utiliser le tableur XCAS pour obtenir ces résultats. On peut égalment crée des algorithmes ...pour vos calculatrices.

\begin{lstlisting}
bezout(a,b):={
local la,lb,lr,q,lb2;
la:=[1,0,a];
lb:=[0,1,b];
lb2:=b;
while (lb2 !=0){
q:=quotient(la[2],lb2);
lr:=la+(-q)*lb;
la:=lb;
lb:=lr;
lb2:=lb[2];
}
return(la);
}
\end{lstlisting}


\Remarque{Il existe bien sûr une fonction XCAS qui fait ça très vite et très bien : \Coms{igcdex}{a,b} renvoie les deux coefficients et le PGCD.}


En ti~:

\begin{lstlisting}
Input "A=", R
Input "B=", Y
1->U: 0->W: 0->V: 1->X
While Y !=0
Int(R/Y)->Q
U->Z: W->U: Z-Q*W->W
V->Z: X->V: Z-Q*X->X
R->Z: Y->R: Z-Q*Y->Y
End
Disp"U=",U,"V=",V
Disp "PGCD=",R
\end{lstlisting}


En Casio~:

\begin{lstlisting}
"A=" :? -> R
"B=" :? -> Y
1->U: 0->W: 0->V: 1->X
While Y !=0
Int(R/Y)->Q
U->Z: W->U: Z-Q*W->W
V->Z: X->V: Z-Q*X->X
R->Z: Y->R: Z-Q*Y->Y
WhileEnd
"U=":U : "V=":V
"PGCD=" :R
\end{lstlisting}


\subsection{Petits exercices}

\exot{}

Trouvez tous les diviseurs communs à~:

\begin{nliste}{3}

\item 300 et 350;
\item 147 et 490;
\item 308 et 364.

\end{nliste}

\exot{}

Soit $n\in\bbn$, $a=n+3$ et $b=2n+1$.

\begin{enumerate}
\item Montrez que si $d$ divise $a$ et $b$, alors $d$ divise 5.
\item Quels sont les valeurs possibles du PGCD de $a$ et $b$~?
\item Déterminez $a\wedge b$ selon les valeurs de $n$.

\end{enumerate}

\exot{}
Soient $a$ et $b$ des entiers naturels.
On a $a=630$, $a\wedge b=105$ et $600<b<\nombre{1100}$. Trouvez b.

Même question avec 600, 12, 260 et  300 respectivement.


\exot{}

Si on divise $\nombre{2897}$ et $\nombre{3505}$ par un même entier positif, on obtient
respectivement 13 et 5 comme restes.

Quel est cet entier~?

Même question avec $\nombre{4294}$, $\nombre{3521}$, 10 et 11.



\section{NOMBRES PREMIERS ENTRE EUX}

\subsection{Définition}
\ENC{\Def\ \ Entiers premiers entre eux}{Deux entiers $a$ et $b$ sont premiers entre eux si et seulement si $$a\wedge b=1$$}

Par exemple, on vérifie à l'aide de la fonction \code{gcd} de XCAS (plus efficace que nos petits programmes) que  1234 et 258147 sont premiers entre eux
\begin{lstlisting}
gcd(1234,258147)
\end{lstlisting}


\subsection{Théorème de Bézout}


D'après l'égalité de Bézout vue précédemment

\ENC{\Thm\ \ Théorème de Bézout}{Les entiers $a$ et $b$ sont premiers entre eux si et seulement s'il existe deux entiers $u$ et $v$ tels que $au+bv=1$  $$a\wedge b=1\ssi \text{ il existe } (u,v)\in\bbz^2 \text{ tel que } au+bv=1$$}

On peut par exemple prouver ainsi que deux entiers consécutifs  sont premiers entre eux  car $$n\times(-1)+(n+1)\times 1=1$$

\subsection{Théorème de Gauss}


\ENC{\Thm\ \ Théorème de Gauss}{Si $a|bc$ et si $a\wedge b=1$ alors $a|c$}

Il suffit d'utiliser le théorème de Bézout. je vous laisse le faire.

Par exemple 8 divise $3\times 16=48$ et 8 est premier avec 3 donc 8 divise 16 (on le savait !)

Mais 8 divise $6\times 4=24$  mais ne divise ni 6 ni 4.


Nous allons en donner un corrolaire souvent très utile 


\ENC{Corrolaire}{Si un entier est divisibles par deux entiers $a$ et $b$ premiers entre eux, alors il est divisible par leur produit}


Ainsi, pour prouver qu'un entier est divisible par 24, il suffit de prouver qu'il est divisible par
3 et 8 qui sont premiers entre eux.





\subsection{Exercices}

\exot{}

Prouvez que $2n+1$ et $3n+2$ sont premiers entre eux.

\exot{}

On suppose que $a$ et $b$ sont premiers entre eux. Prouvez que $a+b$ est premier avec $a$ et $b$.

\exot{}

On suppose que $a\wedge b=1$ et $a\wedge c=1$. 

\begin{enumerate}

\item Montrez que $a\wedge bc=1$.
\item Montrez que $a^n\wedge b^p=1$ pour tous $n$ et $p$ dans $\llbracket 1\pv +\infty\llbracket$.
\end{enumerate}


\exot{}

Trouvez $a$ et $b$ tels que $a+b=112$ et $a\wedge b=14$.

\exot{}

On pose $a=2n^3+5n^2+4n+1$ et $b=2n^2+n$.

\begin{enumerate}
\item Prouvez que $2n+1$ divise $a$ et $b$.
\item $2n+1$ est-il le PGCD de $a$ et $b$~?
\end{enumerate}


\exot{}

Quatre entiers positifs $a$, $b$ et $c$ forment dans cet ordre une suite arithmétique dont la raison
est un nombre entier premier avec $a$.

Trouvez ces nombres sachant que $10a^2=d-b$.

\exot{}

Prouvez que pour tout entier $n$, le nombre $A=n(5n^2+1)$ est divisible par 6.


\section{\'EQUATIONS DIOPHANTIENNES $ax+by=c$}

\exot{Exercice résolu}

\been
\item Nous voulons résoudre dans $\bbz\times\bbz$ l'équation
$1260x+294y=2814$

Aprés simplifications, nous obtenons l'équation équivalente
$$30x+7y=67\quad (1)$$
Or $-3\times 30+13\times 7=1$, d'où $30\times
(-201)+7\times871=67$ et donc $$(1)\ssi 30(x+201)=7(871-y)$$ Mais
30 et 7 étant premiers entre eux, le théorème de Gauss nous permet
d'affirmer que, si $(x,y)$ est solution, alors 30 divise $871-y$
et 7 divise $x+201$. Les couples solutions sont donc de la forme
$(-201+7k,871-30k')$, $(k,k')\in\bbz^2$. Remarquons ensuite que
$k=k'$, puis que $871=29\times30+1$ et $-201=-29\times 7+2$, d'où
$$S=\big\{(-7p+2,30p+1),\ p\in\bbz\big\}$$

\item Si nous voulons faire la même chose avec l'équation
$1260x+294y=3814$, nous remarquons qu'après division par 2,
l'équation est équivalente à
$$(2\times3\times7)\times 45\,x+(2\times3\times 7)\times 21\,y=1907$$
Or 1907 n'est pas divisible par 2 donc $S=\emptyset$.

\een 


\exot{}

Résolvez les équations suivantes dans $\bbz^2$~:

\begin{nliste}{2}
  \item $41x-27y=1$
  \item $5x-8y=2$
  \item $-156x+276y=24$
\end{nliste}




\section{EXERCICES DIVERS}






\exot{\'Eléments inversibles de $\bbz_n$}\label{inv1}

On note $\bbz_n$ l'ensembles des classes modulo $n$. Par exemple,
$\bbz_3$ contient trois éléments : $\dot{0}$, $\dot{1}$ et
$\dot{2}$.

\been
\item
\been

\item À l'aide d'un tableur, dressez les tables de multiplication de
$\bbz_9$, $\bbz_{11}$, $\bbz_{12}$ et $\bbz_{13}$. Vous pourrez
utiliser la fonction \texttt{MOD(nombre;diviseur)} qui renvoie le
reste de la division euclidienne de \texttt{nombre} par
\texttt{diviseur}.

\item Vous avez par exemple obtenu $
4\times2\equiv4\times5[12]$. A-t-on pour autant $2\equiv5[12]$~?

Autre problème : on a $4\times 3\equiv0[12]$, alors que ni 4 ni 3
n'est nul. On dit que 4 et 3 sont des diviseurs de zéro.


Observe-t-on les mêmes <<~anomalies~>> dans $\bbz_9$~?
$\bbz_{11}$~? $\bbz_{13}$~?

\item Résolvez les équations $(E_1)$~: $5x+7=0$, $(E_2)$~:
$6x-3=0$ et $(E_3)$~:~$3x+2=0$ dans $\bbz_9$ puis dans
$\bbz_{13}$. \een

\item On recherche à présent les éléments inversibles de $\bbz_n$.

0 \ENC{Définition }{ On dit que $\dot{a}$ est inversible dans
$\bbz_n$ si et seulement s'il existe un élément $\dot{b}$ de
$\bbz_n$ tel que $$\dot{a}\times\dot{b}=\dot{1}$$} \been

\item Montrez que $\dot{a}$ est inversible dans $\bbz_n$ si et
seulement si $a$ et $n$ sont premiers entre eux. \env{Pensez au
théorème de Bézout.}

\item Commentez alors les résultats observés à la question 1).

\item On suppose à présent que $\dot{a}$ est inversible dans
$\bbz_n$. Déterminez son inverse dans $\bbz_n$ en utilisant les
résultats du a).



\een

\item Première application~: résolution d'équations. \been
\item Résolvez dans $\bbz_{31}\times \bbz_{31}$ le système $\bsyc
8x+7y&=&25\\13x+24y&=&17\esyc$
\item Résolvez dans $\bbz_{4999}$ $2321x+1553=0$.
\een

\item Deuxième application : chiffrement affine.

\sm

Voici notre premier contact avec la \textsl{cryptographie}, la
science du secret. Elle occupe actuellement la pointe de la
recherche, notamment en arithmétique car elle a des applications
quotidiennes en perpétuelle évolution : internet, cartes à puce.
Ce sont les militaires qui les premiers ont eu recours à
l'arithmétique pour coder leurs messages. Les premières méthodes
se contentaient de changer l'ordre des lettres. Par exemple, César
numérotait les lettres de l'alphabet puis les décalait de trois
rang~: un $a$ devenait un $d$, un $r$ devenait un $u$, un $z$
devenait un $c$. Nous allons étudier un système du même style.

\sm

On assimile les vingt-six lettres de l'alphabet auxquelles on
ajoute l'espace aux nombres 0, 1,...,26. On code ces nombres à
l'aide d'une fonction $f$ du type~:
$$f~: \ x\mapsto ax+b[27]$$
où $a$ et $b$ sont des entiers.

\been

\item \'Etude d'un cas particulier~:~$f(x)=17x+22[27]$.

\been
\item Proposez une table de chiffrage à l'aide d'un tableur.
\item Chiffrez <<~LA MAITRESSE EN MAILLOT DE BAIN~>>.
\item Déterminez, s'il existe, l'inverse $u$ de 17 dans $\bbz_{27}$.
\item On veut trouver une fonction de déchiffrage $g$ qui
vérifierait $$y\equiv f(x)[27]\ssi g(y)\equiv x[27]$$ En quoi le
résultat précédent peut vous aider à déterminer $g$~? \een

\item Reprenez les questions précédentes avec $f~:\ x\mapsto
9x+22[27]$

\item Montrez que, pour pouvoir déterminer une fonction de
déchiffrage, il faut et il suffit que $a$ soit premier avec 27.



\een \een

\exot{Le chiffrement de Lester Hill}

Dans les années 20, le bon Lester essaya de mettre un peu de
piquant dans le chiffrement de César. On commence par supprimer
espaces et ponctuations et on associe comme d'habitude chaque
lettre à un nombre de $[\![0\,,\,25]\!]$. L'innovation de Lester
est de ne pas chercher à coder le message lettre par lettre, mais
groupe de lettre par groupe de lettre. Nous allons étudier le cas
particulier des blocs de deux lettres qu'on appellera
\textsl{bigrammes}.

La clé secrète du cryptosystème est cette fois-ci constitué de
quatre entiers $a$, $a'$, $b$ et $b'$ tels que le système
$$\bsyc ax+by&\equiv& c[26]\\a'x+b'y&\equiv& c'[26]\esyc$$
admette toujours une solution unique dans
$[\![0\,,\,25]\!]\times[\![0\,,\,25]\!]$, quels que soient $c$ et
$c'$.

Pour un bigramme, on remplace $x$ et $y$ par les deux nombres
correspondant aux lettres du bigramme. On en déduit les deux
nombres $c$ et $c'$ que l'on remplace ensuite par les deux lettres
correspondantes.

Si le nombre de lettres du message est impair, on convient de
remplacer la dernière par X.

\been
\item Exemple : avec la clé $a=8$, $b=3$, $a'=5$, $b'=2$, codez
<<~TURLUTUTU~>>.
\item Démontrez que le système correspondant à la clé précédente
admet toujours des solutions, quels que soient $c$ et $c'$.
\item Décodage : débrouillez-vous pour donner les formules qui
permettent de décoder (nous avons déjà résolu ce genre de problème
dans l'exercice 20).
\item Cas général : démontrez que le système admet toujours des
solutions si $ab'-a'b$ et 26 sont premiers entre eux. \een



\exot{Le problème du ministre syldave.}

En vue d'intégrer la Confédération Internationale de la
Consommation, le ministre syldave des finances engage un
conseiller étranger qui lui propose, par mesure d'économie, de ne
frapper que des pièces de 4999 Spchprzts et de 3771 Spchprzts. Un
dialogue s'engage :
\begin{itemize}
\item[-] Mais, mon cher Joe Max Bill Pol, comment pourrai-je
acheter mon pichet de bière Zmtschgr à un Spchprzts ?
\item[-] No problem Otto : il souffit que le gawçon vous wende la
money.
\item[-] Soit, mais sera-ce possible pour n'importe quelle somme~?
\item[-] Absolutely dear.
\end{itemize}

Expliquez~!



\exot{Le problème de l'astronome syldave.}

Otto Blortsch, le célèbre astronome syldave, a observé au jour
$J_0$ la comète Arzchtrpm (qu'on notera $A$), qui, comme chacun
sait, apparaît périodiquement tous les 105 jours. Six jours plus
tard, il observe la comète Brtdszztch (qu'on notera $B$) qui, bien
sûr, a une période d'apparition de 81 jours. Otto voudrait
déterminer $J_1$, le jour de la prochaine apparition
\textsl{simultanée} des deux comètes à ses yeux ébaubis.

\been
\item Soient $u$ et $v$ (tiens tiens...) le nombre de périodes
effectuées respectivement par $A$ et $B$ entre $J_0$ et $J_1$.
Montrez que le couple $(u,v)$ est solution de l'équation
$$(E)~:~35x-27y=2$$.
\item Déterminez UNE solution particulière de $(E)$, puis TOUTES
les solutions.
\item Déterminez LA solution correspondant à $J_1$.
\item Le jours $J_0$ était le dimanche 7 décembre 2003. Quelle
fut (ou sera) la date exacte de $J_1$~?
\item Ce jour-là, Otto avait une gastro et a raté l'événement~:
combien de jours devra-t-il attendre jusqu'à la prochaine
conjonction des deux astres~? \een



\exot{Le problème des pirates syldaves.}

\sm


15 pirates syldaves se partagent un butin constitué de pièces
d'or. Mais une fois le partage (équitable) effectué, il reste 3
pièces. Que va-t-on en faire ? La discussion s'anime. Bilan : 8
morts. Les  survivants recommencent le  partage, et il reste cette
fois-ci 2 pièces ! Nouvelle bagarre à l'issue de laquelle il ne
reste que 4 pirates. Heureusement, ils peuvent cette fois-ci se
partager les pièces sans qu'il n'en reste aucune. Sachant que 32
Zmtschgr (bière syldave) coûtent une pièce d'or, combien (au
minimum) de Zmtschgr pourra boire chaque survivant ?


\exot{Numéro I.S.B.N.}


L'\textit{International Standard Book Number} est un numéro qui sert à identifier un livre. Ce numéro est un << mot >> de longueur 10
constitué avec les chiffres $0,1,\cdots,9$ et la lettre $X$ (qui représente le nombre 10). La lettre X ne sera utilisée, si nécessaire,
que pour la clé qui est  le dernier caractère.

$$\rm{Exemples}\ :\ 2\ 84180\ 013\ X,\ \ \rm{ou}\ \
0\ 12\ 163251\ 2.$$ Le premier chiffre représente le pays, ensuite un bloc de chiffres est attribué à un éditeur, puis un autre bloc est
le numéro donné par l'éditeur au livre. Le dernier caractère est la clé, calculée de telle sorte que si $a_1a_2\cdots a_{10}$ désigne un
numéro I.S.B.N., l'entier $\ds\sum_{i=1}^{10}ia_{11-i}$ soit divisible par 11. \been
\item Montrer que les neuf premiers chiffres d'un numéro I.S.B.N.
étant donnés, il y a une seule manière de déterminer la clé.
\item On suppose que lors de la saisie d'un numéro I.S.B.N., on
effectue un erreur sur un (et un seul) des 10 caractères. Montrer que l'on peut détecter l'erreur mais pas la corriger.
\item On suppose que lors de la saisie d'un numéro I.S.B.N., on
permute deux des caractères sans modifier les autres. Montrer que l'on peut détecter l'erreur mais pas la corriger.
\item Pourquoi prendre $\ds\sum_{i=1}^{10}ia_{11-i}$
plutôt que $\ds\sum_{i=1}^{10}a_{i}$ ? \een

\exot{Arithmétique...complexe.}

\sm


 Soit $a$ un nombre complexe. On
note $\bbz[a]$ l'ensemble des complexes $z$ qui s'écrivent sous la
forme $z=x+ay$ avec $x$ et $y$ des entiers. Plus sommairement on
écrit
$$\bbz[a]=\{z=x+ay\,|\,x,y\in\bbz\}$$
\subsection*{A - Structure d'anneau - \'Eléments inversibles}

\been
\item Vérifiez que $\bbz[a]$ contient 0, que si $z$ et $z'$
appartiennent à $\bbz[a]$, il en est de même pour $z-z'$. On dit
alors que $\bbz[a]$ muni de l'addition a une structure de
$groupe$.
\item Vérifiez que $\bbz[a]$ contient 1 et que si $z$ et $z'$
appartiennent à $\bbz[a]$, il en est de même pour leur produit
$zz'$. Sachant que la multiplication des complexes est
distributive sur l'addition, on dit alors que $\bbz[a]$ muni de
l'addition et de la multiplication a une structure  $d'anneau$.
\item Petit rappel~: on dit que $z$ est inversible dans $A$ si et
seulement s'il existe un élément $z'$ de $A$ tel que $zz'=1$.
\been
    \item Trouvez par exemple les éléments inversibles de
          $\bbz[0]$\footnote{Au fait, comment écrit-on plus
          simplement $\bbz[0]$~?}.
    \item Quels sont les éléments inversibles de
    $\bbz[i]$\footnote{Utilisez les modules} ?
\een \een

\subsection*{B - Division euclidienne dans $\bbz[i]$}

On va s'intéresser à l'existence d'une division euclidienne dans
l'anneau $\bbz[i]$, c'est à dire l'existence, pour tout couple
$(z,w)$  d'éléments de $\bbz[i]$ avec $w\neq0$, d'un couple
$(q,r)$ d'éléments de $\bbz[i]$ tel que
$$z=wq+r\quad\text{avec}\quad |r|<|w|$$ \been
\item On considère le plan complexe muni d'un repère orthonormé
$\ouv$. Comment décririez-vous les images des éléments de
$\bbz[i] $ ?
\item On appelle $f$ le complexe égal à $z/w$. Est-ce que $f$
appartient forcément à $\bbz[i]$ ?
\item On note $f=x+iy$ avec $x$ et $y$ des réels et $F$ son image
dans le plan complexe. Soit $Q$ l'image de $q$ dans le plan
complexe. Traduisez graphiquement la division euclidienne de $z$
par $w$.
\item Comment caractérisez par une inégalité l'entier $a$ <<~le
plus proche~>> de $x$~?
\item Soit $b$ l'entier le plus proche de $y$. Notons $q$ le
complexe $a+ib$. Montrez que $|f-q|<1$ et concluez notre petite
étude. \een

\subsection*{C- Le théorème de Bézout mis en défaut dans
$\bbz[i\sqrt{5}]$~?}

Nous aurons besoin de deux définitions pour travailler

\ENC{Définition 1}{Deux éléments d'un anneau $A$ sont dits
premiers entre eux s'ils n'ont pas de diviseur commun non
inversible ( i.e. si tous leurs diviseurs communs sont inversibles
).}

\sm

\ENC{Définition 2}{On dit que deux éléments $a$ et $b$ d'un anneau
$A$ sont étrangers s'ils vérifient $$\lambda a+\mu b=1\quad
\text{avec}\quad \lambda,\,\mu \in A$$}

\sm

Dans la suite de l'exercice, on travaillera dans $\bbz[i\sqrt{5}]$
qu'on notera $A$.

\been
\item Montrez que la définition 1 est compatible avec la
définition donnée dans le cours pour $\bbz$.
\item Quels sont les éléments inversibles de $A$~?
\item Montrez que $4+i\sqrt{5}$ et $4-i\sqrt{5}$ sont étrangers dans $A$.

\item Quels sont les diviseurs de 3 dans $A$~?

\item Montrez alors que $4+i\sqrt{5}$ et 3 sont premiers entre
eux~?

\item Montrez qu'ils ne sont pas étrangers.

\item Commentez ce dernier résultat.

\een

\exot{Utilisation de la base 2 pour accélérer le calcul de $x^n$}

Pour calculer $x^{15}$, on fait 14 multiplications : $x\times
x\times \cdots\times x$. Si on décompose 15 en base 2, on peut
économiser des calculs
$$15=2^3+2^2+2^1+2^0$$
donc
$$x^{15}=\left((x^2)^2\right)^2\times (x^2)^2\times x^2\times x$$
On calcule $x^2$ puis $x^4=(x^2)^2$ puis $x^8=(x^4)^2$ et enfin
$$x^{15}=x\times x^2\times x^4\times x^8$$
soit 6 multiplications au lieu de 14.

Nous verrons bientôt que l'arithmétique est intimement liée à
l'algorithmique~: plus on économisera notre ordinateur, plus il
aura de <<~place~>> pour  résoudre notre problème.

Malgré tout, le calcul de $x^k$ en lui-même n'a que peu d'intérêt.
Ce qui nous sera plus utile, c'est de trouver un algorithme
calculant $rapidement$ $x^k$ modulo $n$. Il faut évidemment éviter
de calculer d'abord $x^k$ puis de regarder sa classe modulo $n$.
Il vaut  mieux travailler à chaque étape modulo $n$ pour ne pas
introduire des nombres gigantesques.

Voici un petit programme calculant $x^k$ modulo $n$ en s'inspirant
de la méthode vue plus haut.

\sm

\begin{algorithmic}

\STATE $X \leftarrow x$

\STATE $K \leftarrow k$
\STATE $N \leftarrow n$
\STATE $A \leftarrow 1$
\WHILE{K>0}\STATE
\IF{K est pair}\STATE $X\leftarrow X*X \text{ mod } N$  \STATE $K\leftarrow K/2$
\ELSE \STATE $A\leftarrow A*X \text{ mod } N$  \STATE $K\leftarrow K-1$
         \ENDIF
\ENDWHILE
\RETURN A
\end{algorithmic}
\sm

\been

\item Expliquez le fonctionnement de cet algorithme.
\item Faîtes pas à pas le calcul de $x^{15}$ tel que le ferait un
ordinateur obéissant à ce programme.
\item Proposer un programme s'adaptant à votre calculatrice ou à
Mupad.
\item Voici ce que ça donne sur XCAS.\label{rapide}

\begin{lstlisting}
Puissance(x,k,n):={
local X,K,A;
X:=x; K:=k; A:=1;
while(K>0){
if (irem(K,2)=0) {X:=X*X;K:=K/2;}
 else {A:=irem(A*X,n); K:=K-1;}
}
return(A);
}
\end{lstlisting} 

On appelle 

\begin{lstlisting}
Puissance(2412,1137,57)
\end{lstlisting}

et on obtient 18.




\Remarque{Bien sûr, XCAS fait ça tout seul grâce à \Coms{powmod}{a,n,p}...}


\een


\exot{Algorithme des différences} \been

\item Soit $a$ et $b$ deux entiers naturels non nuls. Montrez que $a\wedge b=b\wedge (a-b)$

\item Utilisez cette remarque pour déterminer un algorithme
calculant le PGCD de deux entiers naturels non
nuls\footnote{$a_0=max(a,b)$, $b_0=min(a,b)$ et
$b_{n+1}=min(a_n,b_n)$, $a_{n+1}=|a_n-b_n|$. Montrez que $(b_n)$
est nulle à partir d'un certain rang}. Testez-le sur votre machine
ou XCAS. \een


\exot{Algorithme d'Euclide}

Je vous rappelle que $a\wedge b$ est le dernier reste non nul
obtenu par l'algorithme d'Euclide. Déterminez un algorithme
donnant $a\wedge b$ à partir de l'algorithme d'Euclide. Vous
n'utiliserez que les opérations usuelles et la fonction <<~partie
entière~>> de votre calculatrice

Cet algorithme est-il plus efficace que celui de l'exrcice
précédent~?

\exot{Calcul des coefficients de Bézout par la méthode de Borel}

On suppose que $a$ et $b$ sont premiers entre eux et on cherche
deux entiers $u$ et $v$ vérifiant $au+bv=1$.

On s'amuse à calculer les multiples successifs de $a$ et leur
reste dans la division euclidienne par $b$.

En quoi ce petit jeu peut nous permettre d'obtenir $u$ et $v$~?
Peut-il y avoir problème~?

Déterminez un algorithme permettant de  calculer $u$ et $v$.


\exot{Algorithme d'Euclide étendu avec un tableur}

Comme nous l'avons vu en cours,  à chaque étape de l'algorithme
d'Euclide, nous pouvons exprimer le reste $r_n$ en fonction de $a$
et $b$ $$r_n=u_na+v_nb$$

\been
\item On part de $a=bq_1+r_2$, $r_0=a$, $r_1=b$. Sachant qu'à la
$p$-ième division on a
$$r_{p-1}=r_pq_p+r_{p+1}$$
montrez que $$\bsyc
u_{p+1}&=&u_{p-1}-q_{p}u_{p}\\v_{p+1}&=&v_{p-1}-q_{p}v_{p}\esyc$$
\item Déduisez-en un <<~programme~>> permettant de déterminer deux
entiers $u$ et $v$ tels que $$ua+vb=1$$ à l'aide d'un tableur.
\een

\exot{Le tableur décode complètement}

Nous allons résoudre l'exercice XXI à l'aide du tableur XCAS et de
deux de ses fonctions~: \bel

\item \texttt{asc(A1)} qui renvoie le code ASCII du premier
caractère écrit dans la cellule A1. Le code de A est 65, celui de
B est 66, ... , celui de Z est 90. Par commodité, nous
remplacerons l'espace par @ qui a pour code 64;

\item \texttt{char(A1)} qui renvoie le caractère associé au code
ASCII rentré en A1.

\el

Mettez au point un codeur où vous afficherez le message à coder
sur la première ligne, le message <<~chiffré~>> où vous aurez
remplacé chaque lettre par son code sur la deuxième ligne,
appliquez $f$ sur la troisième ligne en utilisant la fonction
\texttt{irem}, puis le message codé sur la quatrième ligne. 


\sm

De la même manière, mettez au point un décodeur et vérifiez les
résultats trouvés à l'exercice XXI.

%\break

%\section{LES SOLUTIONS MuPAD}{Les solutions MuPAD}

%\mup{pgcdDIFF:=proc(a,b) local A,B,aB,k; }\mup{begin}\mup{ A:=a;
%aB:=b; k:=0;}\mup{ while A<>B do
 %  B:=min(A,aB); A:=abs(A-aB);aB:=B;k:=k+1;
  %end\_while;}
%\mup{print("le PGCD de ". expr2text(a). " et  ".expr2text(b). " vaut ".expr2text(A)." trouvé en ".expr2text( k)
%." coups");
%end\_proc}
%\mup{pgcdDIFF(32,27);}
%\begin{center}

%{\textit le\ PGCD\ de} \,32 \,{\textit et\ } \,27 \,{\textit vaut} \,1
%\,{\textit trouvé\ en} \,9 \,{\textit coups}

%\end{center}


%\mup{Euclide:=proc(a,b) local A,B,R,aR,k;}\mup{begin}
%\mup{A:=a;B:=b;k:=0;}\mup{ while R<>0 do
%aR:=R;R:=A-B*floor(A/B);A:=B;B:=R;k:=k+1; end\_while;}
%\mup{ print("le PGCD de ".
%expr2text(a)."  et  ".expr2text( b)."  vaut ".expr2text(aR)." trouvé en ".expr2text( k)." coups");}

%\mup{end\_proc:}

%\mup{Euclide(32,27);}

%\begin{center}

%{\textit le\ PGCD\ de} \,32 \,{\textit et\ } \,27 \,{\textit vaut} \,1
%\,{\textit trouvé\ en} \,4 \,{\textit coups}

%\end{center}

%\mup{Borel:=proc(a,b) local A,B,R,k,v,u;}\mup{ A:=a;}
%\mup{for k from 1 to b-1 while R<>1  do A:=A*k;R:=A-b*floor(A/b); end\_for;}
%\mup{u:=A/a; v:=floor(A/b):}
%\mup{ if R=1 then print(expr2text(u)." $\times$ ".expr2text(a)."  $-$ ".
%expr2text(v)." $\times$ ".expr2text(b)."$=1$");}\mup{ else B:=b;
 %  for k from 1 to a-1 while R<>1  do
  % B:=B*k;R:=B-a*floor(B/a);
   %end\_for;}
  %\mup{ u:=floor(B/a);
  % v:=B/b:}
  % \mup{if R=1 then print(`-`,u,`x`,a,` +`, v,`x`,b,`=1`);}
  % \mup{else print("Cette méthode ne nous permet pas de conclure");end\_if;
%end\_if;
%end\_proc:}

%\mup{Borel(32,5);}

%\begin{center}

%{\textit Cette\ méthode\ ne\ nous\ permet\ pas\ de\ conclure}

%\end{center}

%\mup{Borel(11,32);}

%\begin{center}

%$-349\times 11+120\times 32=1$

%\end{center}


%\break

 \section{PPCM}

\ENC{\Thm}{L'ensemble des multiples strictement positifs communs à $a$ et $b$ admet un plus petit élément qu'on appelle \textbf{plus
petit multiple commun} de $a$ et $b$. On le note $PPCM(a,b)$ ou $a\vee b$}

Pour la preuve, on utilise la propriété des parties de $\bbn$ non vides et minorées.

\ENC{\Prop}{Soient $a$ et $b$ deux entiers positifs, $d$ leur pgcd. Il existe deux entiers $a'$ et $b'$ tels que $a=da'$ et $b=db'$. De
plus $a'$ et $b'$ sont premiers entre eux.}

En reprenant les divisions de l'algorithme d'Euclide, on prouve que $$ka\wedge kb=k(a\wedge b)$$ donc $a'\wedge
b'=\fr{a}{d}\wedge\fr{b}{d}=\fr{1}{d}d=1$

\ENC{\Thm}{$(a\wedge b)(a\vee b)=ab$}

On note $m=a\vee b$ et $d=a\wedge b$. Alors il existe deux entiers $a'$ et $b'$ premiers entre eux tels que $a=da'$ et $b=db'$. Soit $M$
un multiple commun de $a$ et $b$, alors il existe deux entiers $u$ et $v$ tels que $M=au=bv=da'u=db'v$. Or $d$ est non nul, donc
$$a'u=b'v$$ L'intérêt réside dans le fait que $a'$ et $b'$ sont premiers entre eux ( c'est pourquoi cette méthode est souvent utilisée en
exercice ). On peut donc utiliser le magique théorème de Gauss $a'$ divisant $b'v$, $a'$ divise $v$, donc il existe un entier $k$ tel que
$v=a'k$.

Tout ceci pour dire que tout multiple commun $M$ de $a$ et $b$ s'écrit \textit{nécessairement} sous la forme $M=db'a'k$.

\sm

\textit{Réciproquement}, tout nombre s'écrivant sous la forme $db'a'k$ avec $k$ un naturel quelconque est un multiple commun de $a$ et de
$b$ car $$db'a'k=b(a'k)=a(b'k)$$

Donc les multiples communs de $a$ et de $b$ SONT les multiples de $da'b'$. Le plus petit multiple de $da'b'$ étant $da'b'$ lui-même, on
en déduit finalement que $$a\vee b=da'b'$$ Ainsi $(a\wedge b)(a\vee b)=d\cdot da'b'=da'\cdot db'= ab$

\sm

\ENC{\Prop}{Si $k$ est un entier naturel, alors $ka\vee kb=k(a\vee b)$}

La démonstration utilise le théorème précédent et la propriété : $ka\wedge kb=k(a\wedge b)$.


\subsection*{Un exemple corrigé}

\textit{On cherche les entiers naturels non nuls $a$ et $b$ vérifiant $\bsys a^2-b^2=405\\3(a\vee b)=ab\esys$}

\sm

Il est assez naturel d'utiliser le théorème précédent : $(a\wedge b)(a\vee b)=ab$. Les entiers $a$ et $b$ étant non nuls, il en est de
même de leur ppcm, donc $a\wedge b=3$, ce qui nous permet d'introduire les entiers $a'$ et $b'$ vérifiant $a=3a'$ et $b=3b'$ : ils ont en
effet l'énorme avantage d'être premiers entre eux.

La première équation devient donc après simplification $a'^2-b'^2=45$, c'est à dire $$(a'-b')(a'+b')=45$$ En effet, les carrés nous
ennuient, mais on peut discuter sur le produit de deux entiers en parlant diviseur. Il existe en effet peu de diviseurs de 45 : 1, 3, 5,
9, 15 et 45 lui-même. De plus, $a'$ et $b'$ étant positifs, $a'-b'$ l'est aussi et $a'-b'\ie a'+b'$. Envisageons donc les différents cas
\bel
\item $a'-b'=1$ et $a'+b'=45$, alors $a'=23$ et $b'=22$ conviennent.
\item $a'-b'=3$ et $a'+b'=15$, alors $a'=9$ et $b'=6$ mais ils ne sont pas premiers entre eux.
\item $a'-b'=5$ et $a'+b'=9$, alors $a'=7$ et $b'=2$ conviennent.
\el

Il ne peut y avoir d'autres solutions et celles-ci conviennent, donc les couples solution sont
$(21,6)$ et $(69,66)$.





\exot{}

trouvez tous les entiers $a$ et $b$ tels que la différence entre leur PPCM et leur PGCD est égal à
187.

\exot{}
On cherche les entiers naturels non nuls $a$ et $b$ vérifiant $\bsys a\wedge b=18\\a\vee b=108\esys$

\section{Exercices de Bac}

\exot{}



Pour coder un message, on proc\`ede de la mani\`ere suivante : \`a chacune des 26 lettres de l'alphabet, on commence par associer un entier $n$ de l'ensemble \\
$\Omega = \{0~;~ 1~;~2~;~\ldots~;~24~;~ 25\}$ selon le tableau ci-dessous :

\medskip

\noindent \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}

\medskip

\noindent $a$ et $b$ \'etant deux entiers naturels donn\'es, on associe \`a tout entier $n$ de $\Omega$ le reste de la division euclidienne de $(an + b)$ par 26 ; ce reste est alors associ\'e \`a la lettre correspondante.\\
\emph{Exemple} :  pour coder la lettre P avec $a = 2$ et $b = 3$, on proc\`ede de la mani\`ere suivante :\\ \'etape 1 : on lui associe l'entier $n = 15$.\\
\'etape 2 : le reste de la division de $2 \times 15 + 3 = 33$ par 26 est $7$.\\
\'etape 3 : on associe $7$ \`a H. Donc P est cod\'e par la lettre H.
\begin{enumerate}
\item  Que dire alors du codage obtenu lorsque l'on prend $a =  0$ ?
\item  Montrer que les lettres A et C sont cod\'ees par la m\^eme lettre lorsque l'on choisit $a = 13$.
\item  \emph{Dans toute la suite de l'exercice}, on prend $a = 5$ et $b = 2$.
\begin{enumerate}
\item On consid\`ere deux lettres de l'alphabet associ\'ees respectivement aux entiers $n$ et $p$. Montrer, que si $5n + 2$ et $5p + 2$ ont le m\^eme reste dans la division par 26 alors $n - p$ est un multiple de $26$. En d\'eduire que $n = p$.
\item 	Coder le mot AMI.
\end{enumerate}
\item  On se propose de d\'ecoder l
a lettre E.
\begin{enumerate}
\item Montrer que d\'ecoder la lettre E revient \`a d\'eterminer l'\'el\'ement $n$ de $\Omega$ tel que $5n - 26y = 2$, o\`u $y$ est un entier.
\item  On consid\`ere l'\'equation $5x - 26y = 2$, avec $x$ et $y$ entiers relatifs.
\begin{enumerate}
\item  Donner une solution particuli\`ere de l'\'equation $5x - 26y = 2$.
\item   R\'esoudre alors l'\'equation $5x - 26y = 2$.
\item  En d\'eduire qu'il existe un unique couple $(x~;~y)$ solution de l'\'equation pr\'ec\'edente, avec $0 \leqslant x \leqslant  25$.
\end{enumerate}
\item  D\'ecoder alors la lettre E.
\end{enumerate}
\end{enumerate}


\pagebreak 


% \begin{enumerate}
% \item  Si  $a =  0,~an + b = b$, donc  toutes les lettres seront cod\'ees par la m\^eme lettre correspondant au reste de la division de $b$ par 26.
% \item  Si $a = 13$.\\
% A correspond \`a $0$, donc $an + b = b$. A est cod\'ee par la lettre qui correspond au reste de la division de $b$ par 26.\\
% C correspond \`a $2$,~donc $an + b = 26 \times 2 + b \equiv b \quad \mod 26$. Donc C est cod\'e de la m\^eme fa\c{c}on que A. 
% \item  \emph{Dans toute la suite de l'exercice}, on prend $a = 5$ et $b = 2$.
% \begin{enumerate}
% \item Si : $\left\{\begin{array}{l c l}
% 5n + 2 & \equiv& r \quad \mod 26\\
% 5p + 2 &\equiv & r \quad \mod 26\\
% \end{array}\right. $, alors par diff\'erence $5(n - p) \equiv 0 \quad \mod 26 \Rightarrow n - p \equiv 0 \quad \mod 26$ (car 5 est premier avec 26), donc finalement $n \equiv  p \quad \mod 26$. Or $m$ et $p$ sont inf\'erieurs \`a $26$. Conclusion $n = p$. 
% \item 	On a la suite :\\
% A $\to 0 \to 2 \to $ C\\
% M $\to 12 \to 10 \to $ K\\
% I $ \to 8 \to 16 \to $ Q.\\
% AMI est cod\'e \og CKQ \fg.
% \end{enumerate}
% \item  
% \begin{enumerate}
% \item D'apr\`es le tableau E correspond \`a $4$. Donc la lettre cod\'ee E correspond \`a un nombre $n$ tel que $5n + 2 \equiv 4 \quad 26 \iff 5n - 2 \equiv 0 \quad \mod 26 \iff 5n - 2 = 26y,~\text{avec} y \in \Z \iff 5n - 2 = 26y,~y \in \Z$.
% \item  On consid\`ere l'\'equation $5x - 26y = 2$, avec $x$ et $y$ entiers relatifs.
% \begin{enumerate}
% \item  Solution particuli\`ere de l'\'equation $5x - 26y = 2$. On a \\
% $26 = 5 \times 5 + 1 \iff 26 \times 1 - 5 \times 5 = 1 \iff 2 \times 26 - 10 \times 5 = 2 \iff 5 \times (- 10) - 26 \times (-2) = 2$. On a donc une solution : le couple $(-10~;~-2)$.
% \item   On a le syst\`eme :\\
% $\left\{\begin{array}{l c l}
% 5x - 26y&=&2\\
% 5 \times (- 10) - 26 \times (-2) &=& 2\\
% \end{array}\right.$, d'o\`u par diff\'erence : \\
% $5(x + 10) - 26(y + 2) = 0 \iff 5(x + 10) = 26(y + 2)$. 5 et 26 \'etant premiers entre eux, il en r\'esulte d'apr\`es le th\'eor\`eme de Gauss qu'il existe $k \in \Z$ tel que $x + 10 = 26k$, d'o\`u en substituant dans la derni\`ere \'egalit\'e : $y + 2 = 5k$. On obtient donc : les couples solutions sont les couples $(x~;~y)$ tels que $\left\{\begin{array}{l c l}
% x&=&26k - 10\\
% y&=& 5k - 2\\
% \end{array}\right.$
% \item   $0 \leqslant x \leqslant  25 \iff 0 \leqslant 26k - 10 \leqslant  25 \iff 10 \leqslant 26k \leqslant 35 \Rightarrow k = 1$. Finalement $x = 16$ et $y = 3$. Le seul couple solution est $(16~;~3)$.
% \end{enumerate}
% \item  La lettre  cod\'ee E correspond \`a $x= n = 16$. D'apr\`es le tableau c'est Q.
% \end{enumerate}
% \end{enumerate}



\exot{}
\begin{enumerate}
\item \begin{enumerate}
\item Déterminer suivant les valeurs de l'entier naturel non nul $n$ le reste dans la division euclidienne par $9$ de $7^n$.
\item Démontrer alors que $(2005)^{2005}\equiv 7~(9)$.
\end{enumerate}
\item \begin{enumerate}
\item Démontrer que pour tout entier naturel non nul $n~ :~ (10)^n\equiv 1~(9)$.
\item On désigne par $N$ un entier naturel écrit en base dix, on appelle $S$ la somme de ses chiffres.\\
Démontrer la relation suivante : $N\equiv S~(9)$.
\item En déduire 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ésigne 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émontrer la relation suivante : $A\equiv D~(9)$.
\item Sachant que $2 005 < 10\,000$, démontrer que $A$ s'écrit en numération décimale avec au plus $8\,020$ chiffres. En déduire que $B\leqslant 72\,180$.
\item Démontrer que $C\leqslant 45$.
\item En étudiant la liste des entiers inférieurs à $45$, déterminer un majorant de $D$ plus petit que $15$.
\item Démontrer que $D = 7$.
\end{enumerate}
\end{enumerate}






\exot{}
\noindent \textbf{Partie A}

Soit $N$ un entier naturel, impair non premier.

\noindent On suppose que $N =  a^2 - b^2$ où $a$ et $b$ sont deux entiers naturels.

\begin{enumerate}\item Montrer que $a$ et $b$ n'ont pas la même parit\'e. 

\item Montrer que $N$ peut s'écrire comme produit de deux entiers naturels $p$ et $q$.

\item Quelle est la parité de $p$ et de $q$ ?

\end{enumerate}

\vspace{0,5cm}

\noindent \textbf{Partie B}

On admet que 250\,507 n'est pas premier.

\noindent On se propose de chercher des couples d'entiers naturels $(a~;~ b)$ vérifiant la relation 

\[(\text{E})~ :\quad  a^2 -250\,507 =  b^2.\]

\begin{enumerate}\item Soit $X$ un entier naturel.

\begin{enumerate}\item Donner dans un tableau, les restes possibles de $X$ modulo 9 ; puis ceux de $X^2$ modulo 9.

\item Sachant que $a^2 - 250\,507 = b^2$,	déterminer les restes possibles modulo 9 de
$a^2 - 250\,507$ ; en déduire les restes possibles module 9 de $a^2$.

\item Montrer que les restes possibles modulo 9 de $a$ sont 1 et 8.

\end{enumerate}

\item Justifier que si le couple $(a~;~ b)$ vérifie la relation (E), alors $a \geqslant 501$. Montrer qu'il  n'existe pas de solution du type $(501~;~ b)$.

\item On suppose que le couple $(a~;~ b)$ vérifie la relation (E).

\begin{enumerate}\item Démontrer que $a$ est congru à 503 ou à 505 modulo 9.

\item Déterminer le plus petit entier naturel $k$ tel que le couple $(505+9k~;~b)$ soit solution
de (E), puis donner le couple solution correspondant.

\end{enumerate}

\end{enumerate}

\vspace{0,5cm}

\noindent \textbf{Partie C}

\begin{enumerate}\item Déduire des parties précédentes une écriture de 250\,507 en un produit deux facteurs. 

\item Les deux facteurs sont-ils premiers entre eux ? 

\item Cette écriture est-elle unique ?

\end{enumerate}







\exot{}
Dans cet exercice, on pourra utiliser le résultat suivant :

 «  Étant donnés deux entiers naturels $a$ et $b$ non nuls, si PGCD$(a~;~ b) =  1$ alors PGCD$(a^2~;~ b^2) = 1$ ».
 
\noindent Une suite $\left(\text{S}_{n}\right)$ est définie pour $n > 0$ par S$_{n}  = \displaystyle\sum_{p=1}^n p^3$. On se propose de calculer, pour tout entier naturel non nul $n$, le plus grand commun diviseur de S$_{n}$ et S$_{n+1}$.

\begin{enumerate}\item Démontrer que, pour tout $n > 0$, on a : S$_{n}  = \left(\cfrac{n(n+1)}{2}\right)^2$.

\item Étude du cas où $n$ est pair. Soit $k$ l'entier naturel non nul tel que $n = 2k$. 

\begin{enumerate}\item Démontrer que PGCD(S$_{2k}$~;~S$_{2k+1}) =  (2k+1)^2$PGCD$\left(k^2~;~(k+1)^2\right)$. 

\item Calculer PGCD $(k~;~ k + 1)$.

\item Calculer PGCD$\left(\text{S}_{2k}~;~ \text{S}_{2k+1}\right)$.

\end{enumerate}

\item Étude du cas où $n$ est impair. Soit $k$ l'entier naturel non nul tel que $n = 2k+ 1.$

\begin{enumerate}\item Démontrer que les entiers $2k + 1$ et $2k +3$ sont premiers entre eux.

\item Calculer PGCD$\left(\text{S}_{2k+1}~;~ \text{S}_{2k+2}\right)$.

\end{enumerate}

\item Déduire des questions précédentes qu'il existe une unique valeur de $n$, que l'on déterminera, pour laquelle S$_{n}$ et S$_{n+1}$ sont premiers entre eux.

\end{enumerate}








\exot{}
On considère la suite $\left(u_{n}\right)$ d'entiers naturels définie par

\[\left\{\begin{array}{l c l}
u_{0}& =& 14\\
u_{n+1}& =& 5 u_{n} - 6~~\text{pour tout entier naturel}~ n\\
\end{array}\right.\]

\begin{enumerate}\item Calculer $u_{1},~ u_{2},~ u_{3}$ et $u_{4}$.

Quelle conjecture peut-on émettre concernant les deux derniers chiffres de $u_{n}$ ?

\item Montrer que, pour tout entier naturel $n,~ u_{n+2}\equiv  u_{n}\quad  (\text{modulo}~ 4)$.

En déduire que pour tout entier naturel $k,~ u_{2k}\equiv  2 \quad  (\text{modulo}~ 4)$ et\\$u_{2k+1}\equiv 0  \quad  (\text{modulo}~ 4)$.

\begin{enumerate}\item Montrer par récurrence que, pour tout entier naturel $n,\\2u_{n} = 5^{n+2} 	+ 3$.

\item En déduire que, pour tout entier naturel $n,~ 2 u_{n} \equiv  28\quad  (\text{modulo}~100)$.

\end{enumerate}

\item Déterminer les deux derniers chiffres de l'écriture décimale de $u_{n}$ suivant les valeurs de $n$.

\item Montrer que le PGCD de deux termes consécutifs de la suite $\left(u_{n}\right)$ est constant. Préciser sa valeur.

\end{enumerate}



\exot{}
On appelle (E) l'ensemble des entiers naturels qui peuvent s'écrire sous 
la forme $9 + a^2$ où $a$ est un entier naturel non nul ; par exemple $10 = 9 + 
1^2~;~ 13 = 9 + 2^2$ etc.

On se propose dans cet exercice d'étudier l'existence d'éléments de (E) 
qui sont des puissances de 2, 3 ou 5.

\begin{enumerate} \item Étude de l'équation d'inconnue $a \quad :\quad a^2 + 9 = 2^n$ où $a 
\in \N,~n \in \N,~n \geqslant 4$.

\begin{enumerate} \item Montrer que si $a$ existe, $a$ est impair.

\item En raisonnant modulo 4, montrer que l'équation proposée n'a pas de 
solution.

\end{enumerate}

\item Étude de l'équation d'inconnue $a\quad :\quad a^2+9 = 3^n$ où $a \in 
\N,~n \in \N,~n \geqslant 3$.

\begin{enumerate} \item Montrer que si $n \geqslant 3,~ 3^n$ est congru à 1 ou à 3 
modulo 4.

\item Montrer que si $a$ existe, il est pair et en déduire
 que nécessairement $n$ est pair.

\item On pose $n = 2p$ où $p$ est un entier naturel, $p \geqslant 2$. Déduire d'une 
factorisation de $3^n - a^2$, que l'équation proposée n'a pas de solution.

\end{enumerate}

\item Étude de l'équation d'inconnue $a\quad :\quad  a^2 + 9 = 5^n$ où $a \in 
\N ,~n \in \N,~ n \geqslant 2$.

\begin{enumerate} \item En raisonnant modulo 3, montrer que l'équation n'a pas de 
solution si $n$ est impair.

\item On pose $n = 2p$, en s'inspirant de \textbf{2. c.} démontrer qu'il existe un
 unique entier naturel $a$ tel que $a^2 + 9$ soit une
puissance entière de 5.

\end{enumerate}

\end{enumerate}





\exot{}
Les suites d'entiers naturels $(x_n)$ et $(y_n)$ sont définies sur $\N$ 
par :

\[ \begin{array}{l}
x_0 = 3 \quad \text{et} \quad x_{n+1} = 2x_n - 1\\
y_0 = 1 \quad \text{et} \quad y_{n+1} = 2y_n + 3.
\end{array}\]


\begin{enumerate} \item Démontrer par recurrence que pour tout entier naturel 
$n,~ x_n = 2^{n+1} + 1$.

\item \begin{enumerate} \item Calculer le pgcd de $x_8$ et $x_9$, puis celui de 
$x_{2002}$ et $x_{2003}$. Que peut-on en déduire pour $x_8$ et $x_9$ d'une part, pour
 $x_{2002}$ et $x_{2003}$ d'autre part ?

\item $x_n$ et $x_{n+1}$ sont-ils premiers entre eux pour tout entier 
naturel $n$ ?

\end{enumerate}

\item \begin{enumerate} \item Démontrer que pour tout entier naturel $n,~ 2x_n - 
y_n = 5$.

\item Exprimer $y_n$ en fonction de $n$.

\item En utilisant les congruences modulo 5, étudier suivant les valeurs de
 l'entier naturel $p$ le reste de la division euclidienne de $2^p$ par 5.

\item On note $d_n$ le pgcd de $x_n$ et $y_n$ pour tout entier 
naturel $n$.

Démontrer que l'on a $d_n = 1$ ou $d_n = 5$ ; en déduire l'ensemble des entiers
 naturels $n$ tels que $x_n$ et $y_n$ soient premiers entre eux.
 
\end{enumerate}

\end{enumerate}



\exot{}
On considère deux entiers naturels, non nuls, $x$ et $y$ premiers entre eux.

\noindent On pose $S = x + y$ et $P =xy$.

\begin{enumerate}\item \begin{enumerate}\item Démontrer que $x$ et $S$ sont premiers entre eux, de même que $y$ et $S$.

\item En déduire que $S = x+y$ et $P =xy$ sont premiers entre eux.
	
\item Démontrer que les nombres $S$ et $P$ sont de parités différentes (l'un pair,
	l'autre impair).

\end{enumerate}

\item Déterminer les diviseurs positifs de 84 et les ranger par ordre croissant.

\item Trouver les nombres premiers entre eux $x$ et $y$ tels que : $SP = 
84$.

\item Déterminer les deux entiers naturels $a$ et $b$ vérifiant les conditions suivantes :

\[ \left\{ \begin{array}{l c l}
a + b &=& 84\\
ab& =& d^3 \\
\end{array}\right. ~\text{avec}~ d = \text{pgcd}(a ; b)\]

(On pourra poser $a = dx$ et $b = dy$ avec $x$ et $y$ premiers entre eux)

\end{enumerate}





\exot{}
\begin{enumerate} \item On considère l'équation (1) d'inconnue $(n,~m)$ 
élément de $\Z^2$ : 

\[ 11n - 24m = 1.\] 

\begin{enumerate} \item Justifier, à l'aide de l'énoncé d'un théorème, que cette 
équation admet au moins une solution. 

\item En utilisant l'algorithme d'Euclide, déterminer une 
solution particulière de l'équation (1). 

\item Déterminer l'ensemble des solutions de l'équation (1). 

\end{enumerate} 

\item recherche du P.G.C.D. de $10^{11} - 1$ et 
$10^{24} - 1$. 

\begin{enumerate} \item Justifier que 9 divise $10^{11} - 1$ et $10^{24} - 1$. 

\item $(n,~m)$ désignant un couple quelconque d'entiers naturels 
solutions de (1), montrer que l'on peut écrire 

\[\left(10^{11n} - 1\right) - 10\left(10^{24m} - 1\right) = 9.\] 

\item Montrer que $10^{11} - 1$ divise $10^{11n} - 1$. 

(on rappelle l'égalité $a^n - 1 = (a - 1)\left(a^{n-1} + a^{n-2} + 
\cdots + a^0\right)$, valable pour tout entier naturel $n$ non nul). 

Déduire de la question précédente l'existence de deux entiers $N$ et 
$M$ tels que : 

\[\left(10^{11} - 1\right)N - \left(10^{24} - 1\right)M = 9.\] 

\item Montrer que tout diviseur commun à $10^{24} - 1$ et $10^{11} - 
1$ divise 9. 

\item Déduire des questions précédentes le P.G.C.D. de $10^{24} - 1$ et $10^{11} - 
1$. 

\end{enumerate} 

\end{enumerate} 









\exot{}
Pour tout entier naturel n supérieur ou égal à 5, on considère les nombres 

\[a = n^3 - n^2 - 12n \qquad \text{et} \qquad b = 2n^2 - 7n - 4.\] 

\begin{enumerate}\item Montrer, après factorisation, que $a$ et $b$ sont des entiers naturels divisibles 
par $n-4$. 

\item On pose $\alpha = 2 n + 1$ et $\beta = n + 3$. On note $d$ le PGCD 
de $\alpha$ et $\beta$. 

\begin{enumerate}\item Établir une relation entre $\alpha$ et $\beta$ indépendante de $n$. 

\item Démontrer que $d$ est un diviseur de 5. 

\item Démontrer que les nombres $\alpha$ et $\beta$ sont multiples de 5 si et seulement 
si $n - 2$ est multiple de 5. 

\end{enumerate} 

\item Montrer que $2n + 1$ et $n$ sont premiers entre eux. 

\item \begin{enumerate}\item Déterminer, suivant les valeurs de $n$ et en fonction de $n$, le PGCD de $a$ 
et $b$. 

\item Vérifier les résultats obtenus dans les cas particuliers $n = 11$ 
et $n = 12$. 

\end{enumerate} 

\end{enumerate} 




\exot{}
\begin{enumerate}\item On cherche deux entiers relatifs $x$ et $y$ solutions de 
l'équation $(1)~ ax + by = 60 ~(a$ et $b$ entiers naturels donnés tels 
que $ab \neq 0$). On notera $d$ le plus grand commun diviseur de $a$ et $b$.\\ 
\begin{enumerate}\item On suppose que l'équation (1) a au moins une solution $(x_{0}~;~ 
y_{0})$. Montrer que $d$ divise 60.\\ 
\item On suppose que $d$ divise 60. Prouver qu'il existe alors au moins une 
solution $(x_{0}~;~ y_{0})$ à l'équation (1). 
\end{enumerate} 
\item On considère l'équation : 
$(2) \quad 24x + 36y = 60.\quad (x$ et $y$ entiers relatifs).\\ 
\begin{enumerate}\item Donner le PGCD de 24 et 36 en justifiant brièvement. Simplifier l'équation 
(2).\\ 
\item Trouver une solution évidente pour l'équation (2) et résoudre cette 
équation. On appellera $S$ l'ensemble des couples $(x~;~ y)$ solutions.\\ 
\item Énumérer tous les couples $(x~;~ y)$ solutions de (2) et tels que : 
\[- 10 \leqslant x \leqslant 10.\] 
Donner parmi eux, ceux pour lesquels $x$ et $y$ sont multiples de 5.\\ 
\item Dans le plan rapporté à un repère orthonormal (unité graphique : 1 cm), 
représenter l'ensemble $E$ des points $M$ de coordonnées $(x~ ;~ y)$ telles 
que : 
\[\left\{\begin{array}{l c l} 
x &=& 1 + 3t\\ 
y &= &1 - 2t 
\end{array}\right. t \in \R.\] 
\item Montrer que les points ayant pour coordonnées les solutions $(x; y)$ de 
l'équation (2) appartiennent à $E$.\\ 
Comment peut-on caractériser $S$ ? 
\end{enumerate} 
\end{enumerate} 



\exot{}
Dans tout l'exercice, $n$ désigne un entier naturel non nul.\\ 
\begin{enumerate}\item \begin{enumerate}\item Pour $1 \leqslant n \leqslant 6$, calculer 
les restes de la division euclidienne de $3n$ par 7.\\ 
\item Démontrer que, pour tout $n,~ 3^{ n + 6} - 3^n$ est divisible par 7.\\ 
En déduire que $3^n$ et $3^{ n + 6}$ ont le même reste dans la division par 7.\\ 
\item À l'aide des résultats précédents, calculer le reste de la division euclidienne 
de $3^{1\:000}$ par 7.\\ 
\item De manière générale, comment peut-on calculer le reste de la division euclidienne 
de $3^n$ par 7, pour $n$ quelconque ?\\ 
\item En déduire que, pour tout entier naturel $n, 3^n$ est premier avec 7. 
\end{enumerate} 
\item Soit $U_n = 3 + 3^2 + \cdots + 3^{n-1} = 
\displaystyle\sum_{i=0}^{i=n-1} 
3^i$, où $n$ est un entier naturel supérieur ou égal à 2.\\ 
\begin{enumerate}\item Montrer que si $U^n$ est divisible par 7, alors $3^n - 1$ est divisible par 7. \\ 
\item Réciproquement, montrer que si $3^n - 1$ est divisible par 7, alors 
$U_n$ est divisible par 7.\\ 
En déduire les valeurs de $n$ telles que $U_n$ soit divisible par 7. 
\end{enumerate} 
\end{enumerate} 






\exot{}
On considère l'équation
\[(1)\qquad  :\quad  20b - 9c = 2.\]
où les inconnues $b$ et $c$ appartiennent à l'ensemble $\Z$ des 
nombres entiers relatifs.\\
\begin{enumerate}\item \begin{enumerate}\item Montrer que si le 
couple $(b_{0}~;~ c_{0}$ d'entiers relatifs est une solution de l'équation
(1), alors $c_{0}$ est un multiple de 2.\\
\item On désigne par $d$ le p.g.c.d. de $|b_{0}|$ et $|c_{0}|$. Quelles sont 
les valeurs possibles de $d$ ?\\
\end{enumerate}
\item Déterminer une solution particulière de l'équation (1), 
puis déterminer l'ensemble des solutions de cette équation.\\
\item Déterminer l'ensemble des solutions $(b~;~ c)$ de (1) 
telles que p.g.c.d.$(b~;~ c) = 2$.\\
\item Soit $r$ un nombre entier naturel supérieur ou égal à 2. 
Le nombre entier naturel $P$, déterminé par \[P = \alpha_{n}r^n + 
\alpha_{n-1}r^{n-1} + ... + \alpha_{1}r  + \alpha_{0}\] , où
$\alpha_{n},~\alpha_{n-1},~ ... , \alpha_{1},~ \alpha_{0}$ sont des nombres
entiers naturels vérifiant 
$0 < \alpha_{n} < r,~ 0 \leqslant \alpha_{n-1} < r, ...,~ 0 \leqslant,~ \alpha_{0} < r$
est noté 
$\overline{\alpha_{n}\alpha_{n-1}\ldots\alpha_{1}\alpha_{0}}^{(r)}$ ;  
cette écriture est dite « écriture de $P$ en base $r$ ». Soit $P$ un nombre entier 
naturel s'écrivant $\overline{ca5}^{(6)}$ et $\overline{bbaa}^{(4)}$  (en base six
et en base quatre respectivement).\\
Montrer que $a + 5$ est un multiple de 4 et en déduire les  valeurs 
de $a$, puis de $b$ et de $c$.\\
Donner l'écriture de $P$ dans le système décimal.
\end{enumerate}







\exot{}
\begin{enumerate} \item On considère l'équation $(E)~:~8x + 5y = 1$,~où $(x~;~y)$ est un 
couple de nombres entiers relatifs. 

\begin{enumerate} \item Donner une solution particulière de l'équation $(E)$. 

\item Résoudre l'équation $(E)$. 

\end{enumerate} 

\item Soit $N$ un nombre naturel tel qu'il existe un couple $(a~;~b)$ de 
nombres entiers vérifiant : $\left\{ \begin{array}{l c l} 
N& =& 8a + 1\\ 
N &=& 5b + 2.\\ 
\end{array}\right.$ 

\begin{enumerate} \item Montrer que le couple $(a~;~b)$ est solution de $(E)$. 

\item Quel est le reste, dans la division de $N$ par 40 ? 

\end{enumerate} 

\item \begin{enumerate} \item Résoudre l'équation $8x + 5 y = 100$, où $(x~;~ y)$ est un couple de 
nombres entiers relatifs. 

\item Au VIII$\textsuperscript{e}$ siècle, un groupe composé d'hommes et de femmes a 
dépensé 100 pièces de monnaie dans une auberge. Les hommes ont dépensé 8 pièces 
chacun et les femmes 5 pièces chacune. Combien pouvait-il y avoir d'hommes et de 
femmes dans le groupe ? 

\end{enumerate} 

\end{enumerate} 



\exot{}


Dans tout l'exercice $x$ et $y$ désignent des entiers naturels non nuls vérifiant 
$x < y$. 

S est l'ensemble des couples $(x, y)$ tels que PGCD$(x,~y) = y - x$. 

\begin{enumerate} \item \begin{enumerate} \item Calculer le PGCD(363,~ 484). 

\item Le couple (363, 484) appartient-il à S ? 

\end{enumerate} 

\item Soit $n$ un entier naturel non nul ; le couple $(n,~ n + 1)$ appartient-il à S ? 

Justifier votre réponse. 

\item \begin{enumerate} \item Montrer que $(x,~y)$ appartient à S si et seulement si il existe un 
entier naturel $k$ non nul tel que $x = k(y-x)$ et $y = (k+1)(y-x)$. 

\item En déduire que pour tout couple $(x,~ y)$ de S on a : 

PPCM $(x,~y) = k(k+1)(y-x).$ 

\end{enumerate} 

\item \begin{enumerate} \item Déterminer l'ensemble des entiers naturels diviseurs de 228. 

\item En déduire l'ensemble des couples $(x,~ y)$ de S tels que PPCM $(x,~ 
y) = 228$. 

\end{enumerate} 

\end{enumerate} 


\end{document}