Arithmétique/Divisibilité et congruences dans Z

Soient $a$, $b$ et $c$ trois entiers (relatifs).

Congruences

La relation de congruence ne ressemble pas aux relations habituelles, en effet les relations que nous utilisons depuis que nous faisons des mathématiques (=, <, > …) comparent deux nombres alors que la relation de congruence compare les restes des deux nombres étudiés.

Soit $n$ un entier strictement positif.

Les notations changent d’un ouvrage à l'autre mais désignent toutes la même chose :

• $a\equiv b[n]$ ;
• $a\equiv b(n)$ ;
• $a\equiv b(\mathrm{mod}n)$ ;
• $a\equiv b(\mathrm{modulo}n).$

Propriétés des congruences

• $a\equiv b[n]\iff b\equiv a[n].$
• Si $a\equiv b[n]$ et $b\equiv c[n]$, alors $a\equiv c[n].$
• Si $a_1\equiv a_2[n]$ et $b_1\equiv b_2[n]$, alors :
  • (1) $a_1+b_1\equiv a_2+b_2[n]$ et plus généralement,
    • $\mathrm{\forall }u,v\in \mathbb{Z},a_{1}u+b_{1}v\equiv a_{2}u+b_{2}v[n]$ ;
  • (2) $a_1{b}_1\equiv a_2{b}_2[n]$ ;
  • (3) $\mathrm{\forall }p\in {\mathbb{N}}^{*},a_1^p\equiv a_2^p[n].$ Attention : $\mathrm{\forall }p\in {\mathbb{N}}^{*},p^{a_1}\equiv p^{a2}[n]$ n'est pas vrai.