Déjà plus de
1 million
d'inscrits !
Divisibilité et congruences dans Z
Déjà plus de
1 million
d'inscrits !
Avant de commencer, regarde la vidéo
Introduction :
Ce premier cours d’arithmétique concerne les congruences dans : en partant de la notion de divisibilité dans et en utilisant la division euclidienne – qui ont toutes les deux été vues au collège –, nous allons définir la notion de congruences dans et en donner les principales propriétés.
Dans un premier temps, nous allons revoir la notion de divisibilité dans et la division euclidienne qui sera étendue aux nombres entiers relatifs. Nous verrons la notion de congruences dans , qui est une nouveauté, et ses principales propriétés.
Divisibilité dans
Définitions
Commençons par quelques rappels simples, étendus à l’ensemble des entiers relatifs.
Divisibilité dans :
Soit et des entiers relatifs, étant non nul. On dit que est un diviseur de , et on note , lorsqu’il existe un entier relatif tel que .
Rappelons aussi les règles de divisibilité.
Propriétés
Revoyons maintenant les principales propriétés de la divisibilité dans l’ensemble .
Transitivité :
Soit , et des entiers relatifs.
Si divise et si divise , alors divise .
Comme divise , il existe un entier relatif tel que .
Comme divise , il existe un entier relatif tel que .
Ainsi, nous avons :
étant le produit deux entiers relatifs, c’est un entier relatif.
Combinaisons linéaires entières :
Soit , et des entiers relatifs.
Si divise et , alors pour tous les entiers relatifs et , divise .
Autrement dit, si divise et , alors il divise toutes les combinaisons linéaires entières de et .
Comme divise et , il existe deux entiers relatifs et tels que et .
Alors, avec et deux entiers relatifs :
étant la somme de deux produits d’entiers relatifs, c’est un entier relatif.
Division euclidienne
Après avoir revu la notion de divisibilité dans , revoyons la division euclidienne, que nous allons étendre aux nombres entiers relatifs.
Définitions
Division euclidienne :
Soit et deux entiers naturels avec non nul.
Il existe un unique couple d’entiers naturels tels que :
Nous pouvons étendre la division euclidienne sur les entiers naturels à celle d’un entier relatif par un entier naturel non nul.
Soit un entier relatif et un entier naturel.
Il existe un unique couple , avec et , tels que :
Une différence entre la division euclidienne d’un élément de et la division euclidienne d’un élément de est que le quotient peut être négatif.
Une application dans la vie quotidienne
On se sert par exemple de la division euclidienne lorsque qu’on nous attribue notre numéro de Sécurité sociale.
Ce numéro est constitué de 15 chiffres :
Il faut effectuer la division euclidienne des premiers chiffres par .
Ensuite, on calcule la différence entre et le reste obtenu. On a ainsi les deux derniers chiffres, qui constituent une clé de contrôle.
La clé est comprise entre et (ne pas prendre le reste lui-même permet d’éviter d’avoir une clé nulle).
Pour avoir un exemple, très simplifié, d’un code correcteur, vous pouvez regarder ce petit cours sur le code de Hamming .
La divisibilité dans et la division euclidienne de deux entiers relatifs vont nous permettre de travailler sur une nouvelle notion, qui est la congruence dans .
Congruences dans
Commençons par donner la définition de cette nouvelle notion.
Définition
Regardons la suite de nombres suivante :
Si l’on prend nombres, n’importe lesquels, parmi cette suite, nous voyons facilement que leur différence sera toujours un multiple de .
Comme ils sont égaux à un multiple de près, on dit que :
Congruence :
désigne un entier naturel non nul, et sont des entiers relatifs.
On dit que et sont congrus modulo lorsque la différence est un multiple de , ou bien que divise , ce qui est équivalent.
Les notations possibles sont les suivantes :
Prenons quelques exemples pour comprendre cette notion.
Le nombre est un multiple de , donc et sont congrus modulo :
Donc et sont congrus modulo :
Pour utiliser les propriétés vues plus haut, nous pouvons aussi le déduire de la relation 1 :
Le nombre
En revanche,
Les « raccourcis » suivants sont à connaître.
Lien entre congruences et division euclidienne
Maintenant que nous savons ce qu’est la congruence, voyons son lien avec la division euclidienne revue en début de cours.
Pour un entier naturel non nul
Si on effectue la division euclidienne d’un entier relatif
On a alors
Par conséquent, il advient la propriété suivante pour deux entiers relatifs
Prenons deux exemples pour illustrer ces propriétés.
Avec la division euclidienne de
Avec la division euclidienne de
Voyons maintenant les principales propriétés de la congruence dans
Propriétés
Soit un entier naturel non nul
Les réponses données dans l’exemple ci-dessus sont justes.
Il est tout de même préférable, et fortement recommandé, de se ramener à une congruence
Pour cela, nous utilisons la propriété – évidente mais à ne jamais oublier – suivante.
Avec
Ainsi, en reprenant les résultats de l’exemple précédent, nous obtenons :
Nous aurions aussi pu transformer les expressions dès le début, pour arriver au même résultat :
Continuons à étudier les propriétés des congruences.
La congruence est compatible avec la multiplication.
C’est-à-dire que, si on a $a\equiv b\,\lbrack n\rbrack$ et
Ce n’est pas valable avec la division ! Par exemple :
De la dernière propriété, nous pouvons tirer une conséquence.
Si on a $a\equiv b\,\lbrack n\rbrack$, alors, pour tout
Si on a
Nous allons maintenant prendre l’exemple simple d’un raisonnement à mener dans un exercice faisant intervenir les congruences.
Il s’agit de montrer que
Nous avons donc :
Nous obtenons ainsi :
Résolution d’une équation avec des congruences
Nous allons maintenant, à travers un exemple, voir comment nous pouvons résoudre une équation du type
Nous souhaitons résoudre l’équation
Pour résoudre cette équation, nous allons remplir un tableau, afin d’étudier les différents cas possibles.
En règle générale, pour résoudre une équation du type
Conclusion :
Dans ce cours, après avoir rappelé la division euclidienne et l’avoir étendue à l’ensemble des entiers relatifs, nous avons découvert la notion de congruences, où, pour que deux entiers relatifs