Congruences

Échauffement

Trois questions rapides sur des leçons déjà vues.

Découvrir

Il est 22 h. Quelle heure sera-t-il dans 5 heures ?

3 h
27 h

L'idée clé

Deux entiers sont congrus s'ils ont le même reste.

$a \equiv b\ [n]$ signifie que $n$ divise $a - b$ .

On peut additionner, multiplier et élever à une puissance : si $a \equiv b\ [n]$ et $c \equiv d\ [n]$ , alors $a + c \equiv b + d$ , $ac \equiv bd$ et $a^k \equiv b^k\ [n]$ .

Exemple corrigé

Quel est le reste de la division de $7^{100}$ par 5 ?

7 \equiv 2\ [5]

On réduit.

2^4 \equiv 1\ [5]

2⁴ = 16 ≡ 1.

7^{100} \equiv (2^4)^{25} \equiv 1\ [5]

100 = 4 × 25.

À toi, guidé

À toi : réduis 38 modulo 7.

3

38 = 7 × 5 + 3.

Entraînement ★

Quel est le plus petit entier positif $x$ tel que $18 \equiv x\ [4]$ ?
Quel est le plus petit entier positif $x$ tel que $29 \equiv x\ [9]$ ?
Quel est le plus petit entier positif $x$ tel que $9 \equiv x\ [4]$ ?

Attention !

Entraînement ★★

Quel est le reste de la division de $2^{ 20 }$ par 5 ?
Quel est le reste de la division de $2^{ 24 }$ par 5 ?

On sait que $x \equiv 2\ [9]$ et $y \equiv 1\ [9]$ . Quel est le reste de $x + y$ modulo 9 ?

Quel est le reste de la division de $10^{ 10 }$ par 11 ?

Bilan

Trois questions pour vérifier que c'est acquis.

Quel est le plus petit entier positif $x$ tel que $18 \equiv x\ [4]$ ?
Quel est le plus petit entier positif $x$ tel que $29 \equiv x\ [9]$ ?
Quel est le plus petit entier positif $x$ tel que $9 \equiv x\ [4]$ ?

Fiche résumé

Congruences

$a \equiv b\ [n] \iff n \mid a - b$ .
On additionne, on multiplie, on élève à une puissance.

Attention : on ne divise pas dans une congruence.

Fin de la leçon

Leçon suivante: Nombres premiers et décomposition Retour au chapitre

À propos de cette leçon