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é
- 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 :
et
.
$ 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é
- $ 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.