Congruences

Définition 15.1.1  

$$a \equiv b \pmod n$$

si

$$n \vert (a - b)$$

On dit alors que $a$ est congru à $b$ modulo $n$.

Autrement dit, $a$ est $b$ congru à $b$ modulo $n$ si et seulement si $a$ et $b$ ont le même reste de la division par $n$. Plus formellement,

Propriété 15.1.1   $a \equiv b \pmod n$ si et seulement si $a\ mod\ n = b\ mod\ n$.

En effet, si $n \vert(a - b)$, alors il existe $k$ tel que $kn = a - b$. Divisons $a$ et $b$ par $n$, il existe $q$, $q^\prime$, $r$ et $r^\prime$ tels que $a = qn + r$ et $b = q^\prime n + r^\prime$, avec $0 \leq r < n$ et $0 \leq r^\prime < n$. Donc $kn = a - b$ équivaut à

$$kn = qn + r - (q^\prime n + r^\prime)$$

ssi

$$kn = (q - q^\prime)n + (r - r^\prime)$$

ssi

$$n(k + q^\prime - q) = (r - r^\prime)$$

Donc

$$n \vert (r - r^\prime)$$

Or, $\vert r - r^\prime\vert < n$, donc $n$ ne peut diviser $(r - r^\prime)$ que si $r - r^\prime = 0$. On a donc $r = r^\prime$, comme $r = a\ mod\ n$ et $r^\prime = b\ mod\ n$, alors $a\ mod\ n = b\ mod\ n$.

Réciproquement, supposons $a\ mod\ n = b\ mod\ n$. Divisons $a$ et $b$ par $n$, il existe $q$, $q^\prime$ et $r$ tels que $a = qn + r$ et $b = q^\prime n + r$, avec $0 \leq r < n$. Donc

$$a - b = qn + r - (q^\prime n + r)$$

ssi

$$a - b = qn - q^\prime n$$

ssi

$$a - b = (q- q^\prime) n$$

Donc, $n \vert(a - b)$.