Comment effectuer la division euclidienne d'un entier négatif, par exemple $-17$ par $5$ ?

Le reste doit toujours vérifier $0 \leq r < b$. On cherche le plus grand multiple de 5 inférieur ou égal à $-17$ : c'est $-20 = 5 \times (-4)$. Donc $-17 = 5 \times (-4) + 3$, quotient $-4$ et reste $3$. Écrire $-17 = 5 \times (-3) - 2$ est une égalité vraie, mais ce n'est pas la division euclidienne car $-2 < 0$.

Comment trouver tous les entiers $n$ tels que $n + 3$ divise $2n + 1$ ?

On fait apparaître $n + 3$ : $2n + 1 = 2(n + 3) - 5$. Comme $n + 3$ divise $2(n + 3)$, on a $n + 3 \mid 2n + 1 \iff n + 3 \mid 5$. Les diviseurs de 5 dans $\mathbb{Z}$ sont $-5, -1, 1, 5$, d'où $n \in \{-8, -4, -2, 2\}$. On vérifie : pour $n = 2$, $5 \mid 5$ ; pour $n = -8$, $-5 \mid -15$.

Comment déterminer tous les diviseurs positifs d'un entier ?

On teste les entiers $d$ de 1 jusqu'à $\sqrt n$ : chaque diviseur $d \leq \sqrt n$ fournit le diviseur associé $\frac nd \geq \sqrt n$. Pour $36$ : $d = 1, 2, 3, 4, 6$ conviennent et donnent les couples $(1, 36), (2, 18), (3, 12), (4, 9), (6, 6)$, soit 9 diviseurs positifs. Avec la décomposition en facteurs premiers $36 = 2^2 \times 3^2$, on retrouve $(2 + 1)(2 + 1) = 9$.

Divisibilité dans ℤ

Définitions

Définition 1 — diviseur et multiple. Soit $a, b \in \mathbb{Z}$ . On dit que $b$ divise $a$ , ou que $a$ est un multiple de $b$ , et on note $b \mid a$ , s’il existe un entier $k \in \mathbb{Z}$ tel que $a = kb$ . Exemples : $3 \mid 12$ car $12 = 4 \times 3$ ; $-4 \mid 12$ car $12 = (-3) \times (-4)$ ; $5 \nmid 12$ . Les diviseurs de 12 dans $\mathbb{Z}$ sont $\pm 1, \pm 2, \pm 3, \pm 4, \pm 6, \pm 12$ . Remarques : $1$ et $-1$ divisent tout entier ; tout entier divise $0$ (car $0 = 0 \times b$ ) ; $0$ ne divise que $0$ ; si $b \mid a$ , alors $-b \mid a$ et $b \mid -a$ (on peut se limiter aux diviseurs positifs, sans oublier de rétablir les signes).

Définition 2 — entiers pairs et impairs. Un entier $n$ est pair s’il s’écrit $n = 2k$ ( $k \in \mathbb{Z}$ ) et impair s’il s’écrit $n = 2k + 1$ . Tout entier est pair ou impair, et jamais les deux : c’est la division euclidienne par 2 (Théorème 2).

Définition 3 — congruence modulo $n$ . Soit $n \in \mathbb{N}^*$ . Deux entiers $a$ et $b$ sont congrus modulo $n$ , noté $a \equiv b \ [n]$ , si $n \mid (a - b)$ , ce qui équivaut à : $a$ et $b$ ont le même reste dans la division euclidienne par $n$ . Exemples : $17 \equiv 2 \ [5]$ et $-17 \equiv 3 \ [5]$ . Cette relation, compatible avec l’addition et la multiplication, fait l’objet du chapitre Congruences.

Théorèmes et propriétés

Théorème 1 (propriétés de la divisibilité). (démonstrations exigibles pour 3 et 4) Pour $a, b, c \in \mathbb{Z}$ :

$a \mid a$ (réflexivité).
Si $a \mid b$ et $b \mid c$ , alors $a \mid c$ (transitivité).
Si $a \mid b$ et $a \mid c$ , alors $a \mid (ub + vc)$ pour tous $u, v \in \mathbb{Z}$ (combinaison linéaire). En particulier $a \mid b + c$ et $a \mid b - c$ .
Si $a \mid b$ et $b \mid a$ , alors $b = a$ ou $b = -a$ .
Si $a \neq 0$ et $b \mid a$ , alors $|b| \leq |a|$ : un entier non nul n’a qu’un nombre fini de diviseurs.

Démonstration de 3 : $b = ka$ et $c = k'a$ donnent $ub + vc = (uk + vk')a$ . Démonstration de 4 : si $a = 0$ alors $b = 0$ ; sinon $b = ka$ et $a = k'b$ donnent $kk' = 1$ , donc $k = k' = 1$ ou $k = k' = -1$ .

Attention. $a \mid bc$ n’entraîne pas $a \mid b$ ou $a \mid c$ : $6 \mid 2 \times 3$ mais $6 \nmid 2$ et $6 \nmid 3$ . Ce sera vrai si $a$ est premier (théorème de Gauss, chapitre PGCD).

Théorème 2 (division euclidienne). (démonstration exigible : existence et unicité) Soit $a \in \mathbb{Z}$ et $b \in \mathbb{N}^*$ . Il existe un unique couple $(q, r) \in \mathbb{Z} \times \mathbb{N}$ tel que

$a = bq + r \qquad \text{et} \qquad 0 \leq r < b$

$q$ est le quotient et $r$ le reste de la division euclidienne de $a$ par $b$ .

Démonstration. Existence : les multiples de $b$ partagent $\mathbb{Z}$ en intervalles $[bq\,;b(q + 1)[$ ; il existe donc $q \in \mathbb{Z}$ avec $bq \leq a < b(q + 1)$ , et $r = a - bq$ vérifie $0 \leq r < b$ . Unicité : si $a = bq + r = bq' + r'$ , alors $b(q - q') = r' - r$ avec $-b < r' - r < b$ ; le seul multiple de $b$ strictement compris entre $-b$ et $b$ est 0, donc $r = r'$ puis $q = q'$ .

Exemples : $2024 = 7 \times 289 + 1$ (quotient 289, reste 1) ; $-17 = 5 \times (-4) + 3$ (quotient $-4$ , reste 3 : l’égalité $-17 = 5 \times (-3) - 2$ est vraie mais $-2 < 0$ , ce n’est pas la division euclidienne). On peut aussi diviser par $b \in \mathbb{Z}^*$ quelconque avec la condition $0 \leq r < |b|$ .

# Quotient et reste en Python : // et % suivent la convention 0 <= r < b pour b > 0
a, b = -17, 5
q, r = a // b, a % b      # q = -4, r = 3
print(a == b * q + r)     # True

Théorème 3 (divisibilité et reste). $b \mid a$ si et seulement si le reste de la division euclidienne de $a$ par $b$ est nul.

Théorème 4 (entiers consécutifs). Parmi $k$ entiers consécutifs, l’un exactement est divisible par $k$ . En particulier $n(n + 1)$ est pair et $n(n + 1)(n + 2)$ est divisible par $6$ pour tout entier $n$ .

Démonstration (pour $n(n + 1)$ , par disjonction de cas) : si $n = 2k$ , alors $n(n + 1) = 2k(n + 1)$ ; si $n = 2k + 1$ , alors $n + 1 = 2(k + 1)$ et $n(n + 1) = 2n(k + 1)$ .

Méthodes

Méthode 1 — déterminer les diviseurs d’un entier.

Tester les entiers $d$ tels que $1 \leq d \leq \sqrt n$ .
Pour chaque diviseur $d$ trouvé, noter aussi le diviseur associé $\dfrac nd \geq \sqrt n$ (si $d = \sqrt n$ , il est associé à lui-même).
Pour des diviseurs communs à deux entiers, lister les diviseurs de chacun puis croiser les listes.

Exemple : $n = 36$ , $\sqrt{36} = 6$ : $d = 1, 2, 3, 4, 6$ divisent 36, d’où les neuf diviseurs $1, 2, 3, 4, 6, 9, 12, 18, 36$ . Diviseurs communs de 24 et 36 : $1, 2, 3, 4, 6, 12$ , c’est-à-dire les diviseurs de $12 = \text{PGCD}(24, 36)$ .

def diviseurs(n):
    """Liste triée des diviseurs positifs de n >= 1."""
    petits, grands = [], []
    d = 1
    while d * d <= n:
        if n % d == 0:
            petits.append(d)
            if d != n // d:
                grands.append(n // d)
        d += 1
    return petits + grands[::-1]

print(diviseurs(36))   # [1, 2, 3, 4, 6, 9, 12, 18, 36]

Méthode 2 — se ramener à un diviseur fixe pour résoudre $(n + a) \mid (kn + c)$ .

Faire apparaître $n + a$ : écrire $kn + c = k(n + a) + (c - ka)$ .
Utiliser la combinaison linéaire (Théorème 1) : $(n + a) \mid (kn + c) \iff (n + a) \mid (c - ka)$ .
Lister les diviseurs de $c - ka$ dans $\mathbb{Z}$ (sans oublier les négatifs) et en déduire les valeurs de $n$ .

Exemple : $n + 3 \mid 2n + 1$ : $2n + 1 = 2(n + 3) - 5$ , donc $n + 3 \mid 5$ , soit $n + 3 \in \{-5, -1, 1, 5\}$ et $n \in \{-8, -4, -2, 2\}$ .

Méthode 3 — transférer une divisibilité.

Multiplier l’expression divisible par un entier bien choisi.
Retirer un multiple évident du diviseur et conclure par combinaison linéaire (Théorème 1).
Pour une équivalence, vérifier aussi la réciproque.

Exemple : si $7 \mid 2n + 1$ , alors $7 \mid 4(2n + 1) = 8n + 4 = 7n + (n + 4)$ , donc $7 \mid n + 4$ . Réciproquement, $7 \mid n + 4 \Rightarrow 7 \mid 2(n + 4) - 7 = 2n + 1$ . Ainsi $7 \mid 2n + 1 \iff 7 \mid n + 4$ .

Méthode 4 — raisonner par disjonction de cas.

Écrire l’entier selon ses restes possibles dans une division euclidienne bien choisie ( $n = 2k$ ou $2k + 1$ pour la parité ; $n = 3k$ , $3k + 1$ ou $3k + 2$ modulo 3…).
Traiter chaque cas par le calcul.
Conclure : la propriété est vraie dans tous les cas.

Exemple : reste de $(2k + 1)^2$ par 8 : $(2k + 1)^2 = 4k(k + 1) + 1$ et $k(k + 1)$ est pair (Théorème 4), donc $(2k + 1)^2 = 8m + 1$ : le carré d’un impair a pour reste 1 dans la division par 8. Autre exemple : $n^3 - n = (n - 1)n(n + 1)$ est divisible par 3 comme produit de trois entiers consécutifs.

Méthode 5 — résoudre une équation dans $\mathbb{Z}$ par factorisation.

Factoriser l’équation sous la forme (produit de deux expressions entières) $=$ constante.
Lister les couples de diviseurs de la constante compatibles avec les contraintes (signe, ordre).
Résoudre le petit système obtenu pour chaque couple, puis vérifier.

Exemple : couples $(x, y) \in \mathbb{N}^2$ tels que $x^2 - y^2 = 15$ : $(x - y)(x + y) = 15$ avec $0 < x - y \leq x + y$ , donc $(x - y, x + y) \in \{(1, 15), (3, 5)\}$ , d’où $(x, y) \in \{(8, 7), (4, 1)\}$ .

Définitions

Théorèmes et propriétés

Méthodes

Reste informé