Définition et propriétés

$a \equiv b \pmod{n} \iff n \mid (a-b)$

Règles de calcul (si $a \equiv b$ et $c \equiv d$ mod $n$ ) :

$a + c \equiv b + d \pmod{n}$ $ac \equiv bd \pmod{n}$ $a^k \equiv b^k \pmod{n}$

Classes de congruence

L’ensemble $\mathbb{Z}/n\mathbb{Z}$ est composé de $n$ classes :

$\bar{0}, \bar{1}, \ldots, \overline{n-1}$

Chaque entier appartient à exactement une classe.

Exemple : Modulo 5 : $7 \in \bar{2}$ , $-3 \in \bar{2}$ , $12 \in \bar{2}$ .

Méthode : Utiliser les propriétés de congruence + petits exposants.

Exemple : Calculer $3^{100} \pmod{7}$

$3^1 \equiv 3$ , $3^2 \equiv 2$ , $3^3 \equiv 6$ , $3^4 \equiv 4$ , $3^5 \equiv 5$ , $3^6 \equiv 1 \pmod{7}$

Cycle de longueur 6. $100 = 16 \times 6 + 4$ , donc $3^{100} \equiv 3^4 \equiv 4 \pmod{7}$

$a$ est inversible modulo $n$ $\iff$ $\text{PGCD}(a,n) = 1$ .

L’inverse $a^{-1}$ vérifie $a \cdot a^{-1} \equiv 1 \pmod{n}$ .

Méthode : Utiliser Bézout : $au + nv = 1 \implies au \equiv 1 \pmod{n}$ , donc $a^{-1} = u$ .

Exemple : Inverse de 3 modulo 7 : $3 \times 5 = 15 = 2 \times 7 + 1$ , donc $3^{-1} \equiv 5 \pmod{7}$ .

Soit $d = \text{PGCD}(a, n)$ .

Méthode : Diviser par $d$ , puis multiplier par l’inverse de $a/d$ modulo $n/d$ .

Exemple : $3x \equiv 2 \pmod{7}$

PGCD(3,7) = 1, donc $x \equiv 2 \times 3^{-1} \equiv 2 \times 5 \equiv 10 \equiv 3 \pmod{7}$

Si $p$ est premier et $p \nmid a$ , alors $a^{p-1} \equiv 1 \pmod{p}$ .

Application : Calculer $2^{100} \pmod{7}$ : $p=7$ , $2^6 \equiv 1$ . $100 = 16 \times 6 + 4$ . Donc $2^{100} \equiv 2^4 = 16 \equiv 2 \pmod{7}$ .