Shortlist 2015, N7¶
Domaine : Théorie des nombres · Difficulté : ★★★★☆ · Proposé par : Canada
Concepts : Congruences, théorèmes de Fermat et d'Euler · Théorème des restes chinois · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2015 (avec solutions), p. 76 (page 77 du PDF)
Énoncé¶
Let \(\mathbb{Z}_{>0}\) denote the set of positive integers. For any positive integer \(k\), a function \(f : \mathbb{Z}_{>0} \to \mathbb{Z}_{>0}\) is called \(k\)-good if \(\gcd\big(f(m) + n,\, f(n) + m\big) \leq k\) for all \(m \neq n\). Find all \(k\) such that there exists a \(k\)-good function.
Indices : les idées clés
- Parité : il n'existe pas de fonction \(1\)-bonne, car on trouve toujours \(m \neq n\) avec \(f(m) + n\) et \(f(n) + m\) pairs.
- Petit théorème de Fermat (solution 1) : avec \(f(n) = 2^{g(n)+1} - n - 1\) et \(g(n+1) = (2^{g(n)+1})!\), tout premier impair \(p\) divisant \(A\) et \(B\) vérifie \(p - 1 \mid g(m)\), donc \(2^{g(m)} \equiv 1 \pmod p\).
- Théorème des restes chinois (solution 2) : on fixe \(f(m)\) modulo chaque premier « dangereux ».
- Construction récursive (solution 2) : on définit \(f(m)\) étape par étape en maintenant des invariants, avec un résidu « sûr » \(a_p\) pour chaque \(p\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2015 (deux solutions et trois remarques).
Réponse. \(k \geq 2\).
Solution 1¶
Pour \(f : \mathbb{Z}_{>0} \to \mathbb{Z}_{>0}\), notons \(G_f(m, n) = \gcd\big(f(m) + n, f(n) + m\big)\). Une fonction \(k\)-bonne est aussi \((k+1)\)-bonne. Il suffit donc de montrer qu'il n'existe pas de fonction \(1\)-bonne et qu'il existe une fonction \(2\)-bonne.
Pas de fonction 1-bonne. Supposons \(G_f(m, n) = 1\) pour tous \(m \neq n\). S'il existe deux nombres pairs distincts \(m\), \(n\) avec \(f(m)\) et \(f(n)\) pairs, alors \(2 \mid G_f(m, n)\) : contradiction. De même s'il existe deux nombres impairs distincts \(m\), \(n\) avec \(f(m)\) et \(f(n)\) impairs. On peut donc choisir \(m\) pair avec \(f(m)\) impair et \(n\) impair avec \(f(n)\) pair. Mais alors \(f(m) + n\) et \(f(n) + m\) sont pairs, et \(2 \mid G_f(m, n)\) : contradiction.
Une fonction 2-bonne. Posons \(f(n) = 2^{g(n)+1} - n - 1\), où \(g\) est définie par récurrence par \(g(1) = 1\) et \(g(n+1) = \left(2^{g(n)+1}\right)!\). Pour \(m > n\), posons
Il faut montrer que \(\gcd(A, B) \leq 2\). D'abord, \(A + B = 2^{g(m)+1} + 2^{g(n)+1} - 2\) n'est pas divisible par \(4\), donc \(4 \nmid \gcd(A, B)\). Supposons qu'un premier impair \(p\) divise \(\gcd(A, B)\), et cherchons une contradiction.
On a \(2^{g(m-1)+1} \geq B\) (borne assez faible). En effet, \(g(k+1) > g(k)\), donc \(2^{g(k+1)+1} \geq 2^{g(k)+1} + 1\) pour tout \(k\) ; en itérant de \(n\) à \(m - 1\), on obtient \(2^{g(m-1)+1} \geq 2^{g(n)+1} + (m - 1) - n = B\).
Comme \(p \mid B\), on a \(p - 1 < B \leq 2^{g(m-1)+1}\), donc \(p - 1\) divise \(\left(2^{g(m-1)+1}\right)! = g(m)\). Par le petit théorème de Fermat, \(2^{g(m)} \equiv 1 \pmod p\), d'où \(A + B \equiv 2 + 2^{g(n)+1} - 2 = 2^{g(n)+1} \pmod p\). Comme \(p \mid A + B\), on obtient \(p = 2\) : contradiction. \(\blacksquare\)
Solution 2¶
Voici une autre construction d'une fonction \(2\)-bonne (la non-existence d'une fonction \(1\)-bonne se montre comme dans la solution 1).
Soit \(\mathcal{P}\) l'ensemble formé de \(4\) et de tous les premiers impairs. Pour \(p \in \mathcal{P}\), un nombre \(a \in \{0, 1, \ldots, p-1\}\) est dit \(p\)-utile si \(a \not\equiv -a \pmod p\). Un résidu modulo \(p\) qui n'est ni \(0\) ni \(2\) est \(p\)-utile (la condition « \(\neq 2\) » ne sert que pour \(p = 4\)).
On construit \(f\) par récurrence ; à certaines étapes, on définit aussi un nombre \(p\)-utile \(a_p\). Après l'étape \(m\), la construction vérifie :
- (i) \(f(n)\) est défini pour tout \(n \leq m\), et \(a_p\) est défini pour tout \(p \leq m + 2\) ;
- (ii) si \(n \leq m\) et \(p \leq m + 2\), alors \(f(n) + n \not\equiv a_p \pmod p\) ;
- (iii) \(\gcd\big(f(n_1) + n_2, f(n_2) + n_1\big) \leq 2\) pour tous \(n_1 < n_2 \leq m\).
Si ces conditions sont satisfaites à chaque étape, \(f\) est \(2\)-bonne (un pgcd \(> 2\) serait divisible par \(4\) ou par un premier impair, donc par un élément de \(\mathcal{P}\)).
Étape 1. On pose \(f(1) = 1\) et \(a_3 = 1\). Les conditions sont clairement vérifiées.
Étape \(m\), pour \(m \geq 2\). Il faut définir \(f(m)\) et, si \(m + 2 \in \mathcal{P}\), le nombre \(a_{m+2}\).
Définition de \(f(m)\). Soit \(X_m = \{ p \in \mathcal{P} : p \mid f(n) + m \text{ pour un } n < m \}\) (ensemble fini). On fixe \(f(m)\) modulo chaque \(p \in X_m\), puis on choisit \(f(m)\) par le théorème des restes chinois (les éléments de \(\mathcal{P}\) sont deux à deux premiers entre eux). Pour \(p \in X_m\) : si \(p \leq m + 1\), on impose \(f(m) \equiv -a_p - m \pmod p\) ; si \(p \geq m + 2\), on impose \(f(m) \equiv 0 \pmod p\). Précision ajoutée : le livret n'impose la congruence \(f(m) \equiv -a_p - m\) que pour \(p \in X_m\) ; pour que (ii) soit vraie aussi pour \(n = m\) et un \(p \leq m + 1\) hors de \(X_m\), il faut l'imposer pour tous les \(p \in \mathcal{P}\) avec \(p \leq m + 1\) (ils sont en nombre fini, donc les restes chinois s'appliquent encore).
Définition de \(a_{m+2}\). Soit \(p = m + 2\), supposé dans \(\mathcal{P}\). On choisit pour \(a_p\) un résidu modulo \(p\) non congru à \(0\), à \(2\), ni à \(f(n) + n\) pour \(n \leq m\). Comme \(f(1) + 1 = 2\), il y a au plus \(m + 1 < p\) résidus à éviter : c'est toujours possible.
Vérification de (ii). Il suffit de la vérifier si \(p = m + 2\) ou \(n = m\). Dans le premier cas, \(f(n) + n \not\equiv a_p\) par construction. Dans le second, si \(n = m\) et \(p \leq m + 1\), alors \(f(m) + m \equiv -a_p \not\equiv a_p \pmod p\), puisque \(a_p\) est \(p\)-utile.
Vérification de (iii). Supposons au contraire que \(p \mid \gcd\big(f(n) + m, f(m) + n\big)\) pour un \(n < m\) et un \(p \in \mathcal{P}\). Alors \(p \in X_m\) et \(p \mid f(m) + n\). Si \(p \geq m + 2\), alors \(0 \equiv f(m) + n \equiv n \pmod p\), impossible car \(n < m < p\). Sinon \(p \leq m + 1\), et
donc \(f(n) + n \equiv a_p \pmod p\), ce qui contredit (ii). \(\blacksquare\)
Remarques¶
Remarque 1. Pour \(p \in \mathcal{P}\), on peut aussi définir \(a_p\) à une étape \(m \leq p - 2\) quelconque. La construction fonctionne tant qu'on ne définit qu'un nombre fini de \(a_p\) à chaque étape.
Remarque 2 (une construction naturelle mais incomplète). On pose \(f(1) = 1\) puis, pour \(m > 1\), avec \(X_m\) comme dans la solution 2, on impose
Cela semble marcher : si \(p\) divise \(\gcd\big(f(n) + m, f(m) + n\big)\) avec \(n < m\) et \(\max(m, n)\) minimal, alors \(p \in X_m\), on vérifie que \(p < m\), et la construction donne \(p \mid \gcd\big(f(n) + (m - p), f(m - p) + n\big)\). Comme \(\max(n, m - p) < \max(m, n)\), on a presque une contradiction ; le seul problème est le cas \(n = m - p\), qui n'est pas facile à réparer.
Remarque 3 (une approche générale). Notons \(\mathbb{Z}_p\) les résidus modulo \(p\). On garde la structure de la solution 2 (restes chinois pour fixer \(f(m)\)), mais au lieu d'un résidu sûr commun \(a_p\), on définit à une certaine étape, pour chaque \(p \in \mathcal{P}\), des sous-ensembles \(B_p^{(i)} \subset \mathbb{Z}_p\) (\(i \in \mathbb{Z}_p\)) avec la signification :
Dans chacun on choisit un élément sûr \(b_p^{(i)} \in B_p^{(i)}\) : il sera toujours sûr de poser \(f(m) + m \equiv b_p^{(i)}\) quand \(m \equiv i\). Cette sûreté découle de la condition \(p \nmid \gcd\big(b_p^{(i)} + (j - i), c^{(j)} - (j - i)\big)\) pour tout \(j \in \mathbb{Z}_p\) et tout \(c^{(j)} \in B_p^{(j)}\), qui se réécrit
La solution 2 correspond à \(b_p^{(i)} = -a_p\) et \(B_p^{(i)} = \mathbb{Z}_p \setminus \{a_p\}\) pour tout \(i\). La construction incomplète de la remarque 2 revient à poser, à l'étape \(p - 1\), \(B_p^{(0)} = \{b_p^{(0)}\} = \{0\}\) et \(B_p^{(i)} = \{b_p^{(i)}\} = \{f(i) + i \bmod p\}\) pour \(i = 1, \ldots, p-1\) ; elle viole (2) dès qu'un nombre \(f(i) + i\) est divisible par un \(p \in \mathcal{P}\) avec \(i + 2 \leq p\), car alors \(-b_p^{(i)} = b_p^{(i)} \in B_p^{(i)}\). Une réparation possible : à l'étape \(p - 2\), on pose \(B_p^{(1)} = \{b_p^{(1)}\} = \{2\}\), \(B_p^{(-1)} = B_p^{(0)} = \{b_p^{(-1)}\} = \{b_p^{(0)}\} = \{-1\}\), et pour \(i = 2, \ldots, p-2\), \(B_p^{(i)} = \{i, f(i) + i \bmod p\}\) et \(b_p^{(i)} = i\). Ces définitions sont compatibles avec (1) et (2).