Nous présentons ici le
Lifting The Exponent Lemma, souvent appelé plus simplement
LTE. Il s'agit d'un résultat permettant, sous certaines conditions, de savoir le nombre de fois qu'un facteur premier $p$ apparaît dans une expression du type $a^n \pm b^n$. On introduit pour cela une notation :
Par exemple, $v_3(18) = 2$, $v_5(35) = 1$ et $v_7(68) = 0$. Le problème qui nous intéresse est alors simplement celui de trouver une formule pour $v_p(a^n+b^n)$ et $v_p(a^n-b^n)$.
On peut commencer par quelques remarques simples :
- Si exactement un des deux nombres $a$ et $b$ est divisible par $p$, alors $a^n+b^n$ et $a^n-b^n$ ne sont jamais divisibles par $p$. Autrement dit, $v_p(a^n \pm b^n) = 0$. Il s'agit là d'une évidence.
- Si les deux nombres $a$ et $b$ sont divisibles par $p$, alors on peut noter $a = p \cdot a'$ et $b = p \cdot b'$ et on obtient $a^n \pm b^n = p^n \cdot (a'^n \pm b'^n)$. On a donc $v_p(a^n \pm b^n) = n + v_p(a'^n \pm b'^n)$ et on s'est ramené au même problème mais avec des nombres ($a'$ et $b'$) plus petits.
De ces deux remarques, on déduit qu'on peut dorénavant supposer que ni $a$ ni $b$ n'est divisible par $p$.
Première forme
Intéressons-nous à présent à l'expression $a^n - b^n$. Comme on l'a déjà vu précédemment, on a
$$a^n- b^n = (a-b) \cdot (a^{n-1} + a^{n-2}b + \ldots + ab^{n-2} + b^{n-1}).$$ Cela signifie déjà que $v_p(a^n-b^n) \geq v_p(a-b)$. La première forme du LTE nous donne en fait une formule plus précise que cela,
pourvu que $a-b$
soit divisible par $p$ (c'est-à-dire que $v_p(a-b) \geq 1$) et que $p \neq 2$. Elle s'énonce comme suit :
LTE pour $a^n-b^n$
Soit $a$ et $b$ des entiers (non nécessairement positifs), $n$ un entier strictement positif et $p$ un nombre premier impair tel que $p$ divise $a-b$ mais $p$ ne divise ni $a$ ni $b$. Alors
$$v_p(a^n-b^n) = v_p(a-b) + v_p(n).$$
La preuve de ce résultat consiste à montrer que le nombre de facteurs $p$ apparaissant dans l'expression $a^{n-1} + a^{n-2}b + \ldots + ab^{n-2} + b^{n-1}$ est, sous les conditions de l'énoncé, égal à $v_p(n)$. Nous ne donnons pas la preuve ici, bien qu'elle ne soit pas très compliquée.
Remarque importante : Il est primordial de retenir les hypothèses de ces résultats ! Il arrive souvent d'oublier que $p$ doit diviser $a \pm b$, mais dans ce cas le résultat est complètement faux ! Cette remarque est également valable pour les autres formes du lemme, ci-dessous.
Deuxième forme
En ce qui concerne l'expression $a^n+b^n$, il a déjà été vu précédemment que l'on avait la factorisation suivante
pourvu que $n$
soit impair :
$$a^n + b^n = (a+b) \cdot (a^{n-1} - a^{n-2}b + \ldots - ab^{n-2} + b^{n-1})$$ Il faut donc logiquement s'attendre à ce que l'hypothèse comme quoi $n$ est impair apparaisse dans la deuxième forme du LTE. Les autres hypothèses restent les mêmes : $p$ doit être différent de $2$ et doit diviser $a+b$.
LTE pour $a^n+b^n$
Soit $a$ et $b$ des entiers (non nécessairement positifs), $n$ un entier strictement positif impair et $p$ un nombre premier impair tel que $p$ divise $a+b$ mais $p$ ne divise ni $a$ ni $b$. Alors
$$v_p(a^n+b^n) = v_p(a+b) + v_p(n).$$
Quid de $p = 2$ ?
Dans les deux formes du LTE, le nombre $p$ doit être impair et on ne peut donc pas le prendre égal à $2$. Il existe toutefois un résultat similaire à la première forme du LTE pour $p = 2$, mais $a-b$ doit être divisible par $4$ (et pas seulement par $2$).
LTE pour $p = 2$
Soit $a$ et $b$ des entiers impairs tels que $4$ divise $a-b$ et soit $n$ un entier strictement positif. Alors
$$v_2(a^n - b^n) = v_2(a-b) + v_2(n).$$
Preuves et problèmes
Ces résultats proviennent de
cette page (voir le PDF qui y est attaché). On peut y trouver les preuves des différents résultats, ainsi que de nombreux problèmes d'olympiades (certains avec solutions) pouvant se résoudre plus facilement grâce au LTE. Nous détaillons les preuves de deux tels problèmes dans la suite de ce chapitre, mais nous conseillons le lecteur intéressé d'en essayer encore d'autres.