Le théorème de Smith [Python]

Les questions utilisant Python commencent par [P]. Une fonction arithmétique multiplicative est ici une application {f:\mathbb N^*\to\mathbb C}, avec {f(1)=1}, telle que {f(mn)=f(m)f(n)} lorsque {m\wedge n=1}. Le symbole {m\wedge n} désigne le pgcd. On veut calculer les déterminants des matrices de terme général {f(i\wedge j)}.

1. [P] Écrire une fonction gcd(a,b) renvoyant le pgcd de deux entiers strictement positifs. On peut aussi importer gcd depuis math.

On définit {\varphi(n)=\#\{x\in\{1,\ldots,n\}:x\wedge n=1\}}, {\tau(n)=\#\{d\ge1:d\mid n\}} et {\sigma(n)=\sum\limits_{d\mid n}d}.
On pose {\mu(n)=0} si {n} est divisible par le carré d’un entier strictement supérieur à {1}, et {\mu(n)=(-1)^k} sinon, où {k} est le nombre de diviseurs premiers de {n}.

2. Montrer que {\varphi,\tau,\sigma,\mu} sont multiplicatives.

3. [P] Écrire phi(n), tau(n) et sigma(n).

Sur l’ensemble {\mathcal M} des fonctions multiplicatives, on définit
{(f\star g)(n)=\sum_{d\mid n}f(d)g(n/d)}On admet que {(\mathcal M,\star)} est un groupe commutatif.

4. Montrer que {e(1)=1}, {e(n)=0} pour {n\ge2}, définit le neutre. Montrer que l’inverse de {\mu} est la fonction constante {\mathbf1(n)=1}.

5. Soit {H\in\mathcal M} et {h(n)=\sum\limits_{d\mid n}H(d)}. Montrer que {h} est multiplicative et que
{(E)\quad H(n)=\sum_{d\mid n}\mu(d)h(n/d)}Déterminer {h} pour {H=\varphi} et écrire l’égalité correspondante.

Soit {M=(f(i\wedge j))_{1\le i,j\le n}}, {F=\mu\star f}, {D=\operatorname{diag}(F(1),\ldots,F(n))} et {A=(a_{i,j})}, où {a_{i,j}=1} si {i\mid j} et {0} sinon.

6. (a) Calculer {A^tDA} et en déduire {\det M}.

6. (b) En déduire {\det M} pour {f(n)=n}, puis pour {f=\tau}, {f=\sigma} et {f=\mu}.

Indications Python

math.gcd calcule le pgcd ; np.array forme une matrice et np.linalg.det son déterminant numérique.