Shortlist 2011, N3¶
Domaine : Théorie des nombres · Difficulté : ★★★☆☆ · Proposé par : non indiqué
Concepts : Divisibilité, PGCD et algorithme d'Euclide · Congruences, théorèmes de Fermat et d'Euler
Solution officielle : Shortlist officielle 2011 (avec solutions), p. 66 (page 67 du PDF)
Énoncé¶
Let \(n \geq 1\) be an odd integer. Determine all functions \(f\) from the set of integers to itself such that for all integers \(x\) and \(y\) the difference \(f(x) - f(y)\) divides \(x^n - y^n\).
Indices : les idées clés
- Normalisation : on peut supposer \(f(0) = 0\) ; alors \(f(p) \mid p^n\) pour tout premier \(p\), donc \(f(p) = \varepsilon p^d\) pour une infinité de premiers, avec \(\varepsilon\) et \(d\) fixés.
- Congruence modulo \(p^d - f(x)\) : en écrivant \(n = md + r\), on a \(p^n - x^n \equiv p^r f(x)^m - x^n\).
- Taille : pour \(p\) grand, \(\lvert p^r f(x)^m - x^n \rvert < p^d - f(x)\), donc \(p^r f(x)^m = x^n\), d'où \(r = 0\) et \(f(x) = x^d\) (\(m\) impair).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2011 (une solution et une remarque).
Solution¶
Réponse : toutes les fonctions de la forme \(f(x) = \varepsilon x^d + c\), où \(\varepsilon \in \{1, -1\}\), l'entier \(d\) est un diviseur positif de \(n\), et \(c\) est un entier.
Il est évident que toutes les fonctions de la réponse vérifient la condition du problème. Montrons qu'il n'y en a pas d'autres.
Soit \(f\) une fonction vérifiant la condition. Pour tout entier \(c\), la fonction \(g\) définie par \(g(x) = f(x) + c\) vérifie aussi la condition. Quitte à retrancher \(f(0)\) à \(f(x)\), on peut donc supposer \(f(0) = 0\).
Pour tout nombre premier \(p\), la condition avec \((x, y) = (p, 0)\) dit que \(f(p)\) divise \(p^n\). Comme l'ensemble des nombres premiers est infini, il existe des entiers \(d\) et \(\varepsilon\) avec \(0 \leq d \leq n\) et \(\varepsilon \in \{1, -1\}\) tels que \(f(p) = \varepsilon p^d\) pour une infinité de nombres premiers \(p\). Notons \(\mathcal{P}\) l'ensemble de ces nombres premiers. Comme une fonction \(g\) vérifie la condition si et seulement si \(-g\) la vérifie, on peut supposer \(\varepsilon = 1\).
Le cas \(d = 0\) est facilement exclu, car \(0\) ne divise aucun entier non nul. Supposons \(d \geq 1\) et écrivons \(n = md + r\), où \(m\) et \(r\) sont des entiers avec \(m \geq 1\) et \(0 \leq r \leq d - 1\). Soit \(x\) un entier quelconque. Pour tout nombre premier \(p \in \mathcal{P}\), la différence \(f(p) - f(x)\) divise \(p^n - x^n\). En utilisant l'égalité \(f(p) = p^d\), on obtient
Comme \(r < d\), pour des nombres premiers \(p \in \mathcal{P}\) assez grands, on a
Donc \(p^r f(x)^m - x^n\) doit être nul. Cela implique \(r = 0\) (il suffit de prendre \(x = 1\) : le membre de gauche dépendrait sinon de \(p\)) et \(x^n = (x^d)^m = f(x)^m\). Comme \(m\) est impair, on obtient \(f(x) = x^d\). \(\blacksquare\)
Remarque¶
Si \(n\) est un entier pair strictement positif, alors les fonctions \(f\) de la forme
où \(d\) est un diviseur positif de \(\frac{n}{2}\) et \(c\) un entier, vérifient aussi la condition du problème. Avec les fonctions de la réponse, ce sont toutes les fonctions qui vérifient la condition quand \(n\) est pair.