Terminale

Divisibilité, division euclidienne et congruences — Exercices d'application

1. Divisibilité dans les entiers relatifs

↩ Revoir le cours

Exercice 1 — ⭐

Donne tous les diviseurs de $30$ dans $\mathbb{Z}$ .
Vrai ou faux ? Justifie. a) $-7 \mid 91$ ; b) $0 \mid 5$ ; c) si $4 \mid a$ et $6 \mid a$ , alors $24 \mid a$ .
Montre que, pour tout entier $n$ , $n(n + 1)$ est pair.

Voir le corrigé

$\pm 1$ , $\pm 2$ , $\pm 3$ , $\pm 5$ , $\pm 6$ , $\pm 10$ , $\pm 15$ , $\pm 30$ .
a) Vrai : $91 = (-13) \times (-7)$ . b) Faux : $0 \times k = 0 \neq 5$ pour tout $k$ . c) Faux : $a = 12$ est divisible par $4$ et par $6$ , mais pas par $24$ .
Parmi deux entiers consécutifs $n$ et $n + 1$ , l’un est pair : $n = 2k$ donne $n(n + 1) = 2k(n + 1)$ ; $n + 1 = 2k$ donne $n(n + 1) = 2kn$ . Dans les deux cas, le produit est pair.

Exercice 2 — ⭐⭐

Détermine les entiers relatifs $n$ tels que $n - 1$ divise $n + 5$ .
Détermine les entiers naturels $n$ tels que $2n + 1$ divise $n + 8$ .

Voir le corrigé

$n - 1 \mid n - 1$ ; s’il divise $n + 5$ , il divise $(n + 5) - (n - 1) = 6$ . Donc $n - 1 \in \{\pm 1\,;\,\pm 2\,;\,\pm 3\,;\,\pm 6\}$ , soit $n \in \{-5\,;\,-2\,;\,-1\,;\,0\,;\,2\,;\,3\,;\,4\,;\,7\}$ . Réciproquement, chacune convient (par exemple $n = 7$ : $6 \mid 12$ ).
Si $2n + 1 \mid n + 8$ , alors $2n + 1 \mid 2(n + 8) - (2n + 1) = 15$ . Comme $n \geqslant 0$ , $2n + 1 \in \{1\,;\,3\,;\,5\,;\,15\}$ , soit $n \in \{0\,;\,1\,;\,2\,;\,7\}$ . Vérification : $1 \mid 8$ , $3 \mid 9$ , $5 \mid 10$ , $15 \mid 15$ . Les quatre valeurs conviennent.

2. Division euclidienne

↩ Revoir le cours

Exercice 3 — ⭐⭐

Effectue la division euclidienne de $2\,027$ par $13$ , puis de $-2\,027$ par $13$ .
Dans la division de $a$ par $9$ , le reste est $7$ . Quel est le reste de la division de $a + 5$ par $9$ ? de $4a$ par $9$ ?
Montre que, pour tout entier $n$ , $n^2$ est de la forme $4k$ ou $4k + 1$ (on distinguera $n$ pair et $n$ impair). En déduire que $2\,027$ n’est pas la somme de deux carrés.

Voir le corrigé

$2\,027 = 13 \times 155 + 12$ ; $-2\,027 = 13 \times (-156) + 1$ (reste $1$ , car $-2\,027 = -2\,028 + 1$ ).
$a = 9q + 7$ . $a + 5 = 9q + 12 = 9(q + 1) + 3$ : reste $3$ . $4a = 36q + 28 = 9(4q + 3) + 1$ : reste $1$ .
$n = 2m$ : $n^2 = 4m^2$ . $n = 2m + 1$ : $n^2 = 4m^2 + 4m + 1 = 4(m^2 + m) + 1$ . Une somme de deux carrés est donc de la forme $4k$ , $4k + 1$ ou $4k + 2$ . Or $2\,027 = 4 \times 506 + 3$ : ce n’est pas une somme de deux carrés.

3. Congruences

↩ Revoir le cours

Exercice 4 — ⭐

Vrai ou faux : $47 \equiv 2\ [9]$ ; $-13 \equiv 3\ [8]$ ; $100 \equiv -1\ [101]$ ; $25 \equiv 1\ [6]$ .
Donne le plus petit entier naturel congru à $-45$ modulo $7$ .
Aujourd’hui est un vendredi. Quel jour de la semaine serons-nous dans $1\,000$ jours ?

Voir le corrigé

Vrai ( $45 = 5 \times 9$ ) ; vrai ( $-16 = -2 \times 8$ ) ; vrai ( $101 \mid 101$ ) ; vrai ( $24 = 4 \times 6$ ).
$-45 = 7 \times (-7) + 4$ : c’est $4$ .
$1\,000 = 7 \times 142 + 6$ : $1\,000 \equiv 6\ [7]$ . Six jours après un vendredi : jeudi.

4. Compatibilité avec les opérations

↩ Revoir le cours

Exercice 5 — ⭐⭐

Détermine le reste de la division de $3^{2027}$ par $8$ .
Détermine le reste de la division de $2^{2026}$ par $7$ .
Montre que, pour tout entier naturel $n$ , $4^n + 2 \equiv 0\ [3]$ .

Voir le corrigé

$3^2 = 9 \equiv 1\ [8]$ . $2\,027 = 2 \times 1\,013 + 1$ , donc $3^{2027} = (3^2)^{1013} \times 3 \equiv 3\ [8]$ . Reste $3$ .
$2^3 = 8 \equiv 1\ [7]$ . $2\,026 = 3 \times 675 + 1$ , donc $2^{2026} \equiv 2\ [7]$ . Reste $2$ .
$4 \equiv 1\ [3]$ , donc $4^n \equiv 1\ [3]$ et $4^n + 2 \equiv 3 \equiv 0\ [3]$ .

Exercice 6 — ⭐⭐⭐

Complète la table des restes de $n^3$ modulo $7$ selon le reste de $n$ modulo $7$ .
En déduire que, pour tout entier $n$ , $n^3 \equiv -1$ , $0$ ou $1\ [7]$ .
L’équation $x^3 - 7y = 3$ a-t-elle des solutions entières ?
Écris une fonction Python restes_cubes(n) qui renvoie la liste des restes de $k^3$ modulo $n$ pour $k$ de $0$ à $n - 1$ .

Voir le corrigé

$n \equiv$ $0$ $1$ $2$ $3$ $4$ $5$ $6$
$n^3 \equiv$ $0$ $1$ $1$ $6$ $1$ $6$ $6$
Les restes possibles sont $0$ , $1$ et $6$ , et $6 \equiv -1\ [7]$ .
Si $x^3 - 7y = 3$ , alors $x^3 \equiv 3\ [7]$ , ce qui est impossible d’après la table : pas de solution.

$n \equiv$	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$n^3 \equiv$	$0$	$1$	$1$	$6$	$1$	$6$	$6$

def restes_cubes(n):
    return [k**3 % n for k in range(n)]

print(restes_cubes(7))   # [0, 1, 1, 6, 1, 6, 6]

5. Critères de divisibilité et congruences à résoudre

↩ Revoir le cours

Exercice 7 — ⭐⭐

Sans poser la division, détermine le reste de $123\,456\,789$ modulo $9$ et modulo $11$ .
Le nombre $\overline{7a5b}$ (chiffres $7$ , $a$ , $5$ , $b$ ) est divisible par $9$ et par $5$ . Trouve toutes les possibilités.
Démontre le critère de divisibilité par $4$ : un entier est divisible par $4$ si et seulement si le nombre formé par ses deux derniers chiffres l’est (on remarquera que $100 \equiv 0\ [4]$ ).

Voir le corrigé

Somme des chiffres : $45 \equiv 0\ [9]$ , donc reste $0$ . Somme alternée depuis les unités : $9 - 8 + 7 - 6 + 5 - 4 + 3 - 2 + 1 = 5$ , reste $5$ modulo $11$ .
Divisible par $5$ : $b = 0$ ou $b = 5$ . Divisible par $9$ : $7 + a + 5 + b \equiv 0\ [9]$ . Si $b = 0$ : $12 + a \equiv 0$ , $a = 6$ ( $7\,650$ ). Si $b = 5$ : $17 + a \equiv 0$ , $a = 1$ ( $7\,155$ ). Deux nombres : $7\,650$ et $7\,155$ .
$N = 100m + d$ où $d$ est le nombre formé par les deux derniers chiffres. $100 \equiv 0\ [4]$ , donc $N \equiv d\ [4]$ : $4 \mid N$ si et seulement si $4 \mid d$ .

Exercice 8 — ⭐⭐⭐

Clé de contrôle ISBN-10. Un code ISBN-10 $a_1 a_2 \dots a_{10}$ est valide si $S = 10a_1 + 9a_2 + 8a_3 + \dots + 2a_9 + a_{10} \equiv 0\ [11]$ (la clé $a_{10}$ peut valoir $10$ , notée X).

Vérifie que $2\text{-}07\text{-}036002\text{-}4$ est un code valide.
Trouve la clé du code $2\text{-}10\text{-}004533\text{-}?$ .
Montre que si l’on échange deux chiffres consécutifs différents, l’erreur est toujours détectée.

Voir le corrigé

$S = 10 \times 2 + 9 \times 0 + 8 \times 7 + 7 \times 0 + 6 \times 3 + 5 \times 6 + 4 \times 0 + 3 \times 0 + 2 \times 2 + 4 = 132 = 11 \times 12$ : valide.
Sans la clé : $10 \times 2 + 9 \times 1 + 8 \times 0 + 7 \times 0 + 6 \times 0 + 5 \times 4 + 4 \times 5 + 3 \times 3 + 2 \times 3 = 84$ . On veut $84 + a_{10} \equiv 0\ [11]$ ; $84 = 7 \times 11 + 7$ , donc $a_{10} \equiv -7 \equiv 4\ [11]$ : la clé est $4$ .
Si $a_i$ (coefficient $c$ ) et $a_{i+1}$ (coefficient $c - 1$ ) sont échangés, $S$ change de $(ca_{i+1} + (c - 1)a_i) - (ca_i + (c - 1)a_{i+1}) = a_{i+1} - a_i$ . Ce nombre est non nul et compris entre $-9$ et $9$ : il n’est pas multiple de $11$ , donc la nouvelle somme n’est plus $\equiv 0\ [11]$ et l’erreur est détectée.