Fiche de révision : Divisibilité et congruences dans Z

Divisibilité dans $\mathbb Z$ et division euclidienne

Nous étendons ici les définitions et les propriétés connues depuis le collège à l’ensemble des entiers relatifs.

• Soit $a$ et $b$ des entiers relatifs, $b$ étant non nul.
• On dit que $b$ est un diviseur de $a$, et on note $b\vert a$, lorsqu’il existe un entier relatif $k$ tel que $a=k\times b$.
• On peut dire aussi que :
• $a$ est divisible par $b$ ;
• $a$ est un multiple de $b$ ;
• $b$ divise $a$.
• Les diviseurs de $1$ ou $-1$ sont $-1$ et $1$.
• $1$ et $-1$ sont des diviseurs de n’importe quel entier relatif.
• $0$ est multiple de n’importe quel entier relatif, et ne divise aucun entier relatif.
• Les entiers relatifs pairs sont les multiples de $2$, c’est-à-dire ceux qui s’écrivent sous la forme $2k$ avec $k\in\mathbb Z$.
• Les entiers relatifs impairs sont les entiers qui ne sont pas multiples de $2$, c’est-à-dire ceux qui s’écrivent sous la forme $2k+1$ avec $k\in\mathbb Z$.

• Soit $a$, $b$ et $c$ des entiers relatifs.
• Si $b$ divise $a$ et si $c$ divise $b$, alors $c$ divise $a$.
• Si $c$ divise $a$ et $b$, alors pour tous les entiers relatifs $n$ et $n^{\prime}$, $c$ divise $na+n^{\prime} b$.
• Autrement dit, si $c$ divise $a$ et $b$, alors il divise toutes les combinaisons linéaires entières de $a$ et $b$.
• Soit $a$ un entier relatif et $b\neq 0$ un entier naturel.
• Il existe un unique couple $(q, r)$, avec $q\in \mathbb Z$ et $r\in \mathbb N$, tels que : $a=bq+r \text{ et } 0\leq r < b$.
• L’entier relatif $a$ est le dividende et $b$ est le diviseur.
• L’entier relatif $q$ s’appelle le quotient et $r$ s’appelle le reste de la division euclidienne de $a$ par $b$.

Congruences dans $\mathbb{Z}$

• $n$ désigne un entier naturel non nul, $a$ et $b$ sont des entiers relatifs.
• On dit que $a$ et $b$ sont congrus modulo $n$ lorsque la différence $a - b$ est un multiple de $n$, ou bien que $n$ divise $a - b$, ce qui est équivalent.
• Les notations possibles sont :
• $a\equiv b\ \text{mod}\,n$,
• ou $a\equiv b\,(n)$,
• ou encore $a\equiv b\,\lbrack n\rbrack$.
• Nous avons les propriétés suivantes ($a$, $a^\prime$, $b$, $b^\prime$ et $c$ des entiers relatifs, $n$ un entier naturel) :

• Pour résoudre une équation du type $ax\equiv b\,\lbrack n\rbrack$ :
• nous nous assurons que $b<n$, puis nous nous intéressons aux valeurs de $x$ comprises entre $0$ et $n-1$ ;
• nous étudions ensuite, pour chaque cas, $ax \text{ modulo } n$ et nous remplissons un tableau avec les résultats trouvés ;
• nous lisons dans le tableau réalisé, à la colonne concernée, l’ensemble solution cherché.
• Ainsi, par exemple, pour l’équation $3x \equiv 4\,\lbrack 5\rbrack$, nous obtenons le tableau suivant :

• $S=\lbrace 3+5k\ ;\,k\in\mathbb Z\rbrace$.