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