Shortlist 2007, N6¶
Domaine : Théorie des nombres · Difficulté : ★★★☆☆ · Proposé par : United Kingdom
Concepts : Descente infinie et Vieta jumping · Congruences, théorèmes de Fermat et d'Euler
Solution officielle : Shortlist officielle 2007 (avec solutions), p. 62 (page 63 du PDF)
Problème 5 de l'OIM 2007
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2007, où il était le problème 5 (jour 2).
Énoncé¶
Let \(k\) be a positive integer. Prove that the number \((4k^2 - 1)^2\) has a positive divisor of the form \(8kn - 1\) if and only if \(k\) is even.
Indices : les idées clés
- Lemme : \(4xy - 1 \mid (4x^2 - 1)^2\) si et seulement si \(x = y\) ; l'énoncé s'en déduit avec \(x = k\), \(y = 2n\).
- Descente : si \((x, y)\) est un « mauvais » couple avec \(x < y\), le quotient \(r \equiv -1 \pmod{4x}\) s'écrit \(4xz - 1\) avec \(z < x\), et \((x, z)\) est mauvais.
- Symétrie : \((4y^2 - 1)^2 \equiv 16y^4(4x^2 - 1)^2 \equiv 0\) modulo \(4xy - 1\), donc \((y, x)\) est aussi mauvais ; on minimise \(2x + y\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2007 (une solution et une remarque). C'est le problème 5 de l'OIM 2007.
Solution¶
L'énoncé découle du fait suivant.
Lemme. Pour des entiers strictement positifs quelconques \(x\) et \(y\), le nombre \(4xy - 1\) divise \((4x^2 - 1)^2\) si et seulement si \(x = y\).
Preuve. Si \(x = y\), alors \(4xy - 1 = 4x^2 - 1\) divise évidemment \((4x^2 - 1)^2\) ; il suffit donc de considérer le sens réciproque.
Appelons mauvais un couple \((x, y)\) d'entiers strictement positifs tel que \(4xy - 1\) divise \((4x^2 - 1)^2\) mais \(x \neq y\). Pour prouver que les mauvais couples n'existent pas, présentons deux de leurs propriétés, qui fournissent une descente infinie.
Propriété (i). Si \((x, y)\) est un mauvais couple et \(x < y\), il existe un entier strictement positif \(z < x\) tel que \((x, z)\) soit aussi mauvais.
Posons \(r = \frac{(4x^2 - 1)^2}{4xy - 1}\). Alors
et \(r = 4xz - 1\) pour un certain entier \(z > 0\). De \(x < y\), on obtient
et donc \(z < x\). Par construction, le nombre \(4xz - 1\) est un diviseur de \((4x^2 - 1)^2\), donc \((x, z)\) est un mauvais couple.
Propriété (ii). Si \((x, y)\) est un mauvais couple, alors \((y, x)\) l'est aussi.
Comme \(1 = 1^2 \equiv (4xy)^2 \pmod{4xy - 1}\), on a
Donc le nombre \(4xy - 1\) divise aussi \((4y^2 - 1)^2\).
Supposons maintenant qu'il existe au moins un mauvais couple. Prenons un mauvais couple \((x, y)\) tel que \(2x + y\) soit le plus petit possible. Si \(x < y\), la propriété (i) fournit un mauvais couple \((x, z)\) avec \(z < y\), donc \(2x + z < 2x + y\). Sinon, si \(y < x\), la propriété (ii) donne que le couple \((y, x)\) est aussi mauvais, alors que \(2y + x < 2x + y\). Les deux cas contredisent la minimalité de \(2x + y\) ; le lemme est prouvé. \(\square\)
Pour prouver l'énoncé, appliquons le lemme pour \(x = k\) et \(y = 2n\) ; le nombre \(8kn - 1\) divise \((4k^2 - 1)^2\) si et seulement si \(k = 2n\). Il n'y a donc pas de tel \(n\) si \(k\) est impair, et \(n = k/2\) est la seule solution si \(k\) est pair. \(\blacksquare\)
Remarque¶
La constante \(4\) du lemme peut être remplacée par n'importe quel entier supérieur à \(1\) : si \(a > 1\) et \(axy - 1\) divise \((ax^2 - 1)^2\), alors \(x = y\).