Shortlist 2014, N5

Domaine : Théorie des nombres · Difficulté : ★★★☆☆ · Proposé par : Belgium

Concepts : Valuations p-adiques et lemme LTE · Congruences, théorèmes de Fermat et d'Euler · Équations diophantiennes : factorisation et encadrement

Solution officielle : Shortlist officielle 2014 (avec solutions), p. 75 (page 76 du PDF)

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé

Find all triples \((p, x, y)\) consisting of a prime number \(p\) and two positive integers \(x\) and \(y\) such that \(x^{p-1} + y\) and \(x + y^{p-1}\) are both powers of \(p\).

Indices : les idées clés

• Réduire modulo \(p^a\) : avec \(x \leq y\), \(x^{p-1} + y = p^a\) et \(x + y^{p-1} = p^b\), on a \(a \leq b\) et \(p^a \mid x^{p(p-2)} + 1\) ; par Fermat, \(p \mid x + 1\).
• LTE : si \(p^r\) est la plus grande puissance de \(p\) divisant \(x + 1\), alors \(v_p\big(x^{p(p-2)} + 1\big) = r + 1\), donc \(a \leq r + 1\).
• Encadrement : \(p^r \leq x + 1 \leq p^a\) force \(a = r + 1\), puis \(x = p - 1\), \(a = 2\), et \(p \geq 5\) est impossible par taille ; il reste \(p = 3\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2014 (deux solutions et trois remarques).

Solution 1

Réponse : \((p, x, y) \in \{(3, 2, 5), (3, 5, 2)\} \cup \{(2, n, 2^k - n) \mid 0 < n < 2^k\}\).

Pour \(p = 2\), tous les couples d'entiers strictement positifs \(x\), \(y\) dont la somme est une puissance de \(2\) conviennent évidemment. On suppose donc désormais \(p > 2\), et l'on note \(a\) et \(b\) des entiers strictement positifs tels que \(x^{p-1} + y = p^a\) et \(x + y^{p-1} = p^b\). Supposons de plus, sans perte de généralité, \(x \leq y\), de sorte que \(p^a = x^{p-1} + y \leq x + y^{p-1} = p^b\), donc \(a \leq b\) (et \(p^a \mid p^b\)).

On a

\[p^b = y^{p-1} + x = (p^a - x^{p-1})^{p-1} + x.\]

En réduisant modulo \(p^a\), et comme \(p - 1\) est pair, on obtient

\[0 \equiv x^{(p-1)^2} + x \pmod{p^a}.\]

Si \(p \mid x\), alors \(p^a \mid x\), car \(x^{(p-1)^2 - 1} + 1\) n'est pas divisible par \(p\) dans ce cas. C'est impossible, car \(x \leq x^{p-1} < p^a\). Donc \(p \nmid x\), ce qui donne

\[p^a \mid x^{(p-1)^2 - 1} + 1 = x^{p(p-2)} + 1.\]

Par le petit théorème de Fermat, \(x^{(p-1)^2} \equiv 1 \pmod p\), donc \(p\) divise \(x + 1\). Soit \(p^r\) la plus grande puissance de \(p\) qui divise \(x + 1\). Par la formule du binôme,

\[x^{p(p-2)} = \sum_{k=0}^{p(p-2)} \binom{p(p-2)}{k} (-1)^{p(p-2) - k} (x + 1)^k.\]

Hormis les termes \(k = 0\), \(k = 1\) et \(k = 2\), tous les termes de la somme sont clairement divisibles par \(p^{3r}\), donc par \(p^{r+2}\). Les termes restants sont

\[-\frac{p(p-2)(p^2 - 2p - 1)}{2} (x + 1)^2,\]

divisible par \(p^{2r+1}\) donc aussi par \(p^{r+2}\) ;

\[p(p-2)(x + 1),\]

divisible par \(p^{r+1}\) mais pas par \(p^{r+2}\) par le choix de \(r\) ; et le terme final \(-1\), correspondant à \(k = 0\). Il s'ensuit que la plus grande puissance de \(p\) qui divise \(x^{p(p-2)} + 1\) est \(p^{r+1}\).

D'autre part, on sait que \(p^a\) divise \(x^{p(p-2)} + 1\), donc \(a \leq r + 1\). De plus,

\[p^r \leq x + 1 \leq x^{p-1} + y = p^a.\]

On a donc \(a = r\) ou \(a = r + 1\).

Si \(a = r\), il faut \(x = y = 1\) dans l'inégalité ci-dessus, ce qui est impossible pour \(p > 2\). Donc \(a = r + 1\). Comme \(p^r \leq x + 1\), on obtient

\[x = \frac{x^2 + x}{x + 1} \leq \frac{x^{p-1} + y}{x + 1} = \frac{p^a}{x + 1} \leq \frac{p^a}{p^r} = p,\]

donc \(x = p - 1\), puisque \(p\) divise \(x + 1\).

Il s'ensuit que \(r = 1\) et \(a = 2\). Si \(p \geq 5\), on obtient

\[p^a = x^{p-1} + y > (p - 1)^4 = (p^2 - 2p + 1)^2 > (3p)^2 > p^2 = p^a,\]

une contradiction. Il ne reste que le cas \(p = 3\), et \(x = 2\), \(y = p^a - x^{p-1} = 5\) conviennent bien. \(\blacksquare\)

Remarque 1. On utilise implicitement dans cette solution un cas particulier du lemme suivant, appelé lemme de relèvement des exposants (LTE).

Lemme. Soit \(n\) un entier strictement positif, \(p\) un nombre premier impair, et \(v_p(m)\) l'exposant de la plus grande puissance de \(p\) qui divise \(m\). Si \(x\) et \(y\) sont des entiers non divisibles par \(p\) tels que \(p \mid x - y\), alors

\[v_p(x^n - y^n) = v_p(x - y) + v_p(n).\]

De même, si \(x\) et \(y\) sont des entiers non divisibles par \(p\) tels que \(p \mid x + y\), et si \(n\) est impair (précision ajoutée : le livret omet cette hypothèse), alors

\[v_p(x^n + y^n) = v_p(x + y) + v_p(n).\]

Remarque 2. Il existe d'autres façons de résoudre le problème avec ce lemme. En voici une autre, esquissée. Les cas \(x = y\) et \(p \mid x\) s'éliminent facilement ; on suppose donc \(p > 2\), \(x < y\) et \(p \nmid x\). Dans ce cas, on a aussi \(p^a < p^b\) et \(p \mid x + 1\). Alors

\[y^p - x^p \equiv y(y^{p-1} + x) - x(x^{p-1} + y) \equiv 0 \pmod{p^a},\]

donc, par le lemme, \(p^{a-1} \mid y - x\), et \(y = x + t p^{a-1}\) pour un entier \(t > 0\). On obtient

\[x(x^{p-2} + 1) = x^{p-1} + x = (x^{p-1} + y) - (y - x) = p^{a-1}(p - t).\]

Les facteurs du membre de gauche sont premiers entre eux. Si \(p \mid x\), alors \(x^{p-2} + 1 \mid p - t\), ce qui est impossible puisque \(x < x^{p-2} + 1\). Donc \(p \nmid x\), et \(x \mid p - t\). Comme \(p \mid x + 1\), le seul cas restant est \(x = p - 1\), \(t = 1\) et \(y = p^{a-1} + p - 1\). On termine alors comme ci-dessus.

Solution 2

Là encore, on peut se concentrer sur le cas \(p > 2\). Si \(p \mid x\), alors \(p \mid y\) aussi. Dans ce cas, soient \(p^k\) et \(p^\ell\) les plus grandes puissances de \(p\) qui divisent \(x\) et \(y\), et supposons sans perte de généralité \(k \leq \ell\). Alors \(p^k\) divise \(x + y^{p-1}\) mais pas \(p^{k+1}\), alors que \(p^k < x + y^{p-1}\), ce qui est contradictoire. Donc \(x\) et \(y\) ne sont pas divisibles par \(p\). Le petit théorème de Fermat donne \(0 \equiv x^{p-1} + y \equiv 1 + y \pmod p\), donc \(y \equiv -1 \pmod p\), et de même \(x \equiv -1 \pmod p\).

En particulier, \(x, y \geq p - 1\), donc \(x^{p-1} + y \geq 2(p - 1) > p\) : \(x^{p-1} + y\) et \(y^{p-1} + x\) sont tous deux au moins égaux à \(p^2\). On a donc

\[x^{p-1} \equiv -y \pmod{p^2} \quad \text{et} \quad y^{p-1} \equiv -x \pmod{p^2}.\]

Avec le théorème d'Euler-Fermat, ces deux congruences donnent

\[1 \equiv x^{p(p-1)} \equiv (-y)^p \equiv -y^p \equiv xy \pmod{p^2}.\]

Comme \(x \equiv y \equiv -1 \pmod p\), \(x - y\) est divisible par \(p\), donc \((x - y)^2\) est divisible par \(p^2\). Il s'ensuit que

\[(x + y)^2 = (x - y)^2 + 4xy \equiv 4 \pmod{p^2},\]

donc \(p^2\) divise \((x + y - 2)(x + y + 2)\). On sait déjà que \(x + y \equiv -2 \pmod p\), donc \(x + y - 2 \equiv -4 \not\equiv 0 \pmod p\). Donc \(p^2\) divise \(x + y + 2\).

Avec les notations de la première solution, en soustrayant les deux équations de départ, on obtient

\[p^b - p^a = y^{p-1} - x^{p-1} + x - y = (y - x)(y^{p-2} + y^{p-3}x + \cdots + x^{p-2} - 1). \tag{1}\]

Le second facteur est symétrique en \(x\) et \(y\) ; il s'écrit donc comme un polynôme à coefficients entiers en les polynômes symétriques élémentaires \(x + y\) et \(xy\). En particulier, sa valeur modulo \(p^2\) est déterminée par les deux congruences \(xy \equiv 1 \pmod{p^2}\) et \(x + y \equiv -2 \pmod{p^2}\). Comme ces deux congruences sont vérifiées pour \(x = y = -1\), on a

\[y^{p-2} + y^{p-3}x + \cdots + x^{p-2} - 1 \equiv (-1)^{p-2} + (-1)^{p-3}(-1) + \cdots + (-1)^{p-2} - 1 \pmod{p^2},\]

ce qui se simplifie en \(y^{p-2} + y^{p-3}x + \cdots + x^{p-2} - 1 \equiv -p \pmod{p^2}\). Le second facteur de (1) est donc divisible par \(p\), mais pas par \(p^2\).

Donc \(p^{a-1}\) divise l'autre facteur \(y - x\). Il s'ensuit que

\[0 \equiv x^{p-1} + y \equiv x^{p-1} + x \equiv x(x + 1)(x^{p-3} - x^{p-4} + \cdots + 1) \pmod{p^{a-1}}.\]

Comme \(x \equiv -1 \pmod p\), le dernier facteur vérifie \(x^{p-3} - x^{p-4} + \cdots + 1 \equiv p - 2 \pmod p\) ; en particulier, il n'est pas divisible par \(p\). On en déduit \(p^{a-1} \mid x + 1\), et l'on termine comme dans la première solution. \(\blacksquare\)

Remarque. Au lieu de raisonner avec les polynômes symétriques élémentaires, on peut aussi donner un argument plus direct. Pour \(r\) impair, \((x + 1)^2\) divise \((x^r + 1)^2\), et comme \(p\) divise \(x + 1\), \(p^2\) divise \((x^r + 1)^2\). Avec \(xy \equiv 1 \pmod{p^2}\), on obtient

\[0 \equiv y^r (x^r + 1)^2 \equiv x^{2r} y^r + 2x^r y^r + y^r \equiv x^r + 2 + y^r \pmod{p^2}.\]

En appliquant cette congruence avec \(r = p - 2 - 2k\) (où \(0 \leq k < \frac{p-2}{2}\)), on trouve

\[x^k y^{p-2-k} + x^{p-2-k} y^k \equiv (xy)^k (x^{p-2-2k} + y^{p-2-2k}) \equiv 1^k \cdot (-2) \equiv -2 \pmod{p^2}.\]

En sommant sur tous les \(k\), on retrouve

\[y^{p-2} + y^{p-3}x + \cdots + x^{p-2} - 1 \equiv \frac{p - 1}{2} \cdot (-2) - 1 \equiv -p \pmod{p^2}.\]