Fiche de cours Logimaths | Terminale maths expertes
Fiche de cours : Divisibilité et congruences
L'arithmétique des restes : calculer modulo n comme sur une horloge
I. La divisibilité dans ℤ
Diviseurs et multiples
Pour a, b entiers (b ≠ 0) : b divise a (noté b | a) s'il existe un entier k tel que a = kb. On dit aussi que a est un multiple de b.
Propriétés clés :
Propriétés clés :
- transitivité : si c | b et b | a, alors c | a ;
- combinaisons linéaires : si d | a et d | b, alors d divise au + bv pour tous entiers u, v (l'outil n°1 des démonstrations d'arithmétique) ;
- 1 et −1 divisent tout ; tout entier non nul divise 0.
La division euclidienne
Pour a entier et b entier naturel non nul, il existe un unique couple (q, r) tel que : a = bq + r avec 0 \leq r < b.
q est le quotient, r le reste. Exemple : 127 = 12 × 10 + 7 : reste 7. ⚠️ Le reste est TOUJOURS positif ou nul et STRICTEMENT inférieur à b : −17 = 5 × (−4) + 3, le reste de −17 par 5 est 3, pas −2.
q est le quotient, r le reste. Exemple : 127 = 12 × 10 + 7 : reste 7. ⚠️ Le reste est TOUJOURS positif ou nul et STRICTEMENT inférieur à b : −17 = 5 × (−4) + 3, le reste de −17 par 5 est 3, pas −2.
🎮 Entraîne-toi : divise ou pas ?
b divise a si la division tombe juste (reste nul).
🎮 Entraîne-toi : le reste euclidien
Cherche le plus grand multiple de b qui ne dépasse pas a : le reste est ce qui dépasse.
II. Les congruences
a ≡ b (mod n)
Pour n ≥ 2 : a est congru à b modulo n, noté a \equiv b \;[n], si n divise a − b.
De façon équivalente : a et b ont le même reste dans la division euclidienne par n.
Image : l'horloge. Modulo 12, il est « la même heure » à 15 h et à 3 h : 15 ≡ 3 [12]. Tout entier est congru à son reste, qui vit entre 0 et n − 1.
De façon équivalente : a et b ont le même reste dans la division euclidienne par n.
Image : l'horloge. Modulo 12, il est « la même heure » à 15 h et à 3 h : 15 ≡ 3 [12]. Tout entier est congru à son reste, qui vit entre 0 et n − 1.
Les règles de calcul (compatibilité)
Si a \equiv b \;[n] et c \equiv d \;[n], alors :
- a + c \equiv b + d \;[n] et a - c \equiv b - d \;[n] ;
- ac \equiv bd \;[n] ;
- a^k \equiv b^k \;[n] pour tout entier naturel k.
🎮 Entraîne-toi : congrus ou pas ?
Teste si n divise la différence a − b (ou compare les restes).
III. La méthode des restes de puissances
Méthode : trouver le reste de aᵏ modulo n
- Remplacer a par son reste modulo n (plus petit = plus confortable, quitte à utiliser un reste « négatif » comme −1) ;
- calculer les premières puissances jusqu'à repérer un cycle (souvent atteindre 1 ou −1) ;
- réduire l'exposant grâce au cycle.
Exemple rédigé : le reste de 7²⁰²⁶ modulo 10
Puissances de 7 modulo 10 : 7, 9, 3, 1, puis ça recommence (cycle de longueur 4).
2026 = 4 \times 506 + 2 : \begin{aligned}7^{2026} &\equiv 7^2 \\ &\equiv 9 \;[10]\end{aligned}
Le chiffre des unités de 7^{2026} est donc 9 (travailler modulo 10, c'est exactement regarder le chiffre des unités).
2026 = 4 \times 506 + 2 : \begin{aligned}7^{2026} &\equiv 7^2 \\ &\equiv 9 \;[10]\end{aligned}
Le chiffre des unités de 7^{2026} est donc 9 (travailler modulo 10, c'est exactement regarder le chiffre des unités).
Exemple rédigé : l'astuce du −1
Reste de 10^{2026} modulo 11 : comme 10 \equiv -1 \;[11], on a \begin{aligned}10^{2026} &\equiv (-1)^{2026} \\ &= 1 \;[11]\end{aligned}
C'est le cœur du critère de divisibilité par 11 (somme alternée des chiffres), comme 10 \equiv 1 \;[9] explique le critère de divisibilité par 9 (somme des chiffres).
C'est le cœur du critère de divisibilité par 11 (somme alternée des chiffres), comme 10 \equiv 1 \;[9] explique le critère de divisibilité par 9 (somme des chiffres).
🎮 Entraîne-toi : restes de puissances
Réduis la base, cherche le cycle, réduis l'exposant.
IV. Résoudre avec un tableau de congruences
Méthode : le tableau exhaustif des restes
Modulo n, tout entier est congru à 0, 1, …, n − 1 : pour étudier une équation ou une divisibilité, il suffit de tester ces n cas dans un tableau.
Exemple : montrer que n^2 + n est toujours pair. Modulo 2 : si n ≡ 0, alors n² + n ≡ 0 ; si n ≡ 1, alors n² + n ≡ 1 + 1 ≡ 0. Dans tous les cas, 2 divise n² + n. ∎
Exemple : montrer que n^2 + n est toujours pair. Modulo 2 : si n ≡ 0, alors n² + n ≡ 0 ; si n ≡ 1, alors n² + n ≡ 1 + 1 ≡ 0. Dans tous les cas, 2 divise n² + n. ∎
⚠️ Une congruence n'est pas une égalité
« x ≡ 2 [5] » ne signifie pas x = 2, mais x ∈ {… ; −3 ; 2 ; 7 ; 12 ; …} : une infinité de solutions, tous les entiers de la forme 2 + 5k. Toujours conclure en décrivant la famille complète.
👆 ▶ À toi : montre avec un tableau modulo 3 que n³ − n est toujours divisible par 3. Vérifie
n ≡ 0 : n³ − n ≡ 0. n ≡ 1 : 1 − 1 ≡ 0. n ≡ 2 : 8 − 2 = 6 ≡ 0.
Dans les trois cas, 3 divise n³ − n. ∎ (Il est même divisible par 6 : produit de trois entiers consécutifs n(n − 1)(n + 1).)
Dans les trois cas, 3 divise n³ − n. ∎ (Il est même divisible par 6 : produit de trois entiers consécutifs n(n − 1)(n + 1).)