À propos du pgcd
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...
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
$$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)$.