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.

Description

La division euclidienne

Pour tout aZa \in \mathbb{Z} et bNb \in \mathbb{N}, il existe un unique couple (q;r)(q;r) avec qNq \in \mathbb{N} et rZr \in \mathbb{Z}, tel que :

a=b×q+ra=b\times q+r avec 0rb0 \le r \le b

  • L’opération qui associe (q;r)(q;r) à (a;b)(a;b) est appelée division euclidienne de a{a} par bb,
  • aa s’appelle le dividende,
  • qq le quotient,
  • bb le diviseur,
  • rr le reste.
bannière exemple

Exemple

La division euclidienne de 2929 par 55 est : 29=5×5+429=5 \times 5 +4
La division euclidienne de 14-14 par 66 est : 14=6×(3)+4-14=6 \times (-3)+4

Congruence

Soient nNn\in \mathbb{N}, n2n\ge 2 et aa, bZb\in \mathbb{Z}.
Deux entiers aa et bb sont dits congrus modulo nn si, et seulement si, les divisions euclidiennes de aa et bb par nn donnent des restes égaux.
On note alors : ab[n]a \equiv b [n]

bannière exemple

Exemple

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