Ex.1
Divisibilité — définition et propriétés
★
a|b si ∃k∈ℤ, b=ka
→ 1) 42=6×7 et 18=6×3 → 6|42, 6|18 ; 60=42+18=6×(7+3)=6×10 → 6|60
→ 2) 7|a → a=7k ; 3a²+14a=3×49k²+98k=7(21k²+14k) → 7|(3a²+14a)
= 6|60 (démonstration) · 7|(3a²+14a) (démonstration)
Ex.2
Division euclidienne
★
a=bq+r, 0≤r
→ 1) 347=12×28+11
→ 2) −50=7×(−8)+6
→ 3) 1001=37×27+2
= q=28,r=11 · q=−8,r=6 · q=27,r=2
Ex.3
PGCD — algorithme d'Euclide
★
Algorithme d'Euclide
→ 1) 252=198×1+54 ; 198=54×3+36 ; 54=36×1+18 ; 36=18×2+0 → PGCD(252,198)=18
→ 2) 1071=462×2+147 ; 462=147×3+21 ; 147=21×7+0 → PGCD(1071,462)=21
= PGCD=18 · PGCD=21
★★
Niveau 2 — Intermédiaire
Ex. 4 à 6
Ex.4
Congruences — définition
★★
a≡b[n] si n|(a−b)
→ 1) 37−7=30=10×3 → 37≡7 [10] vérifié
→ 2) 2025=7×289+2 → 2025≡2 [7]
→ 3) 3≡−1[4] → 3100≡(−1)100=1 [4]
= vérifié · 2025≡2[7] · 3100≡1[4]
Ex.5
Propriétés des congruences
★★
a≡b et c≡d[n] → ac≡bd[n]
→ 1) 11≡1 [10] → 112n≡12n=1 [10] pour tout n
→ 2) 7≡2[5], 2⁴≡1[5], 100=4×25 → 7100≡2100=(2⁴)²⁵≡1²⁵=1 [5]
= démonstration · 7100≡1[5]
Ex.6
Critères de divisibilité
★★
10≡1[9] et 10≡−1[11]
→ 1) 10≡1[9] → 10ᵏ≡1[9] → un nombre ≡ somme de ses chiffres [9], divisible par 9 ssi cette somme l'est
→ 2) 10≡−1[11] → 10ᵏ≡(−1)ᵏ[11] → un nombre ≡ somme alternée de ses chiffres [11]
= démonstration (base 9) · démonstration (base 11)
mathsotop.frCorrigé — Ch6 — Divisibilité et congruences
5 / 6
M
MathsOtop®
LYCÉE — MATHS EXPERTES
✦ CORRIGÉ
Ch6 — Divisibilité et congruences
✦ Corrigé — Ch6 — Divisibilité et congruences
ACCÈS PREMIUM — Ex. 7 à 12
★★
Niveau 2 — Intermédiaire (suite)
Ex. 7 à 9
Ex.7
Équations de congruence
★★
→ ① 3x≡1[7] : inverse de 3 mod 7 est 5 (3×5=15≡1[7]), donc x≡5[7].
→ ② 5x≡3[11] : inverse de 5 mod 11 est 9 (5×9=45≡1[11]), donc x≡3×9=27≡5[11].
→ ③ 4x≡2[6] : pgcd(4,6)=2 divise 2, solutions existent ; en divisant par 2 : 2x≡1[3], inverse de 2 mod3 est 2, donc x≡2[3], soit x≡2[6] ou x≡5[6].
= ① x≡5[7] ② x≡5[11] ③ x≡2[3] (c-à-d x≡2 ou 5 [6]).
Ex.8
Reste de la division
★★
→ 2¹≡2[3], 2²≡4≡1[3], 2³≡2×1≡2[3], 2⁴≡1[3].
→ La suite des restes est périodique de période 2 : 2impair≡2[3], 2pair≡1[3].
→ 1000 est pair, donc 21000 ≡ 1 [3].
= Le reste de la division de 21000 par 3 est 1.
Ex.9
Démonstration par congruences
★★★
→ n³−n = n(n²−1) = n(n−1)(n+1) : produit de trois entiers consécutifs.
→ Divisibilité par 2 : parmi (n−1) et n, deux entiers consécutifs, l'un des deux est pair, donc le produit est pair.
→ Divisibilité par 3 : parmi trois entiers consécutifs n−1, n, n+1, l'un est nécessairement un multiple de 3.
→ 2 et 3 étant premiers entre eux, le produit n(n−1)(n+1) est divisible par 2×3=6.
= n³−n = n(n−1)(n+1) est toujours divisible par 6, pour tout entier n.
★★★
Niveau 3 — Difficile
Ex. 10 à 12
Ex.10
Théorème chinois des restes
★★★
→ x≡2[3] ⟺ x=3k+2 pour un entier k.
→ On reporte dans x≡3[5] : 3k+2≡3[5] ⟺ 3k≡1[5]. Inverse de 3 mod5 est 2 (3×2=6≡1[5]), donc k≡2[5].
→ k=5m+2, donc x=3(5m+2)+2 = 15m+8.
= x ≡ 8 [15] (théorème chinois : solution unique modulo 3×5=15).
Ex.11
Représentation décimale
★★★
→ N = a_n·10n + a_(n−1)·10n−1 + ... + a_1·10 + a_0 = Σ a_i·10i.
→ Comme 10≡1[9], on a 10i≡1i=1[9] pour tout i≥0.
→ Donc N ≡ Σ a_i·1 = Σ a_i [9] : N est congru modulo 9 à la somme de ses chiffres.
→ En particulier N≡0[9] ⟺ Σa_i≡0[9] : c'est la règle de divisibilité par 9 (et par 3, de façon analogue).
= N ≡ (somme de ses chiffres) [9] ; d'où N≡0[9] ⟺ la somme des chiffres est divisible par 9.
Ex.12
★ Défi BAC Expertes
★★★
→ 7¹≡7[8], 7²≡49≡1[8], 7³≡7×1≡7[8] : période 2, avec 7impair≡7[8] et 7pair≡1[8].
→ 2n+1 est toujours impair (quel que soit n), donc 72n+1 ≡ 7 [8].
→ 72n+1+1 ≡ 7+1 = 8 ≡ 0 [8].
= Pour tout entier n, 72n+1+1 est divisible par 8.
mathsotop.frCorrigé — Ch6 — Divisibilité et congruences
6 / 6