Aller au contenu

Shortlist 2024, N4

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

Concepts : Divisibilité, PGCD et algorithme d'Euclide · Congruences, théorèmes de Fermat et d'Euler · Valuations p-adiques et lemme LTE

Solution officielle : Shortlist officielle 2024 (avec solutions), section N4 (livret PDF)

Problème 2 de l'OIM 2024

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2024, où il était le problème 2 (jour 1).

Énoncé

Determine all positive integers \(a\) and \(b\) such that there exists a positive integer \(g\) such that \(\gcd(a^n + b, b^n + a) = g\) for all sufficiently large \(n\).

Indices : les idées clés
  • Divisibilité et PGCD : en combinant les rangs \(N\) et \(N+1\), on montre que \(g = \gcd(a,b)\) ou \(g = 2\gcd(a,b)\).
  • Théorème d'Euler / petit théorème de Fermat : avec \(n \equiv -1\), \(a^n\) « devient » \(a^{-1}\), et \(a^{-1} + b = a^{-1}(1+ab)\).
  • Le module \(K = d^2xy + 1\) (solution 1) ou les facteurs premiers de \(ab+1\) (solution 2) divisent alors les deux termes pour une infinité de \(n\).
  • Valuation 2-adique (solution 2) : travailler modulo \(4\) pour exclure le cas où \(ab+1\) est une puissance de \(2\).
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2024 (deux solutions).

Réponse : la seule solution est \((a,b) = (1,1)\).

Solution 1

Pour \((a,b) = (1,1)\), on a \(\gcd(1+1, 1+1) = 2\) pour tout \(n\), donc \(g = 2\) convient.

Réciproquement, supposons que \((a,b)\) convienne et soit \(N\) un entier tel que \(\gcd(a^n + b, b^n + a) = g\) pour tout \(n \geq N\).

Lemme. On a \(g = \gcd(a,b)\) ou \(g = 2\gcd(a,b)\).

Preuve. Les nombres \(a^N + b\) et \(a^{N+1} + b\) sont divisibles par \(g\), donc

\[a(a^N + b) - (a^{N+1} + b) = ab - b = b(a-1)\]

est divisible par \(g\). De même, \(a(b-1)\) est divisible par \(g\). Leur différence \(a - b\) est donc divisible par \(g\), et par suite \(g\) divise aussi \(a(b-1) + a(a-b) = a^2 - a\). Ainsi \(a^{k+1} \equiv a^k \pmod g\) pour tout \(k \geq 1\) : toutes les puissances de \(a\) sont congrues modulo \(g\), d'où

\[a + b \equiv a^N + b \equiv 0 \pmod g.\]

Alors \(2a = (a+b) + (a-b)\) et \(2b = (a+b) - (a-b)\) sont divisibles par \(g\), donc \(g \mid 2\gcd(a,b)\). D'autre part, il est clair que \(\gcd(a,b) \mid g\). Comme \(g/\gcd(a,b)\) divise \(2\), le lemme est démontré (divisibilité et PGCD). \(\square\)

Posons \(d = \gcd(a,b)\) et écrivons \(a = dx\), \(b = dy\) avec \(x, y\) entiers positifs premiers entre eux. On a

\[\gcd\big((dx)^n + dy,\ (dy)^n + dx\big) = d \cdot \gcd\big(d^{n-1}x^n + y,\ d^{n-1}y^n + x\big),\]

donc le lemme donne

\[\gcd\big(d^{n-1}x^n + y,\ d^{n-1}y^n + x\big) \leq 2 \quad \text{pour tout } n \geq N.\]

Posons \(K = d^2xy + 1\) ; \(K\) est premier avec \(d\), avec \(x\) et avec \(y\). Par le théorème d'Euler, pour \(n \equiv -1 \pmod{\varphi(K)}\), on a (les inverses étant pris modulo \(K\))

\[d^{n-1}x^n + y \equiv d^{-2}x^{-1} + y \equiv d^{-2}x^{-1}\,(1 + d^2xy) \equiv 0 \pmod K,\]

donc \(K \mid d^{n-1}x^n + y\). De même, \(K \mid d^{n-1}y^n + x\). En choisissant un tel \(n\) avec de plus \(n \geq N\), on obtient

\[K \mid \gcd\big(d^{n-1}x^n + y,\ d^{n-1}y^n + x\big) \leq 2,\]

donc \(K = d^2xy + 1 \leq 2\). Cela n'est possible que si \(d = x = y = 1\), ce qui donne la seule solution \((a,b) = (1,1)\). \(\blacksquare\)

Solution 2

On démontre d'abord le lemme comme dans la solution 1, puis on conclut ainsi.

Soit \(p\) un facteur premier de \(ab + 1\) ; alors \(p\) est premier avec \(a\) et avec \(b\). Prenons \(n \geq N\) tel que \(n \equiv -1 \pmod{p-1}\). Par le petit théorème de Fermat,

\[a^n + b \equiv a^{-1} + b = a^{-1}(1 + ab) \equiv 0 \pmod p, \qquad b^n + a \equiv b^{-1} + a = b^{-1}(1 + ab) \equiv 0 \pmod p,\]

donc \(p\) divise \(g\). D'après le lemme, \(p \mid 2\gcd(a,b)\) ; comme \(p\) ne divise pas \(a\), on a \(p = 2\). Par conséquent \(ab + 1\) est une puissance de \(2\), et \(a\) et \(b\) sont tous deux impairs.

Si \((a,b) \neq (1,1)\), alors \(ab + 1 \geq 4\) est divisible par \(4\), donc \(\{a, b\} \equiv \{-1, 1\} \pmod 4\). Pour \(n \geq N\) impair, on a alors

\[a^n + b \equiv b^n + a \equiv (-1) + 1 = 0 \pmod 4,\]

donc \(4 \mid g\). Mais le lemme donne \(\nu_2(g) \leq \nu_2(2\gcd(a,b)) = 1\) (car \(a, b\) sont impairs) : c'est une contradiction (valuation 2-adique).

La seule solution est donc \((a,b) = (1,1)\). \(\blacksquare\)