Plan du site  
français  English
pixel
pixel

Articles - Étudiants SUPINFO

Relation de congruence

Le but de cette première partie va être d'introduire la notion de congruence. Cela revient plus ou moins à classer les entiers selon la valeur de leur reste après division euclidienne par un entier fixé.

Définition du concept de congruence

La première formalisation de la notion de congruence date de 1801, avec la publication du "Disquisitiones Arithmeticae" de Carl Friedrich Gauss (1777-1855). Mais les idées sont en fait beaucoup plus anciennes.

On ne va plus vraiment raisonner sur les nombres en eux-mêmes mais sur leurs restes dans la division euclidienne par un entier donné. On a en effet constaté au chapitre précédent que les restes possibles après division euclidienne par un entier m étaient 0 , 1 , 2 , . . . , m - 1 .

C’est donc comme si l’on disposait de m boîtes, et que l’on mettait dans une même boîte les entiers ayant le même reste après division euclidienne par m. Deux éléments d’une même boîte seront alors dits congrus modulo m.

Example 1.1. Congruence modulo 3

Dans chacune des trois boîtes ci-dessous, les éléments sont congrus modulo 3 :


Si l'on donne un aspect un tout petit peu plus formel à cette idée, cela conduit à cette définition :

Définition

Soit m élément de .

Deux entiers relatifs a et b sont dits congrus modulo m si et seulement si a et b possèdent le même reste après division euclidienne par m.

On note alors a b [ m ] .

Example 1.2. Une première relation de congruence

On a 19 43 [ 12 ] car les restes de 19 et 43 après division par 12 valent tous les deux 7.


[Note]

D'après l'exemple précédent 7, 19 et 43 heures sont représentées par une même position des aiguilles sur un cadran de montre.

C'est pourquoi la notion de congruence et les résultats qui en découlent sont aussi appelés arithmétique de l'horloge.

La petite propriété qui suit découle directement de la définition.

Propriété

Soit m élément de , r élément de , et a élément de .

Si r est le reste de la division euclidienne de a par m, alors a r [ m ] .

Réciproquement, si 0 r < m et a r [ m ] alors r est le reste de la division euclidienne de a par m.

On va maintenant donner une définition équivalente à celle de la congruence entre deux entiers. Selon le contexte on utilisera l'une ou l'autre.

Définition équivalente

Soit m élément de .

Deux entiers relatifs a et b sont dits congrus modulo m si et seulement si a - b est un multiple de m.

Nous allons à présent vérifier que les deux définitions précédentes sont bien équivalentes.

Démonstration de l'équivalence entre les deux définitions de la congruence

Supposons dans un premier temps que a et b possèdent le même reste après division euclidienne par m. Cela signifie qu'il existe des entiers q, q et r tels que a = m q + r et b = m q + r . On a alors a - b = m × ( q - q ) , ce qui prouve bien que a - b est un multiple de m.

Réciproquement, si a - b est un multiple de m il existe un entier k tel que a - b = k m . Effectuons ensuite les divisions euclidiennes de a et b par m : il existe des entiers q, q , r et r tels que a = m q + r et b = m q + r , avec 0 r < m et 0 r < m . On a donc a - b = m × ( q - q ) + r - r . Les deux écritures précédentes de a - b conduisent alors à k m = m × ( q - q ) + r - r . D'où m × ( k - q + q ) = r - r . Cela signifie que m | ( r - r ) . D'après une propriété élémentaire du chapitre précédent, cela implique que m | r - r | . Cependant, d'après les inégalités portant sur r et r , on a - m < r - r < m , i.e. | r - r | < m . On a alors nécessairement r - r = 0 , ce que l'on souhaitait obtenir.

Example 1.3. Une seconde relation de congruence

On a 17 - 31 [ 6 ] car 17 - ( - 31 ) = 48 est un multiple de 6.


Propriétés

Nous pouvons maintenant énoncer trois petites propriétés de la relation de congruence. A noter que leurs preuves sont réellement élémentaires, c'est pourquoi nous laissons le lecteur y réfléchir.

Propriété de réflexivité

Soit m élément de .

Pour tout entier relatif a, a a [ m ] .

Propriété de symétrie

Soit m élément de .

Pour tous entiers relatifs a et b, a b [ m ] est équivalent à b a [ m ] .

Propriété de transitivité

Soit m élément de .

Pour tous entiers relatifs a, b et c, a b [ m ] et b c [ m ] impliquent a c [ m ] .

[Note]

De façon savante on dit qu'une relation vérifiant les propriétés de réflexivité, symétrie et transitivité est une relation d'équivalence. C'est donc le cas pour la congruence.

Règles opératoires

Les trois règles ci-dessous seront constamment utilisées dans la suite de ce cours. Comme le lecteur le constatera vite, toute la puissance de la relation de congruence en découle.

Règles de calculs

Soit m élément de , et a , b , c , d éléments de .

Si a b [ m ] et c d [ m ] alors

  1. a + c b + d [ m ] .

  2. a c b d [ m ] .

  3. Pour tout élément k de * , a k b k [ m ] .

Démonstration

D'après les hypothèses (et la seconde définition de la relation de congruence) il existe des entiers k et k tels que a = b + k m et c = d + k m .

On a alors a + c = b + d + ( k + k ) × m ce qui prouve la première règle grâce à la seconde définition de la congruence.

De plus a c = b d + ( d k + b k + k k m ) × m ce qui prouve la deuxième règle.

La troisième règle découle de la seconde par récurrence :

  • Initialisation : pour k = 1 la propriété se réduit à a b [ m ] qui est l'hypothèse.

  • Hérédité : supposons que pour un k 1 on ait a k b k [ m ] . D'après la seconde règle et l'hypothèse initiale on peut multiplier le premier terme de l'hypothèse de récurrence par a et le second par b. Cela donne a k a b k b [ m ] , et donc a k + 1 b k + 1 [ m ] . Ce qui est bien l'égalité au rang k + 1 .

  • On conclut alors en appliquant le principe de récurrence.

Example 1.4. Première application de ces règles

Le reste de la division euclidienne de 4 2017 par 3 est égal à 1.

En effet 4 1 [ 3 ] , donc d'après la troisième règle opératoire 4 2017 1 2017 [ 3 ] . Ainsi 4 2017 1 [ 3 ] , ce qui prouve le résultat.


[Note]

Cette troisième règle opératoire est donc très puissante et nous permettra souvent d'esquiver des calculs explicites afin d'obtenir des informations de ce type.

A noter que beaucoup de calculatrices n'arriveraient d'ailleurs pas à calculer la valeur de 4 2017 .

Exercices

Les exercices de cette sous-partie vont permettre au lecteur de se familiariser avec la notion de congruence et lui permettre de continuer à appréhender la force de ses règles opératoires.

Exercice corrigé

1.1.

Quelle heure indique votre montre à aiguille 208 heures après avoir indiqué 5 heures ? On suppose que la montre a un cadran de 12 heures, ce qui n'est pas une hypothèse très restrictive.

L'heure h recherchée vérifie h 208 + 5 [ 12 ] avec 0 h < 11 . Il s'agit donc du reste de la division euclidienne de 213 par 12. Or 213 = 17 × 12 + 9 donc h = 9 .

Exercice corrigé

1.1.

Montrer que 3 512 - 2 256 est un multiple de 7.

On commence par constater que 512 = 2 × 256 . Ainsi, d'après les règles usuelles sur les puissances, 3 512 - 2 256 = 3 2 × 256 - 2 256 = ( 3 2 ) 256 - 2 256 = 9 256 - 2 256 .

Or 9 2 [ 7 ] donc d'après la troisième règle opératoire 9 256 2 256 [ 7 ] . Ce qui démontre le résultat.

Exercice corrigé

1.1.

Quel est le reste de la division euclidienne de 12 1527 par 5 ?

Indication : On commencera par chercher le premier entier k tel que 12 k 1 [ 5 ] .

On vérifie sans peine que 12 2 [ 5 ] , 12 2 4 [ 5 ] , 12 3 3 [ 5 ] et 12 4 1 [ 5 ] . On effectue ensuite la division euclidienne de 1527 par 4 : 1527 = 381 × 4 + 3 . Ainsi 12 1527 = ( 12 4 ) 381 × 12 3 .

D'après la troisième règle opératoire, puisque 12 4 1 [ 5 ] on a ( 12 4 ) 381 1 [ 5 ] . Puisque l'on a déjà remarqué que 12 3 3 [ 5 ] , on obtient finalement 12 1527 3 [ 5 ] . Le reste cherché est donc 3.

[Note]

Que le lecteur comprenne bien qu'il n'est pas utile de calculer explicitement les valeurs des premières puissances de 12 utilisées (exposants 2, 3 et 4), la seule application des règles opératoires conduit à ces résultats.

Bien retenir également cette technique consistant à rechercher le premier exposant donnant une valeur de 1 en congruence, puis à effectuer une division euclidienne par cet exposant.

Inverse multiplicatif

Dans cette partie nous allons présenter une notion d'inverse similaire à celle usuelle des nombres réels, mais mieux adaptée aux questions d'arithmétique.

Définition

Le concept suivant est fondamental, en particulier en cryptographie.

Définition

Soit m élément de et a élément de .

L'entier a est dit inversible modulo m s'il existe un entier relatif b tel que a b 1 [ m ] .

On dit alors que b est un inverse multiplicatif de a modulo m.

Il faut bien comprendre que pour un entier m donné, tous les entiers ne sont pas nécessairement inversibles modulo m. D'autre part si un entier est inversible modulo m, son inverse n'est pas unique. L'exemple suivant va illustrer ces deux points.

Example 1.5. Situations d'inversibilité

  • L'entier 5 est inversible modulo 7 et 3 est l'un de ses inverses multiplicatifs car 5 × 3 1 [ 7 ] . Comme autres inverses multiplicatifs de 5 modulo 7 on peut citer 10,17, - 4 ...

  • Par contre 5 n'est pas inversible modulo 10. En effet, on vérifie facilement que pour tout entier b, on a soit 5 b 0 [ 10 ] , soit 5 b 5 [ 10 ] .


[Note]

Ce concept d'inversibilité est formellement le même que celui des nombres réels. Rappelons en effet qu'un réel x est inversible dans si et seulement si il existe un réel y tel que x y = 1 .

Il est également similaire à celui des matrices carrées. Une matrice carrée A d'ordre n est en effet inversible s'il existe une matrice carrée B d'ordre n telle que A B = I n . Voir cours 1LAL à ce sujet.

Ce qui change à chaque fois, ce sont les définitions des opérations et l’élément unitaire.

Critère d'inversibilité

On a constaté dans la sous-partie précédente que pour un entier m donné, tous les entiers n'étaient pas inversibles modulo m. Il convient donc de donner un critère permettant de savoir à quelle condition c'est le cas.

Théorème

Soit m élément de et a élément de .

L'entier a est inversible modulo m si et seulement si a est premier avec m, i.e. PGCD ( a , m ) = 1 .

Démonstration

Si a est inversible modulo m, par définition il existe b tel que a b 1 [ m ] . Cela signifie que a b - 1 est un multiple de m et donc qu'il existe un entier k tel que a b = 1 + k m . D’après le théorème de Bézout (cf. chapitre précédent) a et m sont alors premiers entre eux.

Réciproquement, si a et m sont premiers entre eux, d’après ce même théorème de Bézout il existe des entiers u et v tels que a u + m v = 1 . On a alors a u 1 [ m ] , ce qui prouve bien que a est inversible modulo m.

Example 1.6. Applications du critère d'inversibilité

  • L'entier 5 est inversible modulo 7 car PGCD ( 5 , 7 ) = 1 .

  • Par contre 5 n'est pas inversible modulo 10 car PGCD ( 5 , 7 ) = 2 .


Calcul de l'inverse

Après avoir énoncé et démontré un critère d'inversibilité dans la précédente sous-partie, il ne nous reste plus maintenant qu'à présenter une méthode pour calculer un inverse multiplicatif.

Propriété

Soit m élément de et a élément de que l'on suppose inversible modulo m.

Le coefficient de a dans sa relation de Bézout avec m est un inverse multiplicatif de a modulo m.

Démonstration

La preuve du théorème de la sous-partie précédente justifie cette propriété.

Example 1.7. Calcul d'un inverse multiplicatif

Vérifions que 9 est inversible modulo 26 et calculons son inverse.

On utilise tout d'abord l'algorithme d'Euclide pour prouver que PGCD ( 9 , 26 ) = 1 , et pour calculer les coefficients de Bézout de 9 et 26 : 3 × 9 + ( - 1 ) × 26 = 1 .

Le fait que 9 et 26 soient premiers entre eux implique que 9 est inversible modulo 26 et la relation de Bézout nous donne son inverse, à savoir 3.


Théorème chinois

Cette partie sera consacrée au célèbre théorème chinois permettant de résoudre des systèmes d’équations de congruences.

Enoncé et démonstration du théorème

On trouve trace du résultat suivant, dit théorème chinois, dans des écrits du 1er siècle : le "Jiuzhang suanshu", en français "prescriptions de calcul en neuf chapitres".

Il permet la résolution de problèmes de ce type : on a un certain nombre d’objets tel que si on les compte par 3 il en reste 2, si on les compte par 5 il en reste 3 et si on les compte par 7 il en reste 2 ; combien y a-t-il d’objets ?

Théorème chinois

On considère le système

{ x a 1 [ m 1 ] x a 2 [ m 2 ] . . . x a n [ m n ]

m 1 , m 2 ,..., m n sont des éléments de premiers entre eux deux à deux, et a 1 , a 2 ,..., a n des éléments de tels que 0 a 1 < m 1 , 0 a 2 < m 2 ,..., 0 a n < m n .

Soit M = m 1 × m 2 × . . . × m n .

Le système précédent admet une unique solution modulo M, donnée par

x = a 1 M 1 y 1 + a 2 M 2 y 2 + . . . + a n M n y n

M i = M m i et y i M i 1 [ m i ]

Démonstration

Montrons tout d'abord que pour tout i, 1 i n , PGCD ( M i , m i ) = 1 . On a

M i = M m i = m 1 × . . . × m i 1 × m i + 1 × . . . × m n

D'après le théorème d'Euclide, voir prochain chapitre du cours, un diviseur premier commun à m i et M i diviserait nécessairement un des m j pour un j i . Mais cela contredirait le fait que PGCD ( m i , m j ) = 1 . Il n’en existe donc pas et par suite PGCD ( M i , m i ) = 1 .

D'après le critère d'inversibilité de la partie précédente cela prouve que M i est inversible modulo m i , et donc qu'il existe un entier y i tel que M i y i 1 [ m i ] .

On peut donc bien définir x tel que cela est fait dans l'énoncé du théorème.

Montrons maintenant que ce x est bien une solution du système. Pour cela vérifions que x a j [ m j ] pour tout j tel que 1 j n .

Puisque

M i = m 1 × . . . × m i 1 × m i + 1 × . . . × m n

il est clair que M i 0 [ m j ] pour tout i j . Par suite x a j M j y j [ m j ] . Or comme on l'a vu précédemment M j y j 1 [ m j ] , donc x a j [ m j ] . Cela étant vrai pour tous les j on en déduit que x est bien une solution du système.

Il reste à prouver l'unicité modulo M. Pour cela considérons x une autre solution du système et montrons que x x [ M ] .

Comme x a j [ m j ] et x a j [ m j ] , on a x x [ m j ] pour tout j, 1 j n . Cela signife que pour tout j, m j | ( x - x ) . Puisque les m j sont premiers entre eux deux à deux, le corollaire du théorème de Gauss (cf. chapitre précédent) implique que M | ( x - x ) , et donc que x x [ M ] . Q.E.D.

[Note]

Le lecteur exigeant pourrait tiquer sur l'emploi du théorème d'Euclide lors de cette démonstration car nous ne l'avons pas encore présenté, ce que nous ferons dans le prochain chapitre de ce cours. Déjà qu'il se rassure, il n'y a pas d'incohérence logique puisque le théorème d'Euclide ne découle en aucune façon de ce théorème chinois.

S'il souhaite s'en passer pour montrer que PGCD ( M i , m i ) = 1 , il pourra commencer par écrire les différentes relations de Bézout entre m i et chacun des m j pour j i . Elles sont de la forme m i u j + m j v j = 1 pour j i . Il suffit ensuite de multiplier ces n - 1 égalités entre elles, de développer le terme de gauche et de le mettre sous la forme suivante grâce à une factorisation

m i u + m 1 . . . m i - 1 m i + 1 . . . m n v = 1

Cette dernière égalité se réécrit alors comme m i u + M i v = 1 , et l'on conclut à l'aide du théorème de Bézout.

Exercice

Le petit exercice suivant permettra au lecteur de vérifier sa capacité à bien appliquer le théorème chinois.

Exercice corrigé

1.1.

Résoudre le système de congruence

{ x 1 [ 3 ] x 4 [ 5 ]

En reprenant les notations du théorème, on a m 1 = 3 , m 2 = 5 , a 1 = 1 , a 2 = 4 . D'où M = m 1 × m 2 = 15 , M 1 = m 2 = 5 et M 2 = m 1 = 3 .

On cherche ensuite les inverses multiplicatifs de 5 modulo 3, et de 3 modulo 5. On trouve facilement y 1 = 2 et y 2 = 2 .

On pose alors x = a 1 M 1 y 1 + a 2 M 2 y 2 = 34 .

Les solutions du système sont donc les entiers congrus à 34 modulo 15.

A propos de SUPINFO | Contacts & adresses | Enseigner à SUPINFO | Presse | Conditions d'utilisation & Copyright | Respect de la vie privée | Investir
Logo de la société Cisco, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société IBM, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sun-Oracle, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Apple, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sybase, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Novell, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Intel, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Accenture, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société SAP, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Prometric, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo du IT Academy Program par Microsoft, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management

SUPINFO International University
Ecole d'Informatique - IT School
École Supérieure d'Informatique de Paris, leader en France
La Grande Ecole de l'informatique, du numérique et du management
Fondée en 1965, reconnue par l'État. Titre Bac+5 certifié au niveau I.
SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels