Division euclidienne dans Z

I. Définition / Théorème de la division euclidienne

Soit $a$ un entier relatif et $b$ un entier naturel non nul.

On appelle division euclidienne de $a$ par $b$ l’opération qui, au couple $(a, b)$, associe l’unique couple d’entiers relatifs $(q, r)$ tel que :

$a = bq + r$ avec $0 \leq r \lt b$

$a$ est le dividende, $b$ est le diviseur, $q$ est le quotient, $r$ est le reste.

Démonstration

1. Montrons l’existence du couple $(q, r)$ pour $a \in \mathbb{Z}$ et $b \in \mathbb{N}^*$.

Pour $a \geq 0$ :

Soit $E$ l’ensemble des entiers $e$ tels que $be \gt a$.

$E$ n’est pas vide, car :

$b \geq 1 \Rightarrow b(a + 1) \geq a + 1 \Rightarrow b(a + 1) \gt a\Rightarrow a + 1 \in E$.

$E$ est une partie non vide de $\mathbb{N}$, donc $E$ admet un plus petit élément $m$ tel que :

$bm \gt a$ et $b(m - 1) \leq a$.

On pose alors $q = m - 1$, d'où :

$bq \leq a \lt b(q + 1) \Rightarrow 0 \leq a - bq \lt b$.

En posant $r = a - bq$, on obtient bien :

$a = bq + r$ avec 0 \leq r < b .

Il existe donc un couple $(q, r)$ tel que :

$a = bq + r$ avec $0 \leq r \lt b$.

Pour $a \lt 0$ :

On pose $a' = a(1 - b)$.

$b \geq 1 \Rightarrow -b \leq -1 \Rightarrow 1 - b \leq 0$.

On a alors $a(1 - b) \geq 0$, soit $a' \geq 0$.

On peut alors utiliser le cas $a \geq 0$ avec $a'$ et $b$.

Il existe un couple $(q', r)$ tel que :

$a' = bq' + r$ avec $0 \leq r \lt b$.

En revenant à $a$, on a alors :

$a(1 - b) = bq' + r \Rightarrow q - ab = bq' + r \Rightarrow a = b(q' + a) + r$.

En posant $q = q' + a$, on obtient alors :

$a = bq + r$ avec $0 \leq r \lt b$.

2. Montrons l’unicité du couple $(q, r)$.

On suppose qu’il existe deux couples $(q, r)$ et $(q', r')$ tels que :

$a = bq + r = bq' + r'$ avec 0 \leq r < b et $0 \leq r' \lt b$.

$bq + r = bq' + r' \Rightarrow b(q - q') = r' - r$.

Or, $-b \lt r' - r \lt b$.

$b$ divise alors $(r' - r)$, qui est compris strictement entre $-b$ et $b$, donc $r' - r = 0$, d’où $r = r'$.

Cela entraîne alors $q' = q$.

Le couple $(q, r)$ est unique.

Remarque

La condition $0 \leq r \lt b$ assure l’unicité du couple $(q, r)$.

II. Des exemples rédigés et des méthodes

1) Savoir utiliser une égalité du type $a = bk + m$

Sachant que $38 367 = 152 \times 251 + 215$, effectuer, sans calculatrice et sans poser l’opération, la division euclidienne de $38 367$
a) par $251$
b) par $152$

Solution :

a) $0 \lt 215 \lt 251$, donc dans la division euclidienne de $38 367$ par $251$, le quotient est $152$ et le reste $215$.

b) $215 = 152 + 63$, donc
$38 367 = 152 \times 251 + 152 + 63$
$= 152 \times 252 + 63$

Or $0 \lt 63 \lt 152$, donc dans la division euclidienne de $38 367$ par $152$, le quotient est $252$ et le reste $63$.

2) Déterminer le reste d’une division

$n$ désigne un entier naturel non nul.
Quel est le reste dans la division euclidienne :
a) de $(n+2)^2$ par $(n+4)$ ?
b) de $2n^2 + n$ par $(n+1)$ ?

Solution :

a) $(n+2)^2 = n^2 + 4n + 4 = (n+4)n + 4$
avec $0 \lt 4 \lt n+4$ (car $n \gt 0$).
Donc cette division a pour reste 4.

b) $2n^2 + n = 2n^2 + 2n - n - 1 + 1$
$= (n+1)(2n - 1) + 1$
Le reste est donc 1.

3) Utiliser les restes d’une division

$n$ désigne un entier relatif et $A = n(n^2 +5)$.
Démontrer que l’entier $A$ est divisible par 3.

Solution :

Les restes possibles dans la division euclidienne de $n$ par 3 sont $0$, $1$ et $2$.
Donc $n$ s’écrit sous l’une des formes suivantes :

$n = 3k$ ; $n = 3k +1$ ; $n = 3k +2$ avec $k \in \mathbb{Z}$.

1er cas : $n = 3k$
Alors $n^2 +5 = (3k)^2 + 5 = 9k^2 + 5$.
$3$ divise $9k^2$, donc $3$ divise $n(n^2 + 5)$.

2ᵉ cas : $n = 3k +1$
Alors :
$n^2 +5 = (3k +1)^2 + 5 = 9k^2 + 6k + 6 = 3(3k^2 + 2k + 2)$
Or, $3k^2 + 2k + 2$ est un entier relatif, donc $3$ divise $n^2 +5$, et donc $3$ divise $n(n^2 +5)$.

3ᵉ cas : $n = 3k +2$
Alors :
$n^2 +5 = (3k +2)^2 + 5 = 9k^2 + 12k + 9 = 3(3k^2 + 4k + 3)$
Or, $3k^2 + 4k + 3$ est un entier relatif, donc $3$ divise $n^2 +5$, et donc $3$ divise $n(n^2 +5)$.

Conclusion :

Les trois cas ci-dessus permettent de conclure que, pour tout entier relatif $n$, $A$ est divisible par 3.