{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Quelques fonctions arithmétiques\n",
    "\n",
    "Marc Lorenzi\n",
    "\n",
    "21 janvier 2019"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.rcParams['figure.figsize'] = (10, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1 Préliminaires"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 De quoi allons-nous parler ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une fonction arithmétique est une fonction définie sur l'ensemble $\\mathbb N^*$ des entiers naturels non nuls, à valeurs dans $\\mathbb R$ ou $\\mathbb C$. Évidemment, vu comme ça, vous me direz : bon, une fonction arithmétique c'est une suite ?\n",
    "\n",
    "Oui, c'est une suite. Mais nous allons examiner ces fonctions différemment. Certaines fonctions arithmétiques jouent un rôle essentiel en théorie des nombres. Leur étude approfondie permet de démontrer des théorèmes célèbres, comme par exemple le\n",
    "\n",
    "__Théorème des nombres premiers__ : Pour tout entier $n\\ge 1$, soit $\\pi(n)$ le nombre de nombres premiers inférieurs à $n$. Lorsque $n$ tend vers l'infini, on a\n",
    "\n",
    "$$\\pi(n)\\sim\\frac n {\\ln n}$$\n",
    "\n",
    "Nous allons nous concentrer dans ce qui suit sur quelques fonctions arithmétiques. Nous allons également définir une opération sur les fonctions arithmétiques, le __produit de Dirichlet__, qui permet d'obtenir des relations \"magiques\" entre les différentes fonctions que nous introduirons. \n",
    "\n",
    "Avant tout cela, il nous sera nécessaire de pouvoir factoriser des entiers, recherchercher tous leurs diviseurs, calculer des valuations $p$-adiques. Nous allons mettre en place quelques fonctions, inefficaces pour de grands entiers mais suffisantes pour nos petits besoins."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__NOTE__ : Le sujet des fonctions arithmétiques est immense. Il est l'un des fondements de la __théorie analytique des nombres__. Chacune des fonctions dont nous allons parler mériterait un notebook à elle seule. J'ai donc fait des choix très arbitraires. Concernant les aspects mathématiques, certaines propriétés seront montrées. D'autres seront admises, soit pour des raisons de longueur, soit à cause de leur difficulté."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 Plus petit diviseur d'un entier"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $n\\ge 2$. Supposons que $n$ est composé. Il existe donc $a,b\\in[2,n[$ tels que $n=ab$. Supposons que $a^2>n$. On a alors $b^2=\\left(\\frac n a\\right)^2=\\frac {n^2} {a^2}<\\frac{n^2} n = n$. Dit autrement, $a^2\\le n$ ou $b^2<n$. Ainsi, $n$ a un diviseur inférieur ou égal à $\\sqrt n$. \n",
    "\n",
    "Soit $p$ le plus petit diviseur de $n$ différent de 1 et $n$. D'après la remarque précédente, $p^2\\le n$. La fonction `plus_petit_diviseur` ci-dessous exploite ce résultat. Elle effectue une boucle `while`. Si un tel diviseur n'est pas trouvé, c'est que $n$ est premier et la fonction renvoie $n$. \n",
    "La complexité de `plus_petit_diviseur` est en $O(\\sqrt n)$, en nombre d'opérations sur des entiers. Inutile donc d'en attendre des miracles mais elle suffira pour des entiers de taille raisonnable, disons inférieurs à un milliard. \n",
    "\n",
    "__Exercice__ : Soit $n\\ge 2$. Montrer que le plus petit diviseur de $n$ différent de 1 est premier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plus_petit_diviseur(n):\n",
    "    p = 2\n",
    "    while p * p <= n and n % p != 0: p += 1\n",
    "    if p * p > n: return n\n",
    "    else: return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plus_petit_diviseur(12345678910111213)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il est maintenant évident d'écrire une fonction `est_premier`. Cette fonction a aussi une complexité en $O(\\sqrt n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_premier(n):\n",
    "    if n <= 1: return False\n",
    "    else: return plus_petit_diviseur(n) == n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print([n for n in range(1000) if est_premier(n)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3 Factorisation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Définition__ : Soit $n\\ge 1$. Soit $p$ un nombre premier. La valuation $p$-adique de $n$, $\\nu_p(n)$, est le plus grand entier naturel $a$ tel que $p^a$ divise $n$.\n",
    "\n",
    "La fonction `valuation`prend deux entiers $n$ et $p$ en paramètres et renvoie $\\nu_p(n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def valuation(n, p):\n",
    "    a = 0\n",
    "    while n % p == 0:\n",
    "        n = n // p\n",
    "        a = a + 1\n",
    "    else: return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(valuation(100000, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `facteurs`, enfin, renvoie une factorisation de $n$ en produit de nombres premiers. Si $n=1$ elle renvoie la liste vide. Si $n\\ge 2$ s'écrit $\\prod_{i=1}^k p_i^{a_i}$ où les $p_i$ sont premiers et distincts, et les $a_i$ sont des entiers non nuls, la fonction renvoie la liste des couples $(p_i,a_i)$ avec les $p_i$ rangés dans l'ordre croissant."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def facteurs(n):\n",
    "    s = []\n",
    "    while n > 1:\n",
    "        p = plus_petit_diviseur(n)\n",
    "        a = valuation(n, p)\n",
    "        s.append((p, a))\n",
    "        n = n // (p ** a)\n",
    "    return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "facteurs(123456789101112132)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "facteurs(2019)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quelle est la complexité $C_n$ de la fonction de factorisation ? Soit $n=\\prod_{i=1}^k p_i^{\\alpha_i}$ la décomposition de $n$ où $p_1<p_2<\\ldots <p_k$ et les $\\alpha_i\\ge 1$.\n",
    "\n",
    "\n",
    "__Proposition__ : $C_n =O(\\sqrt n\\log n)$.\n",
    "\n",
    "__Démonstration__ : Considérons un certain nombre de cas.\n",
    "\n",
    "1. $n$ est premier. La fonction `plus petit_diviseur` renvoie le bon résultat en $O(\\sqrt n)$ opérations.\n",
    "2. $n=p^\\alpha$, où $\\alpha\\ge 2$ est une puissance d'un nombre premier. Le résultat est renvoyé en $O(\\sqrt n + \\alpha)$ opérations. Que dire de $\\alpha$ ? On a $p\\ge 2$ donc $n=p^\\alpha\\ge 2^\\alpha$. Ainsi, $\\alpha\\le \\lg n$. Donc $C_n=O(\\sqrt n)$.\n",
    "3. Il y a au moins deux nombres premiers distincts qui divisent $n$. Combien au plus ? Soit $k$ le nombre de facteurs premiers de $n$. On a $n\\ge\\prod_{i=1}^k p_i\\ge 2^k$ donc $k\\le \\lg n$. Chacun des $p_i$ est trouvé en au plus (majoration très grossière) $\\sqrt n$ opérations, puis l'exposant de $p_i$ dans la décomposition de $n$ est trouvé en au plus $\\lg n$ opérations, par le même raisonnement que celui fait dans le cas 2. Au total, le nombre d'opérations est $O((\\sqrt n +\\lg n)\\lg n)=O(\\sqrt n\\lg n)$ opérations.\n",
    "\n",
    "Ce n'est pas très bon, il faut l'avouer. Remarquons tout de même que si les facteurs premiers de $n$ sont \"petits\" (disons inférieurs à un certain entier $N$, alors $C_n=O(N\\lg n)$ et la factorisation de $n$ sera faite de façon \"instantanée\". Enfin bon, à condition que $n$ soit de taille \"raisonnable\". Évitons les nombres à un million de chiffres :-)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.4 Diviseurs d'un entier"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $n\\ge 2$. Comment obtenir tous les diviseurs de n ?\n",
    "\n",
    "Soit $p$ un diviseur premier de $n$. Soit $a$ la valuation $p$-adique de $n$. Soit $n'=\\frac n {p^a}$. Les diviseurs de $n$ sont :\n",
    "\n",
    "- Les diviseurs de $n'$\n",
    "- $p$ fois les diviseurs de $n'$\n",
    "- $p^2$ fois les diviseurs de $n'$\n",
    "- ...\n",
    "- $p^a$ fois les diviseurs de $n'$\n",
    "\n",
    "Une fonction récursive s'impose. La fonction `diviseurs` fait le travail. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def diviseurs(n):\n",
    "    if n == 1: return [1]\n",
    "    else:\n",
    "        p = plus_petit_diviseur(n)\n",
    "        a = valuation(n, p)\n",
    "        ds = diviseurs(n // p ** a)\n",
    "        ds1 = [p ** k * d for d in ds for k in range(a + 1)]\n",
    "        ds1.sort()\n",
    "    return ds1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quels sont les diviseurs de 100 ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(diviseurs(100))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quels sont les diviseurs de $10!$ ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(diviseurs(3628800))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 Les fonctions d'Euler et de Möbius"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 Fonctions multiplicatives"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Définition__ : Soit $f$ une fonction arithmétique. \n",
    "\n",
    "- On dit que $f$ est __multiplicative__ lorsque pour tous $a,b$ tels que $a\\land b=1$ on a $f(ab)=f(a)f(b)$.\n",
    "- Lorsque la propriété est vraie pour tous $a, b$ sans aucune condition de pgcd, on dit que $f$ est __complètement multiplicative__."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les fonctions arithmétiques que nous allons étudier sont presque toutes multiplicatives. Mais commençons par donner quelques exemples, essentiels pour la suite, de fonctions complètement multiplicatives.\n",
    "\n",
    "__Proposition__ : Les fonctions $\\mathbb 1, \\delta, id, N_\\alpha$ définies ci-dessous sont complètement multiplicatives. \n",
    "- Étant donné $\\alpha\\in\\mathbb R$, pour tout $n\\ge 1$, $N_\\alpha(n)=n^\\alpha$.\n",
    "- Pour tout $n\\ge 1$, $\\mathbb 1(n)=N_0(n)=1$.\n",
    "- Pour tout $n\\ge 1$, $id(n)=N_1(n)=n$.\n",
    "- $\\delta(1)=1$ et pour tout $n\\ge 2$, $\\delta(n)=0$.\n",
    "\n",
    "__Preuve__ : Facile. Notez les définitions de ces fonctions sur un bout de papier parce qu'elles réapparaîtront de temps en temps, sans prévenir. Ne me demandez pas dans une heure : \"C'est qui, $\\mathbb 1$\" :-) ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def un(n): return 1\n",
    "\n",
    "def delta(n):\n",
    "    if n == 1: return 1\n",
    "    else: return 0\n",
    "    \n",
    "def id(n): return n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 La fonction $\\mu$  de Möbius"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Définition__ : On pose $\\mu(1)=1$. Pour tout $n\\ge 2$, on pose $\\mu(n)=(-1)^k$ si $n$ est le produit de $k$ nombres premiers distincts, et $\\mu(n)=0$ sinon."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mu(n):\n",
    "    fs = facteurs(n)\n",
    "    m = 1\n",
    "    for (p, a) in fs:\n",
    "        if a > 1: return 0\n",
    "        else: m = -m\n",
    "    return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[mu(n) for n in range(1, 20)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction $\\mu$ a vraiment l'air de rien, mais elle est __la clé__."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : La fonction $\\mu$ est multiplicative.\n",
    "\n",
    "__Démonstration__ : Soient $m,n\\ge 1$. Supposons $m\\land n=1$. Si $m=1$ ou $n=1$ il est clair que $\\mu(mn)=\\mu(m)\\mu(n)$. Supposons donc $m, n\\ge 2$.\n",
    "\n",
    "- Si $\\mu(m)=0$, il existe un nombre premier $p$ et un entier $a\\ge 2$ tel que $p^a|m$. Mais alors $p^a|mn$, donc $\\mu(mn)=0=\\mu(m)\\mu(n)$. Idem si $\\mu(n)=0$.\n",
    "- Pour terminer, si $m=p_1\\ldots p_k$ et $n=q_1\\ldots q_l$ où les $p_i$, $q_i$ sont premiers et distincts, alors $mn=p_1\\ldots p_kq_1\\ldots q_l$ donc $\\mu(mn)=(-1)^{k+l}=(-1)^k(-1)^l=\\mu(m)\\mu(n)$.\n",
    "\n",
    "__Exercice__ : Où a-t-on utilisé que $m\\land n = 1$ ?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : Soit $n\\ge 2$. On a $\\sum_{d|n} \\mu(d)=0$.\n",
    "\n",
    "__Démonstration__ : Écrivons $n=\\prod_{i=1}^k p_i^{a_i}$ où les $p_i$ sont premiers et distincts et les $a_i\\ge 1$. Les diviseurs de $n$ sont les entiers $d=\\prod_{i=1}^k p_i^{b_i}$ où $0\\le b_i\\le a_i$. Si l'un des $b_i$ est supérieur ou égal à 2, alors $\\mu(d)=0$. Ainsi, $\\sum_{d|n} \\mu(d)=\\sum'_{d|n} \\mu(d)$ où le \"prime\" signifie que l'on somme sur les $d$ qui sont des produits de nombres premiers distincts.\n",
    "\n",
    "Regroupons les termes de cette somme par \"nombre de facteurs\" :\n",
    "\n",
    "$$\\sum_{d|n} \\mu(d)=\\sum_{j=0}^k\\sum_{d|n, (j)}\\mu(d)=\\sum_{j=0}^k(-1)^j\\sum_{d|n, (j)}1$$\n",
    "\n",
    "où le $(j)$ signifie que l'on somme sur les nombre qui ont exactement $j$ facteurs premiers distincts. Combien y en a-t-il ? Il s'agit en fait de choisir $j$ nombres premiers parmi les $k$ nombres $p_1,\\ldots, p_k$. Il y en a donc $\\binom k j$. Ainsi,\n",
    "\n",
    "$$\\sum_{d|n} \\mu(d)=\\sum_{j=0}^k(-1)^j\\binom k j=(1-1)^k=0$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Remarque__ : La fonction arithmétique $n\\mapsto \\sum_{d|n}\\mu(d)$ est donc nulle pour tout $n\\ge 2$. De plus, elle vaut clairement 1 pour $n=1$. Cela ne vous rappelle rien ? Avez-vous noté sur un bout de papier comme je vous l'ai demandé ? C'est la fonction $\\delta$.\n",
    "\n",
    "__Proposition__ : Pour tout $n\\ge 1$, $\\sum_{d|n}\\mu(d)=\\delta(n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dessinons $\\mu$. Comme on va dessiner beaucoup d'autres fonctions, écrivons d'abord une fonction `plot_fun` qui trace la fonction arithmétique $f$ entre les entiers $a$ et $b$, avec des paramètres `opt` et `opt2` pour la fonction `plt.plot`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_fun(f, a, b, *opt, **opt2):\n",
    "    xs = range(a, b + 1)\n",
    "    ys = [f(x) for x in xs]\n",
    "    plt.plot(xs, ys, *opt, **opt2)\n",
    "    plt.grid()\n",
    "    plt.savefig('fig.png')\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_fun(mu, 1, 100, 'ok', markersize=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Oui, bon, bof, c'est plein de 0, de 1 et de $-1$ ... Bientôt, nous ferons des dessins plus intéressants."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3 La fonction indicatrice d'Euler"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Définition__ : Pour tout $n\\ge 1$, $\\varphi(n)$ est le nombre d'entiers compris entre 1 et n (1 et $n$ inclus) et premiers avec $n$. La fonction $\\varphi$ est appelée la __fonction indicatrice d'Euler__."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.3.1 Euler pour les nuls"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La définition nous donne évidemment une (mauvaise) méthode pour calculer $\\varphi(n)$ :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def phi(n):\n",
    "    compte = 0\n",
    "    for k in range(1, n + 1):\n",
    "        if pgcd(n, k) == 1: compte += 1\n",
    "    return compte"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "où `pgcd` est la fonction ci-dessous, qui utilise l'algorithme d'Euclide."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pgcd(a, b):\n",
    "    while b != 0:\n",
    "        a, b = b, a % b\n",
    "    return a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Calculons $\\varphi(n)$ pour les entiers $n$ entre 1 et 20 :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(1, 21):\n",
    "    print('%3d%3d' % (n, phi(n)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notre fonction a une complexité épouvantable, en gros $O(n\\log n)$. Nous avons $n$ calculs de `pgcd` à faire, et pour $1\\le k \\le n$, le calcul de $k\\land n$ se fait en $O(\\log k)$ opérations. Or, $\\sum_{k=1}^n\\log k=O(n\\log n)$. Bref, inacceptable. Si vous n'êtes pas convaincu, évaluez la cellule ci-dessous ... et attendez plusieurs secondes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "phi(5000000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2.3.2 Faisons mieux"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : La fonction $\\varphi$ est multiplicative.\n",
    "\n",
    "__Démonstration__ : Admettons-le pour l'instant. Ce sera évident d'ici la fin du notebook.\n",
    "\n",
    "__Proposition__ : Pour tout nombre premier $p$ et tout entier $\\alpha \\ge 1$, on a \n",
    "\n",
    "$$\\varphi(p^\\alpha) = p^\\alpha-p^{\\alpha-1}$$\n",
    "\n",
    "__Démonstration__ : Quels sont les entiers entre 1 et $p^\\alpha$ qui ne sont pas premiers avec $p^\\alpha$ ? Ce sont les multiples de $p$ : $p,2p,3p,\\ldots,p^\\alpha=p^{\\alpha-1}p$. Il y en a $p^{\\alpha-1}$. D'où le résultat."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous y sommes. Nous voilà en position d'une formule pour calculer $\\varphi(n)$.\n",
    "\n",
    "__Proposition__ : Soit $n\\ge 2$. Posons $n=\\prod_{i=1}^k p_i^{\\alpha_i}$. On a\n",
    "\n",
    "$$\\varphi(n)=\\prod_{i=1}^k \\left(p_i^{\\alpha_i}-p_i^{\\alpha_i-1}\\right)$$\n",
    "\n",
    "__Démonstration__ : Les $p_i^{\\alpha_i}$ sont premiers entre-eux deux à deux et la fonction $\\varphi$ est multiplicative.\n",
    "\n",
    "__Remarque__ : Il existe plusieurs façons de regrouper les facteurs dans l'expression ci-dessus. Par exemple, on trouve fréquemment dans la littérature\n",
    "\n",
    "$$\\varphi(n)=n\\prod_{i=1}^k \\left(1-\\frac 1 {p_i}\\right)$$\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous voici en possession d'un nouvel algorithme pour calculer $\\varphi(n)$.\n",
    "\n",
    "1. Décomposer $n$ en produit de nombres premiers.\n",
    "2. Appliquer la formule ci-dessus."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La complexité de notre nouvelle fonction est $O(\\sqrt n \\log n)$, ce qui est clairement mieux que le $O(n\\log n)$ de notre premier jet. En plus, le $O(\\sqrt n \\log n)$ est très pessimiste pour beaucoup d'entiers $n$. Par exemple, si $n$ n'a que de petits facteurs premiers, le calcul de $\\varphi(n)$ est en $O(N\\log n)$ où $N$ est un majorant des facteurs premiers de $n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def phi(n):\n",
    "    fs = facteurs(n)\n",
    "    m = 1\n",
    "    for (p, a) in fs:\n",
    "        m = m * p ** (a - 1) * (p - 1)\n",
    "    return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(1, 21):\n",
    "    print('%3d%3d' % (n, phi(n)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "phi(5000000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(est_premier(100000007))\n",
    "phi(100000007)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le graphe de $\\varphi$ ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_fun(phi, 1, 1000, 'ok', markersize=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le graphe de la fonction $\\varphi$ est terrible. Mais derrière ce chaos apparent se cachent des propriétés remarquables. Un exemple ? Au lieu de tracer $\\varphi$, traçons la __moyenne__ de $\\varphi$ sur $[1,n]$, c'est à dire la fonction $\\overline\\varphi:n\\mapsto\\frac 1 n \\sum_{k=1}^n\\varphi(k)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_moyennes(f, n, g=None):\n",
    "    s = [f(k) for k in range(1, n + 1)]\n",
    "    for k in range(1, n):\n",
    "        s[k] = s[k] + s[k - 1]\n",
    "    for k in range(1, n):\n",
    "        s[k] = s[k] / k\n",
    "    xs = list(range(1, n + 1))\n",
    "    if g != None:\n",
    "        ys = [g(x) for x in xs]\n",
    "        plt.plot(xs, ys, 'r')\n",
    "    plt.plot(xs, s, 'k')\n",
    "    plt.grid()\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_moyennes(phi, 500)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On dirait une droite ...\n",
    "\n",
    "__Proposition__ : $\\overline\\varphi(n)\\sim \\frac{3}{\\pi^2}n$.\n",
    "\n",
    "__Démonstration__ : La marge de ce notebook est trop étroite pour contenir la démonstration. Plus sérieusement, ce n'est pas _difficile_, c'est juste un peu long."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_moyennes(phi, 500, lambda x:3 * x / math.pi ** 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les courbes noire et rouge sont quasi-superposées."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.4 La valeur moyenne de $\\mu$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une question nous vient soudain à l'esprit : quelle est la valeur moyenne de $\\mu$ ? Faisons une petite expérience."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_moyennes(mu, 1000, lambda x:0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bon, on voit. Étant donné que $\\mu$ prend des valeurs 0, $\\pm 1$ \"un peu n'importe comment\" (selon nous), il ne doit pas être bien difficile de montrer que $\\overline\\mu(n)\\to 0$ lorsque $n$ tend vers l'infini. __Détrompez-vous__ : on vient d'ouvrir la boîte de Pandore.\n",
    "\n",
    "__Proposition__ : $\\overline\\mu(n)\\to 0$ lorsque $n$ tend vers l'infini.\n",
    "\n",
    "__Proposition__ : La proposition précédente est équivalente au théorème des nombres premiers.\n",
    "\n",
    "Considérons les deux propriétés $(P_1)\\ \\overline\\mu(n)\\to 0$ et $(P_2)\\ \\pi(n)\\sim\\frac n{\\ln n}$. Dire que ces propriétés sont équivalentes veut dire qu'elles sont toutes les deux vraies ... ou toutes les deux fausses. Si ce n'était que cela, ce ne serait pas très intéressant. En fait nous avons une équivalence __constructive__ entre $P_1$ et $P_2$ : Si l'on connaît une démonstration de l'une des deux, alors on connaît une démonstration de l'autre. \n",
    "\n",
    "__Fait subjectif : Montrer que $\\overline \\mu\\to 0$ est aussi difficile que démontrer le théorème des nombres premiers .__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3 Une opération sur les fonctions arithmétiques"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notons $\\mathcal A=\\mathbb R^{\\mathbb N^*}$ l'ensemble des fonctions arithmétiques. Nous allons définir sur $\\mathcal A$ une loi de composition interne particulièrement intéresssante.\n",
    "\n",
    "__Exercice__ : Il y a une faute d'orthographe dans la phrase ci-dessus. Trouvez-la."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 Le produit de Dirichlet"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour $f, g\\in\\mathcal A$, on note $f\\star g$ la fonction de $\\mathcal A$ définie pour tout $n\\ge 1$ par\n",
    "\n",
    "$$(f\\star g)(n)=\\sum_{d|n}f(d)g(\\frac n d)$$\n",
    "\n",
    "Ce genre de somme est déjà apparu plus haut : on somme sur tous les diviseurs $d$ de l'entier $n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dirichlet_aux(f, g, n):\n",
    "    ds = diviseurs(n)\n",
    "    s = 0\n",
    "    for d in ds:\n",
    "        s = s + f(d) * g(n // d)\n",
    "    return s\n",
    "\n",
    "def dirichlet(f, g):\n",
    "    return lambda n: dirichlet_aux(f, g, n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Calculons quelques produits pas du tout au hasard ...\n",
    "\n",
    "Commençons par $\\phi * \\mathbb 1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print([dirichlet(phi, un)(n) for n in range(1, 100)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : $\\varphi \\star \\mathbb 1 = id$.\n",
    "\n",
    "__Démonstration__ : Cette propriété exprime que pour tout entier $n\\ge 1$,\n",
    "\n",
    "$$n = \\sum_{d|n}\\varphi(d)$$\n",
    "\n",
    "Écrivons \n",
    "\n",
    "$$n = \\sum_{0<k\\le n} 1 = \\sum_{d|n}\\sum_{0<k\\le n,k\\land n = d}1$$\n",
    "\n",
    "On a $k\\land n = d$ si et seulement si $\\frac k d \\land \\frac n d = 1$. Ainsi, \n",
    "\n",
    "$$\\sum_{0<k\\le n,k\\land n = d}1=\\sum_{0<q\\le n/d,q\\land n/d = 1}1$$\n",
    "\n",
    "où on a posé $q=\\frac k d$. Mais $\\sum_{0<q\\le n/d,q\\land n/d = 1}1=\\varphi(\\frac n d)$. Donc\n",
    "\n",
    "$$n=\\sum_{d|n}\\varphi(\\frac n d)$$\n",
    "\n",
    "Il ne rete plus qu'à poser $d'=\\frac n d$ dans la somme ci-dessus et à remarquer que lorsque $d$ décrit l'ensemble des diviseurs de $n$, $d'$ fait de même."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Autre tentative ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print([dirichlet(mu, id)(n) for n in range(1, 100)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ces nombres ne nous rappellent-ils rien ?\n",
    "\n",
    "__Proposition__ : $\\mu\\star id = \\varphi$.\n",
    "\n",
    "Ceci exprime sous forme ultracompacte, que pour tout $n\\ge 1$, $\\sum_{d|n}\\mu(d)\\frac n d = \\varphi(n)$, ou encore\n",
    "\n",
    "$$\\varphi(n) = n\\sum_{d|n}\\frac{\\mu(d)}d$$\n",
    "\n",
    "Il existe donc un lien profond entre $\\mu$ et $\\varphi$. D'ici la fin du notebook, cette propriété sera une conséquence immédiate de la précédente."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Encore un essai."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print([dirichlet(mu, un)(n) for n in range(1, 100)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : $\\mu \\star \\mathbb 1 = \\delta$.\n",
    "\n",
    "__Démonstration__ : En fait nous avons déjà fait la démonstration. Nous avons vu que pour tout entier $n\\ge 2$, $\\sum_{d|n}\\mu(d)=0$. Dit autrement, $(\\mu\\star \\mathbb 1)(n)=0$. Et comme, bien évidemment, $(\\mu\\star \\mathbb 1)(1)=\\mu(1)\\mathbb 1(1)=1=\\delta(1)$, on a le résultat."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une petite dernière ... Pour tout $n\\ge 1$, nous avons $(id\\star id)(n)=\\sum_{d|n}d\\frac n d=n\\sum_{d|n} 1=n\\sigma_0(n)$ où $\\sigma_0(n)$ est le nombre de diviseurs de $n$ (nous y reviendrons plus loin). Évaluons donc $\\frac{id\\star id}{id}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print([dirichlet(id, id)(n) // id(n) for n in range(1, 100)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous aurons bientôt une formule explicite pour calculer $\\sigma_0(n)$, nous pourrons alors comparer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 Commutativité et associativité du produit de Dirichlet"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : Le produit de Dirichlet est commutatif.\n",
    "\n",
    "__Démonstration__ : Soient $f,g$ deux fonctions arithmétiques. Soit $n\\ge 1$. On a\n",
    "\n",
    "$$(f\\star g)(n)=\\sum_{a|n}f(a)g(\\frac n a)$$\n",
    "\n",
    "Posons $n=ab$. il vient alors\n",
    "\n",
    "$$(f\\star g)(n)=\\sum_{ab=n}f(a)g(b)$$\n",
    "\n",
    "où la somme s'effectue sur tous les couples $(a, b)$ tels que $ab=n$. Sous cette forme, il est clair que $f\\star g=g\\star f$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : Le produit de Dirichlet est associatif.\n",
    "\n",
    "__Démonstration__ : Soient $f,g, h$ trois fonctions arithmétiques. Soit $n\\ge 1$. On a\n",
    "\n",
    "$$((f\\star g)\\star h)(n)=\\sum_{kc=n}(f\\star g)(k)h(c)=\\sum_{kc=n}\\sum_{ab=k}f(a)g(b)h(c)=\\sum_{abc=n}f(a)g(b)h(c)$$\n",
    "\n",
    "Sous cette dernière forme, l'associativité est claire."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3 Élément neutre"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : Pour toute fonction arithmétique $f$, on a\n",
    "\n",
    "$$f\\star \\delta = \\delta\\star f = f$$\n",
    "\n",
    "__Démonstration__ : Exercice. C'est très facile."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si nous nous résumons, nous obtenons la"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : Soit $\\mathcal A$ l'ensemble des fonctions arithmétiques. Alors $(\\mathcal A,\\star)$ est un monoïde commutatif.\n",
    "\n",
    "L'ensemble $\\mathcal A$ est-il un groupe ? Nous verrons que non, mais un sous-ensemble important de $\\mathcal A$ en est un. Patience ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.4 La formule d'inversion de Möbius"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vous avez peut-être remarqué que des sommes du type \"$g(n)=\\sum_{d|n}f(d)$\" apparaissaient très souvent. Ces sommes sont omniprésentes en théorie analytique des nombres. Très souvent, la fonction $g$ est connue et c'est la fonction $f$ qui nous intéresse. Comment \"inverser\" la formule ?\n",
    "\n",
    "Voici la solution à tous nos problèmes, il s'agit de la __formule d'inversion de Möbius__. Et c'est là que la fonction $\\mu$ prend tout son intérêt. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : Soient $f$ et $g$ deux fonctions arithmétiques. On suppose que pour tout $n\\ge 1$,\n",
    "\n",
    "$$g(n)=\\sum_{d|n}f(d)$$\n",
    "\n",
    "Alors, pour tout $n\\ge 1$, \n",
    "\n",
    "$$f(n)=\\sum_{d|n}\\mu(d)g(\\frac n d)$$\n",
    "\n",
    "La réciproque est également vraie.\n",
    "\n",
    "__Démonstration__ : C'est très très facile (si, si !) : il s'agit de montrer que\n",
    "\n",
    "$$g=\\mathbb 1\\star f\\Leftrightarrow f = \\mu\\star g$$\n",
    "\n",
    "- ($\\Rightarrow$) Supposons $g = \\mathbb 1 \\star f$. Multiplions par $\\mu$ :\n",
    "\n",
    "$$\\mu \\star g = \\mu\\star(\\mathbb 1\\star f)=(\\mu\\star \\mathbb 1)\\star f=\\delta\\star f = f$$\n",
    "\n",
    "- ($\\Leftarrow$) Supposons $f=\\mu\\star g$. Multiplions par $\\mathbb 1$ :\n",
    "\n",
    "$$u\\star f=\\mathbb 1\\star(\\mu\\star g)=(\\mathbb 1\\star \\mu)\\star g=\\delta\\star g = g$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Exemple__ : Nous avons admis plus haut que $id=\\varphi\\star \\mathbb 1$, c'est à dire que pour tout $n\\ge 1$, $\\sum_{d|n}\\varphi(d)=n$. La formule d'inversion de Möbius nous dit ici que $\\varphi=\\mu\\star id$, c'est à dire que pour tout $n\\ge 1$,\n",
    "\n",
    "$$\\varphi(n)=\\sum_{d|n}\\mu(d)\\frac n d=n\\sum_{d|n}\\frac{\\mu(d)}d$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.4 Fonctions inversibles pour le produit de Dirichlet"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'ensemble $\\mathcal A$, muni du produit de Dirichlet $\\star$, est un monoïde commutatif. Quels sont ses éléments inversibles ? Dit autrement, quelles sont les fonctions $f\\in\\mathcal A$ telles qu'il existe $g\\in\\mathcal A$ pour laquelle $f\\star g=\\delta$ ? Avec en récompense, la réponse à cette question : connaissant deux fonctions $f$ et $h$, peut-on trouver $g$ telle que $f\\star g = h$ ?\n",
    "\n",
    "__Remarque__ : Si une telle fonction $g$ existe, elle est nécessairement unique par l'associativité et la commutativité de l'opération $\\star$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : Soit $f\\in\\mathcal A$. Si $f(1)=0$, $f$ n'est pas inversible pour $\\star$.\n",
    "\n",
    "__Démonstration__ : En effet, pour toute fonction $g\\in\\mathcal A$, $(f\\star g)(1)=f(1)g(1)=0\\ne 1=\\delta(1)$. Donc $f\\star g\\ne \\delta$.\n",
    "\n",
    "__Proposition__ : Soit $f\\in\\mathcal A$. Si $f(1)\\ne 0$, alors $f$ est inversible pour $\\star$ : il existe $g\\in\\mathcal A$ telle que $f\\star g=\\delta$. De plus, $g(1)\\ne 0$.\n",
    "\n",
    "__Démonstration__ : Posons pour tout $n\\ge 1$, $a_n=f(n)$. On a donc $a_0\\ne 0$. Soit $g\\in\\mathcal A$. Posons pour tout $n\\ge 1$, $b_n=g(n)$. On a $f\\star g=\\delta$ si et seulement si $a_1b_1=1$, c'est à dire $b_1=\\frac 1 {a_1}$, et pour tout $n\\ge 2$\n",
    "\n",
    "$$\\sum_{d|n}b_da_{n/d}=0$$\n",
    "\n",
    "c'est à dire $a_1b_n=-\\sum_{d|n, d\\ne n}b_da_{n/d}$.\n",
    "\n",
    "La fonction $g$ est donc définie de façon unique par récurrence forte par :\n",
    "\n",
    "- $g(1)=\\frac 1 {f(1)}$.\n",
    "- Pour tout $n\\ge 2$, $g(n)=-\\frac 1 {f(1)} \\sum_{d|n, d\\ne n}g(d)f(\\frac n d)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Corollaire__ : L'ensemble $\\mathbb G$ des fonctions arithmétiques qui ne s'annulent pas en 1 est un groupe pour l'opération $\\star$.\n",
    "\n",
    "__Corollaire__ : L'ensemble $\\mathbb H$ des fonctions arithmétiques __à valeurs entières__ qui prennent la valeur 1 en 1 est un sous-groupe de $\\mathbb G$.\n",
    "\n",
    "__Remarque__ : Les fonctions $\\delta, \\mathbb 1, id, N_\\alpha, \\varphi, \\mu$ appartiennent toutes à $\\mathbb H$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `inverse` ci-dessous prend en paramètres une fonction arithmétique $f$ telle que $f(1)\\ne 0$ et un entier $n$. Elle renvoie la liste $[f^{-1}(1),\\ldots,f^{-1}(n)]$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def inverse(f, n):\n",
    "    s = (n + 1) * [0]\n",
    "    s[1] = 1 / f(1)\n",
    "    for k in range(2, n + 1):\n",
    "        ds = diviseurs(k)\n",
    "        b = 0\n",
    "        for d in ds:\n",
    "            if d != k:\n",
    "                b = b - s[d] * f(k // d) / f(1)\n",
    "        s[k] = b\n",
    "    return s[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(inverse(mu, 20))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `inverse1` ci-dessous est un cas particulier important de la précédente. Elle prend en paramètres une fonction arithmétique $f$ à valeurs entières telle que $f(1)=1$ et un entier $n$. Elle renvoie la liste $[f^{-1}(1),\\ldots,f^{-1}(n)]$.\n",
    "\n",
    "Pourquoi $f(1)=1$ ? Parce que dans ce cas, si la fonction $f$ est à valeurs entières, son inverse de Dirichlet aussi. Et nos fonctions préférées, $\\delta, id, \\mathbb 1, \\mu, \\varphi$ vérifient toutes cette propriété."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def inverse1(f, n):\n",
    "    s = (n + 1) * [0]\n",
    "    s[1] = 1\n",
    "    for k in range(2, n + 1):\n",
    "        ds = diviseurs(k)\n",
    "        b = 0\n",
    "        for d in ds:\n",
    "            if d != k:\n",
    "                b = b - s[d] * f(k // d)\n",
    "        s[k] = b\n",
    "    return s[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(inverse1(mu, 20))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : $\\mu^{-1}=\\mathbb 1$.\n",
    "\n",
    "__Démonstration__ : Résultat connu depuis un certain temps : $\\mu\\star \\mathbb 1=\\delta$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.5 L'inverse de $\\varphi$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quel est l'inverse de l'indicatrice d'Euler ??? Tentons une petite expérience."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = inverse1(phi, 30)\n",
    "for k in range(30):\n",
    "    print(k + 1, s[k])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Avant de donner une formule pour $\\varphi^{-1}(n)$, un résultat théorique :\n",
    "\n",
    "__Proposition__ : Soient $f,g\\in\\mathcal A$.\n",
    "\n",
    "- Si $f$ et $g$ sont multiplicatives alors $f\\star g$ est multiplicative.\n",
    "- Si $f$ et $f\\star g$ sont multiplicatives alors $g$ est multiplicative.\n",
    "\n",
    "__Démonstration__ : Ce n'est pas très difficile mais j'admettrai ce résultat par manque de place.\n",
    "\n",
    "__Corollaire__ : $\\varphi$ est multiplicative.\n",
    "\n",
    "__Démonstration__ : En effet, $\\varphi\\star \\mathbb 1=id$, et $\\mathbb 1$ et $id$ sont multiplicatives.\n",
    "\n",
    "__Corollaire__ : Soit $f\\in\\mathbb G$. Si $f$ est multiplicative, alors $f^{-1}$ est multiplicative.\n",
    "\n",
    "__Démonstration__ : $f$ et $f\\star f^{-1}=I$ sont multiplicatives, donc $f^{-1}$ l'est aussi.\n",
    "\n",
    "__Corollaire__ : $\\varphi^{-1}$ est multiplicative.\n",
    "\n",
    "__Démonstration__ : Parce que $\\varphi$ l'est."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notons $\\psi=\\varphi^{-1}$. La fonction $\\psi$ est donc multiplicative par le résultat précédent. Il nous suffit donc de calculer $\\psi(p^\\alpha)$ pour $p$ premier et $\\alpha\\ge 1$.\n",
    "\n",
    "- Commençons par $\\psi(p)$ : on a $(\\varphi\\star\\psi)(p)=I(p)=0$. Ou encore $\\varphi(1)\\psi(p)+\\varphi(p)\\psi(1)=0$, c'est à dire $\\psi(p)+(p-1)=0$. Ainsi, $\\psi(p)=-(p-1)$.\n",
    "\n",
    "- Que vaut $\\psi(p^2)$ ? Même technique. $\\psi(p^2)\\varphi(1)+\\psi(p)\\varphi(p)+\\psi(1)\\varphi(p^2)=0$, ou encore $\\psi(p^2)+(p-1)^2+p^2-p=0$. D'où $\\psi(p^2)=-(p-1)$.\n",
    "\n",
    "- Que vaut $\\psi(p^3)$ ? $\\psi(p^3)\\varphi(1)+\\psi(p^2)\\varphi(p)+\\psi(p)\\varphi(p^2)+\\psi(1)\\varphi(p^3)=0$, ou encore $\\psi(p^3)-(p-1)^2-(p-1)(p^2-p)+(p^3-p^2)=0$. Arrangeons tout cela :\n",
    "\n",
    "$$\\psi(p^3)-(p-1)^2-p(p-1)^2+p^2(p-1)=0$$\n",
    "\n",
    "$$\\psi(p^3)=(p-1)(p-1+p(p-1)-p^2)=1-p$$\n",
    "\n",
    "\n",
    "__Exercice__ : Montrer par récurrence forte sur $\\alpha$ que pour tout $\\alpha\\ge 1$ et tout $p\\in\\mathcal P$, $\\psi(p^\\alpha)=1-p$.\n",
    "\n",
    "On en déduit la\n",
    "\n",
    "__Proposition__ : Pour tout $n=\\prod_{i=1}^k p_i^{\\alpha_i}$ où les $p_i$ sont premiers distincts et les $\\alpha_i\\ge 1$, on a\n",
    "\n",
    "$$\\psi(n)=\\prod_{i=1}^k(1-p_i)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def psi(n):\n",
    "    fs = facteurs(n)\n",
    "    x = 1\n",
    "    for (p, a) in fs:\n",
    "        x = (1 - p) * x\n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Faisons une petite vérification ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for k in range(1, 31):\n",
    "    print('%3d%5d%5d' % (k, psi(k), s[k - 1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C'est fou, la théorie donne un résultat exact en pratique :-).\n",
    "\n",
    "Allez, à quoi ressemble le graphe de $\\varphi^{-1}$ ?."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_fun(psi, 1, 1000, '.k', markersize=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La formule que nous avons obtenue pour $\\psi$ est assez cool, mais peut-on creuser ? Creusons.\n",
    "\n",
    "__Proposition__ = $\\varphi^{-1}=id\\times(\\mu \\star N_{-1})$.\n",
    "\n",
    "Remarquons que $(id\\times(\\mu \\star N_{-1}))(n)=n\\sum_{d|n}\\mu(d)N_{-1}$$(\\frac{n}{d})=n\\sum_{d|n}\\mu(d)\\frac d n=\\sum_{d|n}d\\mu(d)$. Ce que dit notre proposition, c'est que pour tout $n\\ge 1$, \n",
    "\n",
    "$$\\varphi^{-1}(n)=\\sum_{d|n}d\\mu(d)$$\n",
    "\n",
    "__Démonstration__ : La fonction $\\psi$ et la fonction $n\\mapsto n(\\mu \\star N_{-1})(n)$ sont multiplicatives. Il suffit donc de vérifier qu'elle coincident pour tout entier $n=p^\\alpha$ où $p$ est premier et $\\alpha\\ge 1$. Prenons donc un tel entier $n$. Les seuls diviseurs de $n=p^\\alpha$ en lesquels $\\mu$ est non nulle sont 1 et $p$. Ainsi,\n",
    "\n",
    "$$\\sum_{d|n}d\\mu(d)=1-p=\\psi(n)$$\n",
    "\n",
    "D'où l'égalité cherchée par multiplicativité."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et la moyenne de $\\varphi^{-1}$, elle ressemble à quoi ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_moyennes(psi, 10000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Gloups ... Ça monte, ça descend. Mais ça n'a pas l'air de monter très haut ni de descendre très bas. Sur le graphique ci-dessus, $n$ va de 1 à 10000, alors que $\\varphi^{-1}(n)$ oscille entre $-30$ et $20$ (euh un peu plus). Il y a sûrement encore beaucoup à dire."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.6 L'inverse d'une fonction complètement multiplicative"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Exercice__ : Soit $f$ une fonction complètement multiplicative. Montrer que si $f(1)\\ne 1$ alors $f$ est identiquement nulle."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $f$ une fonction __complètement multiplicative__ et pas identiquement nulle (comme par exemple $u$, $I$, $N_\\alpha$). Quel est son inverse de Dirichlet ? Calculons $f\\star (\\mu f)$. Soit $n\\ge 1$. On a\n",
    "\n",
    "$$(f\\star(\\mu f))(n)=\\sum_{d|n}f(d)\\mu(d)f(\\frac n d)=\\sum_{d|n}f(d\\frac n d)\\mu(d)=f(n)\\sum_{d|n}\\mu(d)=f(n)I(n)$$\n",
    "\n",
    "Ainsi, $f\\star (\\mu f)= fI$. Comme $f$ n'est pas identiquement nulle, $f(1)=1)$ et donc $fI=I$.\n",
    "\n",
    "__Proposition__ : Pour toute fonction complètement multiplicative $f$, on a $f^{-1}=\\mu f$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Petit exemple avec la fonction $N_2$ ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 20\n",
    "s = inverse1(lambda n:n ** 2, n)\n",
    "print((n * '%5d') % tuple(range(1, n + 1)))\n",
    "print((n * '%5d') % tuple(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si vous connaissez vos carrés vous apprécierez."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4 Encore des fonctions arithmétiques"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1 Nombre de diviseurs, somme des diviseurs, etc."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour $\\alpha\\in\\mathbb R$ et $n\\ge 1$, on pose\n",
    "\n",
    "$$\\sigma_\\alpha(n)=\\sum_{d|n}d^\\alpha$$\n",
    "\n",
    "Deux cas particuliers importants sont :\n",
    "\n",
    "- $\\alpha =0$ : $d_0(n)=d(n)$ est le nombre de diviseurs de $n$.\n",
    "- $\\alpha =1$ : $d_1(n)$ est la somme des diviseurs de $n$.\n",
    "\n",
    "Nous admettrons ici la\n",
    "\n",
    "__Proposition__ : La fonction $\\sigma_\\alpha$ est multiplicative.\n",
    "\n",
    "\n",
    "__Démonstration__ : Vous l'aviez sûrement remarqué :\n",
    "\n",
    "$$\\sigma_\\alpha = \\mathbb 1 \\star N_\\alpha$$\n",
    "\n",
    "Or, $\\mathbb 1$ et $N_\\alpha$ sont multiplicatives, cqfd.\n",
    "\n",
    "__Conséquence__ : Pour calculer $\\sigma_\\alpha(n)$, il suffit donc de savoir calculer $\\sigma_\\alpha(p^a)$ lorsque $p$ est un nombre premier et $a\\in\\mathbb N^*$. Mais ceci est facile. En effet, les diviseurs de $p^a$ sont : 1, $p, p^2,\\ldots, p^a$. Ainsi,\n",
    "\n",
    "- Si $\\alpha=0$, $d_0(p^a)=a+1$.\n",
    "- Si $\\alpha\\ne 0$, $d_\\alpha(p^a)=\\sum_{i=0}^a (p^i)^\\alpha=\\sum_{i=0}^a (p^\\alpha)^i=\\frac{p^{\\alpha(a+1)}-1}{p^\\alpha - 1}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici donc la fonction `sigma`. Cette fonction distingue le cas où $\\alpha$ est un entier naturel non nul, afin de renvoyer dans ce cas une valeur entière."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sigma(n, alpha):\n",
    "    fs = facteurs(n)\n",
    "    m = 1\n",
    "    for (p, a) in fs:\n",
    "        if alpha == 0:\n",
    "            m = m * (a + 1)\n",
    "        elif type(alpha) == type(int) and alpha > 0:\n",
    "            m = m * (p ** (alpha * ( a + 1)) - 1) // (p ** alpha - 1)\n",
    "        else:\n",
    "            m = m * (p ** (alpha * ( a + 1)) - 1) / (p ** alpha - 1)\n",
    "    return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(1, 31):\n",
    "    print('%3d%3d%3d %5f' % (n, sigma(n, 0), sigma(n, 1), sigma(n, -1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_fun(lambda n:sigma(n, 0), 1, 500, 'ok', markersize=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et si on refaisait le coup des moyennes ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : $\\overline\\sigma_0(n)=\\ln n + (2C-1) + O(\\frac 1 {\\sqrt n})$ où $C\\simeq 0.577216$ est la constante d'Euler.\n",
    "\n",
    "__Démonstration__ : pas la place (mauvaise foi flagrante). La preuve n'est pas très difficile, cela dit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "C = 0.577215664\n",
    "plot_moyennes(lambda n: sigma(n, 0), 500, lambda n: math.log(n) + (2 * C - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_fun(lambda n:sigma(n, 1), 1, 500, 'ok', markersize=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : $\\overline\\sigma_1(n)\\sim \\frac{\\pi^2n}{12}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_moyennes(lambda n: sigma(n, 1), 500, lambda n: math.pi ** 2 / 12 * n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_fun(lambda n:sigma(n, -1), 1, 500, 'ok', markersize=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : $\\overline\\sigma_{-1}(n)\\to \\frac{\\pi^2} 6$ lorsque $n$ tend vers $+\\infty$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_moyennes(lambda n: sigma(n, -1), 500, lambda n: math.pi ** 2 / 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2 La fonction $\\Lambda$ de von Mangoldt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour ne pas donner l'impression que toutes les fonctions arithmétiques importantes sont multiplicatives, en voici une qui ne l'est pas. La fonction $\\Lambda$ de von Mangoldt joue un rôle plus que très extrêmement important en théorie analytique des nombres.\n",
    "\n",
    "__Définition__ : Soit $n\\ge 1$.\n",
    "- Si $n=p^\\alpha$ est une puissance d'un nombre premier, $\\Lambda(n)=\\ln n$.\n",
    "- Sinon, $\\Lambda(n)=0$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mangoldt(n):\n",
    "    fs = facteurs(n)\n",
    "    if len(fs) != 1: return 0\n",
    "    else:\n",
    "        p = fs[0][0]\n",
    "        return math.log(p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print([mangoldt(n) for n in range(1, 20)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_fun(mangoldt,1, 100, 'ok', markersize=2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print([dirichlet(mangoldt, lambda n:1)(n) - math.log(n) for n in range(1, 100)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comme quoi $\\Lambda$ ce n'est pas n'importe quoi. En fait, c'est peut-être la fonction la plus essentielle de ce notebook. Elle est à la base de la démonstration du théorème des nombres premiers.\n",
    "\n",
    "__Proposition__ : En désignant par $\\ln$ la restriction du logarithme à $\\mathbb N^*$,\n",
    "\n",
    "$$\\Lambda \\star \\mathbb 1 = \\ln$$\n",
    "\n",
    "et donc, par inversion : \n",
    "\n",
    "$$\\ln\\star\\mu=\\Lambda$$\n",
    "\n",
    "__Démonstration__ : La fonction $\\Lambda$ est non nulle uniquement en les puissances des nombres premiers. Ainsi, \n",
    "\n",
    "$$(\\Lambda\\star \\mathbb 1)(n)=\\sum_{p^\\alpha|n}\\Lambda(p^\\alpha)=\\sum_{p^\\alpha|n}\\ln p$$\n",
    "\n",
    "la somme étant entendue pour tous les nombres premiers $p$ et les entiers $\\alpha\\ge 1$ tels que $p^\\alpha$ divise $n$.\n",
    "\n",
    "Pour chaque diviseur premier $p$ de $n$, il y a exactement $\\nu_p(n)$ valeurs possibles pour $\\alpha$. Ainsi,\n",
    "\n",
    "$$(\\Lambda\\star \\mathbb 1)(n)=\\sum_{p|n}\\nu_p(n)\\ln p=\\ln\\prod_{p|n}p^{\\nu_p(n)}=\\ln n$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.3 Les moyennes de $\\Lambda$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Eh oui, on ne peut pas ne pas se poser la question !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_moyennes(mangoldt, 500, lambda x:1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Limite égale à 1 ? Facile à montrer ? Non, c'est exactement comme pour la fonction $\\mu$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : $\\overline\\Lambda(n)\\to 1$ lorsque $n$ tend vers l'infini. Ou encore :\n",
    "\n",
    "$$\\frac 1 n \\sum_{k=1}^n\\Lambda(k)\\to_{n\\to\\infty} 1$$\n",
    "\n",
    "__Proposition__ : La propriété précédente est équivalente au théorème des nombres premiers.\n",
    "\n",
    "Inutile, donc, de nous acharner à essayer de la prouver, à moins que nous ne nous appellions Hadamard ou de la Vallée Poussin :-)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5 Dérivation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Allons, un dernier effort. Pour finir je voudrais éclairer les égalités précédentes concernant $\\Lambda$ sous un jour nouveau. Plus de Python dans ce qui va suivre ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.1 C'est quoi la dérivée ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tout le monde sait ce que c'est, n'est-ce pas ? Eh bien non, parce que nous allons définir la dérivée d'une fonction arithmétique de façon très atypique.\n",
    "\n",
    "__Définition__ : Soit $f\\in\\mathcal A$. La dérivée de $f$ est la fonction $f'\\in\\mathcal A$ définie pour tout $n\\ge 1$ par\n",
    "\n",
    "$$f'(n)=f(n)\\ln n$$\n",
    "\n",
    "Dit autrement,\n",
    "\n",
    "$$f'=f\\times \\ln$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Exemples__ \n",
    "\n",
    "- $\\delta'=0$.\n",
    "\n",
    "- La dérivée de $\\mathbb 1$ est $\\mathbb 1'=\\ln$. Du coup, les formules que nous avons vues à la fin du paragraphe précédent deviennent\n",
    "\n",
    "$$\\Lambda\\star \\mathbb 1=\\mathbb 1'$$\n",
    "\n",
    "$$\\mathbb 1'\\star \\mu=\\Lambda$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.2 Propriétés"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut évidemment définir tout et n'importe quoi. Qu'est-ce qui fait la différence entre une bonne et une mauvaise définition ? Ce sont les propriétés que nous pouvons en déduire. Et ici, notre définition de  la dérivée est une __très__ bonne définition. Notre dérivée se comporte comme la dérivée \"normale\", sauf que l'on remplace le produit classique $\\times$ par l'opération $\\star$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Propriété__ : Soient $f,g\\in\\mathcal A$. On a :\n",
    "\n",
    "- $(f + g)'=f'+g'$.\n",
    "- $(f\\star g)'=f'\\star g + f\\star g'$.\n",
    "- Si $f(1)\\ne 0$, $(f^{-1})'=-f'\\star (f \\star f)^{-1}$.\n",
    "\n",
    "__Démonstration__ :\n",
    "\n",
    "- La somme est laissée en exercice.\n",
    "- Pour le produit, la clé est $\\ln d + \\ln \\frac n d = \\ln n$. En effet,\n",
    "\n",
    "$$(f\\star g)'(n)=\\sum_{d|n}f(d)g(\\frac n d)\\ln n=\\sum_{d|n}f(d)g(\\frac n d)\\ln d+\\sum_{d|n}f(d)g(\\frac n d)\\ln \\frac n d$$ d'où le résultat.\n",
    "\n",
    "- On a $I'=0=(f\\star f^{-1})'=f'\\star f^{-1} + f \\star (f^{-1})'$. Ainsi,\n",
    "\n",
    "$$f \\star (f^{-1})'=-f'\\star f^{-1}$$\n",
    "\n",
    "Multiplions par $f^{-1}$. On obtient $(f^{-1})'=-f^{-1}\\star(f'\\star f^{-1})=-f'\\star f^{-1}\\star f^{-1}=-f'\\star(f\\star f)^{-1}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.3 L'identité de Selberg"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous terminerons ce notebook par une identité qui est à la base d'une démonstration \"élémentaire\" du théorème des nombres premiers : l'identité de Selberg. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : Pour tout $n\\ge 1$, on a\n",
    "\n",
    "$$\\Lambda(n)\\ln n + \\sum_{d|n}\\Lambda(d)\\Lambda(\\frac n d)=\\sum_{d|n}\\mu(d)\\ln^2\\frac n d$$\n",
    "\n",
    "__Démonstration magique__ : On part de $\\Lambda\\star \\mathbb 1=\\mathbb 1'$ et on dérive :\n",
    "\n",
    "$$\\Lambda'\\star \\mathbb 1 + \\Lambda\\star \\mathbb 1'=\\mathbb 1''$$\n",
    "\n",
    "Mais $\\mathbb 1'=\\Lambda\\star \\mathbb 1$. Donc\n",
    "\n",
    "$$\\Lambda'\\star \\mathbb 1 + \\Lambda\\star \\Lambda\\star \\mathbb 1=\\mathbb 1''$$\n",
    "\n",
    "Multiplions les deux côtés par $\\mu=\\mathbb 1^{-1}$. Il vient\n",
    "\n",
    "$$\\Lambda' + \\Lambda\\star \\Lambda=\\mathbb 1''\\star \\mu$$\n",
    "\n",
    "__Exercice__ : Vérifiez qu'on a fini :-)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Exercice__ : Vous pensez avoir tout compris. En admettant $\\varphi \\star \\mathbb 1=id$, prouvez que $\\varphi$ est multiplicative. C'est immédiat si l'on sait où chercher."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6 Bibliographie"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La partie I (tests naïfs de primalité, factorisation) fait partie de la mémoire de l'humanité. \n",
    "\n",
    "Pour tout le reste, j'ai puisé sans limites dans les chapitres 2 et 3 du fantastique livre de Tom M. Apostol _Introduction to Analytic Number Theory_, Springer, 1976."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}