La congruence sur les entiers est une relation pouvant unir deux entiers. Elle fut étudiée au XIXe siècle et constitue un des fondements de l’arithmétique.
La division euclidienne
La division euclidienne
Pour tout $a \in \mathbb{Z}$ et $b \in \mathbb{N}$, il existe un unique couple $(q;r)$ avec $q \in \mathbb{N}$ et $r \in \mathbb{Z}$, tel que :
$a=b\times q+r$ avec $0 \le r \le b$
- L’opération qui associe $(q;r)$ à $(a;b)$ est appelée division euclidienne de ${a}$ par $b$,
- $a$ s’appelle le dividende,
- $q$ le quotient,
- $b$ le diviseur,
- $r$ le reste.
Exemple
La division euclidienne de $29$ par $5$ est : $29=5 \times 5 +4$
La division euclidienne de $-14$ par $6$ est : $-14=6 \times (-3)+4$
Congruence
Congruence
Soient $n\in \mathbb{N}$, $n\ge 2$ et $a$, $b\in \mathbb{Z}$.
Deux entiers $a$ et $b$ sont dits congrus modulo $n$ si, et seulement si, les divisions euclidiennes de $a$ et $b$ par $n$ donnent des restes égaux.
On note alors : $$a \equiv b [n]$$
Exemple
$\begin{array}{rcl}29 &\equiv& 4 [5] \\ -14 &\equiv& 4[6] \end{array}$