Divisibilité et congruences dans Z

information-icon

Si tu es un lycéen en terminale, tu dois déjà avoir planifié tes révisions pour ton baccalauréat 2024. Si ce n’est pas le cas, tu peux te baser sur notre programme de révision en le planifiant en fonction des dates du bac 2024 ou des coefficients des matières … 💪

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

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

$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$
  • $S=\lbrace 3+5k\ ;\,k\in\mathbb Z\rbrace$.