Divisibilité et congruences
1. Division euclidienne
Définition
Soient et deux entiers relatifs tels qu'il existe un entier relatif tel que .
On dit alors que :
divise ;
est un diviseur de ;
est un multiple de .
Ceci se note
Exemple
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.
et ont les mêmes diviseurs.
Propriétés
Si divise et divise , alors et sont égaux ou opposés.
Si divise et divise , alors divise .
Si divise et divise , alors divise toute combinaison linéaire de et (c'est-à-dire tout nombre de la forme ).
Théorème et définitions
Division euclidienne dans
Soient et deux entiers relatifs avec .
Il existe un et un seul couple d'entiers relatifs tels que :
et .
et s'appelle respectivement le quotient et le reste de la division euclidienne de par .
Exemple
-14=3(-5)+1 et 013
La division euclidienne de -14 par 3 donne un quotient de -5 est un reste de 1.
Remarques
Attention ! Ne pas oublier la condition . La seule égalité ne suffit pas à prouver que et sont les quotient et reste dans la division euclidienne de par .
est divisible par si et seulement si le reste de la division de par est égal à zéro.
2. Congruences
Définition
On dit que deux entiers relatifs et son congrus modulo ( ) et l'on écrit si et seulement si et ont le même reste dans la division par .
Exemple
car 18 et 23 ont tous les deux 3 comme reste dans la division par 5.
Propriétés
si et seulement si divise en particulier si et seulement si divise .
Si et , alors .
Propriétés (Congruences et opérations)
Soient quatre entiers relatifs tels que et . Alors :
et .
.
pour tout entier relatif .
pour tout entier naturel .
Propriété
est le reste de la division euclidienne de par si et seulement si :
Exemple
On cherche à déterminer le reste de la division euclidienne de par 5.
car 2009-(-1)=2010 est divisible par 5.
Donc :
c'est-à-dire
Or donc
Comme , le reste de la division euclidienne de par 5 est 4.