Somme de tous les diviseurs d'un entier
dans Arithmétique
Bonjour
Je ne parviens pas à démontrer par récurrence le résultat de la somme de tous les diviseurs de n.
Je n'ai pas encore réussi à faire l'initialisation car j'ai du mal à comprendre comment vérifier la véracité de l'écriture pour r=1 en laissant les P1, alpha1...
Faut-il que je transforme l'écriture avant de faire la récurrence ?
Merci d'avance de votre aide
Cordialement
Je ne parviens pas à démontrer par récurrence le résultat de la somme de tous les diviseurs de n.
Je n'ai pas encore réussi à faire l'initialisation car j'ai du mal à comprendre comment vérifier la véracité de l'écriture pour r=1 en laissant les P1, alpha1...
Faut-il que je transforme l'écriture avant de faire la récurrence ?
Merci d'avance de votre aide
Cordialement
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
-- Schnoebelen, Philippe
Si $n=p^\alpha$, quels sont les diviseurs de $n$ ? Ce sont les $p^k$ pour $0\le k\le \alpha$. Il s'agit de calculer $\sum_{k=0}^\alpha p^k$, ce qui doit être à ta portée.
On n'a pas forcément a1 différent de a2...
Enfin je suis perdue.
Dois-je juste vérifier que cela est égale à \sum_{k=0}^\alpha p^k pour conclure ?
et on veut montrer que c'est toujours vrai pour S(n) mais avec le produit allant de 1 à (r+1) et n au rang (r+1).
J'ai donc commencé par S(n) (au rang r+1) = S(n) * ( Pr+1^[a(r+1) + 1] -1 ) / ( Pr+1 - 1 )
mais ça me semble un peu rapide d'étendre le produit au rang r+1 et terminer, nan ?
Je ne suis pas sûre d'avoir posé correctement ma récurrence...
Pour $r=1$, comme on connaît les diviseurs de $p^\alpha$, on sait que $S(p^\alpha)=\sum_{k=0}^\alpha p^k=\frac{p^{\alpha+1}-1}{p-1}$. Cela prouve la formule pour $r=1$.
Pour $r$ quelconque, un diviseur de $n$ est de la forme $p_1^{k_1}\cdots p_r^{k_r}$ avec $0\le k_i\le \alpha_i$ pour tout $i$. Par conséquent : \begin{align*}
S(n)&=\sum_{k_1=0}^{\alpha_1}\sum_{k_2=0}^{\alpha_2}\cdots\sum_{k_r=0}^{\alpha_r}p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}\\
&=\prod_{i=1}^r\sum_{k_i=0}^{\alpha_i}p_i^{k_i}\\
&=\prod_{i=1}^r\frac{p_i^{\alpha_i+1}-1}{p_i-1}.\end{align*}
Si l'on a traité la question 2 avant, c'est encore plus rapide puisque les $p_i^{\alpha_i}$ sont deux à deux premiers entre eux : $S(n)=\prod_{i=1}^rS(p_i^{k_i})$ (OK : ici, on peut faire une récurrence pour montrer que si un truc est multiplicatif pour $2$ machins, il est multiplicatif pour $r$ machins).
Pour traiter la question 2 dans l'esprit de l'énoncé, il faut sans doute appliquer la formule de la question 1. Pour la faire directement, il suffit de montrer qu'en notant $D(N)$ l'ensemble des diviseurs d'un entier $N$, l'application suivante est bijective lorsque $m$ et $n$ sont premiers entre eux : \[f:D(m)\times D(n)\to D(mn),\quad (d,e)\mapsto de.\] D'abord, elle est bien définie : si $m=dd'$ et $n=ee'$ alors $mn=ded'e'$ donc $de\mid mn$. Ensuite, elle est injective : supposons que $de=d'e'$ ; alors, comme $d\mid m$ et $e'\mid n$, on sait que $d$ et $e'$ sont premiers entre eux (utiliser une égalité de Bézout $um+vn=1$ ou remarquer qu'un diviseur premier de $d$ et $e'$ diviserait aussi $m$ et $n$) ; comme $d$ divise $d'e'$ et que $d\wedge e'=1$, on en déduit que $d$ divise $d'$ ; de même, $d'$ divise $d$ et c'est fini. Enfin, elle est surjective : si $c$ est un diviseur de $mn$, on note $d$ le pgcd de $c$ et $m$ ; on écrit alors $c=de$, avec $e\wedge m=1$ ; des faits que $e\mid c\mid mn$ et que $e\wedge m=1$, on tire que $e\mid n$, si bien que $c=f(d,e)$.
Pour conclure : \[S(mn)=\sum_{c\in D(mn)}c=\sum_{d\in D(m)}\sum_{e\in D(n)}de=S(m)S(n).\]