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é¶
Soit \(k\) un entier strictement positif. Montrer que le nombre \((4k^2 - 1)^2\) a un diviseur positif de la forme \(8kn - 1\) si et seulement si \(k\) est pair.
Énoncé original (anglais)
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\).
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2025 N3 ★★☆☆☆ · OIM P4 : Chaque terme est la somme des trois plus grands diviseurs stricts du précédent : avec quelles valeurs la suite peut-elle partir ?
- 2016 N5 ★★★☆☆ : Les entiers \((x^2 - a)/(x^2 - y^2)\) obtenus avec \(x > \sqrt{a}\) sont exactement ceux obtenus avec \(x < \sqrt{a}\).
- 2010 N3 ★★★☆☆ : Combien de carrés de polynômes rationnels faut-il au minimum pour écrire \(x^2 + 7\) ?
- 2009 N4 ★★★☆☆ : Pour quelles longueurs \(n\) la récurrence \(a_{k+1} = (a_k^2 + 1)/(a_{k-1} + 1) - 1\) peut-elle rester entière ?