{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Nombres $p$-adiques\n",
    "\n",
    "Marc Lorenzi\n",
    "\n",
    "29 novembre 2018"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tout le monde le sait, un nombre réel c'est un nombre avec éventuellement une infinité de chiffres après la virgule. Alors c'est quoi un nombre avec une infinité de chiffres __AVANT__ la virgule ? Tout le monde le sait, ça n'existe pas ! Eh bien si, ça existe. Cela s'appelle un nombre $p$-adique.\n",
    "\n",
    "Nous allons nous intéresser seulement à une partie de l'ensemble des nombres $p$-adiques : l'ensemble $\\mathbb Z_p$ des _entiers $p$-adiques_ (ce sont les nombres $p$-adiques qui n'ont pas de chiffres __APRÈS__ la virgule)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans tout le notebook, $p$ désigne un nombre premier (sauf une fois de temps en temps, juste pour voir, où nous prendrons $p=10$). Pour tout $x\\in \\mathbb Z$ et tout entier $n\\ge 2$, nous noterons $x \\bmod n$ le reste de la division de $x$ par $n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $E_p=\\prod_{n=1}^\\infty \\mathbb Z/p^n\\mathbb Z$. Un élément de $E_p$ est une suite $(x_n)_{n\\ge 1}$ telle que pour tout $n\\ge 1$ on ait $x_n\\in \\mathbb Z/p^n\\mathbb Z$.\n",
    "\n",
    "Évidemment, modéliser les éléments de $E_p$ en Python est un tantinet délicat, vu qu'il faudrait pouvoir stocker une infinité de nombres ! En revanche, si $x=(x_n)_{n\\ge 1}\\in E_p$, il est tout à fait possible de manipuler dans notre langage préféré la liste des $n$ premiers termes de $x$, $[x_1,x_2,\\ldots,x_n]$. \n",
    "\n",
    "__Vocabulaire__ : Nous appellerons $[x_1,x_2,\\ldots,x_n]$ __l'approximation__ de la suite $x$ à l'ordre $n$. Pourquoi _approximation_ ? Patience ...\n",
    "\n",
    "Remarquer le subtil décalage entre les indices Python qui commencent à 0, et les indices des termes de la suite qui commencent à 1. Nous essaierons de ne pas l'oublier. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Entiers $p$-adiques"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 Suites cohérentes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Seuls certains éléments de $E_p$ nous intéresseront. Nous allons nous focaliser sur les _suites cohérentes_. Remarquons tout d'abord que si $x,x'\\in\\mathbb Z$ et $n\\ge 1$, alors\n",
    "$$x\\equiv x'[p^{n+1}]\\Rightarrow x\\equiv x'[p^n]$$\n",
    "\n",
    "On peut donc considérer l'application $\\varphi_n : \\mathbb Z/p^{n+1}\\mathbb Z \\to \\mathbb Z/p^{n}\\mathbb Z$ qui à la classe de $x$ modulo $p^{n+1}$ associe la classe de $x$ modulo $p^n$. Comme on peut le montrer facilement, cette application est un morphisme surjectif d'anneaux.\n",
    "\n",
    "__Notation__ : Nous noterons pour $x\\in\\mathbb Z/p^{n+1}\\mathbb Z$, $\\varphi_n(x)=x \\bmod p^n$. \n",
    "\n",
    "__Remarque__ : En composant, $\\varphi_{n+1}\\circ\\varphi_n$ est un morphisme surjectif de $\\mathbb Z/p^{n+2}\\mathbb Z$ sur $\\mathbb Z/p^{n}\\mathbb Z$. Et on peut généraliser. Nous nous autoriserons en fait à noter $x \\bmod p^n$ pour tout $x\\in\\mathbb Z/p^{k}\\mathbb Z$ où $k\\ge p$.\n",
    "\n",
    "__Définition__ : Une suite $(x_n)_{n\\ge 1}\\in E_p$ est dite __cohérente__ lorsque pour tout $n\\ge 1$ on a $x_{n+1}\\bmod p^n= x_n$. \n",
    "\n",
    "__Exemple__ : Pour $p=2$, la suite $(0, 2, 2, 10, 10, 10, \\ldots)$ est cohérente. Je vous laisse le vérifier. Ou alors attendez 5 minutes, une fonction Python le fera pour nous."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Remarque essentielle__ : Si $(x_n)_{n\\ge 1}$ est cohérente, et qu'on connaît la valeur d'un certain terme $x_n$ de la suite, alors on connaît aussi $x_{n-1}=x_n \\bmod p^{n-1}$. Puis on peut calculer $x_{n-2},x_{n-3},\\ldots,x_1$. En revanche, un doute subsiste sur $x_{n+1},x_{n+2},\\ldots$. Ainsi, pour avoir une approximation à l'ordre $n$ d'une suite cohérente, il suffit de posséder le $n$ième terme de la suite. Les termes précédents se retrouvent à partir de celui-ci."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `est_coherente` ci-dessous prend en paramètre une liste d'entiers $s$ et un nombre premier $p$. Elle renvoie `True` si cette liste est une (approximation d'une) suite cohérente, et `False` sinon. La fonction affiche (horreur !!!) les étapes du calcul."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def est_cohérente(s, p):\n",
    "    n = len(s)\n",
    "    for k in range(len(s) - 1, 0, -1):\n",
    "        print('%3d : %-5d mod %5d^%d = %-5d' %(k + 1, s[k], p, k, s[k - 1]))\n",
    "        if s[k] % (p ** k) != s[k - 1]: return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "est_cohérente([0, 2, 2, 10, 10, 10, 10], 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `faire_coherente` prend en paramètres un entier $x$, un nombre premier $p$ et un entier $N\\ge 1$. Elle renvoie l'approximation à l'ordre $N$ de la suite cohérente de $E_p$ dont le $N$-ième terme est $x$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def faire_coherente(x, p, N):\n",
    "    return [x % (p ** k) for k in range(1, N + 1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "faire_coherente(10, 2, 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "faire_coherente(1000000, 7, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "est_cohérente(_, 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "faire_coherente(-1, 2, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "est_cohérente(_, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Faites d'autres essais pour bien comprendre ce qu'est une suite cohérente. Il va y en avoir dans les 25 prochaines pages :-)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 L'anneau $\\mathbb Z_p$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Définition__ : On appelle _entier $p$-adique_ toute suite cohérente de $E_p$. On note $\\mathbb Z_p$ l'ensemble des entiers $p$-adiques."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Résumons-nous. Un entier $p$-adique est une suite $x=(x_n)_{n\\ge 1}$ telle que \n",
    "\n",
    "- Pour tout entier $n\\ge 1$, $x_n\\in\\mathbb Z/p^{n}\\mathbb Z$\n",
    "- Pour tout entier $n\\ge 1$, $x_{n+1}\\bmod p^n=x_n$. \n",
    "\n",
    "__Nous verrons des éléments de $\\mathbb Z_p$ de plus en plus intéressants au fur et à mesure que nous avancerons dans notre étude.__\n",
    "\n",
    "Définissons maintenant une addition et une multiplication dans $E_p$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Définition__ : Soient $(x_n)$ et $(y_n)$ deux éléments de $E_p$. On pose\n",
    "$$x+y=(x_n+y_n)_{n\\ge 1}$$\n",
    "et\n",
    "$$x\\times y=(x_n\\times y_n)_{n\\ge 1}$$\n",
    "\n",
    "\n",
    "__Proposition__ : $(E_p,+,\\times)$ est un anneau commutatif.\n",
    "\n",
    "__Proposition__ : La somme et le produit de deux entiers $p$-adiques sont encore des entiers $p$-adiques.\n",
    "\n",
    "__Proposition__ : $\\mathbb Z_p$ est un sous-anneau de $E_p$.\n",
    "\n",
    "__Démonstrations__ : En exercice, ce sont de simples vérifications. Remarquons tout de même que le neutre pour l'addition est la suite nulle, et le neutre pour la multiplication est la suite \"constante\" égale à 1.\n",
    "\n",
    "__Exercice__ : Pourquoi ai-je mis des guillemets autour du mot \"constante\" ? Indication : c'est qui, 1 ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3 Une injection de $\\mathbb Z$ dans $\\mathbb Z_p$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : L'application $\\varphi : \\mathbb Z\\to\\mathbb Z_p$ définie par $\\varphi(x)=(x \\bmod p^n)_{n\\ge 1}$ est un morphisme d'anneaux injectif."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous identifierons dorénavant les entiers relatifs avec leur image dans $\\mathbb Z_p$. Voici par exemple le nombre 10, vu comme élément de $\\mathbb Z_2$. Plus précisément, voici les 12 premiers termes de la suite $\\varphi(10)$. Je vous laisse deviner les suivants."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "faire_coherente(10, 2, 12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et voici l'entier -1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "faire_coherente(-1, 2, 12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Exercice__ :\n",
    "\n",
    "1- Soit $x=(x_n)_{n\\ge 1}\\in\\mathbb Z_p$. Montrer que la suite est _stationnaire_ si et seulement si il existe $n\\in\\mathbb N$ tel que $\\varphi(n)=x$.\n",
    "\n",
    "2- Critiquez la question 1. Comment une suite peut-elle être stationnaire alors que ses termes appartiennent à des ensembles différents ??? Reformulez correctement la question.\n",
    "\n",
    "2- Quelles sont les images par $\\varphi$ des entiers négatifs ? Je vous rappelle que vous êtes dans un notebook et que vous disposez de la fonction `faire_coherente`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "faire_coherente(-7, 2, 12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pas d'idée ? C'est pourtant facile, regardez ci-dessous."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[2 ** k - 7 for k in range(1, 13)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "[(2 ** k - 7) % (2 ** k) for k in range(1, 13)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.4 Représentation des entiers $p$-adiques en Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous allons créer une classe `Padic`. Un objet de cette classe est la représentation d'un entier $p$-adique, ou plutôt d'une approximation de celui-ci à un certiain ordre.\n",
    "\n",
    "Rappelons que si $x=(x_n)\\in \\mathbb Z_p$ et que, pour un certain entier $k\\ge 2$, nous connaissons $x_k$, alors nous possédons aussi $x_{k-1}$ qui est le reste de la division de $x_k$ (enfin, d'un des représentants de la classe $x_k$) par $p^{k-1}$. Pour un entier $N$ donné, pour stocker l'approximation à l'ordre $N$, $[x_1,x_2,\\ldots,x_{N}]$, il suffit donc de connaître $x_{N}$. Et aussi, bien entendu, $p$ et $N$.\n",
    "\n",
    "Voici la classe `Padic`. Un objet de cette classe possède trois champs :\n",
    "\n",
    "- Un champ $p$ qui contient la valeur de ... $p$.\n",
    "- Un champ $N$ contenant la \"précision\" à laquelle notre entier $p$-adique est stocké.\n",
    "- Un champ $n$ qui contient $x_{N}$.\n",
    "\n",
    "Si un tel objet est la représentation d'un entier $p$-adique $x=(x_n)_{n\\ge 1}$, on peut donc à partir de notre objet retrouver les valeurs de $x_1,x_2,\\ldots,x_{N}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Padic:\n",
    "    \n",
    "    def __init__(self, n, p, N):\n",
    "        q = p ** N\n",
    "        self.n = n % q\n",
    "        self.p = p\n",
    "        self.N = N\n",
    "        self.q = q\n",
    "    \n",
    "    def __repr__(self):\n",
    "        n = self.n\n",
    "        s = ''\n",
    "        for k in range(self.N):\n",
    "            if self.p <= 10: s = str(n % self.p) + s \n",
    "            else: s = str(n % self.p) + ' ' + s \n",
    "            n = n // self.p\n",
    "        return '...' + s\n",
    "\n",
    "    def termes(self):\n",
    "        s = [self.n % (self.p ** k) for k in range(1, self.N + 1)]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La méthode `__repr__` permet un affichage joli des objets. Un exemple ? Oui, je, sais, 10 n'est pas un nombre premier. Mais les choses seront plus claires avec ce nombre parce que, je ne sais pas pourquoi, les gens ont moins de mal avec l'écriture en base 10 :-)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = Padic(123456, 10, 9)\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Euh, oui, ce sont les chiffres de notre nombre en base 10. Remarquez les points de suspension à gauche : il y a une infinité de chiffres, tous nuls dans notre exemple. Remarquez également la méthode `termes` qui renvoie les $N$ premiers termes de la suite cohérente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x.termes()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous retrouvons ici les $N$ premiers termes de la suite $(x_n)$. Comprenez-vous bien ce qu'est une suite cohérente modulo 10 ? Comprenez-vous pourquoi j'ai dit au début du notebook que nous allions travailler avec des nombres qui ont une infinité de chiffres __AVANT__ la virgule ? Parce que ça y est, nous y sommes. Le nombre -1, par exemple, est l'entier $2$-adique qui s'écrit avec une infinité de 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = Padic(-1, 2, 20)\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Évidemment, si $p>10$ cette façon d'afficher les chiffres du nombre en base $p$ ne convient pas. Voilà pour quoi la méthode `__repr__` de la classe `Padic` envisage deux possibiltés. Tentons avec $p=11$ :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = Padic(5678, 11, 9)\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x.termes()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Remarque philosophique__ : Tout cela est bien beau, me direz vous, mais nous aimerions voir un vrai entier $p$-adique, et pas juste un entier relatif écrit de façon très compliquée. Mais vous me demandez l'impossible !\n",
    "\n",
    "Imaginez que vous me disiez : \"Je veux voir un réel, un vrai, pas juste un nombre décimal\" ? Je vous répondrais la même chose. Un \"vrai\" réel ça ne se voit pas, cela s'approche avec des décimaux (montrez-moi $\\sqrt 2$ !). Eh bien un vrai nombre $p$-adique c'est pareil, cela s'approche avec des entiers naturels. Et comme nous verrons d'ici quelque temps que $\\mathbb N$ est __dense__ dans $\\mathbb Z_p$, ce que je raconte ici est bien plus qu'une analogie. La situation des réels et celle des nombres $p$-adiques sont identiques."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.5 Les opérations d'anneau"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Implémenter addition, opposé, soustraction et multiplication est immédiat. Il n'y a qu'à opérer modulo $p^N$. J'ai rajouté également une fonction de division ... qui ne marche pas (enfin pas encore). Diviser dans un anneau n'est pas toujours possible ni facile, et deux questions restent à résoudre (et non des moindres) :\n",
    "\n",
    "- Quels sont les éléments inversibles de $\\mathbb Z_p$ ?\n",
    "- Comment calculer l'inverse d'un élément inversible ?\n",
    "\n",
    "La classe `Padic` ci-dessous recopie le code déjà vu plus haut et rajoute celui les opérations de base. Aucune difficulté."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Padic:\n",
    "    \n",
    "    def __init__(self, n, p, N):\n",
    "        q = p ** N\n",
    "        self.n = n % q\n",
    "        self.p = p\n",
    "        self.N = N\n",
    "        self.q = q\n",
    "\n",
    "    def __repr__(self):\n",
    "        n = self.n\n",
    "        s = ''\n",
    "        for k in range(self.N):\n",
    "            if self.p <= 10: s = str(n % self.p) + s \n",
    "            else: s = str(n % self.p) + ' ' + s \n",
    "            n = n // self.p\n",
    "        return '...' + s\n",
    "\n",
    "    def termes(self):\n",
    "        s = [self.n % (self.p ** k) for k in range(1, self.N + 1)]\n",
    "        return s\n",
    "    \n",
    "    def __add__(self, y):\n",
    "        assert(self.p == y.p)\n",
    "        N = min(self.N, y.N)\n",
    "        return Padic(self.n + y.n, self.p, N)\n",
    "\n",
    "    def __mul__(self, y):\n",
    "        assert(self.p == y.p)\n",
    "        N = min(self.N, y.N)\n",
    "        return Padic(self.n * y.n, self.p, N)\n",
    "    \n",
    "    def __neg__(self):\n",
    "        return Padic(-self.n, self.p, self.N)\n",
    "    \n",
    "    def __sub__(self, y):\n",
    "        return self + (- y)\n",
    "    \n",
    "    def __truediv__(self, y):\n",
    "        z = inverse(y)\n",
    "        return self * z\n",
    "    \n",
    "    def __pow__(self, n):\n",
    "        if n < 0: \n",
    "            return inverse(self ** (-n))\n",
    "        else:\n",
    "            y = Padic(1, self.p, self.N)\n",
    "            for k in range(n):\n",
    "                y = y * self\n",
    "            return y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous pouvons enfin montrer que $8\\times 7 \\simeq 56$ :-)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = Padic(8, 3, 10) * Padic(7, 3, 10)\n",
    "print(x)\n",
    "print(x.termes())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Que vaut $1547$ dans $\\mathbb Z_3$ ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Padic(1547, 3, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Que vaut $3^4 \\times 1547$ ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = Padic(1547, 3, 10) * Padic(3, 3, 20) ** 4\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Règle__ : Multiplier dans $\\mathbb Z_p$ par $p^k$ revient à ajouter $k$ zéros au nombre. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Je vous laisse prouver la règle. Testez sur d'autres exemples, jusqu'à ce que vous ayez bien compris comment fonctionnent les opérations, la multiplication par $p$, le passage à l'opposé, la soustraction, les puissances ...\n",
    "\n",
    "L'intérêt d'un notebook est de tester, tester, et ... tester. Si on ne teste rien et qu'on se contente de lire, alors autant prendre un PDF."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Valuation et valeur absolue $p$-adiques"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous allons maintenant définir dans $\\mathbb Z_p$ une notion de distance, qui sera très différente de la distance usuelle entre les entiers relatifs. Les nombres divisibles par de grandes puissances de $p$ seront très proches de 0. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 Valuation $p$-adique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Définition__ : Soit $x=(x_n)\\in\\mathbb Z_p$. Si $x\\ne 0$ on appelle valuation $p$-adique de $x$ l'entier $v_p(x)=\\min\\{k\\in \\mathbb N^*, x_k\\ne 0\\}-1$. On pose également $v_p(0)=+\\infty$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `valuation` ci-dessous prend un entier $p$-adique $x$ (ou du moins une approximation de celui-ci). Si l'approximation de $x$ est non nulle, la fonction renvoie $v$, la valuation de $x$. Si, en revanche, l'approximation de $x$ est nulle, cela ne veut pas forcément dire que $x$ est nul. La fonction renvoie `N+1` où $N$ est l'ordre d'approximation de $x$. Cela signifie que $v(x)\\ge N+1$, et on ne peut pas dire mieux.\n",
    "\n",
    "Remarquez le parallèle avec $\\mathbb R$. Si $x=0.00000\\ldots$ cela ne veut pas dire que $x=0$, mais seulement que $|x|< 10^{-5}$, parce qu'il y a 5 zéros après la virgule."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `valuation` fonctionne comme suit : elle cherche la plus grande puissance de $p$ qui divise $x$ (ou plus exactement `x.n`). Quel rapport avec la définition de la valuation ??? Voyez le théorème ci-dessous."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def valuation(x):\n",
    "    v = 0\n",
    "    n = x.n\n",
    "    while n % x.p == 0 and v <= x.N:\n",
    "        v += 1\n",
    "        n = n // x.p\n",
    "    return v"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Par exemple, la valuation de $63=3^2\\times 7$ dans $\\mathbb Z_3$ est 2 parce que ce nombre finit par 2 zéros."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = Padic(63, 3, 5)\n",
    "print(x)\n",
    "print(valuation(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et la valuation de 0 \"à l'approximation $3^5$\" est au moins 6."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "valuation(Padic(0, 3, 5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : Soit $x=(x_n)_{n\\ge 1}\\in\\mathbb Z_p\\setminus\\{0\\}$. On a \n",
    "- Pour tout $n\\ge 1$, $p^{v_p(x)}$  divise $x_n$.\n",
    "- Il existe $n\\ge 1$ tel que $p^{v_p(x)+1}$ ne divise pas $x_{n}$ (en l'occurrence, $n = v_p(x)+1$).\n",
    "- $v_p(x)$ est le seul entier vérifiant les deux points précédents.\n",
    "\n",
    "__Démonstration__ : Plaçons nous d'abord dans le cas où $v_p(x)=0$. Le premier point est trivial, puisqu'il faut montrer que pour tout $n\\ge 1$, 1 divise $x_n$. Le second point l'est aussi (trivial) puisque, comme $v_p(x)=0$,  $x_1\\ne 0$. Donc $p^1$ ne divise pas $x_1$. \n",
    "\n",
    "Supposons maintenant que $v = v_p(x)\\ge 1$. On a donc $x_1=\\ldots=x_{v}=0$ et $x_{v+1}\\ne 0$. Comme $x_{v+1}\\bmod p^v=x_{v}=0$, on en déduit que $p^{v}$ divise $x_{v+1}$. Pour tout $k\\ge v+1$, on a $x_k\\bmod p^{k-1}=x_{k-1}$ donc aussi $x_k\\bmod p^v=x_{k-1}$. On en déduit facilement que pour tout $k\\ge v+1, x_k\\bmod p^v= 0$. Si $k\\le v$ la congruence est évidente puisque $x_k=0$. Concernant le second point, $x_{v+1}\\ne 0$ et donc $x_{v+1}\\bmod p^{v+1}\\ne 0$.\n",
    "\n",
    "Le dernier point est clair, en y réfléchissant un peu :-).\n",
    "\n",
    "__Exercice__ : Réfléchissez."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Corollaire__ : Soit $x\\in\\mathbb Z_p\\setminus\\{0\\}$. On a $x=p^{v_p(x)}u$ où $v_p(u)=0$. Et $v_p(x)$ est le seul entier vérifiant cette propriété."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : On a pour tous entiers $p$-adiques $x$ et $y$ :\n",
    "\n",
    "- $v_p(xy)=v_p(x)+v_p(y)$\n",
    "- $v_p(x+y)\\ge \\min (v_p(x), v_p(y))$\n",
    "- Si $v_p(x)\\ne v_p(y)$ alors $v_p(x+y)=v_p(x)+v_p(y)$\n",
    "\n",
    "On fait bien entendu les conventions évidentes dans le cas où l'une des valuations est infinie.\n",
    "\n",
    "__Démonstration__ : Si $x=0$ ou $y=0$ la propriété est évidente. Supposons donc $x$ et $y$ non nuls. Par le corollaire précédent, on a $x=p^{v_p(x)}u$ où $v_p(u)=0$. De même, $y=p^{v_p(y)}u'$ où $v_p(u')=0$. \n",
    "- $xy=p^{v_p(x)+v_p(y)}uu'$. Maintenant, $u_1\\ne 0$ et $u'_1\\ne 0$ puisque $u$ et $u'$ sont de valuation nulle. Mais alors $u_1u'_1\\ne 0$ car $u_1,u'_1\\in\\mathbb Z/p\\mathbb Z$, qui est un corps. Voilà où intervient le fait que $p$ est premier. Donc, $v_p(uu')=0$.\n",
    "\n",
    "- Supposons par exemple $v(x)\\le v(y)$. On a $x+y=p^{v_p(x)}u+p^{v_p(y)}u'=p^{v_p(x)}u''$ où $u''=u+p^{v_p(y)-v_p(x)}u'$. Ainsi, $p^{v_p(x)}$ divise $x+y$, et $v_p(x+y)\\ge v_p(x)=\\min(v_p(x),v_p(y))$.\n",
    "\n",
    "- Supposons en plus que $v_p(x)<v_p(y)$. Reprenons $u''=u+p^{v_p(y)-v_p(x)}u'=u+p^ku'$ où $k>0$. On a alors $u''_1=u_1\\ne 0$ donc $v_p(u'')=0$. Ainsi, $v_p(x+y)=v_p(x)=\\min(v_p(x), v_p(y))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Corollaire__ : L'anneau $\\mathbb Z_p$ est intègre.\n",
    "\n",
    "__Démonstration__ : Soient $x, y\\in\\mathbb Z_p$. Supposons que $xy=0$. On a donc $v_p(xy)=v_p(x)+v_p(y)=\\infty$. Ceci n'est possible que si $v_p(x)=\\infty$ ou $v_p(y)=\\infty$, c'est à dire $x=0$ ou $y=0$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Remarque__ : Que se passe-t-il si on prend pour $p$ un entier non premier ? Eh bien $\\mathbb Z_p$ est toujours un anneau mais on perd l'intégrité. Nous verrons à la fin du notebook un exemple de deux entiers 10-adiques non nuls très intéressants dont le produit est nul."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 Les inversibles de $\\mathbb Z_p$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : Soit $x\\in\\mathbb Z_p$. $x$ est inversible pour la multiplication si et seulement si $v_p(x)=0$.\n",
    "\n",
    "__Démonstration__ : Supposons $x$ inversible. Il existe $y\\in\\mathbb Z_p$ tel que $xy=1$. On a donc $v_p(xy)=v_p(x)+v_p(y)=v_p(1)=0$. Ainsi, $v_p(x)=v_p(y)=0$.\n",
    "\n",
    "Inversement, supposons $v_p(x)=0$. On a donc $x_1\\ne 0$. La suite $x$ est cohérente, donc $p$ ne divise aucun des $x_n$ (facile), ce qui prouve que les $x_n$ sont premiers avec $p^n$. Rappelons que $p$ est premier ! Pour tout $n\\ge 1$, notons $y_n$ l'inverse de $x_n$ dans $\\mathbb Z/p^n\\mathbb Z$. Pourquoi un tel $y_n$ existe-t-il ? Eh bien, d'après le théorème de Bézout, comme $x_n$ et $p^n$ sont premiers entre eux, il existe deux entiers $y_n$ et $z_n$ tels que $x_ny_n+p^nz_n=1$. En réduisant l'égalité modulo $p^n$ il vient $x_ny_n=1$. Soit $y=(y_n)_{n\\ge 1}$. Admettons provisoirement que la suite $(y_n)$ est cohérente. On a alors $x.y=(x_n.y_n)=(1)$, le neutre pour la multiplication dans $\\mathbb Z_p$.\n",
    "\n",
    "Soyons courageux et montrons que la suite $(y_n)$ est cohérente. Soit $n\\ge 1$. On a $x_{n+1}y_{n+1}=1\\equiv 1[p^{n+1}]$. Par ailleurs, la suite $(x_n)$ étant cohérente, il existe $\\lambda\\in\\mathbb Z$ tel que $x_{n+1}=x_n+\\lambda p^n$. De là $x_{n+1}y_{n+1}= (x_n+\\lambda p^n)y_{n+1}\\equiv 1[p^n]$ ou encore $x_ny_{n+1}\\equiv 1[p^n]$. Mais on a $x_ny_n\\equiv 1[p^n]$. En soustrayant, on obtient $x_n(y_{n+1}-y_n)\\equiv 0[p^n]$. Mais comme $x_n$ est inversible dans $\\mathbb Z/p^n\\mathbb Z$, on en déduit que $y_{n+1}-y_n\\equiv 0[p^n]$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ça y est, nous tenons les inversibles ! Nous savons qui inverser, reste à savoir comment. La démonstration de la proposition nous le dit, il suffit d'appliquer le théorème de Bézout pour trouver des inverses dans $\\mathbb Z/p^n\\mathbb Z$. Comment appliquer le théorème de Bézout ? En utilisant l'algorithme d'Euclide. La fonction `invmod` ci-dessous prend en paramètres deux entiers $x$ et $n$ tels que $x$ est premier avec $n$. Elle effectue l'algorithme d'Euclide pour renvoyer un entier $y$ tel que $xy\\equiv 1[n]$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def invmod(x, n):\n",
    "    u1, v1, r1 = 1, 0, x\n",
    "    u2, v2, r2 = 0, 1, n\n",
    "    while r2 != 0:\n",
    "        q = r1 // r2\n",
    "        u = u1 - q * u2\n",
    "        v = v1 - q * v2\n",
    "        r = r1 - q * r2\n",
    "        u1, v1, r1 = u2, v2, r2\n",
    "        u2, v2, r2 = u, v, r\n",
    "    assert r1 == 1\n",
    "    return u1 % n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "invmod(2, 3 ** 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "(2 * _) % (3 ** 10) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et voici la fonciton `inverse`. Elle prend un entier $p$-adique $x$ en paramètre et renvoie $x^{-1}$ dans le cas où $v(x)=0$. Sinon, la fonction lève une exception. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def inverse(x):\n",
    "    v = valuation(x)\n",
    "    if v != 0:\n",
    "        raise Exception('Non inversible')\n",
    "    else:\n",
    "        y = invmod(x.n, x.p ** x.N)\n",
    "        return Padic(y, x.p, x.N)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Maintenant nous pouvons inverser et diviser dans $\\mathbb Z_p$. Essayons. Quel est l'inverse de $17$ dans $\\mathbb Z_3$ ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = Padic(1, 3, 20) / Padic(17, 3, 20)\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(x.termes())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bigre ... Comme on n'est pas obligé d'y croire, vérifions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x * Padic(17, 3, 20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Maintenant, nous voilà convaincus que $\\mathbb Z_p$ contient des objets intéressants. Par exemple, $\\frac 1 {17}$ est un __ENTIER__ 3-adique. Et de façon plus générale, tout rationnel $\\frac p q$ où $q$ n'est pas un multiple de 3 est aussi un entier 3-adique. Voici les 1000 derniers chiffres de l'entier 3-adique égal à la célèbre fraction $\\frac{355}{113}$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = Padic(355, 3, 1000) / Padic(113, 3, 1000)\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 Valeur absolue $p$-adique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Définition__ : Pour tout $x\\in\\mathbb Z_p$, on pose $|x|_p=p^{-v_p(x)}$, avec la convention que $p^{-\\infty}=0$. La quantité $|x|_p$ est appelée la valeur absolue $p$-adique de $x$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def vabs(x):\n",
    "    v = valuation(x)\n",
    "    return x.p ** (- v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "vabs(Padic(63, 3, 8))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : On a les propriétés suivantes :\n",
    "- Pour tout $x\\in\\mathbb Z_p$, $|x|_p\\in\\mathbb R_+$\n",
    "- Pour tout $x\\in\\mathbb Z_p$, $|x|_p=0$ si et seulement si $x=0$.\n",
    "- Pour tous $x, y\\in\\mathbb Z_p$, $|xy|_p=|x|_p|y|_p$\n",
    "- Pour tous $x, y\\in\\mathbb Z_p$, $|x+y|_p\\le\\max(|x|_p,|y|_p)$ (inégalité ultramétrique)\n",
    "\n",
    "L'inégalité ultramétrique implique évidemment que $|x+y|_p\\le|x|_p+|y|_p$ ... et bien d'autres choses. C'est elle qui fait de $\\mathbb Z_p$ un ensemble bizarre.\n",
    "\n",
    "__Démonstration__ : Laissée en exercice, il suffit d'utiliser les propriétés de la valuation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3 Distance $p$-adique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Munis d'une valeur absolue, nous pouvons maintenant définir une _distance_ sur $\\mathbb Z_p$ pour en faire un _espace métrique_. Pour tous $x,y\\in\\mathbb Z_p$, posons $d_p(x,y)=|y-x|_p$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : La fonction $d_p$ est une _distance_ sur l'ensemble $\\mathbb Z_p$. Précisément :\n",
    "\n",
    "- Pour tous $x, y\\in\\mathbb Z_p$, $d_p(x,y)\\in\\mathbb R_+$\n",
    "- Pour tous $x, y\\in\\mathbb Z_p$, $d_p(x,y)=0$ si et seulement si $x=y$.\n",
    "- Pour tous $x, y, z\\in\\mathbb Z_p$, $d_p(x,z)\\le\\max(d_p(x,y),d_p(y,z))$ (inégalité ultramétrique)\n",
    "\n",
    "L'inégalité ultramétrique entraîne bien évidemment l'inégalité triangulaire : $d_p(x,z)\\le d_p(x,y)+d_p(y,z)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def distance(x, y):\n",
    "    return vabs(y - x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "distance(Padic(8, 3, 10), Padic(-1, 3, 10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.4 Suites convergentes dans $\\mathbb Z_p$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Considérons la somme $S_n=\\sum_{k=0}^n 2^k=2^{n+1}-1$. Considérons cet entier comme un élément de $\\mathbb Z_2$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "S20 = Padic(2 ** 20 - 1, 2, 30)\n",
    "print(S20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La distance entre $S_{20}$ et $-1$ est inférieure à $10^{-6}$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(distance(S20, Padic(-1, 2, 30)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Plus généralement, on a $|S_n-(-1)|_2=|2^{n+1}|=\\frac{1}{2^{n+1}}$. Cette quantité tend vers 0 lorsque $n$ tend vers l'infini."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Définition__ : Soit $(u_n)_{n\\ge 0}$ une suite d'éléments de $\\mathbb Z_p$. Soit $\\ell\\in\\mathbb Z_p$. On dit que $u_n$ tend vers $\\ell$ lorsque $n$ tend vers l'infini lorsque $|u_n-\\ell|_p$ tend vers 0.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Munis de notre définition, nous concluons que $1+2+2^2+\\ldots+2^n\\to -1$ lorsque $n\\to \\infty$. Dit autrement,\n",
    "\n",
    "$$\\sum_{n=0}^\\infty 2^n=-1$$\n",
    "\n",
    "Impossible, me direz-vous ? Éduqués dans la $\\mathbb R$-attitude, nous avons du mal à concevoir le monde de $\\mathbb Z_p$. Mais le fait est là, l'anneau $\\mathbb Z_p$ a été construit, une notion de convergence a été définie. Le reste n'est que raisonnements. Et si le résultat nous déplait, nous n'y pouvons rien :-)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Revenons sur le vocabulaire introduit au début du notebook. Si $x=(x_n)_n\\ge 1$ nous avons appelé la liste $[x_1,x_2,\\ldots,x_N]$ __l'approximation__ de $x$ à l'ordre $N$. Pourquoi \"approximation\" ? Posons $u_N=(x_1,\\ldots,x_N,0,0,0,\\ldots)$. On a $x-u_N=(0,\\ldots, 0, x_{N+1},x_{N+1},\\ldots)$. Ainsi, $v_p(x - u_N)\\ge N + 1$ et donc\n",
    "$$d_p(u_N, x)\\le \\frac 1 {p^{N+1}}$$\n",
    "On en déduit que $u_N\\to x$ lorsque $N$ tend vers l'infini. Le mot \"approximation\" est donc tout à fait mérité : $u_N$ est une approximation de $x$ à $p^{-N-1}$ près."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Remarquons que pour tout $N$, $u_N$ est lui-même une suite. Cette suite est stationnaire (elle finit par des zéros), donc $u_N$ est un __entier naturel__. Que venons nous de montrer ? Nous venons de prouver que tout entier $p$-adique est la limite d'une suite d'entiers naturels.\n",
    "\n",
    "__Proposition__ : $\\mathbb N$ est __dense__ dans $\\mathbb Z_p$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Remarquez que cela entraîne que tout entier négatif est la limite d'une suite d'entiers naturels :-).\n",
    "\n",
    "__Exercice__ : On prend $p=2$. Trouvez une suite d'entiers naturels qui tend vers $-13$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.5 Le monde étrange des nombres $p$-adiques"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La vie dans $\\mathbb Z_p$ est vraiment étrange. Pour vous donner un vague aperçu de vos prochaines vacances je me contenterai de deux résultats."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : Dans $\\mathbb Z_p$, tous les triangles sont isocèles.\n",
    "\n",
    "__Démonstration__ : Soient $a,b,c\\in\\mathbb Z_p$. Soient $d=|a-b|_p$, $d'=|b-c|_p$ et $d=|a-c|_p$. Pour fixer les idées, supposons par exemple $d\\le d'\\le d''$. On a $d''=|a-c|_p=|(a-b)+(b-c)|_p$. L'inégalité ultramétrique vue au début du paragraphe sur la valeur absolue $p$-adique nous prouve que \n",
    "$$d''=|a-c|_p=|(a-b)+(b-c)|_p\\le \\max(d,d')=d'$$\n",
    "\n",
    "Ainsi, $d\\le d'\\le d''\\le d'$. Dans un triangle, _les deux côtés les plus grands_ sont égaux."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Définition__ : Soient $a\\in\\mathbb Z_p$ et $r>0$. On appelle boule de centre $a$ et de rayon $r$ l'ensemble\n",
    "\n",
    "$$B(a,r)=\\{x\\in\\mathbb Z_p, |x-a|_p<r\\}$$\n",
    "\n",
    "Rien de bien original, sauf que ...\n",
    "\n",
    "__Proposition__ : Pour tout $b\\in B(a, r)$ on a $B(b, r) = B(a, r)$. Dit autrement, tout point dans une boule est __UN__ centre  d'une boule. Les boules ont des tonnes de centres.\n",
    "\n",
    "__Démonstration__ : Soit $x\\in B(b, r)$. Le triangle $(abx)$ est isocèle, ses deux plus grands côtés étant égaux. Or $d_p(b,a)<r$ et $d_p(b,x)<r$. Donc $d_p(a,x)<r$ sinon le plus grand côté du triangle serait plus grand que les deux autres. Ainsi, $x\\in B(a, r)$ et donc $B(b,r)\\subset B(a, r)$.\n",
    "\n",
    "Comme $b\\in B(a,r)$, on a $d_p(a,b)<r$ et donc $a\\in B(b, r)$. La situation étant symétrique en $a$ et $b$, on a donc aussi $B(a,r)\\subset B(b, r)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Exercice__ : Montrer que si deux boules (pas forcément de même rayon) ont UN point commun, alors l'une des deux est incluse dans l'autre.\n",
    "\n",
    "__Exercice__ : Montrer que $\\mathbb Z_p$ est la réunion de $p$ boules disjointes de rayon 1. Considérer pour cela les boules $B(k, 1)$ pour $k=0,1,\\ldots,p-1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. La méthode de Newton"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le nombre 2 a-t-il une racine carrée ? Ben oui, c'est $\\sqrt 2$. Dans $\\mathbb R$, certes. Mais dans ... $\\mathbb Z_7$ ?? Il y aurait donc des irrationnels dans $\\mathbb Z7$ ? Nous allons voir que oui. Un algorithme ébauché par Newton (dans un cadre très différent !) au XVIIe siècle permet de trouver des solutions à des équations dans $\\mathbb Z_p$, comme par exemple l'équation $x^2-2=0$. Nous terminerons ce notebook par une tentative audacieuse, prendre $p=10$ pour trouver un objet $x$ tel que $x^2=x$ dans $\\mathbb Z_{10}$, cet $x$ n'étant ni 0, ni 1. Nous en trouverons même deux."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Remarquons tout d'abord que si $x\\in\\mathbb Z_p\\setminus\\{0\\}$ possède une racine carrée $y$, il en possède exactement deux. En effet, si $z^2=x$, alors $z^2=y^2$ donc $(z-y)(z+y)=0$. Mais $\\mathbb Z_p$ est intègre, propriété essentielle, donc n'admet pas de diviseurs de 0. Ainsi, $z=\\pm y$. Inversement, $(\\pm y)^2=y^2=x$. Bien entendu, si $p$ n'est premier, rien n'empêche $x$ d'avoir 5 ou 6 racines carrées ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 Remontée modulaire"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $f:\\mathbb Z_p\\to \\mathbb Z_p$, disons un polynôme pour fixer les idées.\n",
    "\n",
    "Suppposons connu $x$ tel que $v_p(f(x))\\ge k$, où $k\\ge 1$. Peut-on trouver $x'$ tel que $v_p(f(x'))\\ge k+1$ ? Oui si $f'(x)\\not\\equiv 0[p^k]$.\n",
    "\n",
    "Soit $x'=x-f(x)f'(x)^{-1}$. Nous avons $f(t)=f(x)+(t-x)f'(x)+(t-x)^2Q(t)$ où $Q$ est un polynôme. Prenons $t=x'$ : \n",
    "\n",
    "$$f(x')=f(x)+(x'-x)f'(x)+(x'-x)^2Q(x')=f(x)^2f'(x)^2Q(x')$$ \n",
    "\n",
    "Ainsi,\n",
    "\n",
    "$$v_p(f(x'))=2v_p(f(x))+2v_p(f'(x))+2v_p(Q(x'))\\ge 2v_p(f(x))\\ge 2k\\ge k+1$$\n",
    "\n",
    "puisque $k\\ge 1$.\n",
    "\n",
    "Remarquons également que \n",
    "\n",
    "$$v_p(x'-x)=v_p(-f(x)f'(x)^{-1})=v_p(f(x))+v_p(f'(x)^{-1})=v_p(f(x))\\ge k$$\n",
    "\n",
    "Ainsi, $|x'-x|_p <\\frac 1 {p^k}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction `lift` prend en paramètres une fonction $f$, sa dérivée $f_1$, un entier $p$-adique $x$. Elle suppose que $v_p(f(x))\\ge k$, où $k\\ge k$. La fonction renvoie un entier $p$-adique $x'$ tel que $v_p(f(x'))\\ge k+1$ et $|x'-x|_p <\\frac 1 {p^k}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lift(f, f1, x):\n",
    "    return x - f(x) / f1(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Prenons un petit exemple. Soit $f:x\\mapsto x^2-2$. Soit $p=7$. Nous avons $3^2\\equiv 2[7]$. Donc $v_7(f(3))\\ge 1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lift(lambda x:x ** 2 - Padic(2, 7, 20), lambda x:Padic(2, 7, 20) * x, Padic(3,7,20))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le nombre $x'$ renvoyé ci-dessus vérifie donc $v_7(f(x'))\\ge 2$. Rien ne nous empêche de recommencer :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lift(lambda x:x ** 2 - Padic(2, 7, 20), lambda x:Padic(2, 7, 20) * x, _)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lift(lambda x:x ** 2 - Padic(2, 7, 20), lambda x:Padic(2, 7, 20) * x, _)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lift(lambda x:x ** 2 - Padic(2, 7, 20), lambda x:Padic(2, 7, 20) * x, _)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lift(lambda x:x ** 2 - Padic(2, 7, 20), lambda x:Padic(2, 7, 20) * x, _)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lift(lambda x:x ** 2 - Padic(2, 7, 20), lambda x:Padic(2, 7, 20) * x, _)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ça ne bouge plus ... automatisons tout cela !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3 Le lemme de Hensel"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Proposition__ : Soit $f:\\mathbb Z_p\\to\\mathbb Z_p$ une fonction polynôme (pour fixer les idées). Soit $x_1\\in\\mathbb Z_p$ tel que $v_p(f(x_1))\\ge 1$ et $v_p(f'(x_1))=0$. Soit la suite $(x_n)_{n\\ge 1}$ définie par $x_{n+1}=x_n-f(x_n)f'(x_n)^{-1}$. Alors :\n",
    "\n",
    "- La suite $(x_n)$ est une suite qui est bien définie et qui tend vers $x\\in\\mathbb Z_p$ tel que $f(x)=0$.\n",
    "- $x$ est l'unique racine $x$ de $f$ telle que $x\\bmod p = x_1$.\n",
    "\n",
    "Ce notebook est déjà bien long. Je ne prouverai pas ce résultat et vous dirai simplement que nous avons en déjà beaucoup montré (mais pas tout) dans le paragraphe __3.2__. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Écrivons une fonction qui calcule tout cela. La fonction `newton` prend en paramètres une fonction $f:\\mathbb Z_p\\to\\mathbb Z_p$, sa dérivée $f_1$, un nombre premier $p$ et un entier $N$. Elle renvoie une racine de l'équation $f(x)=0$ à l'approximation $N$. Dit autrement, elle renvoie $x\\in\\mathbb Z_p$ tel que $v_p(x)>N$, ou encore $|f(x)|_p<\\frac {1}{p^N}$.\n",
    "\n",
    "La fonction `newton` prend également un paramètre optionnel `guess`. Si `guess` est différent de `None`, ce doit être un entier $p$-adique $k$ tel que $f(k)\\bmod p=0$. Si `guess` vaut `None`, un appel à `find_root` trouve un tel entier. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def newton(f, f1, p, N, guess=None):\n",
    "    if guess == None:\n",
    "        x = find_root(f, p, N)\n",
    "    else:\n",
    "        x = guess\n",
    "    while valuation(f(x)) <= N:\n",
    "        x = lift(f, f1, x)\n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Que fait `find_root` ? C'est en fait le point problématique. Elle teste tous les entiers $k$ de 0 à $p-1$ jusqu'à ce qu'elle en trouve (ou pas) un tel que $f(k)\\bmod p=0$. Ceci est totalement inefficace lorsque $p$ est grand, mais je ne discuterai pas plus avant de ce sujet. Pour les personnes intéressées, le notebook sur les résidus quadratiques permet de répondre à la question pour la fonction $x\\mapsto x^2-a$ : l'algorithme de Tonnelli-Shanks y est détaillé, il permet un calcul très efficace d'une racine carrée modulo $p$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_root(f, p, N):\n",
    "    for k in range(p):\n",
    "        x = Padic(k, p, N)\n",
    "        if valuation(f(x)) > 0: return x\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = newton(lambda x:x ** 2 - Padic(2, 7, 20), lambda x:Padic(2, 7, 20) * x, 7, 20)\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.4 Racine carrée d'un entier $p$-adique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'exemple ci-dessus nous montre que $2$ a une racine carrée (et donc deux) dans $\\mathbb Z_7$. Automatisons le procédé : la fonction `sqrt` prend un entier $p$-adique $x$ en paramètre et renvoie une des deux racines carrées de $x$ (à la même précision que $x$) si $x$ possède une racine carrée."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sqrt(x):\n",
    "    return newton(lambda t:t ** 2 - x, lambda t: Padic(2, x.p, x.N) * t, x.p, x.N)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici une racine carrée de 2 dans $\\mathbb Z_7$ avec 1000 chiffres avant la virgule."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = sqrt(Padic(2, 7, 1000))\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Un autre exemple : $i\\in\\mathbb Z_5$. Dit autrement, $-1$ a une racine carrée dans $\\mathbb Z_5$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = sqrt(Padic(-1, 5, 1000))\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(- x * x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.5 Deux nombres bizarres dans $\\mathbb Z_{10}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Trouvons tous les entiers $x$ tels que $x^2=x$. \n",
    "\n",
    "0 et 1, me direz-vous ? Oui, certes, mais si je vous parle d'entiers 10-adiques ? Alors il y en a 4. En effet il y a 4 entiers entre 0 et 9 tels que $x^2\\equiv x[10]$, à savoir 0, 1, 5 et 6. Car $5\\times 5 =25\\equiv 5[10]$ et $6\\times 6=36\\equiv 6[10]$.\n",
    "\n",
    "Lançons la fonction `newton` avec $f(x)=x^2-x$ et, hasardeusement, $p=10$ (je rappelle que 10 n'est pas premier). Prenons une valeur du paramètre `guess` égale à 5."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = newton(lambda x:x ** 2 - x, lambda x: Padic(2, 10, N) * x - Padic(1, 10, N), 10, N, Padic(5, 10, N))\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Relançons avec `guess=6`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "b = newton(lambda x:x ** 2 - x, lambda x: Padic(2, 10, N) * x - Padic(1, 10, N), 10, N, Padic(6, 10, N))\n",
    "print(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Juste pour voir, calculons $a+b$ et $ab$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a + b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a * b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Diantre, aurait-on $a+b=1$ et $ab=0$ ? Cette deuxième égalié prouverait que $\\mathbb Z_{10}$ n'est pas un anneau intègre !\n",
    "\n",
    "__Proposition__ : $a+b=1$ et $ab=0$.\n",
    "\n",
    "__Démonstration__ : $(ab)^2=a^2b^2=ab$. Donc $ab$ est solution de l'équation $x^2=x$. En remarquant que $a=...5$ et $b=...6$ nous voyons que $ab \\bmod 10 = 0$. En espérant qu'il reste quelque chose du lemme de Hensel pour $p=10$, on en déduit que $ab=0$.\n",
    "\n",
    "Par ailleurs $(a+b)^2=a^2+2ab+b^2=a+0+b=a+b$ donc $a+b$ est aussi solution de l'équation $x^2=x$. Mais $a+b\\bmod 10= 5+6= 1$ (on est dans $\\mathbb Z/10\\mathbb Z$) et donc, toujours par le lemme de Hensel, $a+b=1$.\n",
    "\n",
    "__Exercice__ : Montrer que $\\mathbb Z_{10}\\sim \\mathbb Z_5 \\times \\mathbb Z_2$, en considérant l'application $x\\mapsto (ax,bx)$, $a$ et $b$ étant nos deux nombres magiques."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La conséquence sur les entiers normaux, me direz-vous ? Eh bien nous venons de trouver deux nombres $u$ et $v$ de $N$ chiffres tels que leurs $N$ derniers chiffres sont les nombres de départ. Et nous savons faire cela pour tout $N$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "u, v = a.n, b.n\n",
    "print(u)\n",
    "print(u ** 2)\n",
    "\n",
    "print(v)\n",
    "print(v ** 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vous préférez 1000 chiffres ? Ce sera notre test ultime."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = 1000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = newton(lambda x:x ** 2 - x, lambda x: Padic(2, 10, N) * x - Padic(1, 10, N), 10, N, Padic(5, 10, N))\n",
    "b = newton(lambda x:x ** 2 - x, lambda x: Padic(2, 10, N) * x - Padic(1, 10, N), 10, N, Padic(6, 10, N))\n",
    "print('a =', a)\n",
    "print('b =', b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et le fait que $a+b=1$ et $ab=0$, que nous raconte-t-il sur leurs approximations $u$ et $v$ ? Regardez, vu les valeurs de $u$ et $v$ on n'aurait pas pu le deviner sans notre petite théorie. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "u = a.n\n",
    "v = b.n\n",
    "print('u + v =', u + v)\n",
    "print('uv    =', u * v)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Et ensuite ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'ensemble $\\mathbb Z_p$ des entiers $p$-adiques est un anneau intègre, tout comme $\\mathbb Z$. Un théorème sur les anneaux nous dit que tout anneau intègre $\\mathbb A$ possède un __corps de fractions__, c'est à dire qu'il existe un corps $\\mathbb K$ contenant $\\mathbb A$ et tel que, dans un certain sens, $\\mathbb K=\\{\\frac x y, x,y\\in\\mathbb A,y\\ne 0\\}$.\n",
    "\n",
    "Le corps des fractions de $\\mathbb Z$ est bien connu, il s'agit de $\\mathbb Q$. Celui de $\\mathbb Z_p$ est appelé le corps des nombres $p$-adiques, et est noté $\\mathbb Q_p$. On peut montrer que \n",
    "\n",
    "$$\\mathbb Q_p =\\{\\frac{x}{p^n}, x\\in\\mathbb Z_p, n\\in\\mathbb N\\}$$\n",
    "\n",
    "Programmer une classe \"nombre $p$-adique\" n'est pas bien compliqué, il suffit de rajouter à la classe `Padic` un champ qui contient la puissance $n$ du dénominateur de nos fractions. Les opérations sur $\\mathbb Q_p$ sont également très faciles à écrire. Faites-le !\n",
    "\n",
    "Malgré la notation, $\\mathbb Q_p$ est un analogue de $\\mathbb R$ (et pas de $\\mathbb Q$). En fait, tout comme $\\mathbb R$, $\\mathbb Q_p$ contient le corps $\\mathbb Q$ des nombres rationnels, $\\mathbb Q$ est dense dans $\\mathbb Q_p$, et $\\mathbb Q_p$ est __complet__, en un sens que je ne préciserai pas plus ici (suites de Cauchy).\n",
    "\n",
    "Et ensuite ? Peut-on faire dans $\\mathbb Q_p$ de l'analyse ? Suites ? Séries ? Fonctions continues ? Dérivées ? Intégrales ? Nombres complexes $p$-adiques ? Oui, mais ceci est une autre histoire."
   ]
  },
  {
   "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
}