2

Division euclidienne

$a$ s’appelle le dividende et $b$ le diviseur dans la division euclidienne de $a$ par $b$.

Soient $a$ et $b$ deux entiers naturels avec $b\ne 0$. $b|a$ si, et seulement si, le reste de la division euclidienne de $a$ par $b$ est nul.

Si $x⩾0$, alors $\text{E}(x)⩾0$.

DÉMONSTRATION

Soient $a$ et $b$ deux entiers naturels avec $b$ non nul.

Existence

La partie entière d’un réel $x$ est l’entier relatif $n$ tel que $n⩽x<n+1$. On note $n=\text{E}(x)$. Posons alors $q=\text{E}\left(\frac{a}{b}\right)$. On a $\frac{a}{b}⩾0$ donc $q=\text{E}\left(\frac{a}{b}\right)⩾0$. Par définition, $q⩽\frac{a}{b}<q+1$ ou encore $qb⩽a<b\left(q+1\right)$ puisque $b$ est strictement positif.
Autrement dit, on a $bq-bq⩽a-bq<bq+b-bq$ soit enfin $0⩽a-bq<b$.
En posant $r=a-bq$, on a, d’une part, $a=bq+r$ et, d’autre part, $0⩽r<b$. On a donc bien prouvé l’existence d’un couple $(q;r)$ vérifiant les conditions demandées.

Unicité

Supposons qu’il existe deux couples d’entiers naturels $(q;r)$ et $(q^{\prime };r^{\prime })$ vérifiant les deux conditions, c’est-à-dire
$\{\begin{array}{l}a=qb+r\text{ avec }0⩽r<b\\ a=q^{\prime }b+r\text{ avec }0⩽r^{\prime }<b\end{array}$. On a alors :

• $qb+r=q{b}^{\prime }+r^{\prime }$, c’est-à-dire $b\left(q^{\prime }-q\right)=r-r^{\prime }$ et donc $b|\left(r-r^{\prime }\right)$.
• $0⩽r<b$ et, puisque $0⩽r^{\prime }<b$, on a $-b<-r^{\prime }⩽0$.

Ainsi, $b|\left(r-r^{\prime }\right)$ avec $-b<r-r^{\prime }<b$ donc $r-r^{\prime }=0$ et $r=r^{\prime }$.
On a alors $q^{\prime }-q=0$ donc $q^{\prime }=q$. D'où l'unicité.

DÉMONSTRATION

Soit $a$ un entier.
En effectuant la division euclidienne de $a$ par $b$ non nul, il existe deux entiers naturels $q$ et $r$ tels que $a=bq+r$ avec $0⩽r<b$.
Par unicité du quotient et du reste $a=bq$ ou $a=bq+1$ ou $a=bq+2$ ou $a=bq+3$ ... ou $a=bq+(b-1)$.

Ainsi, dans la division par $2$, le reste est $0$ ou $1$.
Tout entier s’écrit sous la forme $2k$ ou $2k+1$.
On retrouve donc qu’un entier est pair ou impair.

Soit $n$ un entier naturel. Posons $\text{A}=n(n-2)(n+2)$. Démontrer que $\text{A}$ est un multiple de $3$.

Exemple

Sachant que $524=30\times 17+14$, on a $-524=-30\times 17-14$.
Le reste ne peut pas être négatif donc il ne peut pas valoir $-14$.
On écrit $-524=-30\times 17-17+17-14$ soit $-524=-31\times 17+3$.
Le reste de la division euclidienne de $-524$ par $17$ est $3$ et le quotient est $-31$.

On définit de même la division euclidienne d’un entier relatif $a$ par un relatif non nul $b$ : il existe un unique couple d’entiers $(q;r)$ tel que $a=bq+r$ et $0⩽r<|b|$.

Dans la division euclidienne de $-37$ par l’entier naturel non nul $b$, le reste est $14$.
Quelles sont les valeurs possibles du diviseur et du quotient ?