1 – Le théorème de la division euclidienne
À l'école primaire, on écrit \(17 = 5 \times 3 + 2\) : « dans \(17\), il y a \(3\) fois \(5\), et il reste \(2\) ». Le reste est toujours plus petit que le diviseur. On étend cette division aux entiers relatifs.
Théorème : Soient \(a \in \mathbb{Z}\) et \(b \in \mathbb{N}^{*}\). Il existe un unique couple \((q\ ;\ r)\) d'entiers relatifs tel que :
\[a = bq + r \quad \text{et} \quad 0 \leq r < b\]
\(q\) est le quotient et \(r\) le reste de la division euclidienne (d.e.) de \(a\) par \(b\).
Remarque : Le théorème s'étend à \(a\) et \(b\) relatifs avec \(0 \leq r < |b|\).
Démonstration
• Existence : Soit \(q = E\left[ \dfrac{a}{b} \right]\) la partie entière de \(\dfrac{a}{b}\) : c'est-à-dire l'entier tel que \(q \leq \dfrac{a}{b} < q + 1\).Comme \(b > 0\), on obtient \(bq \leq a < bq + b\), soit \(0 \leq a - bq < b\).
On pose \(r = a - bq\) : alors \(a = bq + r\) et \(0 \leq r < b\).
• Unicité : Supposons que l'on a l'existence de deux couples d'entiers relatifs \((q\ ;\ r)\) et \((q'\ ;\ r')\) tels que : \[a = bq + r = bq' + r' \quad \text{avec} \quad 0 \leq r < b \quad \text{et} \quad 0 \leq r' < b\] Alors \(b(q - q') = r' - r\), et cela signifie que \(b\) divise \(r' - r\) et donc que \(r' - r\) est un multiple de \(b\).
Comme \(0 \leq r < b\), on a \(-b < -r \leq 0\). En additionnant avec \(0 \leq r' < b\) on obtient \(-b < r' - r < b\).
Mais comme le seul multiple de \(b\) compris entre lui-même et son opposé est \(0\), on a \(r' - r = 0\).
Donc \(r = r'\), puis \(bq = bq'\) et \(q = q'\) car \(b \neq 0\). □
Point de vigilance : le reste est toujours positif ou nul. L'égalité \(-17 = 5 \times (-3) - 2\) n'est pas la division euclidienne de \(-17\) par \(5\) (car \(-2 < 0\)). On écrit \(-17 = 5 \times (-4) + 3\) : le quotient est \(-4\) et le reste \(3\).
Exemple 1 :
Effectuer la division euclidienne de \(2026\) par \(7\), puis celle de \(-2026\) par \(7\).
• \(\dfrac{2026}{7} \approx 289{,}4\) donc \(q = 289\) ; \(7 \times 289 = 2023\) et \(r = 2026 - 2023 = 3\) : \(2026 = 7 \times 289 + 3\) avec \(0 \leq 3 < 7\).
• \(-2026 = 7 \times (-289) - 3\) ne convient pas. On a \(-2026 = 7 \times (-290) + 4\) avec \(0 \leq 4 < 7\) : \(q = -290\) et \(r = 4\).
Exemple 2 :
On a \(107 = 12 \times 8 + 11\). Cette égalité correspond-elle à la d.e. de \(107\) par \(12\) ? par \(8\) ?
• Par \(12\) : \(0 \leq 11 < 12\), donc \(q = 8\) et \(r = 11\).
• Par \(8\) : \(11 \geq 8\), l'égalité ne convient pas. \(107 = 8 \times 13 + 3\) avec \(0 \leq 3 < 8\) : \(q = 13\) et \(r = 3\).
Algorithme : Pour \(a \in \mathbb{N}\) et \(b \in \mathbb{N}^{*}\), on obtient \(q\) et \(r\) en retranchant \(b\) à \(a\) autant de fois que possible (soustractions successives). À chaque tour de boucle, l'égalité \(a = bq + r\) reste vraie et \(r\) diminue de \(b\).
La boucle s'arrête, et à la sortie \(0 \leq r < b\). Par exemple,
La boucle s'arrête, et à la sortie \(0 \leq r < b\). Par exemple,
division(2026, 7) renvoie (289, 3).
def division(a, b):
q, r = 0, a
while r >= b:
r = r - b
q = q + 1
return q, r>>> -2026 // 7, -2026 % 7
(-290, 4)2 – Division euclidienne et divisibilité
Propriété 1 : Soient \(a \in \mathbb{Z}\) et \(b \in \mathbb{N}^{*}\). Alors \(b\) divise \(a\) si et seulement si le reste de la division euclidienne de \(a\) par \(b\) est nul.
Démonstration
Si \(r = 0\), alors \(a = bq\) et \(b \mid a\). Réciproquement, si \(a = bk\) avec \(k \in \mathbb{Z}\), alors \(a = bk + 0\) avec \(0 \leq 0 < b\) : par unicité de la division euclidienne, le reste est \(0\). □
Propriété 2 : Dans la division euclidienne par \(b \in \mathbb{N}^{*}\), il y a \(b\) restes possibles : \(0\ ;\ 1\ ;\ \ldots\ ;\ b - 1\). Tout entier \(n\) s'écrit donc sous l'une des formes \(bk\), \(bk + 1\), …, \(bk + (b - 1)\) avec \(k \in \mathbb{Z}\).
Exemple 3 :
Déterminer l'écriture générale des entiers via leur d.e. par \(b = 2\ ;\ 3\ ;\ 4\).
• Tout entier est pair (\(n = 2k\)) ou impair (\(n = 2k + 1\)).
• Tout entier s'écrit \(3k\), \(3k + 1\) ou \(3k + 2\) avec \(k \in \mathbb{Z}\).
• Tout entier impair s'écrit \(4k + 1\) ou \(4k + 3\). Tout entier pair s'écrit \(4k\) ou \(4k + 2\).
Méthode (disjonction des cas) : pour démontrer une propriété d'un entier \(n\), on distingue les cas suivant le reste de la division euclidienne de \(n\) par un entier \(b\) bien choisi. Dans chaque cas, on écrit \(n = bk + r\) et on calcule.
Exemple 4 :
Démontrer que pour tout entier \(n\), \(n^{2} + 1\) n'est pas divisible par \(3\).
• Si \(n = 3k\) : \(n^{2} + 1 = 9k^{2} + 1 = 3 \times 3k^{2} + 1\) : le reste de la division par \(3\) est \(1\).
• Si \(n = 3k + 1\) : \(n^{2} + 1 = 9k^{2} + 6k + 2 = 3(3k^{2} + 2k) + 2\) : le reste est \(2\).
• Si \(n = 3k + 2\) : \(n^{2} + 1 = 9k^{2} + 12k + 5 = 3(3k^{2} + 4k + 1) + 2\) : le reste est \(2\).
Dans tous les cas, le reste n'est pas nul : \(n^{2} + 1\) n'est jamais divisible par \(3\).
Exemple 5 :
Démontrer que pour tout entier \(n\), le produit \(n(n + 1)(n + 2)\) est divisible par \(3\).
• Si \(n = 3k\), le facteur \(n\) est un multiple de \(3\).
• Si \(n = 3k + 1\), alors \(n + 2 = 3k + 3 = 3(k + 1)\) est un multiple de \(3\).
• Si \(n = 3k + 2\), alors \(n + 1 = 3k + 3 = 3(k + 1)\) est un multiple de \(3\).
Dans tous les cas, l'un des facteurs est multiple de \(3\), donc le produit aussi (propriété 2 de la fiche A1.1).
Remarque : De même, \(n(n + 1)(n + 2)\) est pair (deux entiers consécutifs dont l'un est pair). On montrera au chapitre suivant (théorème de Gauss) qu'un entier divisible par \(2\) et par \(3\) est divisible par \(6\).
