À propos du pgcd — Les-maths.net The most powerful custom community solution in the world

À propos du pgcd

Modifié (21 Nov) dans Arithmétique
Bonsoir
Un ami m'a suggéré d'étudier les nombres suivants.
$$T(y,x)=\gcd(y,x)-\gcd(y,x+1),$$ à propos desquels il a une liste de questions plus ou moins faciles. 
Dans la catégorie facile. Montrer que pour $n\geq3$ :
1) $T(n,n)=-T(n,n-1)=n-1$ et $T(n-1,n)=\frac{(-1)^{n}-1}{2}$
2) $\sum_{k=1}^{n}T(n,k)=0$
3) $\sum_{d\mid n}T(d,n)=\sigma(n)-\tau(n)$
4) $\sum_{k=1}^{n}T(n,k)\left\lfloor \frac{n}{k}\right\rfloor =0\Leftrightarrow\sum_{k=1}^{n}\frac{T(n,k)}{k}=-\frac{1}{n}\Leftrightarrow n$ est premier.
Dans la catégorie un peu moins facile.
5) Pour $n\geq5$ montrer que $\sum_{k=1}^{n}T(k,n)=0$ ssi $\frac{\sigma(n)}{2}$ est premier.
6) Pour un entier $p\geq1$ fixé on définit la suite $\left(a_{p}(n)\right)_{n\geq p}$ par $a_{p}(n)=T(n-p,n)+p$. Montrer que cette suite est périodique de période de longueur $p(p+1)$ et que $0\leq a_{p}(n)\leq2p-1$.
Puis quelque chose que je ne sais pas du tout comment aborder.
7) Soit $\lambda>1$ et soit la suite définie par $u_{1}=1$ puis pour $n\geq2$ par la formule de récurrence
$$u_{n}=-\frac{1}{\lambda n}\sum_{k=1}^{n-1}u_{k}T(n,k)$$ Montrer que $u_{n}\ll n^{-1}$.
J'ai montré 1), 2),3) 4) et je pense pouvoir arriver au bout de 5) et 6). Mais je suis surtout intrigué par cette question 7) qui ne fait visiblement pas appel aux résultats précédents. Si quelqu'un a une idée sur cette dernière...

Réponses

  • Modifié (27 Nov)
    Pour la question 7) que je n'arrive toujours pas à résoudre j'émets une conjecture qui la place dans un cadre plus vaste après quelques essais numériques avec mon tout nouveau logiciel de calcul. Peut-être que cela peut permettre de trouver quelque chose. J'ai lu quelque part que généraliser un problème pouvait aider à sa résolution ;)
    Soit $\varphi(n)$ une suite strictement positive qui décroit vers zéro et telle que $n\varphi(n)<1$ sans tendre vers zéro ou un.  Soit la suite définie par $u_{1}=1$ puis pour $n\geq2$ par la formule de récurrence
    $$u_{n}=-\varphi(n)\sum_{k=1}^{n-1}u_{k}T(n,k).$$
    Alors je conjecture que $u_{n}=O\left(\varphi(n)n^\epsilon\right)$.
  • Modifié (28 Nov)
    Pour illustrer ma conjecture ci-dessus (avec quelques modifications par rapport à mes hypothèses initiales) prenons par exemple $\varphi(n)=\frac{\sin(n)^{2}}{n}$ alors voici le graphique de $\frac{u_{n}}{\varphi(n)}$ pour $n\leq100000$ comparé à $\log n$.qui me parait être en $O\left(\log n\right)$ au dessus de zéro et borné en dessous et donc bien en $O(n^\epsilon)$.




  • Et avec $\varphi(n)=\frac{1}{2n}$ qui est à l'origine le problème proposé on voit que $nu_{n}$ est clairement borné.


Connectez-vous ou Inscrivez-vous pour répondre.
Success message!