Divisibilité et congruences

1. Division euclidienne

Définition

Soient $a$ et $b$ deux entiers relatifs tels qu'il existe un entier relatif $k$ tel que $a=bk$ .

On dit alors que :

$b$ divise $a$ ;
$b$ est un diviseur de $a$ ;
$a$ est un multiple de $b$ .

Ceci se note $b|a$

Exemple

$15=3\times 5$ donc :

3 divise 15.
3 est un diviseur de 15.
15 est un multiple de 3.

Remarques

0 est un multiple de tout entier relatif.
1 et -1 sont des diviseurs de tout entier relatif.
$a$ et $-a$ ont les mêmes diviseurs.

Propriétés

Si $a$ divise $b$ et $b$ divise $a$ , alors $a$ et $b$ sont égaux ou opposés.
Si $a$ divise $b$ et $b$ divise $c$ , alors $a$ divise $c$ .
Si $c$ divise $a$ et $c$ divise $b$ , alors $c$ divise toute combinaison linéaire de $a$ et $b$ (c'est-à-dire tout nombre de la forme $au+bv ; u\in \mathbb{Z}, v\in \mathbb{Z}$ ).

Théorème et définitions

Division euclidienne dans $\mathbb{Z}$

Soient $a$ et $b$ deux entiers relatifs avec $b\neq 0$ .

Il existe un et un seul couple d'entiers relatifs $\left(q,r\right)$ tels que :

$a=bq+r$ et $0 \leqslant r < |b|$ .

$q$ et $r$ s'appelle respectivement le quotient et le reste de la division euclidienne de $a$ par $b$ .

Exemple

-14=3 $\times$ (-5)+1 et 0 $\leqslant$ 1 $<$ 3

La division euclidienne de -14 par 3 donne un quotient de -5 est un reste de 1.

Remarques

Attention ! Ne pas oublier la condition $0 \leqslant r < |b|$ . La seule égalité $a=bq+r$ ne suffit pas à prouver que $q$ et $r$ sont les quotient et reste dans la division euclidienne de $a$ par $b$ .
$a$ est divisible par $b$ si et seulement si le reste de la division de $a$ par $b$ est égal à zéro.

2. Congruences

Définition

On dit que deux entiers relatifs $a$ et $b$ son congrus modulo $n$ ( $n\in \mathbb{N}^*$ ) et l'on écrit $a\equiv b \left[n\right]$ si et seulement si $a$ et $b$ ont le même reste dans la division par $n$ .

Exemple

$18\equiv 23 \left[5\right]$ car 18 et 23 ont tous les deux 3 comme reste dans la division par 5.

Propriétés

$a\equiv b \left[n\right]$ si et seulement si $n$ divise $a-b$ en particulier $a\equiv 0 \left[n\right]$ si et seulement si $n$ divise $a$ .
Si $a\equiv b \left[n\right]$ et $b\equiv c \left[n\right]$ , alors $a\equiv c \left[n\right]$ .

Propriétés (Congruences et opérations)

Soient quatre entiers relatifs $a, b, c, d$ tels que $a\equiv b \left[n\right]$ et $c\equiv d \left[n\right]$ . Alors :

$a+c\equiv b+d \left[n\right]$ et $a-c\equiv b-d \left[n\right]$ .
$ac\equiv bd \left[n\right]$ .
$ka\equiv kb \left[n\right]$ pour tout entier relatif $k$ .
$a^{m}\equiv b^{m} \left[n\right]$ pour tout entier naturel $m$ .

Propriété

$r$ est le reste de la division euclidienne de $a$ par $b$ si et seulement si :

$\left\{ \begin{matrix} r\equiv a \left[b\right] \\ r < |b| \end{matrix}\right.$

Exemple

On cherche à déterminer le reste de la division euclidienne de $2009^{2009}$ par 5.

$2009\equiv -1 \left[5\right]$ car 2009-(-1)=2010 est divisible par 5.

Donc :

$2009^{2009}\equiv \left(-1\right)^{2009} \left[5\right]$ c'est-à-dire $2009^{2009}\equiv -1 \left[5\right]$

Or $-1\equiv 4 \left[5\right]$ donc $2009^{2009}\equiv 4 \left[5\right]$

Comme $0\leqslant 4 < 5$ , le reste de la division euclidienne de $2009^{2009}$ par 5 est 4.

1. Division euclidienne

Définition

Exemple

Remarques

Propriétés

Théorème et définitions

Exemple

Remarques

2. Congruences

Définition

Exemple

Propriétés

Propriétés (Congruences et opérations)

Propriété

Exemple

Dans ce chapitre...

Exercices

Méthodes

VOIR AUSSI...