Exercices — Arithmétique : divisibilité et congruences

1. On cherche les produits de deux entiers égaux à $60$ : $60 = 1 \times 60 = 2 \times 30 = 3 \times 20 = 4 \times 15 = 5 \times 12 = 6 \times 10$. Les diviseurs positifs de $60$ sont donc :

$1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 10,\ 12,\ 15,\ 20,\ 30,\ 60$

2. Si $d \mid a$ et $d \mid b$, il existe des entiers $k$ et $k'$ tels que $a = kd$ et $b = k'd$. Alors :

$3a - 2b = 3kd - 2k'd = (3k - 2k')d$

et $3k - 2k'$ est un entier : donc $d \mid 3a - 2b$. (C’est la propriété générale : $d$ divise toute combinaison linéaire $au + bv$.)

3. On écrit $n + 11 = (n + 2) + 9$. Comme $n + 2$ divise $n + 2$, on en déduit que $n + 2$ divise $n + 11$ si, et seulement si, $n + 2$ divise $9$. Les diviseurs de $9$ dans $\mathbb{Z}$ sont $-9$, $-3$, $-1$, $1$, $3$ et $9$, d’où $n + 2 \in \{-9\,;\,-3\,;\,-1\,;\,1\,;\,3\,;\,9\}$, c’est-à-dire :

$n \in \{-11\,;\,-5\,;\,-3\,;\,-1\,;\,1\,;\,7\}$

Vérification rapide pour $n = 7$ : $n + 2 = 9$ divise bien $n + 11 = 18$ ✓.

Réflexe à retenir : pour « $f(n)$ divise $g(n)$ », fais apparaître une combinaison linéaire constante ($g(n) = f(n) + c$ ou similaire) : le problème devient « $f(n)$ divise la constante $c$ », et il n’y a qu’un nombre fini de cas.

1. $17 \times 14 = 238$ et $247 - 238 = 9$, avec $0 \leq 9 < 17$ :

$247 = 17 \times 14 + 9 \qquad \text{(quotient } 14\text{, reste } 9\text{)}$

De même $7 \times 14 = 98$ : $100 = 7 \times 14 + 2$ (quotient $14$, reste $2$).

2. Attention au piège : le reste doit rester entre $0$ et $6$. On cherche le multiple de $7$ juste en dessous de $-100$ : c’est $7 \times (-15) = -105$. D’où :

$-100 = 7 \times (-15) + 5 \qquad \text{(quotient } -15\text{, reste } 5\text{)}$

Écrire $-100 = 7 \times (-14) - 2$ est numériquement vrai, mais $-2$ n’est pas un reste !

3. $2a = 26q + 10 = 13 \times (2q) + 10$, avec $0 \leq 10 < 13$ : le reste de la division euclidienne de $2a$ par $13$ est $10$. (En langage de congruences : $a \equiv 5 \pmod{13}$ donc $2a \equiv 10 \pmod{13}$.)

Réflexe à retenir : une division euclidienne, c’est une écriture $a = bq + r$ ET une condition $0 \leq r < b$ — les deux. Sur les nombres négatifs, vérifie toujours la condition sur le reste avant de conclure.

1. On calcule $3x$ pour chaque reste possible, puis on réduit modulo $7$ :

$x \equiv$	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$3x \equiv$	$0$	$3$	$6$	$2$	$5$	$1$	$4$

(Par exemple $3 \times 4 = 12 = 7 + 5 \equiv 5$, et $3 \times 6 = 18 = 14 + 4 \equiv 4$.)

2. La ligne du bas ne vaut $5$ que pour $x \equiv 4 \pmod 7$. Les solutions sont donc exactement les entiers de la forme :

$x = 4 + 7k, \qquad k \in \mathbb{Z}$

Vérification : $3 \times 4 = 12 \equiv 5 \pmod 7$ ✓.

3. $2026 = 7 \times 289 + 3$, donc $2026 \equiv 3 \pmod 7$ : ce n’est pas une solution ($3 \not\equiv 4$).

Réflexe à retenir : pour résoudre $ax \equiv b \pmod n$, le tableau des restes est la méthode qui marche toujours : $n$ cas à tester, pas un de plus. Et pense à vérifier ta solution en la réinjectant — ça prend cinq secondes.

1. $2^1 \equiv 2$, $2^2 \equiv 4$ et $2^3 = 8 \equiv 1 \pmod 7$. On a trouvé une puissance congrue à $1$ : c’est la clé de tout l’exercice.

2. On divise l’exposant par $3$ : $2026 = 3 \times 675 + 1$. Alors, par compatibilité des congruences avec les puissances et le produit :

$2^{2026} = \left(2^3\right)^{675} \times 2^1 \equiv 1^{675} \times 2 \equiv 2 \pmod 7$

Le reste de la division euclidienne de $2^{2026}$ par $7$ est $2$.

3. Le chiffre des unités, c’est le reste modulo $10$. Les puissances de $3$ modulo $10$ : $3^1 \equiv 3$, $3^2 \equiv 9$, $3^3 = 27 \equiv 7$, $3^4 = 81 \equiv 1 \pmod{10}$ — cycle de longueur $4$. Or $2026 = 4 \times 506 + 2$, donc :

$3^{2026} = \left(3^4\right)^{506} \times 3^2 \equiv 1^{506} \times 9 \equiv 9 \pmod{10}$

Le chiffre des unités de $3^{2026}$ est $9$.

Réflexe à retenir : face à une grande puissance, cherche d’abord une petite puissance congrue à $1$ (ou à $-1$), puis fais la division euclidienne de l’exposant par la longueur du cycle. Le gros du travail se fait sur l’exposant, jamais sur le nombre lui-même.

1. $9 - 2 = 7$, qui est divisible par $7$ : donc $9 \equiv 2 \pmod 7$. Par compatibilité des congruences avec les puissances, pour tout $n \in \mathbb{N}$ :

$9^n \equiv 2^n \pmod 7 \qquad \text{donc} \qquad 9^n - 2^n \equiv 0 \pmod 7$

c’est-à-dire que $7$ divise $9^n - 2^n$. (Deux lignes, sans récurrence : c’est toute l’élégance des congruences.)

2. $10 - (-1) = 11$ est divisible par $11$, donc $10 \equiv -1 \pmod{11}$. Par compatibilité avec les puissances : $10^k \equiv (-1)^k \pmod{11}$ — c’est-à-dire $1$ si $k$ est pair, $-1$ si $k$ est impair.

3. L’écriture décimale donne $N = 1000a + 100b + 10c + d$. Modulo $11$ : $10 \equiv -1$, $100 \equiv 1$ et $1000 \equiv -1$, donc :

$N \equiv -a + b - c + d \equiv d - c + b - a \pmod{11}$

C’est le critère de la somme alternée des chiffres (en partant des unités).

4. Pour $N = 2\,728$ : $d - c + b - a = 8 - 2 + 7 - 2 = 11 \equiv 0 \pmod{11}$. Donc $2\,728$ est divisible par $11$ — en effet $2\,728 = 11 \times 248$ ✓.

Réflexe à retenir : pour montrer qu’une expression est toujours divisible par $n$, traduis en congruence ($\equiv 0 \pmod n$) et utilise la compatibilité avec les opérations — c’est presque toujours plus court qu’une récurrence. Et les critères de divisibilité ne sont rien d’autre que la congruence de $10$ modulo $n$.