Congruence dans ℤ

Avant de commencer, regarde les vidéos

Épisode 1

1. Définitions

Épisode 2

2. Congruence et division euclidienne : le lien

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

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

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

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

À 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.

Propriété

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

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 :

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

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

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

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

Exemple

$-13\equiv -8\ [5]$ et $46\equiv 21\ [5]$ ; on a alors $33\equiv 13\ [5]$ et $-59\equiv -29\ [5]$

Propriété

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

Attention

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

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

Exemple

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

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.

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.

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.

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$

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 1^er ordre isolés ;

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

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

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

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

Cette fiche de cours fait appel aux contenus suivants

Division euclidienne

Définition

Mathématiques

Congruence dans ℤ

Définitions

Lien entre congruence et division euclidienne

Propriétés

Application : écriture des nombres en base bbb

Application : écriture des nombres en base $b$