Divisibilité et congruences dans Z : Résumé et révision - Mathématiques

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$ .

Un entier relatif est divisible par…	si et seulement si…
$2$	son chiffre des unités est $0$ , $2$ , $4$ , $6$ ou $8$
$3$	la somme de ses chiffres est divisible par $3$
$4$	le nombre formé par son chiffre des dizaines et celui des unités est divisible par $4$
$5$	son chiffre des unités est $0$ ou $5$
$9$	la somme de ses chiffres est divisible par $9$
$10$	son chiffre des unités est $0$

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$ .

$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) :

$a\equiv a\,\lbrack n\rbrack$
Si $a\equiv b\,\lbrack n\rbrack$	$b\equiv a\,\lbrack n\rbrack$
	Pour tout $k\in\mathbb Z$ : $\begin{aligned} k+a&\equiv k+b\,\lbrack n\rbrack \ ka &\equiv kb\,\lbrack n\rbrack \end{aligned}$
$a$ est congru à $0$ modulo $n$ si et seulement si $a$ est un multiple de $n$
Tout nombre pair est congru à $0$ modulo $2$ , et tout nombre impair est congru à $1$ modulo $2$
Tout entier relatif est congru à son chiffre des unités modulo $10$
Tout entier relatif est congru modulo $n$ au reste de sa division euclidienne par $n$
$a$ et $b$ sont congrus modulo $n$ si et seulement si $a$ et $b$ ont le même reste dans la division euclidienne par $n$
Si $a\equiv r\,\lbrack n\rbrack$ avec $r$ tel que $0 \leq r < n$ , alors $r$ est le reste de la division euclidienne de $a$ par $n$
Si $a\equiv b\,\lbrack n\rbrack$ et $b\equiv c\,\lbrack n\rbrack$	$a\equiv c\,\lbrack n\rbrack$
Si $a\equiv b\,\lbrack n\rbrack$ et $a^{\prime}\equiv b^{\prime}\,\lbrack n\rbrack$	$\begin{aligned} a+a^{\prime}&\equiv b+b^{\prime}\,\lbrack n\rbrack \ a-a^{\prime}&\equiv b-b^{\prime}\,\lbrack n\rbrack \ aa^{\prime}&\equiv bb^{\prime}\,\lbrack n\rbrack \end{aligned}$
Si $a\equiv b\,\lbrack n\rbrack$	Pour tout $p\in\mathbb N$ : $a^p\equiv b^p\,\lbrack n\rbrack$

Pour résoudre une équation du type $ax\equiv b\,\lbrack n\rbrack$ :
nous nous assurons que $b$ , 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 :

$x \text{ modulo }5$	$0$	$1$	$2$	$3$	$4$
$3x \text{ modulo }5$	$0$	$3$	$1$	$\red 4$	$2$