Divisibilité

La divisibilité constitue le véritable point de départ de la théorie des nombres, car elle transforme les entiers en un système doté de structure : on ne considère plus les nombres comme de simples « quantités », mais comme des éléments qui s’imbriquent ou non les uns avec les autres. À l’aide d’une seule relation, $a\mid b$ , il est possible d’exprimer aussi bien des critères de simplification et de factorisation que le cœur de certains procédés, tels que l’algorithme d’Euclide, qui permet de calculer des plus grands communs diviseurs en quelques secondes, même pour des nombres de grande taille. En outre, elle constitue la base technique d’idées qui apparaissent de manière récurrente en mathématiques appliquées et en informatique : congruences, arithmétique modulaire, validations, codes, et (ultérieurement) cryptographie. Maîtriser la divisibilité revient, en essence, à apprendre à détecter des motifs invisibles dans les entiers et à les transformer en procédures qui fonctionnent toujours.

Objectifs d’apprentissage
À l’issue de ce support, l’étudiant sera capable de :

Comprendre la relation de divisibilité entre nombres entiers.
Comprendre la définition de la divisibilité et ses propriétés.
Développer des démonstrations mathématiques de résultats et de théorèmes liés à la divisibilité.

INDEX DES CONTENUS
Définition de la divisibilité
Propriétés fondamentales de la divisibilité
Exercices proposés

Définition de la divisibilité

L’idée informelle de « a divise b » devient précise lorsqu’on l’exprime comme une relation entre entiers. Nous dirons qu’un entier $a$ divise un entier $b$ si $b$ peut s’écrire comme un multiple exact de $a$ . Cette définition constitue la base du reste de ce support, car elle transforme des énoncés du type « s’emboîte exactement » en un critère vérifiable.

Définition. Soient $a,b\in\mathbb{Z}$ avec $a\neq 0$ . On dit que $a$ divise $b$ , et l’on écrit $a\mid b$ , si et seulement s’il existe un entier $k\in\mathbb{Z}$ tel que $b=ka$ . Dans le cas contraire, on écrit $a\nmid b$ .

$a\mid b := (\exists k \in \mathbb{Z})(b = ka )$

Dans cette définition, le nombre $k$ est appelé quotient (ou facteur) associé à la divisibilité. Par exemple, affirmer $6\mid 42$ équivaut à affirmer qu’il existe $k\in\mathbb{Z}$ tel que $42=6k$ ; dans ce cas, il suffit de prendre $k=7$ .

Il est important de considérer

La condition $a\neq 0$ est essentielle. En effet, si l’on tentait d’autoriser $a=0$ , la condition de divisibilité exigerait qu’il existe $k\in\mathbb{Z}$ tel que $b=0\cdot k$ . Or $0\cdot k=0$ pour tout $k$ , de sorte que la seule possibilité serait $b=0$ . Dans ce cas, il n’y aurait pas de $k$ « déterminé » par la relation, puisque tout $k\in\mathbb{Z}$ satisfait $0=0\cdot k$ . Autrement dit, l’expression informelle $k=b/a$ devient $k=0/0$ , ce qui n’est pas défini. Afin d’éviter cette dégénérescence (où la notion de quotient cesse d’être significative), on impose $a\neq 0$ . Pour cette raison, la relation $0\mid b$ n’est pas considérée comme valide.
En revanche, $a\mid 0$ est vrai pour tout $a\in\mathbb{Z}$ avec $a\neq 0$ , car il suffit de prendre $k=0$ et l’on a bien $0=a\cdot 0$ .

De cette définition découle une équivalence que nous utiliserons de manière récurrente : dire que $a\mid b$ revient à dire que $b$ appartient à l’ensemble des multiples entiers de $a$ , c’est-à-dire $b\in a\mathbb{Z}$ , où $a\mathbb{Z}=\{ak:\,k\in\mathbb{Z}\}$ . Cette manière de l’écrire souligne que la divisibilité n’est pas un « artifice », mais une façon de décrire des sous-ensembles hautement structurés à l’intérieur de $\mathbb{Z}$ .

Propriétés fondamentales de la divisibilité

Réflexivité : $a\mid a$ .
Démonstration:
$\begin{array}{rll} (1)&\vdash a=ka \leftrightarrow k=1 &\text{; Élément neutre multiplicatif dans $\mathbb{Z}$}\\ (2)&\vdash(\exists k \in \mathbb{Z})(a=ka) &\text{; Intro. existentielle (1)}\\ (3) &\vdash a \mid a &\text{; Déf. de la divisibilité (2)} \\ &\blacksquare & \end{array}$
Transitivité : si $a\mid b$ et $b\mid c$ , alors $a\mid c$ .
Démonstration:
$\begin{array}{rll} (1)& \{a\mid b , b\mid c\} \vdash (\exists k_1\in\mathbb{Z})(b=k_1a) &\text{; Déf. de la divisibilité, présomption}\\ (2)& \{a\mid b , b\mid c\} \vdash (\exists k_2\in\mathbb{Z})(c=k_2b) &\text{; Déf. de la divisibilité, présomption}\\ (3)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})(b=k_1a \wedge c=k_2b) &\text{; $\exists$-compactification (1,2)}\\ (4)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})(k_2b=k_1k_2a \wedge c=k_2b) &\text{; De (3)}\\ (5)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})( c=k_1k_2a) &\text{; De (4)}\\ &\text{Algèbre à l’intérieur du quantificateur}& \\ (6)& \{a\mid b , b\mid c\} \vdash (\exists k\in\mathbb{Z})( c=ka) &\text{; De (5)}\\ &\text{Clôture de $\mathbb{Z}$ pour la multiplication}& \\ (7)& \{a\mid b , b\mid c\} \vdash a\mid c &\text{; Déf. de la divisibilité (6)}\\ (8)& \vdash (a\mid b \wedge b\mid c) \rightarrow a\mid c &\text{; $\wedge$-TD (7)}\\ &\blacksquare& \end{array}$
Compatibilité avec l’addition et la soustraction : si $a\mid b$ et $a\mid c$ , alors $a\mid (b+c)$ et $a\mid (b-c)$ .
Démonstration:
$\begin{array}{rll} (1)&\{a\mid b, a\mid c\}\vdash (\exists k_1 \in \mathbb{Z})(b=k_1 a) &\text{; Déf. de la divisibilité, présomption}\\ (2)&\{a\mid b, a\mid c\}\vdash (\exists k_2 \in \mathbb{Z})(c=k_2 a) &\text{; Déf. de la divisibilité, présomption}\\ (3)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b=k_1 a \wedge c=k_2 a) &\text{; $\exists$-compactification (1,2)}\\ (4)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b+c= (k_1+k_2)a) &\text{; De (3)}\\ &\text{Algèbre à l’intérieur du quantificateur.}& \\ (5)&\{a\mid b, a\mid c\}\vdash (\exists k \in \mathbb{Z})(b+c= ka) &\text{; De (4)}\\ &\text{Clôture de $\mathbb{Z}$ pour l’addition.}& \\ (6)&\{a\mid b, a\mid c\}\vdash a\mid (b+c) &\text{; Déf. de la divisibilité (5)}\\ (7)&\vdash (a\mid b \wedge a\mid c) \rightarrow a\mid (b+c) &\text{; $\wedge$-TD (6)}\\ (8)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b-c= (k_1-k_2)a) &\text{; De (3)}\\ &\text{Algèbre à l’intérieur du quantificateur.}& \\ (9)&\{a\mid b, a\mid c\}\vdash (\exists \overline{k} \in \mathbb{Z})(b-c= \overline{k}a) &\text{; De (8)}\\ &\text{Clôture de $\mathbb{Z}$ pour la soustraction.}& \\ (10)&\{a\mid b, a\mid c\}\vdash a\mid (b-c) &\text{; Déf. de la divisibilité (9)}\\ (11)&\vdash (a\mid b \wedge a\mid c) \rightarrow a\mid (b-c) &\text{; $\wedge$-TD (10)}\\ (12)&\vdash (a\mid b \wedge a\mid c) \rightarrow \left(a\mid (b+c) \wedge a\mid (b-c)\right) &\text{; $\wedge$-intro. dans le conséquent (7,11) }\\ &\blacksquare& \end{array}$
Compatibilité avec les produits : si $a\mid b$ , alors $a\mid (bc)$ pour tout $c\in\mathbb{Z}$ .
Démonstration:
$\begin{array}{rll} (1)& \{a\mid b\}\vdash (\exists k\in\mathbb{Z})(b=ka) &\text{; Déf. de la divisibilité, présomption}\\ (2)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (\exists k\in\mathbb{Z})(cb=cka) &\text{; De (1), $\forall$-intro. (c arbitraire)}\\ &\text{Algèbre dans }\mathbb{Z}\text{ à l’intérieur du quantificateur existentiel.}&\\ (3)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (\exists \overline{k}\in\mathbb{Z})(cb=\overline{k}a) &\text{; De (2), clôture : }\overline{k}=ck\\ (4)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (a \mid cb) &\text{; Déf. de la divisibilité (3)}\\ (5)& \vdash a\mid b \rightarrow \left(\forall c \in \mathbb{Z}\right) (a \mid cb) &\text{; TD (4)}\\ &\blacksquare& \end{array}$

Théorème : borne du diviseur

Si $b\neq 0$ et $a\mid b$ , alors $|a|\le |b|$ .

Démonstration :

$\begin{array}{rll} (1) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash b \neq 0 & \text{; Présomption} \\ (2) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (b=ka) & \text{; Déf. de la divisibilité, présomption} \\ (3) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (|b|=|k||a|) & \text{; Prop. de la valeur absolue, de (2)} \\ (4) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (k\neq 0 \wedge |b|=|k||a|) & \text{; De (1,3)} \\ (5) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (1\le |k| \wedge |b|=|k||a|) & \text{; De (4), si }k\neq 0\Rightarrow |k|\ge 1 \\ (6) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash |a|\le |b| & \text{; De (5)} \\ &\blacksquare& \end{array}$

Exercices proposés

Montrez que le théorème « borne du diviseur » n’est pas nécessairement vrai si $b=0$
Considérons un ensemble $A$ et une relation $\rho$ sur cet ensemble. Si les éléments $x,y\in A$ sont tels que $x$ est relié à $y$ par $\rho$ , alors on écrit $x\rho y$ . La relation $\rho$ est dite d’ordre partiel sur $A$ si :
a) $(\forall x\in A) (x\rho x)$ ,
b) $(\forall x,y\in A) ( (x\rho y \wedge y\rho x) \rightarrow x=y)$
c) $(\forall x,y,z\in A) ( (x\rho y \wedge y\rho z) \rightarrow x\rho z)$ .
Démontrez que la relation de divisibilité est une relation d’ordre partiel sur les entiers.
Démontrez par induction que si $a\mid b_1, a\mid b_2, \cdots, a\mid b_n$ , alors $a\mid \sum_{i=1}^n b_i x_i$ pour tout ensemble $\{x_i\}_{i=1}^n \subset \mathbb{Z}$ . De plus, démontrez que si $a\mid b_i$ , avec $i\in \{1,2,3,\cdots, n\}$ et que $c$ peut être écrit comme une combinaison linéaire de ces $b_i$ , alors $a\mid c$ .
Si $a\neq 0$ , montrez que l’ensemble $\{x\;:\; d\mid a\}$ est un ensemble fini.
Considérez un $n\in\mathbb{Z}^+$ fixé, et soit
$S=\{d\,:\,d\in\mathbb{Z}^+ \wedge d\mid n\}$
Démontrez :
1. $d\in S \leftrightarrow n/d\in S$
2. Si les éléments de $S$ sont disposés par ordre croissant : $1=d_1 \lt d_2 \lt \cdots \lt d_t =n$ , alors les éléments correspondants $n\mid d_i$ avec $i \in \{1,2,\cdots, t\}$ sont en ordre décroissant.
Supposons que $a,b\in\mathbb{Z}^+$ et $ab=c$ . Démontrez que $\min\{a,b\}\le \sqrt{c}$ .
Un entier n est dit pair si $2\mid n$ , et impair si $2\nmid n$ . Démontrez que la somme et la différence de :
1. deux nombres pairs est un nombre pair.
2. deux nombres impairs est un nombre pair.
3. d’un nombre pair et d’un nombre impair est un nombre impair.
Si $n$ est un nombre impair distinct de $\pm 1$ , démontrez que $n$ ne peut pas diviser deux nombres pairs consécutifs.
Soient $a,b,n\in\mathbb{Z}$ tels que $|a-b|\lt |n|$ . Démontrez que $n$ ne peut diviser ni $a$ ni $b$ .
Supposons que $a\in\mathbb{Z}$ . Démontrez que :
1. $(\forall n \in \mathbb{Z})(a\mid n) \leftrightarrow a=\pm 1$
2. $(\forall n \in \mathbb{Z})(n\mid a) \leftrightarrow a=0$
Soient $a,b,c\in\mathbb{Z}$ et supposons que $c\neq 0$ . Montrez que $ac\mid bc$ implique $a\mid b$

Qu’est-ce que la divisibilité ?