Fonctions multiplicatives

Notations

Dans ce problème, les entiers sont les éléments de {\mathbb N^*}. On note {m\wedge n} leur PGCD et {m\vee n} leur PPCM. Une fonction arithmétique est une application de {\mathbb N^*} dans {\mathbb C}. Elle est multiplicative si {f(1)=1} et si {m\wedge n=1} entraîne {f(mn)=f(m)f(n)}.
On note {\mathcal P} l’ensemble des nombres premiers, {D_n} l’ensemble des diviseurs positifs de {n} et {\mathcal P_n=\mathcal P\cap D_n}. Pour {p\in\mathcal P}, {v_p(n)} est l’exposant de {p} dans {n}, soit {\max\{k\in\mathbb N:p^k\mid n\}}. Par exemple {56=2^3\cdot7}.

I. Généralités

I. 1. (a) Pour deux entiers {m,n}, justifier {D_m\cap D_n=D_{m\wedge n}} et {\mathcal P_m\cap\mathcal P_n=\mathcal P_{m\wedge n}}.

I. 1. (b) Prouver {\mathcal P_m\cup\mathcal P_n=\mathcal P_{m\vee n}}.

I. 1. (c) Que dire de {\mathcal P_m,\mathcal P_n} lorsque {m,n} sont premiers entre eux ?

Soient {a,b,c} tels que {a\wedge b=1}. On veut établir, par deux méthodes,
{a\wedge(bc)=a\wedge c,\quad(ab)\wedge c=(a\wedge c)(b\wedge c)}

I. 2. (a) Poser {d=a\wedge c} et considérer {a',c'} tels que {a=da'}, {c=dc'}.

I. 2. (b) Utiliser les valuations {v_p(a),v_p(b),v_p(c)} pour chaque {p\in\mathcal P}.

I. 3. Pour {m\wedge n=1}, définir {\psi:D_m\times D_n\to D_{mn}} par {\psi(d,\delta)=d\delta}, et {\xi:D_{mn}\to D_m\times D_n} par {\xi(q)=(m\wedge q,n\wedge q)}. Montrer que ce sont deux bijections réciproques.

I. 4. (a) Si {f} est multiplicative et les {m_1,\ldots,m_q} sont premiers entre eux deux à deux, montrer que {f(\prod\limits_{j=1}^qm_j)=\prod\limits_{j=1}^qf(m_j)}.

I. 4. (b) Montrer que {f} est caractérisée par les valeurs {f(p^k)}, pour {p\in\mathcal P}, {k\geqslant1}.

II. Exemples de fonctions multiplicatives

On pose {\omega(n)=\operatorname{card}\mathcal P_n}, nombre de diviseurs premiers distincts de {n}.

II. 1. (a) Pour {z\in\mathbb C^*}, montrer que {f(n)=z^{\omega(n)}} est multiplicative.

II. 1. (b) Que valent les {f(p^k)} ?

On pose {\tau(n)=\operatorname{card}D_n}, nombre de diviseurs de {n}.

II. 2. (a) Montrer que {\tau} est multiplicative en utilisant I.3.

II. 2. (b) Que valent les {\tau(p^k)} ?

II. 2. (c) En déduire {\tau(n)=\prod\limits_{p\in\mathcal P_n}(v_p(n)+1)} pour {n\geqslant2}.

La fonction de Möbius est définie par {\mu(n)=0} si un carré de nombre premier divise {n}, et {\mu(n)=(-1)^{\omega(n)}} sinon.

II. 3. (a) Montrer que {\mu} est multiplicative.

II. 3. (b) Que valent les {\mu(p^k)} ?

III. Produit de Dirichlet

On note {\mathcal A} l’ensemble des fonctions arithmétiques, {\mathcal M} celui des fonctions multiplicatives, {\mathrm{Id}(n)=n}, {\mathbf1(n)=1}, et {e(1)=1}, {e(n)=0} pour {n\geqslant2}. Ces trois fonctions sont multiplicatives.
Le produit de Dirichlet est défini par
{(f\star g)(n)=\sum_{d\mid n}f(d)g(n/d)=\sum_{ab=n}f(a)g(b)}Les sommes portent sur les diviseurs positifs, ou sur les couples d’entiers positifs de produit {n}.

III. 1. (a) Montrer que {\mathcal A} est un groupe commutatif pour l’addition des fonctions.

III. 1. (b) Montrer que {\star} est commutatif.

III. 1. (c) Vérifier que {e} est neutre.

III. 1. (d) Montrer l’associativité du produit de Dirichlet et conclure que {(\mathcal A,+,\star)} est un anneau commutatif.

III. 2. (a) Montrer que {f} est inversible pour {\star} si et seulement si {f(1)\ne0}.

III. 2. (b) Montrer que cet anneau est intègre.

III. 3. (a) En utilisant I.3, montrer que {\mathcal M} est stable pour {\star}.

III. 3. (b) Montrer que {\mathcal M} est un sous-groupe du groupe des unités de {\mathcal A}.

IV. La formule d’inversion de Möbius

IV. 1. Pour {f,g,h\in\mathcal M}, montrer que {h=f\star g} équivaut à
{h(p^k)=\sum_{j=0}^kf(p^j)g(p^{k-j})\quad(p\in\mathcal P,\ k\geqslant1)}

IV. 2. Montrer que {\mu} et {\mathbf1} sont inverses dans {(\mathcal M,\star)}.

IV. 3. Soit {f\in\mathcal A} et {F(n)=\sum\limits_{d\mid n}f(d)}. Montrer la formule d’inversion {f(n)=\sum\limits_{d\mid n}\mu(d)F(n/d)}.

IV. 4. En déduire la valeur de {\sum\limits_{d\mid n}\mu(d)\tau(n/d)}.

V. La somme des diviseurs

On définit {\sigma(n)=\sum\limits_{d\mid n}d}.

V. 1. (a) Montrer que {\sigma} est multiplicative en utilisant une question de la partie I.

V. 1. (b) Montrer sa multiplicativité en utilisant les résultats relatifs au produit de Dirichlet.

V. 1. (c) Montrer que {\sigma(n)/n=\sum\limits_{d\mid n}1/d}.

V. 2. (a) Calculer {\sigma(p^k)}.

V. 2. (b) En déduire {\sigma(n)=\prod\limits_{p\in\mathcal P_n}(p^{v_p(n)+1}-1)/(p-1)} pour {n\geqslant2}.

V. 2. (c) Calculer {\sigma(10!)}.

Pour {m\in\mathbb Z}, on pose {\sigma_m(n)=\sum\limits_{d\mid n}d^m}.

V. 3. (a) Exprimer {\sigma_m(n)} en fonction de la factorisation de {n}.

V. 3. (b) Calculer la somme des carrés des diviseurs de {2002}.

Un entier est parfait si {\sigma(n)=2n}, autrement dit s’il est la somme de ses diviseurs stricts. Par exemple {28=1+2+4+7+14}.

V. 4. (a) Montrer que si {2^k-1} est premier, alors {n=2^{k-1}(2^k-1)} est parfait et pair.

V. 4. (b) Réciproquement, montrer que tout entier parfait pair est de cette forme, avec {2^k-1} premier. Écrire {n=2^mq}, {m\geqslant1}, {q} impair ; montrer que {q=(2^{m+1}-1)r} et {\sigma(q)=q+r}.

VI. L’indicateur d’Euler

On note {E_n=\{k\in\{1,\ldots,n\}:k\wedge n=1\}} et {\varphi(n)=\operatorname{card}E_n}.

VI. 1. (a) Pour {f:\{1,\ldots,n\}\to D_n}, {f(k)=n\wedge k}, montrer que chaque {d\mid n} possède exactement {\varphi(n/d)} antécédents.

VI. 1. (b) En déduire {\sum\limits_{d\mid n}\varphi(d)=n}.

VI. 1. (c) Montrer que {\varphi(n)=\sum\limits_{d\mid n}\mu(d)n/d} et que {\varphi} est multiplicative.

VI. 2. (a) Calculer {\varphi(p^k)} par deux démonstrations distinctes.

VI. 2. (b) En déduire {\varphi(n)=n\prod\limits_{p\in\mathcal P_n}(1-1/p)}. Calculer {\varphi(10!)}.

VII. Quelques formules asymptotiques

VII. 1. (a) Montrer que {\sum\limits_{k=1}^n\tau(k)=\sum\limits_{d=1}^n[n/d]}, en intervertissant les sommes dans {\sum\limits_{k=1}^n\sum\limits_{d\mid k}1}.

VII. 1. (b) Avec {S_n=\sum\limits_{d=1}^n1/d}, montrer que {S_n/\ln n\to1}.

VII. 1. (c) En déduire {\bigl(\tau(1)+\cdots+\tau(n)\bigr)/(n\ln n)\to1}.

VII. 2. (a) Montrer que {\sum\limits_{k=1}^n\sigma(k)=\sum\limits_{d=1}^nd[n/d]}.

VII. 2. (b) Justifier les transformations
{\begin{array}{l}\displaystyle\sum_{k=1}^n\sigma(k)=\sum_{d=1}^nd\sum_{k=1}^{[n/d]}1=\sum_{dk\leqslant n}d\\[4pt]\displaystyle\phantom{\sum_{k=1}^n\sigma(k)}=\sum_{k=1}^n\sum_{d=1}^{[n/k]}d=\frac12\sum_{k=1}^n[n/k]([n/k]+1)\end{array}}

VII. 2. (c) Poser {T_n=\sum\limits_{k=1}^n1/k^2}. Montrer que
{\frac12(n^2T_n-nS_n)\leqslant\sum_{k=1}^n\sigma(k)\leqslant\frac12(n^2T_n+nS_n)}

VII. 2. (d) En admettant {T_n\to\pi^2/6}, en déduire {\bigl(\sigma(1)+\cdots+\sigma(n)\bigr)/n^2\to\pi^2/12}.

On pose {U_n=\sum\limits_{k=1}^n\mu(k)/k^2} et l’on admet que {U_n\to6/\pi^2}.

VII. 3. (a) Montrer que
{\begin{array}{l}\displaystyle\sum_{k=1}^n\varphi(k)=\sum_{d=1}^n\mu(d)\sum_{\substack{1\leqslant k\leqslant n\\[4pt]d\mid k}}\frac kd\\[4pt]\displaystyle\phantom{\sum_{k=1}^n\varphi(k)}=\frac12\sum_{d=1}^n\mu(d)[n/d]([n/d]+1)\end{array}}

VII. 3. (b) Montrer que {|n^2U_n/2-\sum\limits_{k=1}^n\varphi(k)|\leqslant3nS_n/2}, puis en déduire {\sum\limits_{k=1}^n\varphi(k)/n^2\to3/\pi^2}.

VII. 3. (c) On choisit indépendamment et uniformément {a,b} dans {\{1,\ldots,n\}}. Quelle est la probabilité {p_n} que {a\wedge b=1} ? Quelle est sa limite ?