Aller au contenu

Shortlist 2020, N4

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

Concepts : Ordre d'un élément et racines primitives · Divisibilité, PGCD et algorithme d'Euclide · Diviseurs premiers : Zsigmondy, premiers divisant un polynôme

Solution officielle : Shortlist officielle 2020 (avec solutions), p. 76 (page 78 du PDF)

Énoncé

For any odd prime \(p\) and any integer \(n\), let \(d_p(n) \in \{0, 1, \ldots, p - 1\}\) denote the remainder when \(n\) is divided by \(p\). We say that \((a_0, a_1, a_2, \ldots)\) is a \(p\)-sequence, if \(a_0\) is a positive integer coprime to \(p\), and \(a_{n+1} = a_n + d_p(a_n)\) for \(n \geq 0\).

(a) Do there exist infinitely many primes \(p\) for which there exist \(p\)-sequences \((a_0, a_1, a_2, \ldots)\) and \((b_0, b_1, b_2, \ldots)\) such that \(a_n > b_n\) for infinitely many \(n\), and \(b_n > a_n\) for infinitely many \(n\)?

(b) Do there exist infinitely many primes \(p\) for which there exist \(p\)-sequences \((a_0, a_1, a_2, \ldots)\) and \((b_0, b_1, b_2, \ldots)\) such that \(a_0 < b_0\), but \(a_n > b_n\) for all \(n \geq 1\)?

Indices : les idées clés
  • Doublement modulo \(p\) : \(x_{n+1} \equiv 2x_n \pmod p\), donc \(x_n \equiv 2^nx_0\) et les restes sont périodiques de période \(T\), l'ordre de 2 modulo p.
  • Accroissement par période : \(x_{n+kT} = x_n + kS_p(x_0)\), où \(S_p(x_0)\) est la somme des restes sur une période ; tout se joue sur la comparaison des \(S_p\).
  • Partie (a) : avec \(p \mid 2^q + 1\), on a \(T = 2q\) et \(S_p(1) = S_p(-1)\), et deux suites peuvent alors se dépasser alternativement.
  • Partie (b) : avec \(p \mid 2^q - 1\), on a \(T = q\) et \(S_p(1) + S_p(-1) = pq\) est impair, donc \(S_p(1) \neq S_p(-1)\) ; la suite de plus grande pente finit par passer devant pour toujours.
  • PGCD de nombres de Mersenne : \(\gcd(2^q \pm 1, 2^r \pm 1)\) se calcule via \(2^{\gcd(q, r)}\), ce qui fournit une infinité de premiers \(p\).
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2020 (une solution).

Réponse : oui pour les deux parties.

Solution

Fixons un premier impair \(p\), et soit \(T\) le plus petit entier positif tel que \(p \mid 2^T - 1\) ; autrement dit, \(T\) est l'ordre multiplicatif de \(2\) modulo \(p\). Nous écrivons \(d\) pour \(d_p\).

Considérons une \(p\)-suite \((x_n) = (x_0, x_1, x_2, \ldots)\). Évidemment \(x_{n+1} \equiv 2x_n \pmod p\), donc \(x_n \equiv 2^nx_0 \pmod p\). Cela donne \(x_{n+T} \equiv x_n \pmod p\), donc \(d(x_{n+T}) = d(x_n)\) pour tout \(n \geq 0\). Il s'ensuit que la somme \(d(x_n) + d(x_{n+1}) + \cdots + d(x_{n+T-1})\) ne dépend pas de \(n\) : c'est une fonction de \(x_0\) (et de \(p\)) seulement, que l'on note \(S_p(x_0)\) ; on étend \(S_p(\cdot)\) à tous les entiers (pas forcément positifs). On a donc \(x_{n+kT} = x_n + kS_p(x_0)\) pour tous entiers positifs \(n\) et \(k\). Clairement, \(S_p(x_0) = S_p(2^tx_0)\) pour tout entier \(t \geq 0\).

Dans les deux parties, on utilise les notations

\[S_p^+ = S_p(1) = \sum_{i=0}^{T-1} d(2^i) \qquad \text{et} \qquad S_p^- = S_p(-1) = \sum_{i=0}^{T-1} d(p - 2^i).\]

(a) Soit \(q > 3\) un nombre premier et \(p\) un diviseur premier de \(2^q + 1\) supérieur à \(3\). Montrons que \(p\) convient pour la partie (a). Remarquons que \(9 \nmid 2^q + 1\) (par exemple par le lemme LTE : \(v_3(2^q + 1) = v_3(3) + v_3(q) = 1\)), donc un tel \(p\) existe. De plus, pour deux premiers impairs \(q < r\), on a \(\gcd(2^q + 1, 2^r + 1) = 2^{\gcd(q, r)} + 1 = 3\) ; on obtient donc une infinité de tels premiers \(p\).

Pour le \(p\) choisi, on a \(T = 2q\) (l'ordre divise \(2q\), et ce n'est ni \(1\), ni \(2\), ni \(q\) puisque \(2^q \equiv -1\) et \(p > 3\)). Comme \(2^q \equiv -1 \pmod p\), les restes de \(-2^i\) parcourent ceux des \(2^{i+q}\), donc \(S_p^+ = S_p^-\). Considérons les \(p\)-suites \((a_n)\) et \((b_n)\) avec \(a_0 = p + 1\) et \(b_0 = p - 1\) ; montrons qu'elles conviennent. On a \(a_0 > b_0\) et \(a_1 = p + 2 < b_1 = 2p - 2\). Comme \(S_p(a_0) = S_p(1) = S_p^+\) et \(S_p(b_0) = S_p(-1) = S_p^- = S_p^+\), on obtient

\[a_{k \cdot 2q} = a_0 + kS_p^+ > b_0 + kS_p^+ = b_{k \cdot 2q} \qquad \text{et} \qquad a_{k \cdot 2q + 1} = a_1 + kS_p^+ < b_1 + kS_p^+ = b_{k \cdot 2q + 1}\]

pour tout \(k = 0, 1, \ldots\), comme voulu.

(b) Soit \(q\) un premier impair et \(p\) un diviseur premier de \(2^q - 1\) ; alors \(T = q\). Montrons que \(p\) convient pour la partie (b). Les nombres de la forme \(2^q - 1\) sont deux à deux premiers entre eux (car \(\gcd(2^q - 1, 2^r - 1) = 2^{\gcd(q, r)} - 1 = 1\) pour deux premiers distincts \(q\) et \(r\)), donc il existe une infinité de tels premiers \(p\). Remarquons que \(d(x) + d(p - x) = p\) pour tout \(x\) avec \(p \nmid x\) ; ainsi \(S_p^+ + S_p^- = pq\) est impair, ce qui donne \(S_p^+ = S_p(1) \neq S_p(-1) = S_p^-\).

Supposons que \((x_n)\) et \((y_n)\) soient deux \(p\)-suites avec \(S_p(x_0) > S_p(y_0)\) mais \(x_0 < y_0\). La première condition donne

\[x_{Mq+r} - y_{Mq+r} = (x_r - y_r) + M\left(S_p(x_0) - S_p(y_0)\right) \geq (x_r - y_r) + M\]

pour tout entier \(M \geq 0\) et tout \(r = 0, 1, \ldots, q - 1\). Donc \(x_n > y_n\) pour tout \(n \geq q + q \cdot \max\{y_r - x_r : r = 0, 1, \ldots, q - 1\}\). Comme \(x_0 < y_0\), il existe un plus grand \(n_0\) tel que \(x_{n_0} < y_{n_0}\). Les \(p\)-suites \(a_n = x_{n+n_0}\) et \(b_n = y_{n+n_0}\) ont alors la propriété voulue : \(a_0 < b_0\) et \(a_n > b_n\) pour \(n \geq 1\). (Remarquons que \(x_n \neq y_n\) pour tout \(n \geq 0\), sinon on aurait \(S_p(x_0) = S_p(x_n) = S_p(y_n) = S_p(y_0)\).)

Il reste à trouver des \(p\)-suites \((x_n)\) et \((y_n)\) vérifiant les deux conditions. Rappelons que \(S_p^+ \neq S_p^-\). Si \(S_p^+ > S_p^-\), on prend \(x_0 = 1\) et \(y_0 = p - 1\). Sinon, si \(S_p^+ < S_p^-\), on prend \(x_0 = p - 1\) et \(y_0 = p + 1\). \(\blacksquare\)