← Cours de mathématiques

Chapitre 8 — Divisibilité et congruences

Maths Expertes · Math@mine · Exercices

Ch7 📖 Cours ✏️ Exercices Ch9

I. Divisibilité et division euclidienne

Exercice 1

Propriétés de la divisibilité

  1. Montrer que si \(a \mid b\) et \(a \mid c\), alors \(a \mid (3b - 5c)\).
  2. Montrer que si \(7 \mid n\), alors \(7 \mid n^2\). La réciproque est-elle vraie ?
  3. Montrer que pour tout entier \(n\), on a \(6 \mid n(n+1)(n+2)\).
  4. Trouver tous les entiers \(n\) tels que \(n \mid 24\).
Correction

a. \(a \mid b\) et \(a \mid c\) ⟹ \(a \mid (3b - 5c)\) par combinaison linéaire (\(u=3, v=-5\)).

b. Si \(7 \mid n\), alors \(n = 7k\), donc \(n^2 = 49k^2 = 7(7k^2)\), d’où \(7 \mid n^2\). La réciproque est vraie aussi (car 7 est premier) : si \(7 \mid n^2\) alors \(7 \mid n\).

c. Parmi 3 entiers consécutifs, l’un est divisible par 3 (donc \(3 \mid n(n+1)(n+2)\)) et au moins l’un est pair (donc \(2 \mid n(n+1)(n+2)\)). Comme \(\pgcd(2,3)=1\), on conclut \(6 \mid n(n+1)(n+2)\).

d. Les diviseurs de 24 sont \(\pm1, \pm2, \pm3, \pm4, \pm6, \pm8, \pm12, \pm24\).

Exercice 2

Division euclidienne

  1. Effectuer la division euclidienne de 2026 par 17.
  2. Effectuer la division euclidienne de \(-83\) par 9.
  3. ⭐ Approfondissement Quel est le reste de la division de \(100!\) par 101 ? (On utilisera le théorème de Wilson — accessible en Expertes, non exigible au BO : si \(p\) est premier, \((p-1)! \equiv -1 \pmod{p}\).)
Correction

a. \(2026 = 17 \times 119 + 3\). Vérif : \(17\times119=2023\), \(2023+3=2026\) ✓. Reste \(r=3\).

b. \(-83 = 9\times(-10) + 7\) car \(9\times(-10)=-90\) et \(-90+7=-83\) ✓ et \(0\le7<9\). Reste \(r=7\).

c. 101 est premier. Par Wilson : \(100! \equiv -1 \equiv 100 \pmod{101}\). Le reste est 100.

🎓 Démonstration du théorème de Wilson (approfondissement)

Énoncé : Si \(p\) est premier, \((p-1)! \equiv -1 \pmod{p}\).

Preuve. Pour \(p=2\) : \(1! = 1 \equiv -1 \pmod 2\). ✓

Pour \(p\) premier impair : dans \((\mathbb{Z}/p\mathbb{Z})^*\), chaque élément \(a \in \{1,\ldots,p-1\}\) admet un unique inverse \(a^{-1} \bmod p\) (théorème de Bézout, ch9).

On cherche les \(a\) tels que \(a \equiv a^{-1} \pmod p\), i.e. \(a^2 \equiv 1 \pmod p\), soit \((a-1)(a+1) \equiv 0 \pmod p\). Comme \(p\) est premier (Gauss) : \(a \equiv 1\) ou \(a \equiv -1 \pmod p\).

Donc seuls \(1\) et \(p-1 \equiv -1\) sont leurs propres inverses. Les \(p-3\) autres éléments se regroupent en \(\tfrac{p-3}{2}\) paires \(\{a, a^{-1}\}\) dont le produit vaut \(1\) modulo \(p\).

D’où \((p-1)! \;\equiv\; 1 \times \underbrace{1 \times \cdots \times 1}_{(p-3)/2\text{ paires}} \times (p-1) \;\equiv\; -1 \pmod p\). \(\square\)

Hors programme BO mais démonstration accessible en Expertes une fois l’inversibilité modulaire maîtrisée (ch9).

II. Congruences

Exercice 3

Calculs de congruences

  1. Calculer \(17^{50} \pmod{6}\).
  2. Calculer \(2^{100} \pmod{7}\).
  3. Quel est le dernier chiffre de \(3^{2026}\) ? De \(9^{2026}\) ?
  4. Montrer que \(n^3 - n\) est divisible par 6 pour tout entier \(n\).
Correction

a. \(17 \equiv 5 \pmod{6}\). \(5^2=25\equiv1\pmod6\). Donc \(17^{50}\equiv5^{50}=(5^2)^{25}\equiv1^{25}=1\pmod6\).

b. \(2^3=8\equiv1\pmod7\). \(100=33\times3+1\). Donc \(2^{100}\equiv2^1=2\pmod7\).

c. Période de \(3^n\) mod 10 : 3, 9, 7, 1 (période 4). \(2026=506\times4+2\). \(3^{2026}\equiv3^2=9\pmod{10}\) : dernier chiffre 9. \(9^{2026}=(3^2)^{2026}=3^{4052}\equiv3^0=1\pmod{10}\) (car \(4052=4\times1013\)) : dernier chiffre 1.

d. \(n^3-n=(n-1)n(n+1)\) : produit de 3 entiers consécutifs, divisible par \(3!=6\).

III. Critères de divisibilité

Exercice 4

Critères de divisibilité

  1. Sans diviser, déterminer si 123 456 789 est divisible par 9.
  2. Montrer que \(\overline{abcabc}\) est toujours divisible par 7, 11 et 13.
  3. Vérifier la règle de divisibilité par 7 sur 343 : soustraire le double du dernier chiffre au nombre formé par les chiffres restants.
Correction

a. Somme des chiffres : \(1+2+\cdots+9=45=9\times5\). Donc \(9 \mid 123\,456\,789\). ✓

b. \(\overline{abcabc} = \overline{abc}\times1001\). Or \(1001=7\times11\times13\). Donc divisible par 7, 11 et 13.

c. \(343\) : dernier chiffre 3, reste 34. \(34-2\times3=28=4\times7\). Divisible par 7. ✓ (\(343=7^3\).)

Maths Expertes — Math@mine