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

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

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

Ce contenu est réservé à nos inscrits. Il reste 50% à lire.

Inscrivez-vous gratuitement pour lire la suite

Inscrivez-vous pour lire la suite et accéder à nos vidéos, quiz, exercices, méthodes… Tout ce qu’il faut pour augmenter sa moyenne. 😉

Déjà un compte ? Je me connecte