Fonctions à caractériser — Les-mathematiques.net The most powerful custom community solution in the world

Fonctions à caractériser

$\newcommand{\pgcd}{\operatorname{pgcd}}$Le problème est de caractériser les fonctions $f:\mathbb{N^{\star}\rightarrow\mathbb{N^{\star}}}$ telles que pour tout couple d'entier non nuls $(u,v)$ on a $\pgcd\big(f(u),f(v)\big)=f\big(\pgcd(u,v)\big)$.
Je vois que $f(n)=n^m$ où $m$ est entier marche ainsi que toute fonction $f$ complètement multiplicative. Mais ce ne sont pas les seules car il me semble qu'une condition suffisante est $u\mid v\Longrightarrow f(u)\mid f(v)$. Ainsi $f(n)=F(n)$ où $F(n)$ est le nième nombre de Fibonacci marche aussi. En voyez vous d'autres ?

Réponses

  • Bonjour,

    Il existe une infinité de solutions.

    La fonction constante (non nulle).

    Si $f$ et $g$ sont solutions, alors $f+g$ est solution. On écrit que c'est faux dans plusieurs messages ci-dessous : ça doit être faux.

    Soit $f$ une fonction multiplicative, alors nécessairement $f(1)=1$, et alors il suffit d’échanger deux premiers comme dans $f(2)=3$ et $f(3)=2$ avec pour les autres premiers $f(p)=p.$

    Les fonctions $f(n)=c n^m$ sont solutions…
  • Salut.
    @Beocien, d'après ce que tu dis la fonction $f(n) = F(n)$ ne marche que si $u\mid v$. Donc on ne peut pas de là dire que ceux sont des fonctions qui marchent, si je ne me trompe.
  • je propose après lecture du post de @YvesM, les fonctions :

    $f_{(c, p, q, \delta)} (u) = c\prod_{i = 1}^{n}p_{i}^{\delta (\alpha_{i})}$ lorsque $u = \prod_{i=1}^{n}p_{i}^{\alpha_{i}}$ et où $c$ est une constante non nul, $p$ et $q$ deux nombres premiers que $f$ permute et $\delta$ une fonction strictement croissante..

    Cordialement.
  • La fonction f(n)=F(n), nième nombre de Fibonacci marche car elle a cette propriété de divisibilité.
    Pour YvesM j'ai vu qu'il y avait des solutions comme les fonctions complètements multiplicatives et de la forme Cn^a.
    En revanche ce que tu dis h= f+g est solution si f et g le sont ne semble pas vrai. Par exemple f(n)=F(n) le nième Fibonacci et g(n)=n^2 je trouve gcd(h(18),h(6))=4 et h(gcd(18,6))=44.
  • Boécien a écrit:
    La fonction $f(n)=F(n)$, $n$-ième nombre de Fibonacci marche car elle a cette propriété de divisibilité.

    Mais elle ne marche que pour $u\mid v$, et pas pour $u$ et $v$ quelconques, si j'ai bien compris.

    Je donne une forme plus générale des fonctions que je propose...
    $f_{(c, (q_1, q'_1)\cdots (q_m, q'_m), \delta)} (u) = c\prod_{i = 1}^{n}p_{i}^{\delta (\alpha_{i})}$ lorsque $u = \prod_{i=1}^{n}p_{i}^{\alpha_{i}}$ et où $c$ est une constante non nul, les $(q_j, q'_j)_{1\leq j\leq m}$ des pairs de nombres premiers que $f$ permute et $\delta$ une fonction strictement croissante
    ... et je me demande s'il y a des fonctions convenables qui n'entrent pas dans cette catégorie.

    Toutefois ce que dit @YvesM sur la sommation n'est pas vrai. Il suffit de prendre les deux formes de fonction qu'il propose.
    Soient $u = 2\times 11\times 7$ et $v = 3\times 11 \times 5$, $f(x) = 2x$ et $g(x) = f_{(1, (2, 3), id)}(x)$. Et soit $h = f + g$.
    On a $h(\pgcd(u, v) = h(11) = 33$ et $\pgcd(h(u), h(v)) = \pgcd(49\times 11, 40\times 11) = 11$. ($id$ est la fonction identité).

    Cordialement.
  • Non elle marche pour tout u,v
  • On cherche les endomorphismes du monoïde $(\mathbb N^*, \wedge)$, où $m\wedge n:= \pgcd(m,n)$.
    Soit $\mathcal P$ l'ensemble des nombres premiers positifs.
    Pour deux séquences d'entiers presque tous nuls $(\alpha_p)_{p\in \mathcal P}$ et $(\beta_p)_{p\in \mathcal P}$, on a :
    $$
    (\prod_{p\in \mathcal P} p^{\alpha_p}) \wedge (\prod_{p\in \mathcal P} p^{\beta_p}) = \prod_{p\in \mathcal P} p^{min(\alpha_p, \beta_p)}.

    $$ Autrement dit, en tant que monoïde, $(\mathbb N^*, \wedge)$ est isomorphe au produit direct d'une infinité de copies, indexées par $\mathcal P$, du monoïde $(\mathbb N, \min)$ ($\min$=loi du minimum) ; plus précisément à un sous-monoïde de ce produit infini, correspondant aux suites d'entiers presque tous nuls (par opposition aux suites quelconques d'entiers).
    Les endomorphismes de $(\mathbb N, \min)$ sont les fonctions croissantes (assez direct à vérifier).

    Admettant que les endomorphismes de $A\times A$ sont tous de la forme $\sigma\circ (f_1\times f_2)$, où $f_1, f_2$ sont des endomorphismes du monoïde $A$, et $\sigma$ est une permutation de $\{1,2\}$, et ainsi de suite, fixer un endomorphisme $\varphi$ de $(\mathbb N^*, \wedge)$ revient à fixer :
    • pour chaque $p\in \mathcal P$, une fonction croissante $f_p: \mathbb N\to \mathbb N$,
    • une permutation $\sigma$ de $\mathcal P$.
    On a alors $\varphi(\prod_{p\in \mathcal P} p^{\alpha_p}) = \prod_{p\in \mathcal P} \sigma(p)^{f_p(\alpha_p)}$.
    Après je bloque.
  • J'espère que ce que j'ai écrit ci-dessus n'est pas incorrect, mais j'ai eu un gros doute car j'ai cru que ma description n'incluait pas les fonctions du type $\varphi(n)=cn$, $c\in\mathbb N^*$ étant fixé. En fait, pour $c=\prod_{p\in \mathcal P}p^{\alpha_p}$, ça correspond à $f_p(n) = n+\alpha_p$ (qui est bien croissante), et $\sigma = \mathrm{id}$.

    @AD: désolé pour les tremas !!
    Après je bloque.
  • Bonsoir,

    Soit $u$ une suite $\N^* \to \N^*.$
    $\bullet\quad $Il existe une unique suite $v: \N^* \to \Q^*$ telle que $\forall n \in \N^* , \quad u_n =\displaystyle \prod _{d\mid n} v_d. \quad$ ($v$ est définie par $v_n= \displaystyle \prod _{d\mid n} u_d^{\mu (n/d)}$.)
    $\bullet \quad $Soit $w: \N^* \to \N^*$ la suite définie par: $\quad w_1 = u_1,\:\: \forall n>1: \:\: w_n = \dfrac {\mathrm{PPCM}(u_1,u_2,\dots u_{n})}{\mathrm{PPCM}(u_1,u_2,\dots u_{n-1})}$

    $\bullet \quad$On dira que "$u$ possède la propriété $\:\mathcal P\:$" lorsque $\: \forall m,n \in \N^*, \quad u_m \wedge u_n = u_{m\wedge n}.$

    Assez délicate à établir, la proposition suivante est une caractérisation des suites qui satisfont à $\mathcal P$.
    $$ \boxed{u \:\text {possède la propriété}\: \mathcal P \iff v=w.}$$
    Voici d'autre part, à titre d'exercices, des exemples de suites $u$ dont il me paraît intéressant de démontrer qu'elles possèdent la propriété $ \mathcal P.$

    $1)\quad u_n = a^n -b^n, \qquad( a,b \in \N^*, \:\:b<a,\:\: a\wedge b =1).$
    $2)\quad u_1 =1, u_2 =a, \quad \forall n \in \N^*, \:\: u_{n+2} = au_{n+1} +b u_{n}\qquad( a,b \in \N^*, \:\: a\wedge b = 1).$
    $3)\quad u_n= \sup \left\{ k \in \N^* \mid \dfrac{ (1+ \sqrt 2 )^n -1}k \in \Z[\sqrt 2 ]\right \}.$
    $3\text{bis})\quad u_n = \sup \left\{k \in \N^* \mid \dfrac {\theta ^n-1}k \in \mathbb A \right\}\qquad ( \mathbb A:\: \text{anneau des entiers algébriques},\:\:\theta \in \mathbb A).$


    Remarque:
    @Yves Martin: il est faux de dire que si $a$ et $b$ possèdent la propriété $\mathcal P$, alors il en est de même de la suite $a+b$
    @i.zitoussi: il me semble aussi inexact d'affirmer que les endomorphismes de $A\times A $ sont tous de la forme que tu as indiquée (considérer par exemple $A= (\N,+), \:\: f: (x,y) \mapsto (x+y,0)$ qui est un endomorphisme de $A\times A $) et que toutes les suites possédant la propriété $ \mathcal P$ seront ainsi obtenues par ton procédé.
  • LOU16, merci de me corriger.
    J'ai bien fait de commencer mon paragraphe par "En admettant que...", car je n'en étais en fait pas sûr du tout.
    C'est complètement faux.
    Après je bloque.
  • Merci LOU16. Je suppose donc qu'on ne peut pas faire plus simple que cette propriété P pour caractériser ces fonctions. Le "assez délicate" veut dire que c'est très long à démontrer?
    Dans l'exemple 3) si je comprends bien u(n)=a(n)sqrt(2)+b(n) pour des suites d'entiers a(n) et b(n) et pgcd(u(i),u(j))=sqrt(2)pgcd(a(i),a(j))+pgcd(b(i),b(j))? Ces suites semblent liées au développement en fraction continue de sqrt(2) non?
  • Bonsoir Beotien Boecien

    $1)$"Délicate"
    Je disposais d'un document qui énonçait sans démonstration cette proposition.
    J'en ai donc cherché une justification, que je n'ai atteinte qu'au terme d'un cheminement passablement laborieux.
    La mise au propre de la rédaction de cette preuve conduit à un texte qui n'est finalement pas si long, mais dont la lecture demande un peu de concentration.
    C'est donc seulement une appréciation personnelle que j'ai formulée et bien entendu, il se peut qu' "il y ait plus simple".

    $2)$ Exemple $3$
    $ (1+\sqrt 2 )^n = a_n + b_n \sqrt 2,\:\: a_n, b_n \in \N, \qquad u_n = (a_n-1) \wedge b_n, \quad\dfrac{ a_n }{b_n}$ est en effet une réduite de $\sqrt 2,\:$ (mais ce fait est dénué d'intérêt dans le problème qui nous occupe: j'aurais pu proposer $1492+1789\sqrt 2, \:$ à la place de $1+\sqrt 2 .$)

    Pour $n\geqslant 1,\: $ les valeurs successives prises par $u_n$ sont: $\:1,\:2,\:1,\:4,\:1,\:14,\:1, \:24,\:1,\dots $
  • Merci LOU16 pour ces précisions. Je vais essayer de le montrer par moi même. Sinon c'est Boécien, disciple de Boèce le "dernier romain", et non pas béotien :-) même si j'en suis un j'en conviens.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!