I. Rappels : divisibilité et division euclidienne
Divisibilité
Pour a ∈ ℤ, b ∈ ℤ*, on dit que b divise a (b | a) s'il existe k ∈ ℤ tel que a = bk.
Division euclidienne
Pour tout a ∈ ℤ et b ∈ ℕ*, il existe un unique (q, r) ∈ ℤ × ℕ tel que a = bq + r avec 0 ≤ r < b.
II. Congruences modulo n (approfondissement)
Définition
Soit n ∈ ℕ*. a ≡ b [n] ⇔ n | (a − b) ⇔ a et b ont le même reste dans la division par n.
Opérations compatibles
Si a ≡ a' [n] et b ≡ b' [n], alors :
- a + b ≡ a' + b' [n]
- a · b ≡ a' · b' [n]
- ak ≡ a'k [n] pour tout k ∈ ℕ
- P(a) ≡ P(a') [n] pour tout polynôme P à coefficients entiers
Simplification dans une congruence
ac ≡ bc [n] n'implique pas a ≡ b [n] en général. Mais :
Si pgcd(c, n) = 1 : ac ≡ bc [n] ⇒ a ≡ b [n]
III. PGCD, PPCM — rappels et approfondissements
Propriétés du PGCD
- pgcd(a, b) = pgcd(b, a − bq) pour tout q ∈ ℤ (base de l'algorithme d'Euclide).
- Tout diviseur commun de a et b divise pgcd(a, b).
- pgcd(ka, kb) = |k| · pgcd(a, b).
Caractérisation du PGCD
d = pgcd(a, b) ⇔ d ≥ 0, d | a, d | b, et tout diviseur commun de a et b divise d.
Relation PGCD × PPCM
pgcd(a, b) × ppcm(a, b) = |a × b|
IV. Théorème de Bézout
Identité de Bézout
Pour tous a, b ∈ ℤ non tous deux nuls, il existe u, v ∈ ℤ tels que :
au + bv = pgcd(a, b)
Forme caractéristique (nombres premiers entre eux)
pgcd(a, b) = 1 ⇔ ∃ u, v ∈ ℤ, au + bv = 1
Algorithme d'Euclide étendu
Les coefficients u, v s'obtiennent par remontée des divisions successives de l'algorithme d'Euclide.
V. Théorème de Gauss
Énoncé
Si a | bc et pgcd(a, b) = 1, alors a | c.
Corollaires utiles
- Si a | n, b | n et pgcd(a, b) = 1, alors ab | n.
- Si pgcd(a, n) = 1 et pgcd(b, n) = 1, alors pgcd(ab, n) = 1.
- Si pgcd(a, b) = 1, alors pgcd(ak, bm) = 1 pour tous k, m ∈ ℕ.
VI. Nombres premiers — approfondissement
Lemme d'Euclide
Si p est premier et p | ab, alors p | a ou p | b.
Théorème fondamental de l'arithmétique
Tout n ≥ 2 se décompose, de manière unique (à l'ordre près), en produit de facteurs premiers :
n = p1α1 · p2α2 · ... · pkαk
Nombre de diviseurs
Si n = p1α1·...·pkαk, le nombre de diviseurs positifs de n est :
τ(n) = (α1 + 1)(α2 + 1)...(αk + 1)
VII. Petit théorème de Fermat
Énoncé
Soit p un nombre premier et a un entier.
- Si p ne divise pas a : ap−1 ≡ 1 [p]
- Pour tout a : ap ≡ a [p]
Applications
- Calcul rapide de restes de puissances élevées modulo un nombre premier.
- Critères d'irréductibilité, tests de primalité (test de Fermat).
- Résolution d'équations du type an ≡ b [p].
Exemple
Calculer 32024 mod 7. Comme 7 est premier et 7 ∤ 3 : 36 ≡ 1 [7]. Or 2024 = 6·337 + 2. Donc 32024 = (36)337·3² ≡ 1·9 ≡ 2 [7].
VIII. Équations diophantiennes ax + by = c
Critère d'existence de solutions
ax + by = c admet des solutions (x, y) ∈ ℤ² si et seulement si pgcd(a, b) | c.
Méthode complète
- Calculer d = pgcd(a, b). Si d ∤ c : pas de solution.
- Diviser par d : a'x + b'y = c' avec pgcd(a', b') = 1.
- Chercher une solution particulière (x0, y0) par Bézout.
- Solution générale : x = x0 + b'·k, y = y0 − a'·k pour k ∈ ℤ.
IX. Systèmes de congruences — théorème chinois
Théorème chinois des restes
Soient m, n ∈ ℕ* avec pgcd(m, n) = 1. Pour tous a, b ∈ ℤ, le système :
{ x ≡ a [m] et x ≡ b [n] }
admet une unique solution modulo mn.
Résolution pratique
- Écrire x = a + mk pour un k ∈ ℤ.
- Reporter dans la deuxième : a + mk ≡ b [n] ⇒ mk ≡ b − a [n].
- Comme pgcd(m, n) = 1, m est inversible modulo n : k ≡ m−1(b − a) [n].
- Remonter : x = a + mk = a + m·[m−1(b − a) mod n] mod mn.
X. Critères de divisibilité (applications)
- Par 3 ou 9 : un entier est divisible par 3 (resp. 9) ssi la somme de ses chiffres l'est. (Car 10 ≡ 1 [3] et [9].)
- Par 11 : somme alternée des chiffres divisible par 11. (Car 10 ≡ −1 [11].)
- Par 7 : le nombre formé en soustrayant 2× le dernier chiffre au nombre privé de son dernier chiffre est divisible par 7.
- Par 4 : les 2 derniers chiffres forment un nombre divisible par 4.
- Par 8 : les 3 derniers chiffres forment un multiple de 8.