Chargement de l'audio en cours
Plus

Plus

3. Congruences
P.98-99

Mode édition
Ajouter

Ajouter

Terminer

Terminer

COURS


3
Congruences




A
Définition


Définition

Soient mm un entier naturel non nul, et aa et bb deux entiers relatifs.
On dit que aa et bb sont congrus modulo m\boldsymbol{m} lorsqu’ils ont le même reste dans la division euclidienne par mm.
On dit aussi que aa est congru à b\boldsymbol{b} modulo m\boldsymbol{m}.

NOTATION

On note ab[m]a \equiv b[m] ; ab(m)a \equiv b(m) ou abmodma \equiv b \bmod m.

Exemple

15=2×7+115 = 2 \times 7 + 1 et 21=2×10+121 = 2 \times 10 + 1 donc 1521[2]15 \equiv 21[2].

Théorème

Soient mm un entier naturel non nul et aa et bb deux entiers relatifs. ab[m]a \equiv b[m] si, et seulement si, m(ab)m |(a-b).

Remarque

En particulier, si a0[m]a \equiv 0[m], alors m  am\ |\ a.

DÉMONSTRATION

Voir exercice
96
p. 109
.

B
Congruences et opérations


Propriété

Soient aa, bb et cc trois entiers relatifs et mm un entier naturel non nul.
Si ab[m]a \equiv b[m] et bc[m]b \equiv c[m], alors ac[m]a \equiv c[m].

Remarque

On dit que la relation de congruence est transitive.

DÉMONSTRATION

D’après les hypothèses, aa et bb ont le même reste dans la division euclidienne par mm, et bb et cc ont le même reste dans la division euclidienne par mm, donc aa et cc ont le même reste dans la division euclidienne par mm donc ac[m]a \equiv c[m].

Exemple

2518[3]251 \equiv 8[3] et 82[3]8 \equiv 2[3] donc 2512[3]251 \equiv 2[3].

Propriétés

Soient aa, bb, cc et dd quatre entiers relatifs et mm un entier naturel non nul.
1. Compatibilité avec l'addition
Si ab[m]a \equiv b[m] et cd[m]c \equiv d[m], alors a+cb+d[m]a+c \equiv b+d[m].

2. Compatibilité avec la multiplication
Si ab[m]a \equiv b[m] et cd[m]c \equiv d[m], alors a×cb×d[m]a \times c \equiv b\times d[m].

3. Compatibilité avec les puissances
Soit pp un entier naturel non nul. Si ab[m]a \equiv b[m], alors apbp[m]a^p \equiv b^p[m].

Cas particuliers

cc[m]c \equiv c[m] donc, si ab[m]a \equiv b[m], alors a+cb+c[m]a+c \equiv b+c[m] et a×cb×c[m]a \times c \equiv b \times c[m].

ATTENTION

Il n’y a pas de compatibilité avec la division : 6226[4]62 \equiv 26[4] mais 3131 et 1313 ne sont pas congrus modulo 44.

DÉMONSTRATION

Voir exercice
97
p. 109
.

Application et méthode - 5

Énoncé

Montrer en utilisant un tableau de congruence que, pour tout entier relatif nn, n(n+1)(2n+1)n(n + 1)(2n + 1) est divisible par 33.

Solution


On dresse un tableau de congruence de nn modulo 3.
n[3]\boldsymbol{n \equiv … [3]} 00 11 22
(n+1)[3]\boldsymbol{(n+1) \equiv … [3]} 11 22 303 \equiv 0
(2n+1)[3]\boldsymbol{(2n+1) \equiv … [3]} 1 303 \equiv 0 525 \equiv 2
Produit
n(n+1)(2n+1)\boldsymbol{n(n+1)(2n+1)}[3]\boldsymbol{\equiv … [3]}
0×1×100 \times 1 \times 1 \equiv 0 1×2×001 \times 2 \times 0 \equiv 0 2×0×202 \times 0 \times 2 \equiv 0

On remarque que, pour tout entier nn, n(n+1)(2n+1)0[3]n(n+1)(2 n+1) \equiv 0[3], c’est‑à‑dire que n(n+1)(2n+1)n(n+1)(2 n+1) est divisible par 33.

Pour s'entraîner : exercices 50 et 51

Méthode

On recherche les restes possibles de nn dans la division par 33 (conséquence de la division euclidienne).
On complète le tableau de congruence pour obtenir, dans la dernière ligne, les restes possibles de la division de n(n+1)(2n+1)n(n + 1)(2n + 1) par 33. Ces restes étant toujours nuls, on en déduit que, pour tout entier nn, n(n+1)(2n+1)n(n + 1)(2n + 1) est divisible par 33.

C
Inverse modulo m\boldsymbol{m}


Définition

Soient aa un entier relatif et mm un entier naturel non nul.
On dit que aa est inversible modulo m\boldsymbol{m} lorsqu’il existe un entier bb tel que a×b1[m]a \times b \equiv 1 [m].

Exemple

88 est inversible modulo 33 car 8×21[3]8 \times 2 \equiv 1 [3]. 22 est donc un inverse de 88 modulo 22.

Application et méthode - 6

Énoncé

1. Démontrer que 33 est inversible modulo 55.
2. Montrer que 44 n’admet pas d’inverse modulo 66.

Solution


1. Soit bb un entier relatif. On établit un tableau de congruence modulo 55.

b[5]\boldsymbol{b \equiv …[5]} 00 11 22 33 44
3b[5]\boldsymbol{3b \equiv …[5]} 00 33 11 44 22

On a donc 3×21[5]3 \times 2 \equiv 1 [5] donc 22 est un inverse de 33 modulo 55.
Cet inverse n’est d’ailleurs pas unique : tout entier s’écrivant 5k+25k + 2, avec kZk \in \mathbb{Z}, est un inverse de 33 modulo 55.

2. Soit cc un entier relatif. On établit un tableau de congruence modulo 66.

c[6]\boldsymbol{c \equiv …[6]} 00 11 22 33 44 55
4c[6]\boldsymbol{4c \equiv …[6]} 00 44 22 00 44 22

Il n’existe pas d’entier cc tel que 4c1[6]4c \equiv 1 [6] Donc 44 n’admet pas d’inverse modulo 66.

Pour s'entraîner : exercices 52 et 53 p. 105

Méthode

1. On recherche un entier bb tel que 3b1[5]3b \equiv 1 [5].
Pour cela, on établit un tableau de congruence modulo 55, en recherchant les restes possibles de 3b3b modulo 55. Dans le tableau, on recherche s’il existe un entier bb tel que 3b1[5]3b \equiv 1 [5]. Dans ce cas, on observe que l’entier 22 est une solution.

2. On établit un tableau de congruence modulo 66. On observe que 4c4c n’est jamais congru à 11 modulo 66.



Utilisation des cookies
En poursuivant votre navigation sans modifier vos paramètres, vous acceptez l'utilisation des cookies permettant le bon fonctionnement du service.
Pour plus d’informations, cliquez ici.