Divisibilité, division euclidienne et congruences (Terminale)

Q: Le reste d'une division euclidienne peut-il être négatif ?

Non : le reste vérifie toujours 0 \leqslant r < b. Par exemple -47 = 6 \times (-8) + 1, donc le reste de -47 par 6 est 1 et le quotient est -8.

Q: Quelle est la différence entre « reste » et « congruence » ?

Le reste est un nombre précis entre 0 et n-1. La congruence a \equiv b\;[n] dit seulement que a et b ont le même reste : on peut donc remplacer un nombre par n'importe quel entier qui lui est congru, par exemple -1, pour simplifier les calculs.

Q: Une congruence ax \equiv b\;[n] a-t-elle toujours des solutions ?

Non. Par exemple 4x \equiv 3\;[6] n'a aucune solution, car 4x n'a que les restes 0, 4 ou 2 modulo 6. Un tableau de restes permet de trancher ; le théorème de Bézout, vu au chapitre suivant, donne un critère général.

Ce chapitre ouvre le thème Arithmétique des maths expertes. Tu y apprends à manipuler la divisibilité et la division euclidienne dans $\mathbb{Z}$ , puis les congruences, qui permettent de calculer des restes sans effectuer d'énormes calculs. Tu les utilises ensuite pour établir des tests de divisibilité et résoudre des congruences simples.

Définitions

$a$ divise $b$ , noté $a \mid b$ , s'il existe $k \in \mathbb{Z}$ tel que $b = ka$ .
Division euclidienne : pour $a \in \mathbb{Z}$ et $b \in \mathbb{N}^*$ , il existe un unique couple $(q\,;\,r)$ tel que $a = bq + r$ et $0 \leqslant r < b$ .
Pour $n \geqslant 2$ , $a \equiv b\;[n]$ signifie que $n$ divise $a - b$ .
Le reste de $a$ modulo $n$ est l'unique $r \in \{0,\dots,n-1\}$ tel que $a \equiv r\;[n]$ .

Propriétés

Si $a \mid b$ et $a \mid c$ , alors $a \mid bu + cv$ pour tous entiers $u$ et $v$ .
$a \equiv b\;[n]$ si et seulement si $a$ et $b$ ont le même reste dans la division euclidienne par $n$ .
Si $a \equiv b\;[n]$ et $c \equiv d\;[n]$ , alors $a + c \equiv b + d\;[n]$ , $ac \equiv bd\;[n]$ et $a^p \equiv b^p\;[n]$ .
On ne peut pas diviser dans une congruence : $2 \times 3 \equiv 2 \times 8\;[10]$ mais $3 \not\equiv 8\;[10]$ .

Formules à retenir

$10 \equiv 1\;[9]$ : un entier est congru modulo 9 (et modulo 3) à la somme de ses chiffres.
$10 \equiv -1\;[11]$ : un entier est congru modulo 11 à la somme alternée de ses chiffres.
Si $a^p \equiv 1\;[n]$ et $N = pk + r$ , alors $a^N \equiv a^r\;[n]$ .
Test par 7 : $7 \mid 10a + b \iff 7 \mid a - 2b$ .

Exemple corrigé

Déterminer le reste de la division euclidienne de $3^{2026}$ par $7$ .

On calcule les restes des premières puissances de 3 modulo 7 : $3,\ 2,\ 6,\ 4,\ 5,\ 1$ .
On obtient $3^6 \equiv 1\;[7]$ : les restes forment un cycle de longueur 6.
On divise l'exposant par 6 : $2026 = 6 \times 337 + 4$ .
Donc $3^{2026} = (3^6)^{337} \times 3^4 \equiv 1 \times 81 \equiv 4\;[7]$ .
Le reste de la division de $3^{2026}$ par 7 est 4.

Ce que tu sauras faire

Savoir déterminer tous les diviseurs d'un entier et utiliser les combinaisons linéaires
Savoir effectuer une division euclidienne, y compris d'un entier négatif
Savoir utiliser la compatibilité des congruences avec l'addition, la multiplication et les puissances
Savoir calculer le reste de $a^N$ modulo $n$ à l'aide d'un cycle de restes
Savoir établir et utiliser les tests de divisibilité par 2, 3, 4, 5, 9, 11 et 7
Savoir résoudre une congruence $ax \equiv b\;[n]$ à l'aide d'un tableau de restes

Questions fréquentes

Le reste d'une division euclidienne peut-il être négatif ?

Non : le reste vérifie toujours $0 \leqslant r < b$ . Par exemple $-47 = 6 \times (-8) + 1$ , donc le reste de $-47$ par 6 est 1 et le quotient est $-8$ .

Quelle est la différence entre « reste » et « congruence » ?

Le reste est un nombre précis entre 0 et $n-1$ . La congruence $a \equiv b\;[n]$ dit seulement que $a$ et $b$ ont le même reste : on peut donc remplacer un nombre par n'importe quel entier qui lui est congru, par exemple $-1$ , pour simplifier les calculs.

Une congruence $ax \equiv b\;[n]$ a-t-elle toujours des solutions ?

Non. Par exemple $4x \equiv 3\;[6]$ n'a aucune solution, car $4x$ n'a que les restes 0, 4 ou 2 modulo 6. Un tableau de restes permet de trancher ; le théorème de Bézout, vu au chapitre suivant, donne un critère général.