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.