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.

Maths-cours

COURS & EXERCICES DE MATHÉMATIQUES

Maths-cours

Divisibilité et congruences

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 :

Maths-cours

Divisibilité et congruences

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 :

Cours

Exercices

Méthodes