Médaille
N°1 pour apprendre & réviser du collège au lycée.
Congruence dans ℤ

Déjà plus de

1 million

d'inscrits !

Introduction :

La notion de congruence fait souvent peur aux étudiants mais elle est indispensable en spécialité maths du bac S. Nous verrons dans un premier temps les définitions indispensables à sa compréhension. Ensuite, nous verrons le lien avec la division euclidienne. Les propriétés nous amèneront à une application : l’écriture des nombres en base $b$.

Définitions

bannière definition

Définition

Congruence :

$n$ désigne un entier naturel non nul, $a$ et $b$ sont des entiers relatifs.

On dit que $a$ et $b$ sont congrus modulo $n$ lorsque la différence $a - b$ est un multiple de $n$.

Notations : $a\equiv b\ \text{mod}\ n$ ou $a\equiv b [n]$ ou encore $a\equiv b\ (n)$

bannière à retenir

À retenir

  • On peut ajouter ou multiplier membre à membre des congruences.
  • La relation de congruence est symétrique, c’est-à-dire que si $a\equiv b [n]$ on a aussi $b\equiv a [n]$. Autrement dit, si $a-b$ est un multiple de $n$, $b-a$ est aussi un multiple de $n$.
  • Dernier point, la relation de congruence est réflexive, c’est-à-dire qu’on a toujours $a\equiv a [n]$
bannière exemple

Exemple

  • $-19-(-4)=-15$
    Le nombre $-15$ est un multiple de $5$ donc $-19$ et $-4$ sont congrus modulo $5$ : $-19\equiv -4\ [5]$
  • $-19+3=-16$ et $-4+3=-1$ Donc $-16$ et $-1$ sont congrus modulo $5$ : $-16\equiv -1\ [5]$ ou $ -1\equiv-16\ [5]$
  • $8-16=-8$
    Le nombre $-8$ n’est pas un multiple de $5$ donc $8$ et $16$ ne sont pas congrus modulo $5$ : $8 \not \equiv 16\ [5]$
bannière à retenir

À retenir

Quelques raccourcis à connaître :

  • Un nombre est congru à $0$ modulo $n$ si, et seulement si, ce nombre est un multiple de $n$. Par exemple $25$ est congru à $0$ modulo $5$ : $25\equiv 0\ [5]$.
  • Tout nombre pair est congru à $0$ modulo $2$ et tout nombre impair est congru à $1$ modulo $2$ :
  • donc $1 235$ est congru à $1$ modulo $2$ : $1 235\equiv 1\ [2]$
  • et $1 236$ est congru à $0$ modulo $2$ : $1 236\equiv 0\ [2]$.
  • Tout nombre est congru à son chiffre des unités modulo $10$. Donc $35\ 794$ est congru à $4$ modulo $10$ : $35\ 794\equiv 4\ [10]$.

Lien entre congruence et division euclidienne

Maintenant que nous savons ce qu’est la congruence, voyons le lien avec la division euclidienne vue dans le cours précédent.

bannière propriete

Propriété

Tout nombre est congru modulo $n$ au reste de sa division euclidienne par $n$.

bannière demonstration

Démonstration

Si on fait la division euclidienne de $a$ par $n$, on sait qu’il existe $q$ appartenant à l’ensemble des entiers relatifs $\mathbb Z$ et $r$ appartenant à l’ensemble des entiers naturels $\mathbb N$ tels que $a=qn+r$ avec $0≤ r < n$.

On a alors $a-r=qn$. Donc $a-r$ est un multiple de $n$ et ainsi a est congru à $r$ modulo $n$.

Par conséquent, il advient la propriété suivante :

bannière propriete

Propriété

  • $a$ et $b$ sont congrus modulo $n$ si et seulement si $a$ et $b$ ont le même reste dans la division euclidienne par $n$.
  • Si $a\equiv r\ [n]$ avec $r$ compris entre zéro inclus et $n$ exclu $0 ≤ r < n$ alors $r$ est le reste de la division euclidienne de $a$ par $n$.
bannière exemple

Exemple

Avec la division euclidienne de $551$ par $26$, on obtient : $551=21\times26+5$ donc $551$ est congru à $5$ modulo $26\ 551\equiv 5\ [26]$

bannière exemple

Exemple

Avec la division euclidienne de $189$ par $35$, on obtient : $189=5\times35+14$ donc $189$ est congru à $14$ modulo $35$ $189\equiv 14\ [35]$

Propriétés

bannière propriete

Propriété

  • Si on a $a\equiv b\ [n]$ et $b\equiv c\ [n]$ alors $a\equiv c\ [n]$. C’est la transitivité.
  • Si on a $a\equiv b\ [n]$ et $a'\equiv b'\ [n]$ alors :
  • $a+a'\equiv b+b'[n]$
  • et $a-a'\equiv b-b'[n]$
bannière exemple

Exemple

  • $-13\equiv -8\ [5]$ et $46\equiv 21\ [5]$ ; on a alors $33\equiv 13\ [5]$ et $-59\equiv -29\ [5]$
bannière propriete

Propriété

Si on a $a\equiv b\ [n]$ et $a'\equiv b' [n]$ alors $aa'\equiv bb'[n]$

bannière attention

Attention

Ce n’est pas valable avec la division ! Par exemple $25\equiv 5\ [10]$ mais $5\not \equiv1\ [10]$

bannière propriete

Propriété

  • Si on a $a\equiv b\ [n]$ alors pour tout $k∈\mathbb Z$, on a  : $ka\equiv kb\ [n]$
  • Si on a $a\equiv b\ [n]$ alors pour tout $p∈\mathbb N^*$, on a : $a^p\equiv b^p\ [n]$
bannière exemple

Exemple

$7\equiv 2\ [5]$ donc $7^2 \equiv 2^2\ [5]$, c’est à dire $7^2\equiv 4\ [5]$.

bannière astuce

Astuce

Si on a $a\equiv -1\ [n]$ alors $a^p\equiv(-1)^p\ [n]$

Application : écriture des nombres en base $b$

En mathématiques, l’écriture des nombres se fait en base 10. Cette base est celle utilisée dans notre société. Mais il existe d’autres bases d’écriture de nombres.

Voyons en détail l’écriture en base 10, aussi appelé le système décimal.

Dans ce système, on utilise 10 chiffres : 0, 1, 2, 3, 4, 5, 6, 7, 8 et 9.

On fait un regroupement par 10 : c’est-à-dire qu’on forme une dizaine avec 10 unités, une centaine avec 10 dizaines, etc.

bannière exemple

Exemple

$\begin{aligned}\begin{array}{rl} &&3249\\ &=&3\times1000+2\times100+4\times10+9\times1\\ &=&3\times10^3+2\times10^2+4\times10^1+9\times10^0 \end{array}\end{aligned}$

De la même manière, on peut faire des groupements par 5 ; ce qui donne un système en base 5 où on utilise 5 chiffres : 0, 1, 2, 3 et 4.

bannière exemple

Exemple

$\overline{1302}^5$ en base 5 correspond à :

$\begin{aligned}\begin{array}{rl} &&1\times5^3+3\times5^2+0\times5^1+2\times5^0\\ &=&1\times125+3\times25+0\times5+2\times1 \end{array}\end{aligned}$

Ce qui donne $202$ en base 10.

bannière propriete

Propriété

Soit $b$ élément de $\mathbb N\setminus\lbrace0\ ;1\rbrace$ :

  • Tout entier naturel $n$ peut s’écrire d’une manière unique : $n=n_pb^p+n_{p-1}b^{p-1}+…+n_1b^1+n_0b^0$

Avec $np≠0$ et pour tout $i$ de $\lbrace0\ ;1\ ;…;P\rbrace$, $0 ≤ n_i < b$.

  • De plus, les chiffres de l’écriture en base $b$ de $n$ sont les nombres $n_p,\ n_{p-1},…,\ n_1\text{ et }n_0$.

L’écriture en base $b$ de $n$ est : $\overline{n_pn_{p-1}…n_1n_0}^b$

bannière exemple

Exemple

  • Écrire $n=\overline{402}^7$ en base 10.

    $\begin{aligned}\begin{array}{rl} n=\overline{402}^7&=4\times7^2+0\times7^1+2\times7^0 \\ &=4\times49+2\\ &=198\\ n&=\overline{198}^{10}\\ \end{array}\end{aligned}$

  • Écrire $n=\overline{534}^{10}$ en base 8.

On peut utiliser la division euclidienne :

$534=8\times66+6$ donc 6 éléments isolés ;

$66=8\times8+2$ donc 2 groupements du 1er ordre isolés ;

$8=8\times1+0$ donc 0 groupement du 2e ordre isolé ;

$8=8\times0+0$ donc 1 groupement du 3e ordre.

La condition d’arrêt est que le quotient soit nul.

  • On peut donc écrire $534=\overline{1026}^8$