À propos du pgcd

Boécien
Modifié (December 2021) 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

  • Boécien
    Modifié (November 2021)
    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)$.
  • Boécien
    Modifié (December 2021)
    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é.


  • Boécien
    Modifié (December 2021)
    Au sujet de la question 7) j'offre une boite de chocolats artisanaux à qui arrive à répondre à cette question dès lors que la preuve proposée est validée B).  Je la repose avec moins de notations, juste le pcgd. Je pense que c'est un problème d'apparence difficile mais qui doit être facile à résoudre pour les cracks de ce forum !
    Soit $\left(u_{n}\right)_{n\in\mathbb{N}}$ la suite définie par $u_{0}=0$, $u_{1}=1$ et pour $n\geq2$ par $$u_{n}=\frac{1}{2n}\sum_{k=1}^{n-1}u_{k}\left(\gcd(n,k+1)-\gcd(n,k)\right)$$ Il faut montrer que $u_{n}=O\left(n^{-1}\right)$ et que c'est optimal. La suggestion que l'on m'a faite de regarder du côté des équations aux différences finies du type Volterra ne m'a pas (encore) aidée.
Connectez-vous ou Inscrivez-vous pour répondre.