Si \(a\) et \(b\) sont deux entiers, on dit que \(a\) divise \(b\), ou que \(b\) est divisible par \(a\), s’il existe un entier \(q\) tel que \(b = a \times q\). On dit encore que \(a\) est un diviseur de \(b\), ou que \(b\) est un multiple de a. On le note \(a|b\).
Soient \(a\) et \(b\) deux entiers tel que \(b \ne 0\), Effectuer une division euclidienne, c’est déterminer le quotient \(q\) et le reste \(r\) de la division de \(a\) par \(b\).
I. Division euclidienne dans \( \mathbb{N}\)
Théorème : Existence et Unicité
Soient \(a\) et \(b\) deux entiers et positifs, (avec\(b \ne 0\)), il existe un couple unique \(\left( {q,r} \right)\) d'entiers positifs ou nuls tels que : \(a = bq + r\) et \(0 \le r \prec b\)
On dit que \(q\) est le quotient et \(r\) le reste de la division euclidienne de \(a\) par \(b\).
a) Démonstration : Existence du couple \(\left( {q,r} \right)\)
On distingue deux cas.
1) Si \(a \prec b\). On prend \(q=0\) et \(r=a\). Si \(a=0\), on prendra \(q=r=0\)
2) Si \(a \ge b\), On considère l'ensemble \(A\) des entiers naturels de la forme \(a - mb\) pour \(m\) entier naturel. Cet ensemble est non vide puisqu'il contient \(a\) pour \(m = 0\); il admet donc un plus petit élément tel que : \(a – qb\). On \(r \prec b\) sinon \(a - \left( {q + 1} \right)b\) appartiendrait à \(A\) et serait plus petit que \(r\). On a donc \(0 \le a - qb \prec b\). On a trouvé un couple d'entiers \(\left( {q,r} \right)\) répondant au problème.
\(\left\{ \begin{array}{l}a = bq + r\\0 \le r \prec b\end{array} \right.\)
b) Démonstration : Unicité du couple (q, r)
On suppose l'existence d'un deuxième couple \(\left( {q',r'} \right)\) répondant au problème.
Ie \(\left\{ \begin{array}{l}a = bq' + r'\\0 \le r' \prec b\end{array} \right.\)
On en déduit \(bq + r = \) \(bq' + r'\), soit \(b\left( {q - q'} \right)\) \( = \left( {r' - r} \right)\). Des inégalités\(0 \le r \prec b\), on déduit \( - b \prec - r\) \( \le 0\) et par addition respectivement avec les inégalités \(0 \le r' \prec b\), on déduit des inégalités strictes : \( - b \prec r' - r\) \( \prec b\) et donc que \(r' - r\) est strictement inférieur à \(b\).
Comme \(b\) divise \(r' - r\), il en résulte que \({r' - r = 0}\) et donc que \({q = q'}\).
Il y a donc unicité du couple \(\left( {q,r} \right)\).
II. Division euclidienne dans \( \mathbb{Z}\)
Soient \(a\) et \(b\) deux entiers relatifs tels que : \(b \ne 0\)
Il existe un unique couple \(\left( {q;r} \right)\) tel que :
\(\left\{ \begin{array}{l}a = bq + r\\0 \le r \prec \left| b \right|\end{array} \right.\)
a) Démonstration : Existence du couple \(\left( {q,r} \right)\)
Soit \(A\) l’ensemble des entiers naturels de la forme : \(a - bq\) avec \(q \in \) \( \mathbb{Z}\)
\(a + \left| {ba} \right|\) est element de \(A\) ; donc \(A\) est une partie non vide de \( \mathbb{N}\), qui admet un plus petit élément \(r\).
\(r\) est élément de \(A\) ; donc \(r \ge 0\) et \(r = a - bq\) (\(q \in \) \( \mathbb{Z}\))
De plus, \(r \prec \left| b \right|\) ( sinon \(r - \left| b \right|\) \( = a - bq\) \( - \left| b \right| = a\) \( - bq'\) ; donc \(r - \left| b \right|\) serait un élément de \(A\), plus petit que \(r\) ; c’est-à-dire que \(r\) ne serait plus le plus petit élément de \(A\)).
On déduit qu’il existe un couple \(\left( {q;r} \right)\) de \( \mathbb{Z}\) \( \times \) \( \mathbb{N}\) tel que \(\left\{ \begin{array}{l}a = bq + r\\0 \le r \prec \left| b \right|\end{array} \right.\)
b) Démonstration : unicité du couple \(\left( {q,r} \right)\)
Soient \(\left( {q;r} \right)\) et \(\left( {q';r'} \right)\) deux couples de \( \mathbb{Z}\) \( \times \) \( \mathbb{N}\) tels que \(\left\{ \begin{array}{l}a = bq + r\\a = bq' + r'\end{array} \right.\) et \(\left\{ \begin{array}{l}0 \le r \prec \left| b \right|\\0 \le r' \prec \left| b \right|\end{array} \right.\).
On a : \(0 = b\left( {q' - q} \right)\) \( + \left( {r' - r} \right)\); donc \(\left| b \right|\left| {q' - q} \right|\) \( = \left| {r' - r} \right|\) ;
Or \( - \left| b \right| \prec r' - \) \(r \prec \left| b \right|\); donc \(\left| {r' - r} \right| \prec \left| b \right|\)
On en déduit que \(\left| {q' - q} \right| = 0\) ( si \(\left| {q' - q} \right| \ge 1\), on aurait \(\left| b \right|\left| {q' - q} \right|\) \( \ge \left| q \right|\)).
De plus \(\left| {r' - r} \right| = \left| b \right|\) \(\left| {q' - q} \right|\) ; donc \({q' = q}\) et \({r' = r}\)
On déduit qu’il existe un couple unique \(\left( {q;r} \right)\) de \( \mathbb{Z}\) \( \times \) \( \mathbb{N}\) tel que \(\left\{ \begin{array}{l}a = bq + r\\0 \le r \prec \left| b \right|\end{array} \right.\)
