Division Euclidienne
Division euclidienne dans N
Théorème : Existence et Unicité
Étant donnés deux entiers \(a\) et \(b\) positifs, (avec \(b\) non nul), il existe un couple unique \((q,r)\) d'entiers positifs ou nuls tels que : \(a = bq + r\) et\( 0 \leq r < b\)
Définition :
On dit que \(q\) est le quotient et \(r\) le reste de la division euclidienne de \(a\) par \(b.\) Les restes possibles sont les entiers \(0, 1, 2, ..., b - 1.\)
Si \(b \mid a\), alors \(r = 0,\) et réciproquement si \(r = 0, b \mid a.\)
Par conséquent si \(b \not\vert \quad a,\) alors \(0 < r < b,\) et réciproquement, si \(r \neq 0, b \not\vert \quad a.\)
Démonstration : Existence du couple (q, r)
On distingue deux cas.
Premier cas : si \(a < b,\) on prend \(q = 0\) et \(r = a.\) En particulier, si \(a = 0,\) on prend \(q = r = 0.\)
Deuxième cas : si \(a \geq 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 \(r\) tel que : \(r = a - qb.\) On a \(r < b,\) sinon \(a - (q + 1)b\) appartiendrait à \(A\) et serait plus petit que \(r.\) On a donc \(0 \leq a - qb < b.\) On a trouvé un couple d'entiers \((q, r)\) répondant au problème.
\(a = bq + r \quad \textrm {et} \quad 0 \leq r < b.\)
Démonstration : Unicité du couple (q, r)
On suppose l'existence d'un deuxième couple \((q', r')\) répondant au problème. \(a = bq' + r' \quad \textrm {et} \quad 0 \leq r' < b.\)
On en déduit \(bq + r = bq' + r',\) soit \(b(q - q') = (r' - r).\) Des inégalités \(0 \leq r < b\) on déduit \(- b < - r \leq 0,\) et par addition respectivement avec les inégalités \(0 \leq r' < b,\) on déduit des inégalités strictes : \(- b < r' - r < 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 \((q, r).\)
Division euclidienne dans Z
Théorème :
Étant donnés deux entiers \(a\) et \(b,\) (avec \(b\) non nul), il existe un couple unique \((q,r)\) d'entiers tels que : \(a = bq + r \quad \textrm {et} \quad 0 \leq r < \mid b\mid.\)
Remarque :
Nous utiliserons très peu cette division d'entiers relatifs. La plupart du temps nous travaillerons avec des entiers naturels et nous examinerons à part les questions de signe.
Démonstration :
La démonstration examine trois cas suivant les signes de \(a \quad \textrm {et} \quad b\) et utilise le théorème d'existence et d'unicité valable pour les entiers positifs. \(\\\)
Si \(a \geq 0 \quad \textrm {et} \quad b < 0,\)
on peut écrire \(a = (- b)q' + r \quad \textrm {avec} \quad 0 \leq r < \mid b\mid.\) On pose \(q = -q'. \\\)
Si \(a < 0 \quad \textrm {et} \quad b > 0,\)
on peut écrire \(-a = bq' + r' \quad \textrm {soit} \quad a = b(-q') -r' \quad \textrm {avec} \quad 0 \leq r' <b\) et donc \(-b < -r' \leq 0.\) Nous distinguons
--- le cas où \(r' = 0\) et \(a = b(-q'),\) on pose \(r = 0 \quad \textrm {et} \quad q = -q'\)
--- le cas où \(r' \neq 0\) ou encore \(a = b(-1 - q') + (b - r') \quad \textrm {avec} \quad 0 < b - r' < b.\) On pose \(q = -1 - q' \quad \textrm {et} \quad r = b -r'.\\\)
Si \(a < 0 \quad \textrm {et} \quad b < 0,\)
on a \(-a = (-b)q' + r', \quad \textrm {avec} \quad 0 \leq r' < -b.\) Ici encore nous distinguons
--- le cas où \(r' = 0\) où on a \(a = bq'\) ; on pose \(r = 0 \quad \textrm {et} \quad q = q'\)
--- le cas où \(r' \neq 0\), soit \(0 < r' < -b, b < -r' <0, \quad \textrm {et} \quad 0 < -b -r' < -b.\) Alors \(a = bq' - r' = b(q' + 1) + (-b - r') \quad \textrm {avec} \quad 0< -b-r' < \mid b\mid .\) On pose \(q = q' + 1 \quad \textrm {et} \quad r = - b - r'.\)