Arithmétique/Divisibilité et congruences dans Z
Soient , et trois entiers (relatifs).
Multiples d’un entier relatif, divisibilité dans Z
[modifier | modifier le wikicode]On dit que
- « a est un multiple de b », ou que « b est un diviseur de a », ou encore que « b divise a »,
et l’on note
- b | a
si :
- il existe un entier q tel que a = b×q.
- a est multiple de 1, a, –1 et –a, car a = 1×a = a×1 = (–1)×(–a) = (–a)×(–1).
- Zéro n'admet qu'un multiple : lui-même, car
- Zéro est multiple de tout entier, car
- Les seuls diviseurs de 1 sont 1 et –1.
Si a et b sont égaux ou opposés, on a déjà remarqué que chacun divise l'autre.
Réciproquement, supposons que chacun divise l'autre et montrons qu’ils sont égaux ou opposés.
- S'ils sont tous deux nuls, c’est immédiat.
- Si l'un au moins est non nul, par exemple b non nul, alors :
d'où donc (en simplifiant par b, qui est non nul) .
Par conséquent, est égal à 1 ou à –1, donc a est égal à b ou à –b.
Si et alors, pour .
Tout diviseur commun à deux entiers et est un diviseur de leur somme et, plus généralement, de , quels que soient les entiers et .
Si et alors, .
Division euclidienne
[modifier | modifier le wikicode]Si , il existe un unique couple d'entiers , tel que :
- le « dividende » soit égal au produit du « diviseur » par le « quotient » plus le « reste » et
- le reste soit positif et strictement inférieur à la valeur absolue du diviseur.
Formellement, cette définition s'écrit :
Deux entiers et vérifient ces deux conditions si et seulement si :
- ;
- .
La condition 1 détermine en fonction de , et en posant (c'est-à-dire , selon le signe de ), la condition 2 devient :
-
- le plus grand élément de l'ensemble .
Un tel entier (donc un tel couple ) existe et est unique, car est un ensemble d'entiers non vide (il contient ) et majoré (par ).
- Si alors est la partie entière du nombre rationnel .
- Si de plus alors , et l'on retrouve la division euclidienne dans les entiers naturels.
est la division euclidienne de 101 par 4 ou la division euclidienne de 101 par 25.
ne constitue pas la division euclidienne de 34 par 10. En effet, on n'a pas l'inégalité .
est la division euclidienne de -37 par 11 mais n’est pas la division euclidienne de –37 par –4.
Congruences
[modifier | modifier le wikicode]La relation de congruence ne ressemble pas aux relations habituelles, en effet les relations que nous utilisons depuis que nous faisons des mathématiques (=, <, > …) comparent deux nombres alors que la relation de congruence compare les restes des deux nombres étudiés.
Soit un entier strictement positif.
et sont dits congrus modulo s'ils ont même reste dans la division euclidienne par . Formellement :
Les notations changent d’un ouvrage à l'autre mais désignent toutes la même chose :
- ;
- ;
- ;
Soient et les divisions euclidiennes de et par . Alors,
donc (d'après la propriété « Combinaison linéaire » ci-dessus) divise si et seulement s'il divise , c'est-à-dire (puisque ) si et seulement si .
Propriétés des congruences
[modifier | modifier le wikicode]- Si et , alors
- Si et , alors :
- (1) et plus généralement,
- ;
- (2) ;
- (3) Attention : n'est pas vrai.
- (1) et plus généralement,
- n divise a – b si et seulement s'il divise son opposé, b – a.
- Si n divise a – b et b – c alors il divise leur somme, a – c.
- Notons respectivement et les différences et . Par hypothèse, n divise et .
(1) Montrons qu’il divise aussi le nombre (quels que soient les entiers u et v). Ce nombre est égal à , donc la propriété « Combinaison linéaire » ci-dessus permet de conclure.
(2) Montrons maintenant qu’il divise le nombre . Ce nombre est égal à donc, à nouveau, la propriété « Combinaison linéaire » permet de conclure.
(3) se démontre par récurrence, en appliquant (2) à et . On peut aussi montrer directement que n divise , en utilisant l'identité remarquable suivante :
pour et quelconques et
Il suffit pour démontrer celle-ci de développer le membre de droite ; après simplification, on obtient bien le membre de gauche de l'égalité.
Cette égalité prouve que est multiple de , qui est lui-même multiple de n par hypothèse. La propriété « Transitivité » ci-dessus permet de conclure.
Méthode plus simple pour calculer le reste de la division de 216 par 7 :
On remarque que et que
Donc modulo 7,
Le reste de la division de 216 par 7 est donc égal à celui de la division de 2 par 7, c'est-à-dire à 2.