Shortlist 2007, N5¶
Domaine : Théorie des nombres · Difficulté : ★★★☆☆ · Proposé par : Iran
Concepts : Congruences, théorèmes de Fermat et d'Euler · Équations fonctionnelles : substitutions, injectivité, surjectivité
Solution officielle : Shortlist officielle 2007 (avec solutions), p. 60 (page 61 du PDF)
Énoncé¶
Find all surjective functions \(f : \mathbb{N} \to \mathbb{N}\) such that for every \(m, n \in \mathbb{N}\) and every prime \(p\), the number \(f(m + n)\) is divisible by \(p\) if and only if \(f(m) + f(n)\) is divisible by \(p\).
(\(\mathbb{N}\) is the set of all positive integers.)
Indices : les idées clés
- Plus petit multiple : avec \(d = \min\{x : p \mid f(x)\}\), on a \(p \mid f(x) \iff d \mid x\).
- Lemme de congruences : \(x \equiv y \pmod d \iff f(x) \equiv f(y) \pmod p\), en utilisant le terme auxiliaire \(f(2xd - x)\) ; la surjectivité donne alors \(d = p\).
- Récurrence : si \(f(n) = k \neq n\), un premier \(p\) divisant \(\lvert k - n \rvert + 1\) contredit le lemme, d'où \(f(n) = n\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2007 (une solution).
Réponse : \(f(n) = n\).
Solution¶
Supposons que la fonction \(f : \mathbb{N} \to \mathbb{N}\) vérifie les conditions du problème.
Lemme. Pour tout nombre premier \(p\) et tous \(x, y \in \mathbb{N}\), on a \(x \equiv y \pmod p\) si et seulement si \(f(x) \equiv f(y) \pmod p\). De plus, \(p \mid f(x)\) si et seulement si \(p \mid x\).
Preuve. Considérons un nombre premier \(p\) quelconque. Comme \(f\) est surjective, il existe un \(x \in \mathbb{N}\) tel que \(p \mid f(x)\). Posons
Par récurrence sur \(k\), on obtient que \(p \mid f(kd)\) pour tout \(k \in \mathbb{N}\). Le cas de base est vrai puisque \(p \mid f(d)\). De plus, si \(p \mid f(kd)\) et \(p \mid f(d)\), alors, d'après la condition du problème, \(p \mid f(kd + d) = f((k + 1)d)\), comme voulu.
Supposons qu'il existe un \(x \in \mathbb{N}\) tel que \(d \nmid x\) mais \(p \mid f(x)\). Posons
Par le choix de \(d\), on a \(y > d\), et \(y - d\) est un entier strictement positif non divisible par \(d\). Alors \(p \nmid f(y - d)\), alors que \(p \mid f(d)\) et \(p \mid f(d + (y - d)) = f(y)\). Cela contredit la condition du problème. Un tel \(x\) n'existe donc pas, et
Prenons des \(x, y \in \mathbb{N}\) quelconques tels que \(x \equiv y \pmod d\). On a \(p \mid f(x + (2xd - x)) = f(2xd)\) ; de plus, comme \(d \mid 2xd + (y - x) = y + (2xd - x)\), on obtient \(p \mid f(y + (2xd - x))\). Alors, par la condition du problème, \(p \mid f(x) + f(2xd - x)\) et \(p \mid f(y) + f(2xd - x)\), donc \(f(x) \equiv -f(2xd - x) \equiv f(y) \pmod p\).
D'autre part, supposons \(f(x) \equiv f(y) \pmod p\). On a de nouveau \(p \mid f(x) + f(2xd - x)\), ce qui, avec notre hypothèse, implique \(p \mid f(x) + f(2xd - x) + (f(y) - f(x)) = f(y) + f(2xd - x)\). Donc, par la condition du problème, \(p \mid f(y + (2xd - x))\). Avec (1), on obtient \(0 \equiv y + (2xd - x) \equiv y - x \pmod d\).
On a donc prouvé que
Il reste à montrer que \(p = d\) : dans ce cas, (1) et (2) donnent les énoncés voulus.
Les nombres \(1, 2, \ldots, d\) ont des restes distincts modulo \(d\). D'après (2), les nombres \(f(1), f(2), \ldots, f(d)\) ont des restes distincts modulo \(p\) ; il y a donc au moins \(d\) restes distincts, et \(p \geq d\). D'autre part, par surjectivité de \(f\), il existe \(x_1, \ldots, x_p \in \mathbb{N}\) tels que \(f(x_i) = i\) pour tout \(i = 1, 2, \ldots, p\). D'après (2), tous ces \(x_i\) ont des restes distincts modulo \(d\). Pour les mêmes raisons, \(d \geq p\). Donc \(d = p\). \(\square\)
Montrons maintenant que \(f(n) = n\) par récurrence sur \(n\). Si \(n = 1\), alors, d'après le lemme, \(p \nmid f(1)\) pour tout nombre premier \(p\), donc \(f(1) = 1\), et le cas de base est établi. Supposons \(n > 1\) et notons \(k = f(n)\). Remarquons qu'il existe un nombre premier \(q \mid n\), donc, d'après le lemme, \(q \mid k\) et \(k > 1\).
Si \(k > n\), alors \(k - n + 1 > 1\), et il existe un nombre premier \(p \mid k - n + 1\) ; on a \(k \equiv n - 1 \pmod p\). Par l'hypothèse de récurrence, \(f(n - 1) = n - 1 \equiv k = f(n) \pmod p\). Alors, d'après le lemme, \(n - 1 \equiv n \pmod p\), ce qui est impossible.
De même, si \(k < n\), alors \(f(k - 1) = k - 1\) par l'hypothèse de récurrence. De plus, \(n - k + 1 > 1\), donc il existe un nombre premier \(p \mid n - k + 1\) et \(n \equiv k - 1 \pmod p\). D'après le lemme, \(k = f(n) \equiv f(k - 1) = k - 1 \pmod p\), ce qui est aussi faux. Le seul cas restant est \(k = n\), donc \(f(n) = n\).
Enfin, la fonction \(f(n) = n\) vérifie évidemment la condition. \(\blacksquare\)