Valuations p-adiques et lemme LTE¶
Domaine : Théorie des nombres · Niveau : intermédiaire · Prérequis : Congruences
L'idée¶
Pour un nombre premier \(p\) et un entier \(n \neq 0\), la valuation \(p\)-adique \(v_p(n)\) est l'exposant de \(p\) dans la décomposition de \(n\) en facteurs premiers : le plus grand \(k\) tel que \(p^k \mid n\). Par exemple \(v_2(40) = 3\) et \(v_5(40) = 1\).
Raisonner avec les valuations, c'est regarder un nombre premier à la fois. Beaucoup de questions de divisibilité deviennent alors des comparaisons d'entiers.
Propriétés¶
| Propriété | Énoncé |
|---|---|
| Produit | \(v_p(ab) = v_p(a) + v_p(b)\), et donc \(v_p(a^k) = k\,v_p(a)\) |
| Somme | \(v_p(a + b) \geq \min\big(v_p(a), v_p(b)\big)\), avec égalité si \(v_p(a) \neq v_p(b)\) |
| Divisibilité | \(a \mid b\) si et seulement si \(v_p(a) \leq v_p(b)\) pour tout premier \(p\) |
| Puissances | \(n > 0\) est une puissance \(k\)-ième si et seulement si \(k\) divise tous les \(v_p(n)\) |
| Factorielle (Legendre) | \(v_p(n!) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \cdots\) |
La règle de la somme est la plus utile : si deux termes n'ont pas la même valuation, la somme a la plus petite des deux. C'est ce qui permet de montrer qu'une somme est non nulle, ou qu'elle n'est pas divisible par une grande puissance de \(p\).
Le lemme LTE¶
Le lemme LTE (Lifting The Exponent, « faire monter l'exposant ») donne la valuation de \(a^n - b^n\).
Lemme LTE
Soit \(p\) un nombre premier impair, et \(a, b\) des entiers non divisibles par \(p\) avec \(p \mid a - b\). Alors, pour tout \(n \geq 1\),
Si de plus \(n\) est impair et \(p \mid a + b\), alors \(v_p(a^n + b^n) = v_p(a + b) + v_p(n)\).
Pour \(p = 2\), avec \(a, b\) impairs : si \(n\) est impair, \(v_2(a^n - b^n) = v_2(a - b)\) ; si \(n\) est pair,
L'idée de la preuve. On écrit \(a^n - b^n = (a - b)(a^{n-1} + a^{n-2}b + \cdots + b^{n-1})\). Modulo \(p\), chaque terme de la seconde parenthèse est \(\equiv a^{n-1}\), donc elle est \(\equiv n\,a^{n-1}\). Si \(p \nmid n\), elle n'apporte aucun facteur \(p\). Pour \(n = p\), on montre qu'elle apporte exactement un facteur \(p\) ; on conclut en décomposant \(n\).
Exemple résolu¶
Problème
Montrer que pour tout \(k \geq 0\), \(3^{k+1}\) divise \(2^{3^k} + 1\), mais que \(3^{k+2}\) ne le divise pas.
Étape 1 : reconnaître la forme. On veut la valuation \(3\)-adique exacte de \(a^n + b^n\) avec \(a = 2\), \(b = 1\) et \(n = 3^k\).
Étape 2 : vérifier les hypothèses de LTE. \(p = 3\) est impair, \(3 \nmid 2\) et \(3 \nmid 1\), \(3\) divise \(a + b = 3\), et \(n = 3^k\) est impair.
Étape 3 : appliquer.
Donc \(3^{k+1}\) divise \(2^{3^k} + 1\), et \(3^{k+2}\) ne le divise pas.
Sans LTE, on peut le prouver par récurrence avec \(x^3 + 1 = (x + 1)(x^2 - x + 1)\) : quand \(x \equiv -1 \pmod 3\), le second facteur est divisible par \(3\) mais pas par \(9\). C'est exactement la preuve de LTE dans ce cas particulier.
Comment le reconnaître¶
- L'énoncé contient des puissances de premiers : « la plus grande puissance de \(2\) qui divise… », « \(p^k \mid \ldots\) ».
- Des expressions \(a^n - b^n\) ou \(a^n + b^n\) avec un exposant variable.
- Des factorielles ou des coefficients binomiaux dont on veut la divisibilité.
- On doit montrer qu'un nombre est (ou n'est pas) une puissance parfaite, ou une puissance de \(2\).
- Une égalité entre produits : on compare les exposants de chaque premier des deux côtés.
Techniques classiques¶
| Situation | Technique |
|---|---|
| Égalité ou divisibilité entre produits | Comparer \(v_p\) des deux membres, pour chaque premier \(p\) |
| Somme de termes | Si un terme a une valuation strictement plus petite que les autres, il impose la valuation de la somme |
| \(a^n \pm b^n\) | Lemme LTE (attention aux hypothèses, et au cas \(p = 2\)) |
| \(n!\), \(\binom{n}{k}\) | Formule de Legendre |
| Puissance parfaite | Toutes les valuations sont multiples de l'exposant |
| Montrer qu'un nombre n'est pas une puissance de \(2\) | Trouver un facteur premier impair, ou étudier \(v_2\) |
| Suite de valuations | Une suite d'entiers positifs décroissante est stationnaire |
Exercices d'échauffement¶
- Calculer \(v_5(100!)\) et \(v_2(100!)\).
- Montrer que \(\sqrt{2}\) est irrationnel en comparant \(v_2\) des deux membres de \(p^2 = 2q^2\).
- Calculer \(v_2(3^{2026} - 1)\).
- Calculer \(v_7(8^{49} - 1)\).
- Soient \(a, b > 0\) tels que \(a^2\) divise \(b^2\). Montrer que \(a\) divise \(b\).
Valuations dans la shortlist¶
- 2017 N4 : LTE donne \(v_p(10^{\ell\alpha} - 1) = v_p(10^\alpha - 1) + v_p(\ell)\).
- 2022 N4 : \(v_2(p^{p-1} - 1)\) et \(v_q(p^p - p)\) sont trop petites, par LTE.
- 2023 N3 : la formule de Legendre donne les nombres de zéros de \(n!\) en base \(10\) et en base \(9\).
- 2018 A1 : un rationnel positif qui est une puissance \(2^n\)-ième pour tout \(n\) vaut \(1\), car ses valuations seraient divisibles par toutes les puissances de \(2\).
- 2019 N1 : \(v_2\) du produit vaut \(\frac{n(n-1)}{2}\), et la formule de Legendre donne \(v_2(m!) < m\).
Pour approfondir : Objectif Olympiades de Mathématiques, tome 5 (M. Aassila), p. 303 à 309 (lemme LTE : premières observations, énoncés pour \(p\) impair et pour \(p = 2\), exemples), p. 187 à 194 (formule de Legendre) ; tome 1, p. 504 à 506 (formule de Legendre et applications).
Problèmes de la shortlist¶
45 problèmes · difficulté moyenne : ★★★★★ (2,9) · dont 12 choisis pour l'OIM
Répartition par difficulté : 1 ★ : 6 · 2 ★ : 11 · 3 ★ : 16 · 4 ★ : 6 · 5 ★ : 6
| Problème | Difficulté | Concepts |
|---|---|---|
| 2025 C2 | ★☆☆☆☆ | Invariants et monovariants |
| 2023 N1 · OIM P1 | ★☆☆☆☆ | Divisibilité, PGCD et algorithme d'Euclide · Récurrence et constructions récursives |
| 2023 N2 | ★☆☆☆☆ | Équations diophantiennes : factorisation et encadrement · Congruences, théorèmes de Fermat et d'Euler |
| 2019 N1 · OIM P4 | ★☆☆☆☆ | - |
| 2018 A1 | ★☆☆☆☆ | Équations fonctionnelles : substitutions, injectivité, surjectivité |
| 2015 N1 | ★☆☆☆☆ | Congruences, théorèmes de Fermat et d'Euler · Descente infinie et Vieta jumping |
| 2025 N3 · OIM P4 | ★★☆☆☆ | Congruences, théorèmes de Fermat et d'Euler · Invariants et monovariants · Descente infinie et Vieta jumping |
| 2024 N3 | ★★☆☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2023 N3 | ★★☆☆☆ | Partie entière et majorations · Ordre d'un élément et racines primitives |
| 2022 N4 · OIM P5 | ★★☆☆☆ | Équations diophantiennes : factorisation et encadrement · Diviseurs premiers : Zsigmondy, premiers divisant un polynôme · Congruences, théorèmes de Fermat et d'Euler |
| 2020 N3 · OIM P5 | ★★☆☆☆ | Divisibilité, PGCD et algorithme d'Euclide · Principe extrémal |
| 2017 N4 | ★★☆☆☆ | Ordre d'un élément et racines primitives |
| 2015 N3 | ★★☆☆☆ | Divisibilité, PGCD et algorithme d'Euclide · Congruences, théorèmes de Fermat et d'Euler |
| 2012 N2 | ★★☆☆☆ | Équations diophantiennes : factorisation et encadrement · Congruences, théorèmes de Fermat et d'Euler |
| 2011 N2 | ★★☆☆☆ | Diviseurs premiers : Zsigmondy, premiers divisant un polynôme · Principe des tiroirs |
| 2007 N2 | ★★☆☆☆ | Résidus quadratiques |
| 2006 N1 · OIM P4 | ★★☆☆☆ | Équations diophantiennes : factorisation et encadrement |
| 2025 N5 | ★★★☆☆ | Invariants et monovariants · Divisibilité, PGCD et algorithme d'Euclide |
| 2024 N4 · OIM P2 | ★★★☆☆ | Divisibilité, PGCD et algorithme d'Euclide · Congruences, théorèmes de Fermat et d'Euler |
| 2024 N5 | ★★★☆☆ | Partie entière et majorations · Congruences, théorèmes de Fermat et d'Euler · Divisibilité, PGCD et algorithme d'Euclide |
| 2021 N5 | ★★★☆☆ | AM-GM et moyennes · Congruences, théorèmes de Fermat et d'Euler |
| 2020 N5 | ★★★☆☆ | Principe extrémal · Congruences, théorèmes de Fermat et d'Euler |
| 2019 N5 | ★★★☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2018 N4 · OIM P5 | ★★★☆☆ | Divisibilité, PGCD et algorithme d'Euclide |
| 2015 N5 · OIM P2 | ★★★☆☆ | Équations diophantiennes : factorisation et encadrement · Congruences, théorèmes de Fermat et d'Euler |
| 2014 N4 | ★★★☆☆ | Congruences, théorèmes de Fermat et d'Euler · Partie entière et majorations |
| 2014 N5 | ★★★☆☆ | Congruences, théorèmes de Fermat et d'Euler · Équations diophantiennes : factorisation et encadrement |
| 2013 N4 | ★★★☆☆ | Équations diophantiennes : factorisation et encadrement · Congruences, théorèmes de Fermat et d'Euler |
| 2011 N4 | ★★★☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2010 N5 · OIM P3 | ★★★☆☆ | Diviseurs premiers : Zsigmondy, premiers divisant un polynôme · Équations fonctionnelles : substitutions, injectivité, surjectivité |
| 2009 N3 | ★★★☆☆ | Divisibilité, PGCD et algorithme d'Euclide |
| 2008 N4 | ★★★☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2007 N4 | ★★★☆☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2025 N7 · OIM P3 | ★★★★☆ | Congruences, théorèmes de Fermat et d'Euler · Ordre d'un élément et racines primitives |
| 2016 N7 · OIM P3 | ★★★★☆ | - |
| 2014 N7 | ★★★★☆ | Diviseurs premiers : Zsigmondy, premiers divisant un polynôme · Congruences, théorèmes de Fermat et d'Euler · Suites et récurrences |
| 2011 N7 | ★★★★☆ | Congruences, théorèmes de Fermat et d'Euler |
| 2010 N6 | ★★★★☆ | Suites et récurrences · Graphes : degrés, chemins, arbres |
| 2007 N7 | ★★★★☆ | Principe des tiroirs |
| 2024 N7 | ★★★★★ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Divisibilité, PGCD et algorithme d'Euclide · Graphes : degrés, chemins, arbres |
| 2020 C8 | ★★★★★ | Jeux et stratégies gagnantes · Invariants et monovariants |
| 2019 A7 | ★★★★★ | Équations fonctionnelles : substitutions, injectivité, surjectivité · Principe extrémal |
| 2018 N7 | ★★★★★ | Divisibilité, PGCD et algorithme d'Euclide |
| 2014 N8 | ★★★★★ | Partie entière et majorations · Fonctions arithmétiques : nombre de diviseurs, indicatrice d'Euler, somme des diviseurs |
| 2009 N7 | ★★★★★ | Suites et récurrences · Résidus quadratiques |