Quel est le dernier chiffre de 32026 ? Quel jour de la semaine sera-t-il dans 1 000 jours ? Pour répondre sans calculer des nombres gigantesques, on ne garde que les restes : c’est le principe des congruences, introduites par Gauss, qui sont aujourd’hui au cœur de la cryptographie.
Une question sur ce cours ?
ULU, le tuteur d’ULUMINE, t’aide à partir de ce cours.
Objectifs
- Utiliser la définition et les propriétés de la divisibilité dans ℤ
- Effectuer une division euclidienne, y compris d’un entier négatif
- Calculer avec les congruences (sommes, produits, puissances)
- Déterminer le reste d’une grande puissance et résoudre une congruence simple
1. Divisibilité dans ℤ
Diviseur, multiple : Soit a et b deux entiers relatifs. On dit que 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.
- Si a | b et b | c, alors a | c (transitivité).
- Si d | a et d | b, alors d | au + bv pour tous entiers u et v (combinaison linéaire).
- Si a | b avec b ≠ 0, alors |a| ≤ |b|.
Trouver les entiers naturels n tels que n + 3 divise n + 10
- n + 3 divise n + 3 et n + 10, donc il divise leur différence 7.
- n + 3 ∈ {1 ; 7}, et n + 3 ≥ 3, donc n + 3 = 7.
n = 4 (vérification : 7 divise 14).
2. Division euclidienne
Théorème de la division euclidienne : Soit a ∈ ℤ et b ∈ ℕ*. Il existe un unique couple (q ; r) d’entiers tel que a = bq + r avec 0 ≤ r < b. q est le quotient et r le reste.
Division de −17 par 5
- −17 = 5 × (−3) − 2 ne convient pas : le reste doit être positif.
- −17 = 5 × (−4) + 3, avec 0 ≤ 3 < 5.
q = −4 et r = 3.
3. Congruences
Congruence modulo n : Soit n ≥ 2. On dit que a est congru à b modulo n, noté a ≡ b [n], si n divise a − b, c’est-à-dire si a et b ont le même reste dans la division par n.
- Si a ≡ b [n] et a′ ≡ b′ [n], alors a + a′ ≡ b + b′ [n] et aa′ ≡ bb′ [n].
- Si a ≡ b [n], alors aᵏ ≡ bᵏ [n] pour tout entier naturel k.
- a ≡ r [n] avec 0 ≤ r < n signifie que r est le reste de a dans la division par n.
4. Méthode : reste d’une grande puissance
Reste de 22026 dans la division par 9
- On cherche une puissance de 2 congrue à 1 : 2³ = 8 ≡ −1 [9], donc 2⁶ ≡ 1 [9].
- 2026 = 6 × 337 + 4, donc 22026 = (2⁶)337 × 2⁴ ≡ 1 × 16 [9].
- 16 ≡ 7 [9].
Le reste est 7.
| n ≡ … [4] | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| n² ≡ … [4] | 0 | 1 | 0 | 1 |
À retenir
- b | a ⟺ a = kb ; un diviseur commun divise toute combinaison au + bv.
- Division euclidienne : a = bq + r, 0 ≤ r < b, couple unique.
- a ≡ b [n] ⟺ n | a − b ; les congruences se conservent par somme, produit et puissance.
- Pour une grande puissance, chercher une puissance congrue à 1 (ou −1).
Et maintenant, à toi !
Vérifie que tu as compris avec les exercices, puis révise avec la fiche.