Prépa, 1re année › Arithmétique dans $\mathbb{Z}$ › Opérations sur les congruences
Opérations sur les congruences : énoncé (MPSI)
Propriété
Opérations sur les congruences
Soit $n \in \mathbb{N}^*$.
- La congruence modulo $n$ est une relation d'équivalence sur $\mathbb{Z}$ (réflexive, symétrique, transitive).
- Si $a \equiv b \;[n]$ et $c \equiv d \;[n]$, alors $$a + c \equiv b + d \;[n] \quad \text{et} \quad ac \equiv bd \;[n].$$
- Si $a \equiv b \;[n]$, alors $a^k \equiv b^k \;[n]$ pour tout $k \in \mathbb{N}$.
Preuve du produit. $ac - bd = a(c - d) + d(a - b)$, et $n$ divise $c - d$ et $a - b$. Les puissances s'en déduisent par récurrence sur $k$.
Attention
On ne divise pas une congruence
$2 \times 3 \equiv 2 \times 0 \;[6]$, mais $3 \not\equiv 0 \;[6]$. On ne peut pas simplifier par $2$.
La simplification est permise si le facteur est premier avec le module : si $ka \equiv kb \;[n]$ et $k \wedge n = 1$, alors $n \mid k(a - b)$ et le lemme de Gauss donne $a \equiv b \;[n]$.
S’entraîner
- Restes de puissances et divisibilité par congruences
- PGCD dépendant d'un paramètre
- Congruences linéaires et piège de la simplification
Dans le cours
Arithmétique dans $\mathbb{Z}$ : Opérations sur les congruences