Médaille
N°1 pour apprendre & réviser du collège au lycée.
Division euclidienne et congruence
Bien rédiger

Introduction

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.

Decription

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.
bannière exemple

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

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]$$

bannière exemple

Exemple

$\begin{array}{rcl}29 &\equiv& 4 [5] \\ -14 &\equiv& 4[6] \end{array}$