Congruence dans ℤ
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é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
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é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$
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 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$