<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\section{Principe de rÃ©currence }

Pour dÃ©montrer par \emph{rÃ©currence}
\index{rÃ©currence!restreinte} 
qu'une propriÃ©tÃ© $P(n)$ est vraie quel que soit l'entier $n \ge n_0$, 
on procÃ¨de en deux Ã©tapes:
\begin{enumerate}
\item on vÃ©rifie que $P(n_0)$ est vraie;
\item\label{itm:2} on suppose que $P(n)$ est vraie pour un certain entier $n \ge n_0$, 
  c'est l'hypothÃ¨se de rÃ©currence, et on dÃ©montre que $P(n+1)$ est vraie.
\end{enumerate}  
Le \emph{principe de rÃ©currence} dit alors que $P(n)$ est vraie quel que soit 
l'entier $n \ge n_0$. 
% Une variante consiste Ã&nbsp; remplacer l'Ã©tape~\ref{itm:2} par 
% \begin{enumerate}
% \item[2 bis.] on suppose que $P(k)$ est vraie pour tout $k$ compris entre 
% $n_0$ et $n$, et on dÃ©montre que $P(n+1)$ est vraie.
% \end{enumerate}
% Ceci se dÃ©duit du fait que $\N$ est un ensemble complÃ¨tement ordonnÃ©. 


\begin{Exo}
\begin{enumerate}
\item Calculez 1, 1+3, 1+3+5, et 1+3+5+7.
\item A quoi $1+3+5+7+...+(2n-1)+(2n+1)$ semble-t-il Ãªtre Ã©gal (en fonction de $n$) ?
\item DÃ©montrer par rÃ©currence que l'on a effectivement l'Ã©galitÃ©.
\end{enumerate}
\end{Exo}


% \begin{Exo}
% On souhaite calculer $S_1(n) = 1+2+...+n$.
% \begin{enumerate}
% \item Cherchez un bon candidat $S_1(n)$ pour cette formule.
% \begin{itemize}
% \item On pourra chercher un lien logique entre $S_1(1), S_1(2), S_1(3), S_1(4), ...$
% \item On pourra aussi faire le lien avec les suites arithmÃ©tiques.
% \item Ou encore, retrouver la mÃ©thode de Gauss : $S = 1+2+...+n$, et $S = n+(n-1)+...+2+1$. Si on somme ces deux expressions...
% \end{itemize}
% \item Prouvez, par rÃ©currence, que la somme est bien Ã©gale Ã&nbsp; ce candidat.
% \item Quelle est la \og forme \fg{} de ce candidat (fonction tangente ? polynÃ´me ?) 
% \end{enumerate}
% \end{Exo}


\begin{Exo}
On souhaite calculer $S_2(n) = 1^2+2^2+...+n^2$.
\begin{enumerate}
\item Cherchez un bon candidat $S_2(n)$ pour cette formule.
\begin{itemize}
\item On pourra chercher un lien logique entre $S_2(1), S_2(2), S_2(3), S_2(4), ...$
\item Ou encore, 
\begin{itemize}
\item Regardez la forme de $S_0(n) = 1^0+2^0+...+n^0$, et de $S_1(n) = 1^1+2^1+...+n^1$
\item Extrapolez la formule pour $S_2(n)$. On pourra imaginer que $S_2(n)$ est toujours un polynÃ´me en $n$. Quel serait son degrÃ© le plus probable ? Quelle en serait donc la forme ? On aura Ã&nbsp; dÃ©terminer les coefficients intervenant dans ce polynÃ´me. Pour ce faire, il suffit de considÃ©rer que cette formule doit convenir pour n=1, 2, etc.
\end{itemize}
\end{itemize}
\item DÃ©montrez, par rÃ©currence, que l'on a bien Ã©galitÃ© entre $1^2+2^2+...+n^2$ et votre candidat.
\end{enumerate}
\end{Exo}

% \begin{Exo}
% Poursuivre le raisonnement pour $S_3(n)$. Cette mÃ©thode permet-elle de calculer $S_k(n)$ pour tout $k$ et $n$ dans $\N$?
% \end{Exo}


\begin{Exo}
Soit la suite $(U_n)_{n\in \N}$ dÃ©finie par $U_n = 3^{2n+1} + 2^{n+2} $.
\begin{enumerate}
\item Calculer $U_0$, $U_1$ et $U_2$. Remarquer que ce sont tous 
des multiples de $7$.
\item Montrer que $U_{n+1} = 7 \times 3^{2n+1} + 2 U_n$.
\item Montrer que $7$ est un multiple de $U_n$ pour tout entier naturel $n$.
\end{enumerate}
\end{Exo}



\begin{Exo}
Montrer que pour tout entier naturel $n$, 3 divise $4^n -1$.
\end{Exo}

\begin{Exo}
Soit $(u_n)_{n \in \N}$ une suite rÃ©elle telle que pour tout $ n \in \N$,
$$u_{n+2}-5u_{n+1}+6u_n = 0$$
Montrez qu'il existe $\alpha, \beta \in \N$ tels quel pour tout $ n \in \N, u_n = \alpha 3^n + \beta 2^n$.
\end{Exo}

\begin{Exo}
Montrer que $\forall m,n \in \N^*, \forall r \in \N, m^{2r+1}+n^{2r+1}$ est divisible par $m+n$.
\end{Exo}




\section{Nombres premiers}

\begin{Def}[Multiple, diviseur]
Si un entier $n$ peut s'Ã©crire sous la forme $n=pq$, oÃ¹ $p$
et $q$ sont des entiers, on dit que $n$ est un \emph{multiple} \index{multiple}
de $p$ et que $p$ est un \emph{diviseur}\index{diviseur} de $n$.
On Ã©crit aussi $p \mid n$ pour $p$ divise $n$.
\end{Def}

\begin{Exo}
 Soit $m = 2^3 * 5 * 7^2 * 13^3$. Combien le nombre $m$ a-t-il de diviseurs naturels ?
\end{Exo}

%\noindent RÃ©ponse : (3+1)*(1+1)*(2+1)*(3+1)=96.

\begin{Def}[Nombre premier]
Un \emph{nombre premier}\index{nombre!premier} est un nombre entier strictement supÃ©rieur Ã&nbsp; 1 qui n'est divisible que par 1 et par lui-mÃªme.
\end{Def}


\begin{Exo}
Ainsi, le plus petit nombre premier (et le seul qui soit pair) est 2.
\end{Exo}






\begin{Rem}
 Le problÃ¨me de la primalitÃ© d'un nombre (trÃ¨s grand, Ã©videmment) est difficile.
\end{Rem}





%\subsection{DÃ©composition en facteurs premiers}

\begin{Def}[DÃ©composition en facteurs premiers]
L'Ã©criture d'un entier $n$ sous la forme $n=a^{\alpha}b^{\beta}c^{\gamma}\ldots$, oÃ¹ \begin{itemize}
\item $a$, $b$, $c$, \ldots  sont des nombres premiers distincts 
deux Ã&nbsp; deux tels que $a &lt; b &lt; c &lt;\ldots$;
\item les exposants $\alpha$, $\beta$, $\gamma$ sont des entiers naturels 
  non nuls;
\end{itemize}
\noindent s'appelle la \emph{dÃ©composition en facteurs premiers} \index{dÃ©composition en facteurs premiers} de $n$.

On dit que les exposants $\alpha$, $\beta$, $\gamma$, \ldots sont les ordres de multiplicitÃ© des diviseurs $a$, $b$, $c$, \ldots
\end{Def}



\begin{Th}
La dÃ©composition d'un entier en ses facteurs premiers est unique.
\end{Th}


\begin{Exo}
 \'Ecrivez les nombres 3850 et 1911 sous forme de produits de nombres premiers.
\end{Exo}




%\noindent RÃ©ponses : $2*5^2*7*11$ et $3*7^2*13$.


\begin{Th}
Il existe une infinitÃ© de nombres premiers.
\end{Th}

\begin{Exo}[Nombres premiers en quantitÃ© infinie]
Supposons comme hypothÃ¨se que l'ensemble des nombres premiers $\{ p_1, p_2, p_3 \ldots p_{n-1}, p_n \}$ est de cardinalitÃ© finie $n$.
On construit le nombre $N =  p_1. p_2. p_3. \ldots .p_{n-1}. p_n +1$.
\begin{enumerate}
\item Montrer que d'aprÃ¨s l'hypothÃ¨se, il existe un nombre premier $q$ tel que 
  $N$ est un multiple de $q$.
\item Montrer cependant que $N$ n'est pas un multiple de $p_1$. Idem pour $p_2$, \ldots $p_n$.
\item En dÃ©duire que $q$ est un nombre premier diffÃ©rent de $p_1$, de $p_2$, \ldots de $p_n$. 
\item En dÃ©duire une contradiction dans l'hypothÃ¨se.
\end{enumerate}
\end{Exo}



%\subsection{Relation de divisibilitÃ©}

% Dans le chapitre sur les relations entre ensembles,
% on a vu que la relation binaire de \og divisibilitÃ©\fg{} (notÃ©e $\mid$) 
% dÃ©finie dans $\Net$.
% est une relation d'ordre.
% Or 6 ne divise pas 14 et 14 ne divise pas 6.
% Ces deux entiers ne sont donc pas comparables.
% Cet ordre n'est donc que partiel.

% Cependant 2 divise 6 et 14. C'est le plus grand des minorants de 6 et 14
% selon cette relation. C'est donc la borne infÃ©rieure.
% De mÃªme  42 est divisible par 6 et 14 aussi. 
% C'est le plus petit des majorants de 6 et 14
% selon cette relation. C'est donc la borne supÃ©rieure.
% Chaque couple d'entiers a donc  une borne infÃ©rieure et une borne supÃ©rieure. 



\begin{Def}[PGCD, PPCM]
Soient $a$ et $b$ deux entiers naturels strictement positifs. 
\begin{itemize}
\item L'ensemble des diviseurs communs Ã&nbsp; 
$a$ et $b$ admet un plus grand Ã©lÃ©ment $d$, 
le \emph{plus grand commun diviseur (PGCD)}\index{plus grand commun diviseur}\index{PGCD}
de ces entiers. On le note  $\textit{PGCD}(a,b)$. 
\item L'ensemble des multiples strictement positifs
  communs Ã&nbsp; $a$ et $b$ admet un plus petit Ã©lÃ©ment $m$, 
le \emph{plus petit commun multiple (PPCM)} \index{PPCM} \index{plus petit commun multiple} de ces deux entiers.
On le note $\textit{PPCM}(a,b)$.
\end{itemize}
Pour $a$ et $b$ dans $\N$, 
$\textit{PGCD}(a,b)$ et 
$\textit{PPCM}(a,b)$ et 
sont respectivement notÃ©s $a\et b$ et $a\ou b$.
\end{Def}

\begin{Def}[Nombres premiers entre eux]
Deux nombres entiers strictement positifs $a$ et $b$ sont dits \emph{premiers entre eux} lorsque $a\et b=1$. 
\end{Def}




\begin{Exo}[Nombres de Fermat]
Pour $p \in \N$, on appelle nombres de Fermat les nombres de la forme 
$F_p = 2^{2^p}+1$.
\begin{enumerate}
\item Question prÃ©liminaire: montrer que les deux Ã©galitÃ©s suivantes sont Ã©tablies:
\begin{enumerate}
\item $x^n- 1 = (x-1)(x^{n-1}+x^{n-2}+\ldots+ x + 1)$  pour tout entier naturel $n$ strictement positif.
\item $x^n+ 1 = (x+1)(x^{n-1}-x^{n-2}+\ldots \pm x \mp 1)$  pour tout entier naturel $n$ impair
\end{enumerate}

\item Montrer que, 
  pour que $2^n+1$ soit premier, il est nÃ©cessaire 
  que $n$ soit une puissance de 2. 

\item Pour montrer que ce n'est pas suffisant, vÃ©rifier que $F_5$ est 
  divisible par 641.

\item Montrer que, pour $k\geqslant 1$, $F_p$ divise $F_{p+k}-2$.

\item En dÃ©duire que $F_p$ et $F_{p+k}$ sont premiers entre eux.


\end{enumerate}
\end{Exo}



\section{Algorithmes d'Euclide et applications}\index{algorithme!d'Euclide}

Par dÃ©finition, le PGCD de $a$ non nul avec
0 est $a$ (dÃ©fintion raisonnable, car 0
est divisible par tout entier non nul, donc par $a$, qui l'est aussi par $a$) 
et enfin le PGCD de 0 et de 0 n'est pas
dÃ©fini.



L'algorithme consistant Ã&nbsp; comparer les dÃ©compositions en facteurs
premiers n'est pas efficace.
La dÃ©couverte de diviseurs de nombres
trÃ¨s grands est un problÃ¨me difficile dont nous reparlerons plus loin.







On se limite ici au cas de deux entiers $a$ et $b$ strictement positifs. Supposons par exemple $a&gt;b$

\begin{enumerate}
\item La division euclidienne de $a$ par $b$ peut s'Ã©crire $a=bq+r$ avec $0\infeg r&lt;b$.

\item Montrons que \og $d$ est un diviseur commun Ã&nbsp; $a$ et $b$ \fg{}
  est Ã©quivalent Ã&nbsp;  \og $d$ est un diviseur commun Ã&nbsp; $b$ et $r$ \fg{}.
\begin{itemize}
\item  Soit $d$ un diviseur commun Ã&nbsp; $a$ et $b$, qui peuvent alors s'Ã©crire $a=da'$ et $b=db'$. L'Ã©galitÃ© $a=bq+r$ devient $da'=db'q+r$ ou encore $r=d(a'-b'q)$, donc $d$ est aussi un diviseur commun Ã&nbsp; $b$ et $r$.

\item RÃ©ciproquement, soit $d$ un diviseur commun Ã&nbsp; $b$ et $r$, qui peuvent alors s'Ã©crire $b=db'$ et $r=dr'$ et l'Ã©galitÃ© $a=bq+r$ devient $a=d(b'q+r')$.
Donc $d$ est un diviseur commun Ã&nbsp; $a$ et $b$.
\end{itemize}

Ainsi, les ensembles des diviseurs communs Ã&nbsp; $a$ et $b$ 
d'une part et Ã&nbsp; $b$ et $r$ d'autre part sont identiques.
En particulier $a\et b=b\et r$.

\item Si $r=0$ on a $a\et b= b\et 0$ qui est Ã©gal Ã&nbsp; $b$.

\item Sinon,  $r$ est diffÃ©rent de $0$ et on peut donc effectuer la
  division euclidienne de $b$ par $r$, qui donne un reste $r_{1}$, 
  tel que $0 \le r_{1}&lt;r$ et $b\et r=r\et r_{1}$.

\item Cet algorithme est itÃ©rÃ© jusqu'Ã&nbsp; l'obtention d'un reste nul, ce qui se produit obligatoirement puisqu'il s'agit d'entiers et que la suite des restes ainsi construite est strictement dÃ©croissante.
  Le PGCD est alors l'avant-dernier reste (le dernier non nul).
\end{enumerate}


\begin{Rem}
Cet algorithme permet donc d'obtenir le PGCD de deux nombres sans connaÃ®tre leurs dÃ©compositions en facteurs premiers.
\end{Rem}

\begin{Exo}
DÃ©terminer $154 \land 35$ par l'algorithme d'Euclide.
\end{Exo}


Voici sa programmation itÃ©rative en Python:

\begin{scriptsize}
\begin{verbatim}
def pgcd_euclide(a,b) :
    assert a&gt;b and b &gt;=0
    while b != 0 :
        r = a%b
        a = b
        b = r 
    return a
\end{verbatim}
\end{scriptsize}
\bigskip

\begin{Exo}[Application de l'algorithme d'Euclide]
Si $p$ est un nombre premier, et $n$ un entier avec $n \ge 2$, on note 
$a=p^n+1$ et  
$b=p^n-1$.
\begin{enumerate}
\item On suppose que $p$ est Ã©gal Ã&nbsp; 2. 
\begin{enumerate}
\item Montrer que $2^n -1 = 2 \times (2^{n-1} -1) +1$ pour $n \ge 2$.
\item Calculer $d = a \et b$ au moyen de l'algorithme d'Euclide.
\item DÃ©terminer un couple d'entiers relatifs $(u,v)$ tels que $ua + vb=d$.
\end{enumerate}
\item On suppose maintenant que $p$ est diffÃ©rent de 2. 
 \begin{enumerate}
\item Montrer que $a$ et $b$ sont pairs et poser $a=2A$ et $b=2B$. 
\item Calculer $A-B$. En dÃ©duire la valeur $d$ de $a \et b$.
\item DÃ©terminer un  couple d'entiers relatifs $(u,v)$ tels que $ua + vb=d$.
\end{enumerate}
\end{enumerate}
\end{Exo}

% \begin{Exo}
% Comme $48=2^43$ et que $56=2^37$, on voit aisÃ©ment que $48\et 56=2^3$.
% \end{Exo}

% \begin{Exo}
%  Calculez $102 \ou 138$.
% \end{Exo}

% \noindent RÃ©ponse : 2346.

% \begin{Th}
% $\Net$ est un treillis pour la divisibilitÃ©. 

% On peut de plus montrer que :

% \begin{itemize}
%  \item ce treillis est distributif, c'est-Ã&nbsp;-dire que $x\ou(y\et z)=(x\ou y)\et(x\ou z)$ et que $x\et(y\ou z)=(x\et y)\ou(x\et z)$,
%  \item il admet un Ã©lÃ©ment minimum (1), mais pas d'Ã©lÃ©ment maximum,
%  \item les nombres premiers sont les Ã©lÃ©ments minimaux de ($\Net\moins\{1\}$).
% \end{itemize}
% \end{Th}




% \begin{Exo}
%  Soient $a,b,c,d$ des entiers naturels non nuls tels que $ad=bc$.

% Prouvez que si $a$ et $b$ sont premiers entre eux, alors $b|d$
% \end{Exo}

% \noindent RÃ©ponse : En se plongeant dans le calcul modulo $b$, on a : ad = 0.

% Comme $a$ et $b$ sont premiers entre eux, $a$ est inversible, et donc $d=0$.

% On en dÃ©duit que $d$ est un multiple de $b$.





\section{Division euclidienne dans $\Z$ et applications}

L'ensemble habituellement notÃ© $\Z$ des entiers relatifs
est obtenu Ã&nbsp; partir de $\N$ par le procÃ©dÃ© de symÃ©trisation pour l'addition: 
cela consiste Ã&nbsp; introduire les entiers strictement nÃ©gatifs comme
opposÃ©s des positifs correspondants, par $n+(-n)=0$.


On se donne deux entiers relatifs $a$ et $b$, $b$ non nul.

\begin{Th}
Il existe un et un seul couple d'entiers relatifs $q$ et $r$ qui
vÃ©rifient la relation suivante : $a=bq+r$ , avec $0\leqslant r&lt;|b|$. 
\end{Th}


\begin{Def}[Division euclidienne]
Obtenir les valeurs de $q$ et de $r$, c'est effectuer la \emph{division
euclidienne}\index{division euclidienne} de $a$ par $b$.
Le nombre $q$ est appelÃ© \emph{quotient}\index{quotient}, et 
le nombre $r$ est appelÃ© \index{reste}\emph{reste} 
(dans la division euclidienne).
Lorsque $r$ est nul, $a$ est dit \emph{divisible} par $b$, ou $b$ est un \emph{diviseur} de $a$.
\end{Def}


\begin{Ex}
Tout nombre non nul est au moins divisible par 1 et par lui-mÃªme ($a=a\times 1+0$). 
\end{Ex}

\begin{Ex}
0 est divisible par tout nombre entier non nul $(0 = 0 \times b + 0 )$. 
\end{Ex}


\begin{Exo}
Quels sont le quotient et le reste de la division euclidienne de $m$ par $n$ dans le cas oÃ¹ :
\begin{enumerate}
 \item $m = -38$ et $n=6$,
\item $m=165$ et $n=-14$.
\end{enumerate}
\end{Exo}



\begin{Exo}
On se place dans l'ensemble $\N$.
\begin{enumerate}
\item Trouver les restes dans la division par 5 du carrÃ© d'un entier.
\item Trouver les restes dans la division par 8 du carrÃ© d'un entier impair.
\item Trouver les restes dans la division par $11$ de $37^n$ (pour $n\in\Net$).
\item Montrer que $10^n(9n-1)+1$ est divisible par 9.
\end{enumerate}
\end{Exo}




\section{ThÃ©orÃ¨me de BÃ©zout}


On considÃ¨re deux nombres entiers strictement positifs $a$ et $b$.

\begin{Th}[ThÃ©orÃ¨me de BÃ©zout]
\index{thÃ©orÃ¨me!de BÃ©zout}
Il existe un couple d'entiers $u$ et $v$ tels que $au-bv=d$, oÃ¹ $d$ est le PGCD de $a$ et de $b$. 
\end{Th}

\begin{Proof}
On peut se ramener au cas oÃ¹ $a \et b=1$.

En effet, si $d&gt;1$, on peut Ã©crire $a=a'd$ et $b=b'd$ avec $a' \et b'=1$; si le thÃ©orÃ¨me est Ã©tabli dans le cas du PGCD Ã©gal Ã&nbsp; $1$, on peut affirmer l'existence de $u$ et de $v$ tels que $a'u-b'v=1$; en multipliant les deux membres de cette Ã©galitÃ© par $d$, on obtient $a'du-b'dv=d$,
soit $au-bv=d$.

Il suffit donc d'Ã©tablir le thÃ©orÃ¨me dans le cas oÃ¹ $d=1$ ($a$ et $b$ premiers entre eux). PlaÃ§ons nous dans $(\Z/b\Z)^*$ et considÃ©rons l'application de cet ensemble dans lui-mÃªme dÃ©finie par $x \fc ax$. Essayons de rÃ©soudre $ax=ax'$, soit $a(x-x')=0$, soit encore $a(x-x') \equiv 0[b]$, ou finalement $a(x-x')=kb$, avec $k \in \Z$.

Comme $a\et b=1$, $a$ ne divise pas $b$, donc divise $k$; on peut Ã©crire $k=k'a$, il reste $x-x'=k'b$, donc $x \equiv x'[b]$, donc $x=x'$; finalement $ax=ax' \Imp x=x'$, donc l'application envisagÃ©e est injective; comme il s'agit d'un ensemble fini, elle est Ã©videmment aussi surjective, donc il existe $u$ tel que $au=1$, ce qui s'Ã©crit encore $au \equiv 1[b]$, ou encore $au=bv+1$, finalement $au-bv=1$. 
\end{Proof}



\begin{Rem}
Ce couple n'est pas unique.
\begin{Proof}
En effet, si $(u,v)$ est un couple de BÃ©zout pour $(a,b)$, donc tel que $au-bv=d$, oÃ¹ $d=a\et b$, alors, pout tout $k$ dans $\Z$, $a(u+kb)-b(v+ka)= au-bv+kab-kab=au-bv=d$ aussi. 
\end{Proof}
\end{Rem}



\begin{Exo}
Montrez que, si $m$ est multiple de deux nombres premiers entre eux $a$ et $b$, alors $m$ est multiple de $ab$. 
\end{Exo}

% \noindent RÃ©ponse : $1 = aa'+bb'$, donc $m = maa'+mbb'$. Or $m=ax=by$, donc $m = ab(ya'+xb')$.



\begin{Exo}
\begin{enumerate}
\item Montrez que, si on divise deux entiers naturels $a$ et $b$ par leur pgcd, alors les quotients obtenus sont premiers entre eux.

\item RÃ©ciproquement, montrer que, si les quotients obtenus en divisant $a$ et $b$ par un diviseur commun $d$ sont premiers entre eux, alors $d=\textit{PGCD}(a,b)$.
\end{enumerate}
\end{Exo}

% \noindent RÃ©ponse : Soit $d = \textit{PGCD}(a,b)$, et $q_1$ et $q_2$ les quotients de $a$ et $b$ par $d$. Alors $d = aa'+bb' = d q_1 a' + d q_2 b'$. Donc $1 = q_1 a' + q_2 b'$ : $q_1$ et $q_2$ sont premiers entre eux. La rÃ©ciproque est du mÃªme genre.

\subsection{Algorithme d'Euclide gÃ©nÃ©ralisÃ©}



Pour deux entiers positifs $a$ et $b$, on a vu que l'algorithme d'Euclide s'Ã©crit : $a \et b = b \et r$, oÃ¹ $r$ est le reste dans la division euclidienne de $a$ par $b$.


En supposant $a&gt;b$, si on pose $a=r_0$ et $b=r_1$, on dÃ©finit une famille finie $(r_0,r_1,\ldots,r_k,r_{k+1})$ par $r_i=q_{i+1}r_{i+1}+r_{i+2}$ (c'est-Ã&nbsp;-dire que $r_{i+2}$ est le reste dans la division euclidienne de $r_i$ par $r_{i+1}$).


\noindent Cette famille...
\begin{itemize}
\item est strictement dÃ©croissante,
\item est telle que $r_{k+1}=0$,
\item vÃ©rifie $r_0 \et r_1 = r_1 \et r_2= \ldots = r_{k-1} \et r_k = r_k \et r_{k+1} = r_k \et 0 = r_k$.
\end{itemize}

\bigskip

On remarque que $r_{k-1}$ est un multiple de $r_k$, puisque la division euclidienne de $r_{k-1}$ par $r_k$ s'Ã©crit $r_{k-1}=q_kr_k$.

Soit $d$ le PGCD de $a$ et de $b$ (Ã©videmment, $d=r_k$), on peut Ã©crire $1 \times r_k-0 \times r_{k-1} = d$ puis $1 \times r_{k-2} - q_{k-1} \times r_{k-1}=d$.


D'une maniÃ¨re gÃ©nÃ©rale, si $(u,v)$ est un couple de BÃ©zout pour $r_{i+1}$ et $r_{i+2}$, soit $u \cdot r_{i+1}+v \cdot r_{i+2}=d$, comme $r_i=q_{i+1}\cdot r_{i+1} + r_{i+2}$, on a $u\cdot r_{i+1}+v \cdot (r_i-q_{i+1}\cdot r_{i+1})=d$, soit $(u-q_{i+1}\cdot v)\cdot r_{i+1}+v \cdot r_i=d$.

\subsection{L'algorithme.}
\index{algorithme!d'Euclide!gÃ©nÃ©ralisÃ©}
Ceci donne l'idÃ©e de construire deux familles par les relations :
\begin{itemize}
\item $u_0=1$, $u_1=0$,$u_{i+2}=u_i-q_{i+1} \cdot u_{i+1}$
\item $v_0=0$, $v_1=1$, $v_{i+2}=v_i-q_{i+1} \cdot v_{i+1}$.
\end{itemize}

C'est ce que l'on appelle algorithme d'Euclide gÃ©nÃ©ralisÃ©. On a alors $(u_k,v_k,r_k)=(u,v,d)$, $u$ et $v$ tels que $a \cdot u+b \cdot v=d$.

\begin{Pre}
Pour cela, il suffit de montrer par rÃ©currence que $\qqs i \in
\{0,\ldots,k\}, r_0 \cdot u_i + r_1 \cdot v_i = r_i$.
\begin{itemize}
 \item Initialisation de la rÃ©currence : la relation est vraie pour $i=0$, en effet $r_0 \cdot u_0+r_1 \cdot v_0=r_0$, puisque $u_0=1$ et $v_0=0$.
\item CaractÃ¨re hÃ©rÃ©ditaire de la propriÃ©tÃ© : en supposant que $i$ est un entier pour lequel $r_0 \cdot u_i + r_1 \cdot v_i =
r_i$ et $r_0 \cdot u_{i+1}+r_1 \cdot v_{i+1}=r_{i+1}$, calculons $r_0 \cdot u_{i+2}+r_1 \cdot v_{i+2}= r_0 \cdot (u_i-q_{i+1} \cdot u_{i+1}) + r_1 \cdot (v_i-q_{i+1} \cdot v_{i+1}) = r_0 \cdot
u_i+r_1 \cdot v_i-q_{i+1}\cdot (r_0 \cdot u_{i+1}+r_1 \cdot
v_{i+1})=r_i-q_{i+1}\cdot r_{i+1}=r_{i+2}$.
\end{itemize}
\end{Pre}


\subsection{Exemple.}

Illustrons la mise en \oe{}uvre de cet algorithme...

\begin{Ex}
Soit Ã&nbsp; obtenir un couple de BÃ©zout pour (23,17) :\vskip 10pt
\begin{center}\begin{tabular}{c c c c}
(23,1,0) &amp; (17,0,1) &amp; $\longrightarrow$ &amp; $q=1$ \\
(17,0,1) &amp; (6,1,-1) &amp; $\longrightarrow$ &amp; $q=2$ \\
(6,1,-1) &amp; (5,-2,3) &amp; $\longrightarrow$ &amp; $q=1$ \\
(5,-2,3) &amp; (1,3,-4) &amp; $\longrightarrow$ &amp; $q=5$ \\
(1,3,-4) &amp; (0,-17,23) &amp; $\longrightarrow$ &amp; FIN 
\end{tabular}\end{center}\vskip 10pt
On a bien $3 \times 23-4 \times 17=1$.\psaut 
\end{Ex}

\begin{Rem}
Il est possible d'obtenir -1 (ou $-d$ en gÃ©nÃ©ral) comme rÃ©sultat, donc $au-bv=-1$, cela dÃ©pend de la paritÃ© du nombre d'itÃ©rations effectuÃ©es dans l'algorithme prÃ©cÃ©dent.

Ce n'est pas un rÃ©sultat faux, puisqu'alors $bv-au=1$ et qu'on a quand mÃªme un couple de BÃ©zout pour $(b,a)$.

S'il est nÃ©cessaire d'obtenir un couple $(u,v)$ tel que $au-bv=1$
et oÃ¹ $a$ et $b$ figurent dans cet ordre, et que l'algorithme a fourni un couple $(u',v')$ tel que $bv'-au'=1$, il suffit de prendre $u=b-u'$ et $v=a-v'$ et, dans ces conditions $au-bv=a(b-u')-b(a-v')= ab -au' -ab +bv'=bv'-au'=1$. 
\end{Rem}

\begin{Exo}
Exprimer $\textit{PGCD}(1330,602)$ comme combinaison Ã&nbsp; coefficients entiers des nombres 1330 et 602.
\end{Exo}



\begin{Th}[ThÃ©orÃ¨me de Gauss]
Soient $a$, $b$ et $c$ trois entiers naturel non nuls. 
Si $a$ divise le produit $bc$ et si $a$ est premier avec $b$, 
alors $a$ divise $c$.
\end{Th}


\begin{Exo}
L'objectif est de rÃ©soudre l'Ã©quation $(E)$ d'inconnues $x$ et $y$ 
$405x -120y =15$.
\begin{enumerate}
\item Trouver le pgcd de 405 et 120  Ã&nbsp; l'aide de l'algorithme d'Euclide.
\item En dÃ©duire une solution particuliÃ¨re de cette Ã©quation.
\item En utilisant la solution particuliÃ¨re, montrer que $(E)$ est 
  Ã©quivalente Ã&nbsp; $27(x-3) = 8(y-10)$.
\item Utiliser le thÃ©orÃ¨me de Gauss pour montrer que 
  l'ensemble solution de $(E)$ est $\{(8k+3;27k+10)| k \in \Z\}$. 
\end{enumerate}
\end{Exo}

\begin{Exo}
  On considÃ¨re l'Ã©quation $\frac{x}{9}-\frac{y}{4}=3$ oÃ¹ $x$ et $y$ sont des entiers naturels. 
 \begin{enumerate}
\item Montrer que cela implique qu'il existe $k \in \N$ tel que  
 $x= 9(k+ 3)$ et $y=4k$.
\item DÃ©montrer que le PGCD de $x$ et $y$ ne peut Ãªtre quâ€™un diviseur de 108. 
\item Soit $m$ le  ppcm de $x$ et de $y$. 
  On envisage la dÃ©composition de $m$ en facteurs premiers. 
  Trouver l'ensemble des entiers naturel $k$ pour que 
  \begin{enumerate}
 \item $m$ ne contienne pas le facteur 2.
 \item $m$ contienne le facteur 2 ou le facteur $2^2$.
\item  $m$ ne contienne pas le facteur 3.
\item  $m$ contienne le facteur 3, ou le facteur $3^2$, ou le facteur $3^3$.
\end{enumerate}
\item Comment faut-il choisir $x$ et $y$ de telle faÃ§on que
  lâ€™on ait $\textit{PGCD}(x,y) = 18$? 
\end{enumerate}
\end{Exo}

\begin{Exo}
\begin{enumerate}
\item DÃ©composer 319 en facteurs premiers. 

\item DÃ©montrer que si $x$ et $y$ sont deux entiers 
  naturels premiers entre eux, il en est de mÃªme pour les 
  nombres $3x + 5y$ et $x + 2y$. 
\item RÃ©soudre dans $\Z^2$ le systÃ¨me dâ€™inconnues $a$ et $b$: 
$$
\left\{
\begin{array}{rcl}
(3a +5b)(a+2b) &amp;= &amp; 1276\\
ab &amp; = &amp; 2m
\textrm{ tel que  $m$ est le PPCM de $a$ et $b$. }
\end{array}
\right.
$$
\end{enumerate}
\end{Exo}

\begin{Exo}
Au 8Â° 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{Exo}

\section{ArithmÃ©tique modulo $n$} 

On rappelle ici la dÃ©finition de la relation dite de \og congruence modulo n\fg{} dÃ©finie dans $\Z$ Ã©tudiÃ©e dans le chapitre consacrÃ© aux relations entre ensembles.

\begin{Def}[Congruence modulo $n$]
Soit $n$ un entier strictement supÃ©rieur Ã&nbsp; 1 et $x$ et $y$ deux Ã©lÃ©ments de $\Z$.
On dit que \og $x$ est \emph{congru} Ã&nbsp; $y$ \emph{modulo}\index{congru}\index{modulo} $n$\fg{} lorsque $x$ et $y$ possÃ¨dent le mÃªme reste dans la division (euclidienne) par $n$ :
$$x \equiv y [n] \Ssi \exi k \in \Z, x-y=k \cdot n $$
\end{Def}


\begin{Exo}
 Calculez :
\begin{enumerate}
 \item $3*10^9 \mod 97$,
\item $3^{1024} \mod 1037$.
\end{enumerate}
\end{Exo}

%\noindent RÃ©ponses : 5 et 630.




\begin{Th}
La relation de congruence modulo $n$ est une relation d'Ã©quivalence dans $\Z$. 
\end{Th}

\begin{Proof}
En effet :
\begin{itemize}
\item $\qqs x \in \Z, x-x=0=0 \cdot n$; or $0 \in \Z$, donc $x
\equiv x [n]$ (rÃ©flexivitÃ©). \item Si $x \equiv y
[n]$, $\exi k \in \Z$, $x-y=k \cdot n$; alors $y-x=(-k) \cdot n$, et,
puisque $k \in \Z$, $(-k) \in \Z$, donc $y \equiv x [n]$ (symÃ©trie).
\item Si $x \equiv y [n]$, $\exi k\in\Z$, $x-y=k \cdot n$; si, de
plus, $y \equiv z [n]$, $\exi l\in\Z$, $y-z=l \cdot n$; alors (par
addition), $x-z=(k+l) \times n$; comme $k\in\Z$ et $l\in\Z$,
$(k+l)\in\Z$, donc $x \equiv z [n]$ (transitivitÃ©).
\end{itemize}
\end{Proof}


La classe d'Ã©quivalence d'un entier donnÃ© comprend donc cet entier et tous ceux qui ont le mÃªme reste que lui dans la division euclidienne par $n$.

\begin{Ex}
Si $n = 3$, il y a trois classes distinctes :
\begin{itemize}
 \item $\dot 0=\{\ldots,-6,-3,0,3,6,9,\ldots\}$, 
\item $\dot 1=\{\ldots,-5,-2,1,4,7,10,\ldots\}$,
\item $\dot 2=\{\ldots,-4,-1,2,5,8,11,\ldots\}$.
\end{itemize}

On retrouve ensuite les mÃªmes Ã©lÃ©ments : $\dot 3=\dot 0$, etc... 
\end{Ex}

D'une maniÃ¨re gÃ©nÃ©rale, pour $n$ quelconque, il y a exactement $n$ classes d'Ã©quivalence, notÃ©es de $\dot 0$ Ã&nbsp; $\dot {(n-1)}$, c'est-Ã&nbsp;-dire, il faut le remarquer, un nombre fini.




\begin{Th}
L'ensemble-quotient (ensemble des classes d'Ã©quivalence) de la relation de congruence modulo $n$ est un ensemble fini.
\end{Th}

\begin{Notation}
Il est notÃ© $\Z/n\Z$.
\end{Notation}


\begin{Ex}
 $\Z/3\Z =\{ \dot 0,\dot 1,\dot 2\}$.
\end{Ex}


\begin{Def}
On dit qu'une relation d'Ã©quivalence, notÃ©e  $\equiv$, 
dÃ©finie dans une structure algÃ©brique $S$, 
est compatible avec les lois de $S$  
lorsque les rÃ©sultats des opÃ©rations effectuÃ©es sur des Ã©lÃ©ments Ã©quivalents
demeurent Ã©quivalents:
\begin{itemize}
\item pour l'addition: si $x \equiv x'$ et  $y \equiv y'$, 
alors on doit avoir $x + y  \equiv x' + y'$;
\item pour la multiplication $\times$:  si $x \equiv x'$ et  $y \equiv y'$, 
alors on doit avoir $x \times y  \equiv x' \times y'$.
\end{itemize}
\end{Def}





\begin{Th}
La relation de \og congruence modulo $n$\fg{} est compatible avec l'addition et la multiplication des nombres entiers. 
\end{Th}


\begin{Proof}
En effet, on suppose que:
\begin{itemize}
\item $x \equiv x' [n] \Ssi \exi k\in \Z,\ x-x'=k \cdot n$;
\item $y \equiv y' [n] \Ssi \exi l\in \Z, y-y'=l \cdot n$.
\end{itemize}
Alors:
\begin{itemize}
\item par addition, $(x+y)-(x'+y')=(k+l)\cdot n$; $(k+l)\in\Z$, donc $(x+y)\equiv(x'+y') [n]$: la congruence modulo $n$ est compatible avec l'addition dans $\Z$
\item en multipliant l'Ã©galitÃ© $x-x'=k \cdot n$  par $y$, on a 
  $xy-x'y=(ky)\cdot n$ et l'Ã©galitÃ© 
  $y-y'=l \cdot n$
  par $x'$ on a $x'y-x'y'=(x'l)\cdot n$.
  
  Par addition, $xy-x'y'=(ky+lx')\cdot n$. $(ky+lx')\in\zmat$, donc $x\cdot y\equiv x'\cdot y' [n]$: la congruence modulo $n$ est aussi compatible avec la multiplication dans $\Z$.
\end{itemize}
\end{Proof}


% \begin{Rem}
% C'est cette propriÃ©tÃ© qui permet de dÃ©finir dans l'ensemble quotient $\Z/n\Z$ des opÃ©rations, dites \emph{induites} par celles qui existent dans $\Z$...
% \end{Rem}





\begin{Def}
Par dÃ©finition, on pose $\dot x + \dot y = \dot {(x+y)}$ et $\dot x \cdot
\dot y = \dot {(xy)}$.
\end{Def}


\begin{Ex}
C'est ainsi qu'on obtient les tables d'opÃ©rations suivantes dans $\Z/4\Z$ :\\


\begin{center}
$\begin{array}{|c|c|c|c|c|}\hline
+ &amp; \dot 0 &amp; \dot 1 &amp; \dot 2 &amp; \dot 3 \\ \hline
\dot 0 &amp; \dot 0 &amp; \dot 1 &amp; \dot 2 &amp; \dot 3 \\ \hline
\dot 1 &amp; \dot 1 &amp; \dot 2 &amp; \dot 3 &amp; \dot 0 \\ \hline
\dot 2 &amp; \dot 2 &amp; \dot 3 &amp; \dot 0 &amp; \dot 1 \\ \hline
\dot 3 &amp; \dot 3 &amp; \dot 0 &amp; \dot 1 &amp; \dot 2 \\ \hline \end{array}$
\hskip 50pt
$\begin{array}{|c|c|c|c|c|}\hline
\times &amp; \dot 0 &amp; \dot 1 &amp; \dot 2 &amp; \dot 3 \\ \hline 
\dot 0 &amp; \dot 0 &amp; \dot 0 &amp; \dot 0 &amp; \dot 0 \\ \hline
\dot 1 &amp; \dot 0 &amp; \dot 1 &amp; \dot 2 &amp; \dot 3 \\ \hline
\dot 2 &amp; \dot 0 &amp; \dot 2 &amp; \dot 0 &amp; \dot 2 \\ \hline
\dot 3 &amp; \dot 0 &amp; \dot 3 &amp; \dot 2 &amp; \dot 1 \\ \hline \end{array}$ 
\end{center}
\vskip 10pt
\end{Ex}


\begin{Rem}
On aperÃ§oit la prÃ©sence de \og diviseurs de zÃ©ro\fg{} ($\dot 2 \times \dot 2=\dot 0$), mais aussi l'apparition d'un inverse pour certains Ã©lÃ©ments ($\dot 3 \times \dot 3=\dot 1$). 
\end{Rem}


\begin{Exo}
RÃ©solvez modulo 18 les Ã©quations suivantes :

\begin{enumerate}
 \item $2x+17 = 15$,
\item $3x+4 = 12$,
\item $5x+13 = 16$.
\end{enumerate}
\end{Exo}

%\noindent RÃ©ponses : \{8,17\}, \{ \} et \{15\}.


\begin{Exo}[SystÃ¨mes de congruences]
Il s'agit de trouver des entiers $x$ qui satisfont des systÃ¨mes de la forme
$$\left\{\begin{array}{ccc}
x &amp; \equiv &amp; a\ [p] \\
x &amp; \equiv &amp; b\ [q] \\
\end{array}\right.$$
Un tel systÃ¨me peut ne pas avoir de solution
(par exemple, $a=1,\ p=2,\ b=0,\ q=4$: un nombre impair ne peut Ãªtre un multiple de 4).

Une condition suffisante d'existence de
solutions est que $p$ et $q$ soient premiers entre eux.

C'est le cas que nous traiterons ici; dans ce cas, il existe deux entiers $u$ et $v$ tels que $pu+qv=1$ (thÃ©orÃ¨me de BÃ©zout).

Donc $pu \equiv 1\ [q]$ et $qv \equiv 1\ [p]$, et $x=bpu+aqv$ est une solution du systÃ¨me (pourquoi??); les autres sont de la forme $x + kpq$, oÃ¹ $k$ est un entier quelconque.
\begin{enumerate}
\item RÃ©soudre le systÃ¨me de congruences 
$$\left\{\begin{array}{ccc}
x &amp; \equiv &amp; 2\ [88] \\
x &amp; \equiv &amp; 1\ [27] \\
\end{array}\right..$$
\item {\it Application au problÃ¨me du cuisinier}: une bande de 17 pirates s'est emparÃ©e d'un butin composÃ© de piÃ¨ces d'or, toutes d'Ã©gale valeur.

Ils dÃ©cident de se les partager Ã©galement et de donner le reste Ã©ventuel au cuisinier. Celui-ci recevrait alors 3 piÃ¨ces d'or. 

Malheureusement, une querelle Ã©clate, au cours de laquelle 6 pirates sont tuÃ©s. Le cuisinier recevrait alors 4 piÃ¨ces d'or.

Dans un naufrage ultÃ©rieur, seuls le butin, 6 pirates et le cuisinier sont sauvÃ©s. Le partage laisserait alors 5 piÃ¨ces Ã&nbsp; ce dernier.

Quel est le plus petit nombre de piÃ¨ces d'or qu'il espÃ¨re lorsqu'il dÃ©cide d'empoisonner les derniers pirates?
\end{enumerate}
\end{Exo}




\begin{Exo}
 Si $m$ est un entier naturel plus grand que 2, quel est l'inverse de $m-1$ modulo $m$ ?
\end{Exo}

%\noindent RÃ©ponse : $m-1$.


\begin{Exo}
Un nombre \og pseudo-premier de base $b$ \fg{}\index{pseudo-premier} est un entier naturel non premier $p$ tel que $(b^p-b) \mod p = 0$.
VÃ©rifier que 561 est pseudo-premier de base 3 et que 341 est pseudo-premier de base 2.
\end{Exo}



\section{ReprÃ©sentation des nombres entiers}



\begin{Def}[Principe de la numÃ©ration de position]
\index{Principe de la numÃ©rotation de position}
Il consiste Ã&nbsp; choisir une base $b$ de numÃ©ration, et $b$ symboles qui constitueront les chiffres dans la reprÃ©sentation d'un entier positif en base $b$.
Celle-ci s'Ã©crira alors
$$n=n_{p}b^p+n_{p-1}b^{p-1}+\cdots+n_{1}b^1+n_{0}$$ 

Cette Ã©criture est abrÃ©gÃ©e en ${\left(\overline{n_{p}n_{p-1}\ldots n_{0}}\right)}_{b}$.
\end{Def}

En informatique, on utilise couramment les bases 2, 8 et 16.





L'algorithme pour obtenir la reprÃ©sentation en base $b$ d'un entier est :

\begin{enumerate}
 \item Effectuer la division euclidienne de cet entier par $b$, division qui donne un premier quotient et un premier reste.
 \item Le quotient est Ã&nbsp; sont tour divisÃ© par $b$ pour donner un second quotient et un second reste, et ainsi de suite jusqu'Ã&nbsp; obtenir un quotient nul.
\item Les restes successifs (tous strictement infÃ©rieurs Ã&nbsp; $b$), et en commenÃ§ant par le dernier, constituent la reprÃ©sentation en base $b$ de l'entier donnÃ©.
\end{enumerate}

\begin{Exo}
Donner la reprÃ©sentation de 23 en base 2.
\end{Exo}



\begin{Exo}[NumÃ©ration, changements de base]
\begin{enumerate}
\item Chercher les entiers dont le carrÃ© a, en reprÃ©sentation dÃ©cimale, 
le mÃªme chiffre pour les dizaines et les unitÃ©s. 
\item On pose $a=2p-1$, $b=2p+1$, $c=2p+3$; trouver l'entier $p$ de maniÃ¨re que $a^2+b^2+c^2$ soit de la forme $\sur{xxxx}_{10}$.
\item L'entier $n$ s'Ã©crit $\sur{341}_{10}$ et $\sur{2331}_a$. Trouver $a$.
\item Montrer que, dans toute base $b$ supÃ©rieure ou Ã©gale Ã&nbsp; 3, l'entier qui s'Ã©crit $\sur{11211}_b$ n'est pas  premier.
\item Soit $n\geqslant 7$. Donner l'Ã©criture de $(n+1)^4$ en base $n$.
\end{enumerate}
\end{Exo}



\begin{Exo}[DÃ©veloppement dÃ©cimal]
On considÃ¨re le nombre rÃ©el $x$ dont le dÃ©\-ve\-lop\-pe\-ment dÃ©cimal s'Ã©crit $x=0,012\ 345\ 679\ 012\ 345\ 679\ \ldots\ \ldots\ \ldots$ (la sÃ©quence $012\ 345\ 679$ est reproduite indÃ©finiment). Ce dÃ©veloppement dÃ©cimal est pÃ©riodique, de pÃ©riode 9.
\begin{enumerate}
\item Montrer que $x$
vÃ©rifie une Ã©quation de la forme $10^kx=n+x$, oÃ¹ $k$ et $n$ sont
des entiers Ã&nbsp; dÃ©terminer. En rÃ©solvant cette Ã©quation,
montrer que $x$ est un nombre rationnel, et le mettre sous la forme
$x= \fr pq$ , oÃ¹ $p$ et $q$ sont premiers entre eux.
\item Appliquer
la mÃªme mÃ©thode au ``nombre" $y$ dont le dÃ©veloppement
dÃ©cimal est $y= 0,999\ 999\ 999\ 999\ \ldots$ (pÃ©riodique de pÃ©riode
1). Quelle conclusion peut-on en tirer?
\item DÃ©montrer que tout nombre rÃ©el dont le dÃ©veloppement
dÃ©cimal est fini ou pÃ©riodique Ã&nbsp; partir d'un certain rang
est un nombre rationnel.
\item RÃ©ciproquement, on se propose de dÃ©montrer que le
dÃ©veloppement dÃ©cimal de tout nombre rationnel est fini ou
pÃ©riodique Ã&nbsp; partir d'un certain rang. Pour cela, on
considÃ¨re un rationnel $x=\fr pq$ , avec $q&gt;0$, $p\in
\Z$, $p$ et $q$ premiers entre eux, et on Ã©tudiera successivement
les cas suivants:
\begin{itemize}
\item $x$ est entier (c'est Ã&nbsp; dire $q=1$).
\item $x$ est rationnel non entier, et $q$ est premier avec 10 (On
pourra montrer que, si $q$ est premier avec 10, il existe un entier
$k$, non nul, tel que $10^k\equiv 1\ [q]$).
\item $x$ est rationnel non entier, mais $q$ n'est pas premier avec 10.
\end{itemize}
\end{enumerate}

\end{Exo}



\section{ArithmÃ©tique en informatique}


La plupart des langages de programmation utilisÃ©s en informatique disposent d'un type de donnÃ©es pour reprÃ©senter ce que les informaticiens appellent les entiers signÃ©s (les entiers relatifs) et possÃ¨dent des opÃ©rateurs pour effectuer les calculs classiques sur ces nombres.

\subsection{Division entiÃ¨re}

En C ou java, par exemple, le symbole $/$ reprÃ©sente le quotient dans la \og division entiÃ¨re\fg{} et le symbole $\%$ reprÃ©sente ce que les informaticiens appellent improprement le modulo (le reste dans leur \og division entiÃ¨re\fg{} ).


Pour des raisons pratiques de rÃ©alisation des micro-circuits des processeurs qui rÃ©alisent ces opÃ©rations, la \og division entiÃ¨re\fg{} ne donne pas exactement le mÃªme rÃ©sultat que la division euclidienne.



ConsidÃ©rons par exemple les 4 cas possibles de division euclidienne de $a$ par $b$ lorsque $|a|=29$ et $|b|=7$ (en n'oubliant pas que le reste d'une division euclidienne ne peut Ãªtre que positif)


\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$a$ &amp; $b$ &amp; division euclidienne &amp; $q$ &amp; $r$ &amp; $a/b$ &amp; $a\%b$ \\ \hline
$29$ &amp;$7$ &amp; $29=4\times 7+1$ &amp; $4$ &amp; $1$ &amp; $4$ &amp; $1$ \\ \hline
$29$ &amp;$-7$ &amp; $29=(-4)\times (-7)+1$ &amp; $-4$ &amp; $1$ &amp; $-4$ &amp; $1$ \\ \hline
$-29$ &amp;$7$ &amp; $-29=(-5)\times 7+6$ &amp; $-5$ &amp; $6$ &amp; $-4$ &amp; $-1$ \\ \hline
$-29$ &amp;$-7$ &amp; $-29=5\times (-7)+6$ &amp; $5$ &amp; $6$ &amp; $4$ &amp; $-1$ \\ \hline
\end{tabular}
\end{center}



Autrement dit, mathÃ©matiquement, le quotient est positif lorsque les deux nombres ont le mÃªme signe et le reste est toujours positif, et, pour que le reste soit toujours positif, le quotient peut ne pas Ãªtre le quotient des valeurs absolues.


Informatiquement, le \og quotient\fg{} est positif lorsque les nombres ont le mÃªme signe, le \og reste\fg{} a le signe du dividende, et la valeur absolue du \og quotient\fg{} est toujours le quotient des valeurs absolues.


Dans les applications de calcul arithmÃ©tique, par exemple un calcul de PGCD, ce n'est pas gÃªnant parce que les restes \og informatiques\fg{} sont congrus aux restes mathÃ©matiques modulo la valeur absolue du
diviseur, et qu'il ne s'agit alors que du choix d'un reprÃ©sentant de la classe concernÃ©e (addition et multiplication Ã©tant compatibles avec la congruence modulo $n$).

Mais il faut quand mÃªme savoir que l'on peut obtenir un \og reste\fg{} nÃ©gatif et prendre ses dispositions le cas Ã©chÃ©ant...


\subsection{ArithmÃ©tique modulo $2^n$}

 

Les calculs sur les entiers, dans un ordinateur, se font dans $\Z/2^n\Z$, oÃ¹ $n$ est le nombre de bits utilisÃ©s dans la reprÃ©sentation de ces nombres.


Dans la plupart des microprocesseurs, les entiers sont reprÃ©sentÃ©s sur 64 bits, les calculs se font donc dans $\Z/2^{64}\Z$.


Disposer d'entiers signÃ©s ou d'entiers non signÃ©s est uniquement une question de choix du reprÃ©sentant dans les classes d'Ã©quivalence, mais
la reprÃ©sentation physique est la mÃªme.


Comme il nous est difficile de reprÃ©senter ici la liste complÃ©te de tous ces entiers, nous allons illustrer ce propos en supposant que les entiers sont reprÃ©sentÃ©s sur 4 bits.
Pour des mots de 4 bits, il y a alors 16 entiers reprÃ©sentables : (a.s.= arithmÃ©tique signÃ©e, a.n.s. = arithmÃ©tique non signÃ©e)

\begin{center}\begin{tabular}{|c|c|c|c|} \hline
code binaire &amp; &amp; a.s. &amp; a.n.s. \\ \hline
0000 &amp; interprÃ©tÃ© par &amp; 0 &amp; 0 \\ \hline
0001 &amp; interprÃ©tÃ© par &amp; 1 &amp; 1 \\ \hline
0010 &amp; interprÃ©tÃ© par &amp; 2 &amp; 2 \\ \hline
0011 &amp; interprÃ©tÃ© par &amp; 3 &amp; 3 \\ \hline
0100 &amp; interprÃ©tÃ© par &amp; 4 &amp; 4 \\ \hline
0101 &amp; interprÃ©tÃ© par &amp; 5 &amp; 5 \\ \hline
0110 &amp; interprÃ©tÃ© par &amp; 6 &amp; 6 \\ \hline
0111 &amp; interprÃ©tÃ© par &amp; 7 &amp; 7 \\ \hline
1000 &amp; interprÃ©tÃ© par &amp; 8 &amp; -8 \\ \hline
1001 &amp; interprÃ©tÃ© par &amp; 9 &amp; -7 \\ \hline
1010 &amp; interprÃ©tÃ© par &amp; 10 &amp; -6 \\ \hline
1011 &amp; interprÃ©tÃ© par &amp; 11 &amp; -5 \\ \hline
1100 &amp; interprÃ©tÃ© par &amp; 12 &amp; -4 \\ \hline
1101 &amp; interprÃ©tÃ© par &amp; 13 &amp; -3 \\ \hline
1110 &amp; interprÃ©tÃ© par &amp; 14 &amp; -2 \\ \hline
1111 &amp; interprÃ©tÃ© par &amp; 15 &amp; -1 \\ \hline
\end{tabular}\end{center}\vskip 10pt


Pourquoi ce choix ? Pourquoi ne pas avoir, en a.s., reprÃ©sentÃ© les entiers dans l'ordre croissant de 0000 (-8) Ã&nbsp; 1111 (7)?

\begin{itemize}
 \item Tout simplement pour des raisons d'efficacitÃ© : 0 doit toujours Ãªtre reprÃ©sentÃ© par le code \og nul\fg{} 0000.
\item Ensuite, il faut pouvoir comparer efficacement ces codes entre eux, ce qui explique que 0 doit Ãªtre suivi de 1, arithmÃ©tique signÃ©e ou pas.
\end{itemize}

\bigskip

Ces principes ont ainsi conduit Ã&nbsp; placer les codes interprÃ©tÃ©s comme entiers nÃ©gatifs aprÃ¨s ceux qui reprÃ©sentent les entiers positifs.


Par ailleurs, on s'aperÃ§oit que, de cette maniÃ¨re, les codes des entiers
nÃ©gatifs commencent tous par 1.
On parle improprement de \og bit de signe\fg{}\index{bit de signe}: s'il s'agissait d'un vÃ©ritable bit de signe, le code 1001 devrait Ãªtre celui de -1, or c'est celui de -7.
Mais il n'en reste pas moins que tous les entiers nÃ©gatifs commencent par 1).


Ainsi, il est facile de dÃ©duire la comparaison signÃ©e de la comparaison non signÃ©e : les codes qui commencent par 1 sont \og plus petits\fg{} que ceux qui commencent par 0, et, s'ils commencent par le mÃªme bit, c'est la comparaison non signÃ©e qui peut Ãªtre utilisÃ©e.





Pour l'addition et la soustraction, les opÃ©rations et les tests de validitÃ© des rÃ©sultats sont les mÃªmes en arithmÃ©tique signÃ©e et non signÃ©e.
Pour la multiplication, l'instruction n'est pas la mÃªme (le dÃ©passement de capacitÃ© doit Ãªtre ignorÃ© en a.s. dans le dernier exemple).

\begin{Ex}

Premiers rÃ©sultats, corrects :

 \begin{center}
\begin{tabular}{r | r | r}
OpÃ©ration binaire &amp; Entiers non signÃ©s &amp; Entiers signÃ©s \\
\hline
0010 &amp; 2 &amp; 2 \\
\underline{+ 1001} &amp; \underline{+ 9} &amp; \underline{+(-7)} \\
1011 &amp; 11 &amp; (-5) \\
\end{tabular}
 \end{center}
\end{Ex}


\begin{Ex}
 Un rÃ©sultat correct en arithmÃ©tique non \break signÃ©e, et nÃ©gatif en arithmÃ©tique signÃ©e, mais correct modulo 16 (-6 et 10 sont dans la mÃªme classe, mais cette classe  est reprÃ©sentÃ©e par 10 en a.n.s. et par -6 en a.s.) :
\begin{center}
\begin{tabular}{r | r | r}
OpÃ©ration binaire &amp; Entiers non signÃ©s &amp; Entiers signÃ©s \\
\hline
0100 &amp; 4 &amp; 4 \\
\underline{+ 0110} &amp; \underline{+ 6} &amp; \underline{+ 6} \\
1010 &amp; 10 &amp; (-6) \\
\end{tabular}
\end{center}
\end{Ex}


\begin{Ex}
Un dÃ©passement de capacitÃ© dans les deux cas, mais  le rÃ©sultat est correct modulo 16 : les classes de 21, de -11 et de 5 sont les mÃªmes :
 \begin{center}
\begin{tabular}{r | r | r}
OpÃ©ration binaire &amp; Entiers non signÃ©s &amp; Entiers signÃ©s \\
\hline
1100 &amp; 12 &amp; (-4) \\
\underline{+ 1001} &amp; \underline{+ 9} &amp; \underline{+(-7)} \\
(1)0101 &amp; 5 &amp; 5 \\
\end{tabular}
 \end{center}
Le rÃ©sultat (correct modulo 16) est disponible dans tous les cas, les \og dÃ©passement de capacitÃ©\fg{} et \og rÃ©sultat nÃ©gatif\fg{} sont signalÃ©s par le positionnement d'un bit dans un registre spÃ©cial.
\end{Ex}




\begin{Ex}
Un rÃ©sultat correct en a.n.s., rÃ©sultat nÃ©gatif en a.s., mais correct modulo 16 :
 \begin{center}
\begin{tabular}{r | r | r}
OpÃ©ration binaire &amp; Entiers non signÃ©s &amp; Entiers signÃ©s \\
\hline
0101 &amp; 5 &amp; 5 \\
\underline{$\times$ 0010} &amp; \underline{$\times$ 2} &amp;
\underline{$\times$ 2} \\ 1010 &amp; 10 &amp; (-6) \\
\end{tabular}
 \end{center}
\end{Ex}


\begin{Ex}
DÃ©passement de capacitÃ© dans les deux cas, rÃ©sultat nÃ©gatif en a.s., mais rÃ©sultat correct modulo 16, compte tenu du choix des reprÃ©sentants dans les deux arithmÃ©tiques:
 \begin{center}
\begin{tabular}{r | r | r}
OpÃ©ration binaire &amp; Entiers non signÃ©s &amp; Entiers signÃ©s \\
\hline
0101 &amp; 5 &amp; 5 \\
\sou{$\times$ 0110} &amp; \sou{$\times$ 6} &amp; \sou{$\times$ 6} \\
(1)1110 &amp; 14 &amp; (-2) \\
\end{tabular} 
 \end{center}
\end{Ex}




\begin{Ex}
DÃ©passement de capacitÃ© dans les deux cas,  rÃ©sultat correct en a.s., correct modulo 16 en a.n.s.
 \begin{center}
\begin{tabular}{r | r | r}
OpÃ©ration binaire &amp; Entiers non signÃ©s &amp; Entiers signÃ©s \\
\hline
1101 &amp; 13 &amp; (-3) \\
\sou{$\times$ 1110} &amp; \sou{$\times$ 14} &amp; \sou{$\times$
(-2)} \\ (1011)0110 &amp; 6 &amp; 6 \\
\end{tabular} 
\end{center}
\end{Ex}
\centerline{\x{Fin du Chapitre}}</pre></body></html>