\documentclass[a4paper,11pt]{article}
\usepackage[francais]{babel}
\usepackage[dvips]{graphics}
\usepackage{graphicx}
\usepackage[latin1]{inputenc}
%\usepackage{isolatin1}
\usepackage{amsmath}
\usepackage{amscd}
\usepackage{amstext}
\usepackage{amsbsy}
\usepackage{amsopn}
\usepackage{amsthm}
\usepackage{amsxtra}
\usepackage{upref}
\usepackage{euscript}
\usepackage{amssymb}
\usepackage{amsfonts}
%\usepackage{ulsy}
\usepackage[all]{xy}
\usepackage{enumerate} % pour avoir des enumerations plus evoluees
\usepackage{vmargin}
\usepackage{txfonts}
\usepackage{textcomp}
\usepackage{fontenc}
%\usepackage{marvosym}
% Idem pour avoir un beau symbole du si et seulement si
\def\NN{\ensuremath{\mathbb{N}}}
\def\ZZ{\ensuremath{\mathbb{Z}}}
\def\QQ{\ensuremath{\mathbb{Q}}}
\def\RR{\ensuremath{\mathbb{R}}}
\def\CC{\ensuremath{\mathbb{C}}}
\def\KK{\ensuremath{\mathbb{K}}}
%
\parindent=0pt
\setmarginsrb{2,5cm}{0,5cm}{2,5cm}{1,5cm}{16pt}{30pt}{16pt}{45pt}
%\setmarginsrb{1}{2}{3}{4}{5}{6}{7}{8} 
% {1} marge gauche, {2} est la marge en haut,{3} est la marge droite,{4} est la marge en bas, {5} fixe la hauteur de l'entête, {6} fixe la distance entre l'entête et le texte, {7} fixe la hauteur du pied de page, {8} fixe la hauteur entre le texte et le pied de page.
%
\date{}
%
\title{Exposé 9 : Division Euclidienne dans \ZZ.\\Unicité du quotient et du reste. Applications.}
%\author{Gwendal}
%pour la date en français
\def\today{\ifnum\day=1\relax 1\raisebox{.6ex}{\small er}
\else \number\day\fi
\space\ifcase\month\or janvier\or février\or mars\or avril\or mai\or juin\or juillet\or août\or septembre\or octobre\or novembre\or décembre\fi\space\number\year}  
% guillemets ouvrant \og  fermant \fg
%
\newenvironment{pluslong}[2][]%
{\begin{flushleft}\textbf{#1} \textsc{#2\\} \textup}%
{\end{flushleft} }
%
%
\newenvironment{pluslong2}[2][]%
{\begin{flushleft}\textbf{#1} \textsc{#2} \textup}%
{\end{flushleft} }
%
\newenvironment{moyen}[1][]%
{\begin{flushleft}\textbf{#1\\} \textup}%
{\end{flushleft} }
%
\newenvironment{moyen2}[1][]%
{\begin{flushleft}\textbf{#1} \textup}%
{\end{flushleft} }
%
\newenvironment{court}%
{\begin{flushleft} \textup}%
{\end{flushleft} }
%
%
\newenvironment{preuve}[1][]%
{\begin{flushleft}\underline{preuve} \textup}%
{\qed\end{flushleft}}
%
\begin{document}
\maketitle
%\tableofcontents
% (table des matières)
%\newpage
\textbf{Prérequis}\footnotemark[1] :\\
-Majorants, minorants, plus petit élément, plus grand élément\\
-Théorème : toute partie non vide de $\ZZ$ majorée (repect. minorée) admet un plus grand élément (resp. un plus petit élément).\\
-Diviseurs\\
-Sous groupes\\

\textsc{Introduction} : lorsque l'on effectue une division de deux entiers relatifs à la calculatrice, elle affiche très souvent un nombre à virgule. Ici, on étudie une division particulière où n'interviennent que des entiers.

\footnotetext[1]{L'exposé a été tapé et présenté à Bordeaux(4) le 19/10/2005 par Gwendal Haudebourg. Mis à jour le 31/07/2007.}

\section{Division Euclidienne}

\subsection{Division Euclidienne dans \ZZ}

\begin{moyen2}[Théorème] : Soient $(a,b)\in \ZZ\times\ZZ^{*}$. Il existe un unique couple $(q,r)\in \ZZ \times \NN $ tq. $a=bq+r$, avec $0\leqslant r < \vert b \vert $
\end{moyen2}

\begin{preuve} :
-\underline{Existence} : supposons $b>0$ et posons $\mathcal{B}=\lbrace  k \in \ZZ$, tel que $kb\leqslant a \rbrace$\\
$\mathcal{B}$ est une partie non vide de $\ZZ$ (car si $a \geqslant 0$, alors $0 \in \mathcal{B}$, et si $a<0$, alors $a \in \mathcal{B}$).\\
$\mathcal{B}$ est majorée par $max(0,a)$ donc $\mathcal{B}$ admet un plus grand élément $q$ qui vérifie $qb\leqslant a < (q+1)b$ (donc $qb\leqslant a <bq+b$ donc $\exists r \in \NN$ tq. $a=bq+r$ pour le $q$ précédemment déterminé)\\
Lorsque $b<0$ on se ramène au cas précédent avec $(-b)q+r=b(-q)+r$. Dans tous les cas, on a prouvé l'existence de $q \in \ZZ$ et $r \in \NN$ tel que $r=a-bq$, d'où $0\leqslant r < \vert b \vert$.\\
-\underline{Unicité} : soient $(q,r)$, $(q',r')$ $\in (\ZZ\times \NN)$ tels que $a=bq+r$ et $a=bq'+r'$ avec $0\leqslant r < \vert b \vert$ et $0\leqslant r' < \vert b \vert$.\\
On a : $b(q-q')=r-r'$ donc $\vert b \vert.\vert q-q' \vert=\vert r-r' \vert$ or $\vert r-r' \vert <\vert b \vert$, d'où $0 \leqslant \vert q-q' \vert <1$ (car $b\neq 0$), d'où $q=q'$ et $r=r'$.
\end{preuve}

\begin{moyen2}[Définition] :
L'opération ainsi définie, associant au couple $(a,b)$ le couple $(q,r)$ est appelée division Euclidienne de $a$ par $b$.\\
$a$ est appelé le dividende, $b$ le diviseur, $q$ le quotient et $r$ le reste.
\end{moyen2}

\begin{moyen2}[Remarque] :
si $r=0$, on dit que $b$ divise $a$, que $b$ est un diviseur de $a$, que $a$ est un multiple de $b$, et on note $b \vert a$
\end{moyen2}

\subsection{Division Euclidienne dans \NN}

\begin{moyen2}[Théorème] : Soient $(a,b)\in \NN\times\NN^{*}$. Il existe un unique couple $(q,r)\in \NN \times \NN $ tq. $a=bq+r$, avec $0<r \leqslant b$
\end{moyen2}

\begin{moyen}[preuve :]
-\underline{Existence} : posons $\mathcal{B}=\lbrace  k \in \NN$, tel que $kb\leqslant a \rbrace$ après idem.\\
-\underline{Unicité} : idem.
\end{moyen}

\section{Applications}

\subsection{Algorithme d'Euclide}

\begin{moyen2}[Théorème] : soient $a,b \in \left( \ZZ^{*}\right)^{2}$. L'ensemble des diviseurs communs à $a$ et $b$ admet un plus grand élément.
\end{moyen2}

\begin{moyen2}[Définition] : soient $a,b \in \left( \ZZ^{*}\right)^{2}$. Le plus grand diviseur commun à $a$ et $b$ est appelé $pgcd$ de $(a,b)$, et on note le note $pgcd(a,b)$ ou $a \wedge b$.
\end{moyen2}

\begin{pluslong2}[Théorème]{(d'Euclide)} : soient $a,b,q,r$ non nuls. Alors $a=bq+r$ $\Rightarrow pgcd(a,b)=pgcd(b,r)$.
\end{pluslong2}

\begin{preuve} : (du théorème d'Euclide)\\
$pgcd(a,b)\vert b$ donc $pgcd(a,b)\vert bq$, $pgcd(a,b)\vert a$ et $r=a-bq$ donc $pgcd(a,b)\vert r$ d'où $pgcd(a,b)\vert pgcd(r,b)$ car $pgcd(r,b)$ est le plus grand diviseur commun à $r$ et $b$.\\
De même $pgcd(b,r)\vert b$, $pgcd(b,r)\vert r$ donc $pgcd(b,r)\vert bq$ or $a=bq+r$ donc $pgcd(b,r)\vert a$, $pgcd(b,r)\vert b$ donc $pgcd(b,r)\vert pgcd(a,b)$ d'où l'égalité.
\end{preuve}

On en déduit l'algorithme d'Euclide dans $\NN$ pour la recherche du $pgcd(a,b)$ où $a,b$ sont des entiers non nuls :\\
Soient $(a,b) \in \left( \NN^{*}\right)^{2}$. $\exists !(q_{1},r_{1})\in \NN^{2}$ tq. $a=bq_{1}+r_{1}$, $0\leqslant r_{1}<b$ (division Euclidienne)\\
-si $r_{1}=0$ alors $pgcd(a,b)=b$\\
-si $r_{1}\neq 0$ alors $pgcd(a,b)=pgcd(b,r_{1})$ (théorème d'Euclide). $\exists ! (q_{2},r_{2})\in \left( \ZZ^{*}\right)^{2}$ tq. $b=r_{1}q_{2}+r_{2}$, $0\leqslant r_{2}<r_{1}$\\
...\\
On construit ainsi une suite $(r_{n})_{n}$ de $\NN$ strictement décroissante et minorée (par $0$), donc $\exists k \in \NN$ tq. $r_{k}\neq 0$ et $r_{k+1}=0$.\\
De plus, on a (théorème d'Euclide) $pgcd(a,b)=pgcd(b,r_{1})=pgcd(r_{1},r_{2})=...=pgcd(r_{k},r_{k+1})=r_{k}$ (ie dernier reste non nul).\\

\underline{Exemple} : $a=93$ et $b=66$
\vspace{0.28cm}
$93=66\times1+27$ d'où $pgcd(93,66)=pgcd(66,27)$\\
$66=27\times2+12$ d'où $pgcd(66,27)=pgcd(27,12)$\\
$27=12\times2+3$ d'où $pgcd(27,12)=pgcd(12,3)=3$\\
$12=3\times4+0$ d'où $pgcd(93,66)=3$

\subsection{Numération en base $b \in \NN-\left\lbrace 0,1 \right\rbrace$ }

\textbf{Théorème} : pour tout $x$ entier naturel non nul, il existe un unique $n \in \NN$ et un unique $n+1$-uplets $x_{0},...,x_{n}\in \NN$ tel que :
\begin{enumerate}
\item $x_{n}\neq 0$
\item $\forall i=0...n$, $0\leqslant x_{i}<b$ et $x=x_{0}+bx_{1}+...+b^{n}x_{n}$
\end{enumerate}

\begin{moyen2}[Définition] : on notera $x=\overline{x_{n}x_{n-1}...x_{0}}^{b}$, c'est l'écriture en base $b$ de $x$
\end{moyen2}

\begin{preuve} (Théorème) :
\vspace{0.12cm}
Soit $x=bq_{0}+r_{0}$, $0\leqslant r_{0}<b$ (division euclidienne de $x$ par $b$)\\
On a $q_{0}\leqslant \dfrac{x}{b}<x$ car $b>1$, donc $q_{0}b\leqslant x <bx$\\
$q_{0}=bq_{1}+r_{1}$ où $0 \leqslant r_{1}<b$ (division Euclidienne de $q_{0}$ par $b$)\\
De même $q_{1}<bq_{1}\leqslant q_{0}$ car $b>1$ et $r\geqslant 0$  (car $\dfrac{q_{1}}{b}<q_{1}$ et $q_{1}b\leqslant q_{0}<q_{0}b$)\\
...\\
$q_{p}b=bq_{p+1}+r_{p}$ où $0\leqslant r_{p}<b$\\
D'où $q_{p+1}<bq_{p+1}\leqslant q_{p}<q_{p-1}<...<q_{1}<q_{0}$\\
On définit ainsi une suite $(q_{n})_{n}$ strictement décroissante d'entiers positifs (car on effectue des divisions Euclidiennes dans $\NN$ de $q_{i}$ par $b$). Donc il existe $n \in \NN$ tq. $q_{n}=0$\\
$x=bq_{0}+r_{0}=b(q_{1}b+r_{1})+r_{0}=b^{2}q_{1}+br_{1}+r_{0}=b^{2}(bq_{2}+r_{2})+br_{1}+r_{0}=b^{3}q_{2}+b^{2}r_{2}+br_{1}+r_{0}$\\
$=...$\\
$=b^{n}q_{n-1}+b^{n-1}r_{n-1}+...+br_{1}+r_{0}$\\
or $q_{n-1}=bq_{n}+r_{n}$ et $q_{n}=0$, $q_{n-1}\neq 0$ (sinon on s'arrête avant) donc $r_{n}\neq 0$ et $q_{n}=r_{n}$\\
d'où $x=b^{n}r_{n}+b^{n-1}r_{n-1}+...+br_{1}+r_{0}$\\
d'où $x_{i}=r_{i} \forall i \in \lbrace 0,...,n \rbrace$ or $0\leqslant r_{i}<b$ (division Euclidienne) et $x_{n}\neq 0$, donc on a bien le résultat souhaité.
\end{preuve}

\underline{Exemples} :\\ 
Ecriture en base $3$ de $85$ (85 est ausi noté $\overline{85}^{10}$)\\
$85=28\times3+1$ ($q_{0}=28$)\\
$28=9\times3+1$ ($q_{1}=9$)\\
$9=3\times3+0$ ($q_{2}=3$)\\
$3=1\times3+0$ ($q_{3}=1$)\\
$1=0\times3+1$ ($q_{4}=0$, on s'arrête)\\
donc $85=10011$ en base 3 ie $\overline{85}^{10}=\overline{10011}^{3}$. On a bien : $85=3^{4}\times 1+3^{3}\times 0+3^{2}\times 0+3^{1}\times 1+3^{0}\times 1$.\\
Ecriture en base $4$ de $\overline{16}^{16}$\\
$\overline{16}^{16}=1\times 16^{1}+6\times 16^{0}=22=1\times 4^{2}+1\times 4^{1}+2\times 4^{0}=\overline{112}^{4}$

\subsection{Sous-groupes de $\left(\ZZ,+\right)$}

\begin{moyen2}[Théorème] : tous les sous groupes de $(\ZZ,+)$ sont de la forme $(n\ZZ,+)$, $n\in \NN$
\end{moyen2}

\section{Compléments}

\subsection{Preuves}

\begin{moyen2}[Théorème] : soient $a,b \in \left( \ZZ^{*}\right)^{2}$. L'ensemble des diviseurs communs à $a$ et $b$ admet un plus grand élément, noté $pgcd(a,b)$.
\end{moyen2}

\begin{preuve} : soit $\mathcal{D}$ cet ensemble. $\mathcal{D}$ est non vide car $1 \vert a$ et $1 \vert b$, donc $1 \in \mathcal{D}$.\\
$\vert a \vert$ est le plus grand diviseur de $a$ donc tout élément de $\mathcal{D}$ est inférieur à $\vert a \vert$.\\
$\mathcal{D}$ est donc une partie non vide et majorée de $\ZZ$. Elle admet donc un plus grand élément.
\end{preuve}

\begin{moyen2}[Théorème] : tous les sous groupes de $(\ZZ,+)$ sont de la forme $(n\ZZ,+)$, $n\in \NN$
\end{moyen2}

\begin{preuve} : Soit $H$ sous-groupe de $\ZZ$\\
Si $H=\lbrace 0 \rbrace$, on a $H=0.\ZZ$\\
Si $H\neq\lbrace 0 \rbrace$, $\exists c\neq 0$ tel que $c \in H$ et $-c \in H$ (car $H$ groupe), donc $H$ contient au moins un élément strictement positif.\\
Si on considère l'ensemble $H^{+}:=\lbrace x \in H, x>0 \rbrace$, cet ensemble est non vide car contient $c$ ou $-c$, et est un sous ensemble de $\NN$. Donc $H^{+}$ est un sous ensemble non vide de $\NN$, donc contient un plus petit élément $n$ (car $\NN$ minorée par $0$). On a donc $n>0$.\\
$\forall x \in H, \exists (q,r)\in \ZZ\times\NN$, $x=nq+r$, $0\leqslant r<n$ (division Euclidienne de $x$ par $n$), donc $r=x-nq$ or $x\in H$, $nq \in H$ donc $r \in H$. Si $r>0$, alors $r \in H^{+}$ et $r<n$ absurde !\\
Donc $r=0$ et $x=nq$, donc $H^{+}\subset a\ZZ$, $a \in \NN$ donc $H \subset a\ZZ$.\\
Réciproquement, si on considère un élément de $a\ZZ$, il est clairement dans $H$ (puisque $H$ sous groupe de \ZZ), donc $H=a\ZZ$.
\end{preuve}

\subsection{Remarques}

Dans la division Euclidienne "classique", $bq$ n'est pas forcément le multiple de $b$ le plus proche de $a$ (ex : $a=5, b=3, q=1, r=2, bq=3$ moins proche de 5 que $6=3\times 2)$.\\

Dans la division Euclidienne "classique", si on remplace la condition $0 \leqslant< \vert b \vert$ par $\vert r \vert<\vert b \vert$ (donc avec $r \in \ZZ$ ie peut être négatif), il n'y a plus unicité du couple $(q,r)$ (ex: $10=3*3+1=4*3-2$). Par ailleurs, on a le corollaire suivant :

\begin{moyen2}[Corollaire] : pour tout couple $(a,b)\in \ZZ \times \ZZ^{*}$, il existe un couple (q,r) tel que $a=bq+r$ et $\vert r \vert \leqslant \dfrac{\vert b \vert}{2}$
\end{moyen2}

\begin{moyen2}[remarque] : on obtient ainsi le multiple de $b$ le plus proche de $a$, mais on perd l'unicité (quand $\vert r \vert=\dfrac{\vert b \vert}{2}$ ex: $10=4\times 2+1=4\times 3-2$)\\
Si on effectue les divisions Euclidiennes successives  de cette manière, on obtient un algorithme d'Euclide "amélioré" (ie tend plus vite vers le $pgcd$).
\end{moyen2}

On définit le $pgcd(a,b)$ lorsque $\left( \ZZ^{*}\right)^{2}$ car $(0,0)$ n'a pas de plus grand diviseur. Comme convention, on pose $pgcd(0,0)=0$\\

\textbf{Méthode de détermination des quotients et du reste} : (la descente de Fermat)\\
Soient $(a,b)\in \NN\times \NN^{*}$\\
-si $a<b$, alors le couple $(0,a)$ est le couple (quotient, reste) cherché\\
-si $a\geqslant b$, soit $q_{1}\in \NN^{*}$ tel que $bq_{1}\leqslant a$. On pose $r_{1}=a-bq_{1}$. Si $r_{1}<b$, $(q_{1},r_{1})$ est le couple recherché. Si $r_{1}\geqslant b$, soit $q_{2}\in \NN^{*}$ tel que $bq_{2}\leqslant r_{1}$ et on pose $r_{2}=r_{1}-bq_{2}$.\\
Si $r_{2}<b$, le couple $(q_{1}+q_{2},r_{2})$ convient, sinon, on recommence...\\
On construit ainsi deux suites $(q_{n})_{n}$ et $(r_{n})_{n}$ tq. si $r_{n}\geqslant b$ alors $q_{n+1}$ est tele que $bq_{n+1}\leqslant r_{n}$, et $r_{n+1}=r_{n}-bq_{n+1}$\\
La suite $(r_{n})_{n}$ est strictement décroissante dans $\NN$, donc il existe un rang $n$ pour lequel $r_{n}<b$, donc $(r_{n})_{n}$ est une suite finie, et $(q_{1}+...+q_{n},r_{n})$ est le couple recherché.

\subsection{Comentaires-compléments du professeur Z.}

On peut dans cette leçon étudier d'abord les sous groupes de $(\ZZ,+)$, puis définir le $pgcd(a,b)$ et le $ppcm(a,b)$ par :\\
$\forall a,b \in \NN\times \NN^{*}$, $\exists ! d \in \ZZ$ tq. $a\ZZ+b\ZZ=d\ZZ$. $d$ s'appelle le $pgcd$ de $a$ et $b$\\
$\forall a,b \in \NN\times \NN^{*}$, $\exists ! m \in \ZZ$ tq. $a\ZZ \bigcap b\ZZ=m\ZZ$. $m$ s'appelle le $ppcm$ de $a$ et $b$\\
\\
Autre définition possible :\\
$d$ est appelé $pgcd(a,b)$ si(si) $d \vert a,d\vert b$ et si $d' \vert a,d'\vert b$ alors $d'\vert d$\\
$m$ est appelé $ppcm(a,b)$ si(si) $m$ multiple de $a$ et de $b$, et si $m'$ multiple de $a$ et $b$ alors $m'$ multiple de $m$\\
\\
On peut définir voir la division Euclidienne dans $\ZZ$ comme :\\
\textbf{Théorème} : Soient $(a,b)\in \ZZ\times\NN^{*}$. Il existe un unique couple $(q,r)\in \ZZ \times \NN $ tq. $a=bq+r$, avec $0<r \leqslant b$

\end{document}
