Calcul modulo

Congruence modulo m

m est un nombre naturel.

a et b entiers sont dits congruents modulo m si a - b est divisible par m.

Notation: a b (mod m)

Ce qui peut aussi se lire a est congru à b modulo m ou encore b est congru à a modulo m

Définitions équivalentes

• a et b sont congruents modulo m
• m | (a - b)
• a = b + k m avec k entier
• La division euclidienne de a par m et la division euclidienne de b par m ont le même reste

Exemples

• 4 0 (mod 2)
• 5 1 (mod 2)
• 5 2 (mod 3)
• 13 1 (mod 12)

Propriétés

Relation d'équivalence

La relation de congruence est une relation d'équivalence: si a b (mod m) et si b c (mod m) alors a c (mod m)

Etant donné m, l'ensemble des entiers congrus à un nombre s'appelle une classe de restes modulo m. Ou simplement classe de restes si m est sous-entendu. La classe de restes de a se note $\bar a$.

Si $b \in \bar a$ alors $\bar b = \bar a$. Cele découle de la relation d'équivalence.

Partition des entiers

Etant donné m, les classes des restes modulo m constituent une partition des entiers. C'est-à-dire Z est la réunion disjointe des classes de restes modulo m.

Exemple: m = 5, on note la classe par le plus petit élément positif:

• $\bar 0$ = {..., -10, -5, 0, 5, 10, 15, ...}
• $\bar 1$ = {..., -9, -4, 1, 6, 11, 16, ...}
• $\bar 2$ = {..., -8, -3, 2, 7, 12, 17, ...}
• $\bar 3$ = {..., -7, -2, 3, 8, 13, 18, ...}
• $\bar 4$ = {..., -6, -1, 4, 9, 14, 19, ...}

$Z = \bar 0 \cup \bar 1 \cup \bar 2 \cup \bar 3 \cup \bar 4$

Compatibilité avec les opérations

L'addition dans Z repecte la relation modulo: si a1 b1 (mod m) et si a2 b2 (mod m) alors a1 + a2 b1 + b2 (mod m)

Exemples (m = 5): en additonnant n'importe quel élément de $\bar 2$ à n'importe quel élément de $\bar 4$ on obtient un élément de $\bar 1$.

La multiplication dans Z repecte la relation modulo: si a1 b1 (mod m) et si a2 b2 (mod m) alors a1 x a2 b1 x b2 (mod m)

Exemples (m = 5): en multipliant n'importe quel élément de $\bar 2$ à n'importe quel élément de $\bar 4$ on obtient un élément de $\bar 3$.

Le calcul modulo est le calcul effectué sur les classes de restes. Lorsque le contexte est clairement celui du calcul modulo, on note simplement a à la place de $\bar a$.

Système complet de restes modulo

Un système complet de reste modulo m est un ensemble de m nombres, un par classe de restes.

0, 1, 2, 3, 4, ... m-1 est un système complet de restes modulo m.

Si m est pair: -m/2, ... , -1, 0, 1, 2, ..., m/2 est un système complet de restes modulo m.

Si m est impair: -(m-1)/2, ... , -1, 0, 1, 2, ..., (m-1)/2 est un système complet de restes modulo m.