Shortlist 2016, N4¶
Domaine : Théorie des nombres · Difficulté : ★★☆☆☆ · Proposé par : non indiqué
Concepts : Divisibilité, PGCD et algorithme d'Euclide · Équations diophantiennes : factorisation et encadrement
Solution officielle : Shortlist officielle 2016 (avec solutions), p. 77 (page 80 du PDF)
Énoncé¶
Let \(n\), \(m\), \(k\) and \(l\) be positive integers with \(n \neq 1\) such that \(n^k + mn^l + 1\) divides \(n^{k+l} - 1\). Prove that
- \(m = 1\) and \(l = 2k\); or
- \(l \mid k\) and \(m = \dfrac{n^{k-l} - 1}{n^l - 1}\).
Indices : les idées clés
- Divisibilité : on ajoute le diviseur au dividende pour obtenir \(n^k + mn^l + 1 \mid n^{k+l} + n^k + mn^l\), puis on simplifie par une puissance de \(n\), première avec le diviseur.
- Encadrement : un diviseur positif d'un entier positif lui est inférieur ; comparer les tailles (ou montrer que le quotient vaut \(1\)) force l'égalité.
- Quotient borné (solution 1, cas \(l < k\)) : le quotient \(t\) de \(n^{k+l} - 1\) par \(n^k + mn^l + 1\) vérifie \(t \leq n^l - 1\), ce qui donne l'inégalité inverse.
- \(n^l - 1 \mid n^{k-l} - 1 \Rightarrow l \mid k - l\), d'où \(l \mid k\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2016 (deux solutions et une remarque).
Solution 1¶
On a, par hypothèse,
Donc
On distingue deux cas.
Cas 1 : \(l \geq k\). Comme \((n^k + mn^l + 1, n) = 1\), on peut diviser le membre de droite de (2) par \(n^k\) :
En particulier, \(n^k + mn^l + 1 \leq n^l + mn^{l-k} + 1\), soit \((m - 1)n^l \leq mn^{l-k} - n^k\). Comme \(n \geq 2\) et \(k \geq 1\), \((m - 1)n^l\) est au moins \(2(m - 1)n^{l-k}\) ; on vérifie que l'inégalité ne peut pas être vraie si \(m \geq 2\).
Précision ajoutée : pour \(m \geq 2\), \((m-1)n^l \geq 2(m-1)n^{l-k} \geq m\,n^{l-k} > mn^{l-k} - n^k\).
Pour \(m = 1\), la divisibilité devient
Or \(n^l + n^{l-k} + 1 < n^l + n^l + 1 < 2(n^k + n^l + 1)\). On a donc nécessairement \(n^l + n^{l-k} + 1 = n^k + n^l + 1\), d'où \(l - k = k\), c'est-à-dire \(l = 2k\) : c'est la première conclusion.
Cas 2 : \(l < k\). Cette fois, en divisant par \(n^l\), (2) donne
En particulier, par encadrement, \(n^k + mn^l + 1 \leq n^k + n^{k-l} + m\), ce qui donne
D'autre part, d'après (1), on peut écrire \(n^{k+l} - 1 = (n^k + mn^l + 1)t\) avec \(t\) entier strictement positif. Clairement \(t < n^l\), donc \(t \leq n^l - 1\) puisque \(t\) est entier. Alors \(n^{k+l} - 1 \leq (n^k + mn^l + 1)(n^l - 1)\), ce qui équivaut à
Les inégalités (3) et (4) donnent \(m = \dfrac{n^{k-l} - 1}{n^l - 1}\). Comme c'est un entier, \(n^l - 1 \mid n^{k-l} - 1\), donc \(l \mid k - l\). Ainsi \(l \mid k\), et c'est la seconde conclusion. \(\blacksquare\)
Précision ajoutée : \((n^k + mn^l + 1)(n^l - 1) = n^{k+l} - n^k + mn^{2l} - mn^l + n^l - 1\), donc l'inégalité équivaut à \(n^k - n^l \leq m(n^{2l} - n^l)\), soit \(n^{k-l} - 1 \leq m(n^l - 1)\) ; et \(n^l - 1 \mid n^{k-l} - 1\) implique \(l \mid k - l\) (écrire \(k - l = ql + r\) avec \(0 \leq r < l\) : alors \(n^{k-l} - 1 \equiv n^r - 1 \pmod{n^l - 1}\), et \(0 \leq n^r - 1 < n^l - 1\) impose \(r = 0\)).
Solution 2¶
On part, comme dans la solution 1, de la relation (2).
Cas 1 : \(l \geq k\). Alors (2) donne
Comme \(2(n^k + mn^l + 1) > 2mn^l + 1 > n^l + mn^{l-k} + 1\), le quotient vaut \(1\) et
Si \(m \geq 2\), alors \(m(n^l - n^{l-k}) \geq 2n^l - 2n^{l-k} \geq 2n^l - n^l > n^l - n^k\), contradiction. Donc \(m = 1\) et \(l - k = k\), c'est-à-dire \(m = 1\) et \(l = 2k\).
Cas 2 : \(l < k\). Alors (2) donne
Comme \(2(n^k + mn^l + 1) > 2n^k + m > n^k + n^{k-l} + m\), le quotient vaut \(1\) et \(n^k + mn^l + 1 = n^k + n^{k-l} + m\). Cela donne \(m = \dfrac{n^{k-l} - 1}{n^l - 1}\). Enfin, \(n^l - 1 \mid n^{k-l} - 1\) implique \(l \mid k - l\), donc \(l \mid k\). \(\blacksquare\)
Remarques¶
Remarque. Une autre version du problème : soient \(n, m, k, l\) des entiers strictement positifs avec \(n \neq 1\), tels que ni \(k\) ne divise \(l\), ni \(l\) ne divise \(k\). Montrer que \(n^k + mn^l + 1\) ne divise pas \(n^{k+l} - 1\).