{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Nombres premiers\n",
    "\n",
    "La suite des nombres premiers\n",
    "\n",
    "$$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 \\ldots$$\n",
    "\n",
    "intrigue les mathématiciens depuis l'antiquité. \n",
    "\n",
    "Dans les [Éléments d'Euclide](https://fr.wikipedia.org/wiki/%C3%89l%C3%A9ments_%28Euclide%29), on trouve déjà les énoncés suivants :\n",
    "\n",
    "- *Tout entier $>1$ est divisible par un nombre premier*\n",
    "\n",
    "En effet, si $n>1$ n'est pas lui-même premier, il possède des diviseurs non triviaux. Soit $p$ le plus petit\n",
    "d'entre eux. Alors, $p$ est premier, car sinon il aurait un diviseur non trivial $1\\lt d\\lt p$ qui diviserait $n$.\n",
    "\n",
    "- *Tout entier $>1$ se décompose en produit de facteurs premiers, de manière unique à l'ordre près des facteurs*\n",
    "\n",
    "En itérant l'énoncé précédent, si $n$ n'est pas premier, on peut l'écrire $n=p_1n_1$ avec $p_1$ premier, et on \n",
    "recommence avec $n_1$ jusqu'à aboutir à $n_{k-1}=p_kn_k$ avec $n_k=p_{k+1}$ premier, car on ne peut pas continuer indéfiniment.\n",
    "Alors, $n=p_1\\cdots p_{k+1}$.\n",
    "\n",
    "L'unicité de la décomposition est moins évidente. On a besoin de l'énoncé suivant :\n",
    "\n",
    "- *Si un nombre premier $p$ divise un produit $ab$ alors il divise l'un des facteurs.*\n",
    "\n",
    "On peut le prouver avec l'identité de Bézout. Si $p$ ne divise pas $a$ alors $a\\wedge p=1$ et donc on peut\n",
    "trouver $u,v$ tels que $au+vp=1$. Alors, \n",
    "$uab+vbp=b$ et comme $p$ divise $ab$ et $pb$, il divise $b$.\n",
    "\n",
    "On peut maintenant en déduire l'unicité de la décomposition en facteurs premiers. Si on suppose\n",
    "$$n=p_1^{a_1}p_2^{a_2}\\cdots p_k^{a_k} = q_1^{b_1}q_2^{b_2}\\cdots q_l^{b_l}$$\n",
    "alors chaque $p_i$ divise le produit $q_1^{b_1}q_2^{b_2}\\cdots q_l^{b_l}$, donc divise l'un des facteurs.\n",
    "Ainsi, chaque $p_i$ est un $q_j$ et symétriquement, chaque $q_j$ est un $p_i$. Donc $k=l$ et les deux décompositions\n",
    "sont identiques à l'ordre près.\n",
    "\n",
    "- *La suite des nombres premiers est infinie.*\n",
    "\n",
    "Si $p_1,\\ldots,p_n$ sont les $n$ premiers nombres premiers,  $N=p_1p_2\\cdots p_n + 1$ n'est divisible\n",
    "par aucun d'entre eux. Or il est divisible par un nombre premier, la liste $p_1,\\cdots,p_n$ ne les contient\n",
    "donc pas tous.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "Il n'existe aucune formule exacte pour le $n$-ième nombre premier $p_n$. Cependant, il existe un formule\n",
    "asymptotique\n",
    "$$p_n \\sim_{+\\infty} n \\ln n,$$\n",
    "conjecturée vers la fin du XVIIIème siècle par Legendre et par Gauss, et prouvée seulement un siècle plus tard,\n",
    "en 1896, indépendament par Hadamard et de la Vallée-Poussin.\n",
    "\n",
    "Ce résultat, appelé *théorème des nombres premiers*, s'appuie sur des travaux de Riemman de 1850 utilisant les\n",
    "fonctions de variables complexes, et développant un idée qui remonte à Euler."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from ent3 import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.3862943611198906"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "log(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from math import *\n",
    "pp = primes(100000)\n",
    "qq = [float(n*log(n)) for n in range(1,len(pp))] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x7f0028632978>]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZgAAAD8CAYAAABKKbKtAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XlcVXX+x/HXBxVcUNxxwV1zX1JcM9O0XLIsc6ucrDH9\nzbSvppZlu1pZto9lo1mmpqbmmntabrgDgqK4gIgiAgqy3fv9/XGODeNUKtzLBe7n+Xjw4PK995zz\n/TLGe875bmKMQSmllHI1H09XQCmlVNGkAaOUUsotNGCUUkq5hQaMUkopt9CAUUop5RYaMEoppdxC\nA0YppZRbaMAopZRyCw0YpZRSblHc0xVwtcqVK5u6det6uhpKKVWo7Nq1K8EYU8WV5yxyAVO3bl1C\nQkI8XQ2llCpUROS4q8+pj8iUUkq5hQaMUkopt9CAUUop5RYaMEoppdxCA0YppZRbXDVgRORrETkj\nIqE5yiqKyBoROWx/r5DjvXEiEiUikSLSO0d5OxE5YL/3kYiIXe4nIvPs8u0iUjfHMSPsaxwWkRGu\narRSSin3u5Y7mJlAnyvKxgLrjDGNgHX2z4hIM2AY0Nw+5jMRKWYf8zkwCmhkf10+50jgvDGmIfAB\nMNk+V0XgVaAj0AF4NWeQKaWUKtiuGjDGmF+AxCuKBwCz7NezgLtzlM81xmQYY6KBKKCDiFQHyhlj\nthlrj+Zvrjjm8rkWAD3tu5vewBpjTKIx5jywhv8NOqWUUsDa8Hjmh5z0dDX+S277YAKNMXH269NA\noP26JpCzhTF2WU379ZXl/3WMMSYbSAYq/cW5/oeIjBaREBEJOXv2bC6bpJRShU9aZjZjFuzjkW9C\nmLvjBE6n8XSVfpfnmfzGGCMiHm2RMWY6MB0gODi44Px2lVLKjcJPpfDs/L1Exl/g0e4NeKpXI3x8\nxNPV+l1uAyZeRKobY+Lsx19n7PJYoFaOzwXZZbH26yvLcx4TIyLFgQDgnF3e/YpjNuayvkopVWQY\nY5j12zHeXhFBQOkSfD2iPT2aVPV0tf5Hbh+RLQUuj+oaASzJUT7MHhlWD6szf4f9OC1FRDrZ/SsP\nXnHM5XMNAtbb/TSrgdtFpILduX+7XaaUUl7rfGomo77ZxcSfwrm5UWVWP92tQIYLXMMdjIh8j3Un\nUVlEYrBGdk0C5ovISOA4MATAGBMmIvOBcCAbeMwY47BP9SjWiLRSwEr7C2AGMFtEorAGEwyzz5Uo\nIm8AO+3PvW6MuXKwgVJKeY2tR87xzLy9JKZm8kr/Zjx8U13sGR8Fklg3C0VHcHCw0dWUlVJFSbbD\nybR1h/lkQxT1KpXho/tupEXNAJdeQ0R2GWOCXXnOIrdcv1JKFSVxyZd4Ys4eQo6fZ3C7ICbe1Zwy\nfoXjT3fhqKVSSnmhzYfP8tTcvWRmO5k2rA0D2vzhTI0CSwNGKaUKmJT0LKasiuDbbSdoVNWfz4e3\npWHVsp6u1nXTgFFKqQJk8+GzPDd/H2cvZjCyaz2ev70xpXyLXf3AAkgDRimlCoC0zGwmr4xg1tbj\nNKhShq9GBNMqqLynq5UnGjBKKeVhYaeSeWLOHo4mpPJQl7qM7duEkiUK511LThowSinlIcYYFu6O\nZeLSMPz9ijPnkY50aVjZ09VyGQ0YpZTygNPJ6YxbtJ8NkWdpV6cCn97flmoBJT1dLZfSgFFKqXzk\ncBrm7jzBpJURZDmcvNK/GSO61KVYAVqk0lU0YJRSKp/EnE/jie/3sOdEEp3qV2TSwFbUrVzG09Vy\nGw0YpZTKB1sOJ/D0vL2kZzmYOqQ199xYs0CvI+YKGjBKKeVGGdkOXvspnDnbT9CgShm+H9WRRoGF\nb9JkbmjAKKWUm8QmXeLR73az72QSo7vV59nbbigSw4+vlQaMUkq5mMNpmP7LUT5ad5hiPsLnD7Sl\nb8vqnq5WvtOAUUopF4o6c4EXFuxnz4kkbmsWyCv9m1GrYmlPV8sjNGCUUsoFMrOdfLn5KB+vP0xp\n3+K8N7g1g9oFXf3AIkwDRiml8iglPYtHv93NlqgEejUN5M27WxS5SZO5oQGjlFJ5cPxcKv/8djeH\n4i8wZVArhgTXyv9KZGfAlg/AGOgxLv+v/yc0YJRSKhecTsM3W4/xzsoI/Ir78NWIYLo3rpr/FTn2\nKyx7GhIOQev7rZApIPNrNGCUUuo6xaek8/wP+9h8OIFbm1TlzbtbUKN8qfytRFoirHkF9syG8nVg\n+EJo2Ct/63AVGjBKKXUdfo1K4Mnv95CW6eCte1pwf4fa+Tsj3xgIXQirxlohc9NTcMtY8C14I9U0\nYJRS6hpkZDt4b3UkX26OpmFVf+b9XzsaVvXP30qcPwbLnoUj66BmO/jbj1CtZf7W4TpowCil1FUc\nir/AU3P3cjAuheGdavNSv2b5u42xIwu2fQYb3gGfYtB3CrR/xHpdgGnAKKXUnzDGMGNLNFNWRVK2\nZHFmjAimZ9PA/K1EzC746SmIPwBN+lvhElAzf+uQSxowSin1B04np/Py4lDWHoynV9OqvDOwFVXK\n+uVfBTIuwLo3YMd0KFsNhn4LTe/Mv+u7gAaMUkpd4beoBP7x7S4ysp2M69uE0d3q529HfsRyWPEC\npJyCDqPg1glQslz+Xd9FNGCUUsqWme3kw7WH+HzTERpU8efLB4Opl58bgqWcsoIlYhlUbQ6DZ0Gt\n9vl3fRfTgFFKKeDMhXQe/XY3IcfPM6hdEK/d1Zwyfvn0J9LpgJCvYe1r4MyCXhOh8+NQrET+XN9N\nNGCUUl7NGMOPe2KZuDSMTIeTacPaMKBNPnainw61OvFjQ6B+D+g/FSrWz7/ru5EGjFLKa529kMHE\npWEsPxBHuzoVmHxvq/yb25KZBpsmw9ZPoGQADPwSWg4uMMu8uIJPXg4WkWdEJExEQkXkexEpKSIV\nRWSNiBy2v1fI8flxIhIlIpEi0jtHeTsROWC/95HYvWki4ici8+zy7SJSNy/1VUqpyzZEnqHPh7+w\n5mA8L/RuzA//1zn/wuXIevi8M/z6IbQaBo+HQKshRSpcIA8BIyI1gSeBYGNMC6AYMAwYC6wzxjQC\n1tk/IyLN7PebA32Az0Tk8iyhz4FRQCP7q49dPhI4b4xpCHwATM5tfZVSCqzhx8/M28vD/95JJX9f\nlj3Rlcd6NMTHJx/+uKcmwKLRMPsekGIw4ie4+1MoXdH91/aAvD4iKw6UEpEsoDRwChgHdLffnwVs\nBF4EBgBzjTEZQLSIRAEdROQYUM4Ysw1ARL4B7gZW2sdMtM+1APhERMQYY/JYb6WUF1oTHs/zP+zj\nUqaDx3s05PFbG1KyRD7MhjcG9n4HP78MGReh2xi4+TkoUbT3jMl1wBhjYkXkPeAEcAn42Rjzs4gE\nGmPi7I+dBi5Pe60JbMtxihi7LMt+fWX55WNO2tfLFpFkoBKQkNt6K6W8T2pGNpNWRjB723Fa1CzH\nJ/e1pW5+DT9OiLKW0z+2GWp1gjunQdUm+XNtD8t1wNh9KwOAekAS8IOIDM/5GWOMERG3322IyGhg\nNEDt2rXdfTmlVCHyW1QCLy7aT8z5S4y6uR7P926MX/F8uGvJzoAtH8Lm96B4Kej/IbQdAT556vou\nVPLyiKwXEG2MOQsgIouALkC8iFQ3xsSJSHXgjP35WCDnVm9Bdlms/frK8pzHxIhIcSAAOHdlRYwx\n04HpAMHBwfr4TCmF02n4cvNRJq2KoE7F0sz/v860r5tPfR3Ht1pDjxMiofk90GeStdyLl8lLwJwA\nOolIaaxHZD2BECAVGAFMsr8vsT+/FJgjIlOBGlid+TuMMQ4RSRGRTsB24EHg4xzHjAC2AoOA9dr/\nopS6msTUTP757S62RyfSt0U1pg5pkz+rH186D2snwq6ZEFAb7v8Bbrjd/dctoPLSB7NdRBYAu4Fs\nYA/WXYQ/MF9ERgLHgSH258NEZD4Qbn/+MWOMwz7do8BMoBRW5/5Ku3wGMNseEJCINQpNKaX+1KZD\nZxm7cD/nLmYy5d5WDA4Ocv86YsZA2CJYORbSEqxZ+D3Gg28+LjNTAElRuyEIDg42ISEhnq6GUiqf\nnbuYwYQloaw4cJq6lUrzyf1taVEzwP0XToyG5c9Zm4BVb2N14tdo4/7rupiI7DLGBLvynDqTXylV\n6G2IOMPzP+wjJT2LF3o35pGb67m/Iz87E377CH55F3yKQ5/J1srHBXwTsPykAaOUKrSyHU4mrYzg\nqy3RNKlWlu9GdaRJtXxY1v74Vmvo8dkIa4+WPpMLzSZg+UkDRilVKEWducgLC/ax50QSD3auw/h+\nTd0/aTItEda+Cru/gYBacN9caNzXvdcsxDRglFKFisNp+GrzUaauOYRfcR8+vu9G7mxdw70XNQb2\nz4fV462RYl2egFvGgl8+rV1WSGnAKKUKjdPJ6Tw5dw87ohPp1bQqbw9sSdWybl5uJSEKlj8L0Zug\nZjA8uBiqtXTvNYsIDRilVKGw4kAcYxfuJ8theH9wa+5tF3T1g/Li95n470NxP+j3HgT/XTvxr4MG\njFKqQEvNyOb1n8KZF3KS1kEBfDC0DfWruPnRVPRmWPYMnDsMzQdCn3e8ciZ+XmnAKKUKrAMxyTw5\ndw/HzqXyWI8GPN3rBkoUc+NaXqnnrBWP982B8nXggYXQqJf7rlfEacAopQqczGwn76+J5MtfjhJY\nriRzHulE5waV3HfB35fTnwAZKdD1Wej2AviWdt81vYAGjFKqQAk7lcyYBfsJO5XCkOAgxvdrSvnS\nvu674NlD1uOw41us5fT7fwCBzdx3PS+iAaOUKhDSsxx8vP4wX2w6SoXSvnwxvB19Wrix3yMr3erA\n3/KBdady5zS48UGvWk7f3TRglFIet+t4ImMW7OfI2VTubRvEhP5uvms5ssEaepx4FFoOgd5vgX9V\n913PS2nAKKU8Jj3Lwfs/R/LVlmhqBJRi1t87cMsNVdx3wYtnYPVLcGA+VKwPf1sMDXq473peTgNG\nKeUR+2OSeHb+PqLOXOT+jrUZ368p/n5u+pPkdMLuWdYyL5lp0G0M3PwclHDzJE0vpwGjlMp3M7ZE\n8/aKg1Tx92Pmw+3p3tiNj6fiw62FKU9uhzpdof9UqNLYfddTv9OAUUrlm9SMbCYuDeOHXTH0bh7I\nlEGtCShVwj0Xy0yDX6bAbx+DXzkY8Bm0uR/cvfmY+p0GjFIqX4TGJvPk93uIPpfK4z0a8nSvRhR3\n16TJw2usTcCSjkObB+C2N6CMG+fRqD+kAaOUciun0zBjSzRTVkdQ2d+P70d1olN9N/2xv3AaVo2F\nsB+hUiMYsQzq3eyea6mr0oBRSrlNbNIlxi7cz+bDCfRuHsjke1u5Z/ix0wEhX8O6161FKnu8BDc9\nZS1SqTxGA0Yp5XIOp+Gbrcd4d3UkTmN4654W3N+hNuKO/o9Te2DZs3BqN9S7xZqJX6mB66+jrpsG\njFLKpU4mpvHMvL2EHD/PLTdU4a17WhBUwQ1reqUnw/q3YOeXULoyDPwKWg7STvwCRANGKeUyGyLO\n8Pic3fiI8P7g1gxsW9P1dy3GQNgiWDUeLsZD+0fg1pehVHnXXkflmQaMUirPEi5mMHXNIeZsP0Gz\n6uWY/mA799y1nDtijQ47ugGqt4b75kDNdq6/jnIJDRilVJ6sCj3Ny4tDSUrL5KEudRnbtwklS7h4\n18esdPj1Q9g81eq47zvFunPR3SULNA0YpVSupGc5eHlxKAt2xdCsejlmj+xA0+rlXH+hI+utu5bE\no9DiXuj9tu4uWUhowCilrlt8SjqjZ+9i38kknri1IU/2bOT6nSYvnIbV4yF0ob0w5Y/Q4FbXXkO5\nlQaMUuqaZTucfL/zJNPWHiIt0+GePVucDtg5A9a/Adnp0H0c3PS0LkxZCGnAKKWuScz5NEZ9s4uD\ncSl0qFeRNwa0oHG1sq69SOxua3fJuL1Qvwfc8b7OaSnENGCUUle1aHcMExaHIiJ8/kBb+rSo5trh\nx5eSYP2bsPMra+OvQV9D84E6p6WQ04BRSv2pC+lZvLEsnPkhMXSoV5H3B7emVkUXDj82Bg4ssPpa\n0hKgw2i49SUoGeC6ayiP0YBRSv2hy6sfHzuXyqPdG/Dc7Y0p5uPCO4qEKGvb4uhNUONGeGC+9V0V\nGXka9iEi5UVkgYhEiMhBEeksIhVFZI2IHLa/V8jx+XEiEiUikSLSO0d5OxE5YL/3kdj33iLiJyLz\n7PLtIlI3L/VVSl2d02n4YtMR7vnsV1Izs5kzqhNj+jRxXbhkpcOGt+HzznBqL/R7Dx5Zp+FSBOV1\nXOE0YJUxpgnQGjgIjAXWGWMaAevsnxGRZsAwoDnQB/hMRC7PkvocGAU0sr/62OUjgfPGmIbAB8Dk\nPNZXKfUXTienM3zGdiatjKBnk0BWPdXNtUvrR62FzzrBpsnQbAA8vhM6jNIJk0VUrh+RiUgA0A14\nCMAYkwlkisgAoLv9sVnARuBFYAAw1xiTAUSLSBTQQUSOAeWMMdvs834D3A2stI+ZaJ9rAfCJiIgx\nxuS23kqp/2WMYem+U7y6NIyMLCeT723JkOBaruvIT4mD1ePsfVoawoNLoH5315xbFVh56YOpB5wF\n/i0irYFdwFNAoDEmzv7MaSDQfl0T2Jbj+Bi7LMt+fWX55WNOAhhjskUkGagEJOSsiIiMBkYD1K5d\nOw9NUsr7JKVl8tLiUJbvj6N1UAAfDG1D/Sr+rjm5I9ta7Xj9W+DI1H1avExeAqY40BZ4whizXUSm\nYT8Ou8wYY0TE7XcbxpjpwHSA4OBgvbtR6hoYY/hxTyyTVkZwPi2TMX0a83/dGriuryVmFyx7Gk7v\nh4a9oN+71ox85TXyEjAxQIwxZrv98wKsgIkXkerGmDgRqQ6csd+PBWrlOD7ILou1X19ZnvOYGBEp\nDgQA5/JQZ6UU1l3L68vCWbQ7lta1yvPViGBaBblouftL562dJUP+ba0ZNngmNLtb57R4oVwHjDHm\ntIicFJHGxphIoCcQbn+NACbZ35fYhywF5ojIVKAGVmf+DmOMQ0RSRKQTsB14EPg4xzEjgK3AIGC9\n9r8olTerQuN4eXEY59MyebxHQ5657QbX3LUYA/vnwc8vQ9o56PgP6DEeSrphAUxVKOR1HswTwHci\n4gscBR7GGpk2X0RGAseBIQDGmDARmY8VQNnAY8YYh32eR4GZQCmszv2VdvkMYLY9ICARaxSaUioX\nktOymLAklKX7TtGsejlmPtyeFjVdNKExPhxWPA/Hf4WawTB8obVfi/JqUtRuCIKDg01ISIinq6FU\ngbImPJ6XfjzAudRMnurZiH92b+Ca1Y8zLsDGSbDtc+tOpddrcOPfwMfFKysrtxORXcaYYFeeU2fy\nK1WEnUq6xCtLQll78AyNA8vy9UMuumsxxhpyvHo8XIiDtg9Cz4lQxoVzZlShpwGjVBFkjOGHkBje\nWB5OlsPJuL5NePimevgWd8GdRcJhWPGCtW1xtVYwZDbUap/386oiRwNGqSImPiWdMQv2s+nQWTrU\nq8i7g1pRp1KZvJ84Mw02vw+/ToMSpaHvu9B+pM7CV39KA0apImTFgTjG/3iA9CwHr93VnOGd6rhm\nhFjEClj5IiSfgFbD4PY3rGX1lfoLGjBKFQGJqZm8udye1xIUwNShbWjgitn4549ZwXJoFVRpCg8t\nh7pd835e5RU0YJQq5NaGxzN20QGSL2XyWI8GPNXzhrz3tWSlw28fWY/EpBjc9gZ0+icUK+GaSiuv\noAGjVCGVmpHNhCWhLNodS9Pq5Zg9sgNNq7tgUmPUWqsTP/GoNQO/99sQUPPqxyl1BQ0YpQqhzYfP\nMv7HA8Sev+S6u5bkWGvF4/AlULEBDF8EDXu6psLKK2nAKFWIXMp08NaKcL7ddoL6Vcowd3RnOtSr\nmLeTOrJg22ewcTIYB9z6MnR5Ulc8VnmmAaNUIbHvZBLPzNvL0YRUHulaj+d7N6ZkiTwOET62BZY/\nB2cj4Ia+0HcSVKjrkvoqpQGjVAF3IT2Lj9YdZuZvx6js78ecRzrSpWHlPJ403lqU8sB8KF8b7psL\njfu6psJK2TRglCrAdkQn8tTcPcSnpHPPjUFM6N+U8qV9c39CRzaEzID1b0J2OnR7Abo+C76lXVdp\npWwaMEoVQA6n4cvNR3l3dSRBFUqx4J9daFu7Qt5OenIHLH8WTh+ABrdaM/ErN3RNhZX6AxowShUw\nh+Iv8PLiUHZEJ9K7eSDvDW5N2ZJ5mH+Seg7Wvgp7ZkPZGjB4FjQboBuAKbfTgFGqgMjMdvLZxig+\nWR9FGb/iTBnUisHtgpDcBoHTAbtnWbtLZlyALk/ALS+CX1nXVlypP6EBo1QBsO9kEmMW7Ccy/gID\n2tTg1TubU7FMHvpaYkKs0WFxe6FOV7jjPaja1HUVVuoaaMAo5UHpWQ7e/zmSGVuiqVq2JDNGBNOz\naWDuT5iaYD8O+xbKVod7Z0CLe/VxmPIIDRilPCTidApPz91LxOkL3NehNuP6NaFcbvtaHNkQ8jVs\neBMyU62JkreM0cdhyqM0YJTKZ+lZDj5Ye4ivNkdTvlQJ/v1we3o0zsPS9ye2wfLnIf4A1LsF+r0L\nVRq7rsJK5ZIGjFL5KOxUMk98v4ejZ1MZEhzE2L5Nc9/XciHeehy273soVxMGz7QWp9THYaqA0IBR\nKh84nIbpvxzlgzWHqFCmBN+O7EjXRrmcje/Ihh3TYeM7kHXJmijZ7XnwdcGulUq5kAaMUm52MjGN\n5+bvY8exRPo0r8bbA1vm/q7l2BZrKf0z4dCgJ/SdopMlVYGlAaOUmxhjWLw3llcWh2GA9we3ZmDb\nmrmb15ISZ60dFroAAmrD0O+gyR36OEwVaBowSrlBUlomLy8OZdn+ONrVqcCHQ9tQq2Iu1vvKzoTt\nX8Cmyday+t3GQNdndO0wVShowCjlYusOxvP8D/tISc/mhd6N+cctDSjmk4s7jaMbrcdhCYegUW9r\nKf2K9V1eX6XcRQNGKRdJSsvkpcWhLN8fR5NqZZkzqk3utjBOjoHVL0H4YmtvlvvmQeM+Lq+vUu6m\nAaOUC/x2JIEnv99D8qUsnr3tBkbdXJ9Svte5GVh2Bmz9BH55D4wTerxkTZgsUdI9lVbKzTRglMqD\nC+lZTF4VYW1hXLkMMx/uQIuaAdd/oqi1sGIMJB6BJv2h99tQoY7rK6xUPtKAUSqXVoedZuLSME6n\npPP3m+rx3O03UMbvOv+TOn8cVo+HiGVQsQE8sBAa9XJPhZXKZxowSl2n2KRLvLokjLUH42kcWJbP\nHmjLjde7GVhWOvz2EWx+H8QHer4CnR+H4n7uqbRSHpDngBGRYkAIEGuM6S8iFYF5QF3gGDDEGHPe\n/uw4YCTgAJ40xqy2y9sBM4FSwArgKWOMERE/4BugHXAOGGqMOZbXOiuVGw6n4avNR5m65hA+IrzY\npwmjbq5H8WI+134SYyByBawaB0nHrY2/bn8LytdyX8WV8hBX3ME8BRwELg+XGQusM8ZMEpGx9s8v\nikgzYBjQHKgBrBWRG4wxDuBzYBSwHStg+gArscLovDGmoYgMAyYDQ11QZ6WuS9SZCzz/w372nkzi\n9maBTOjf7PrntZw9BKtehCProUoT+NtiaNDDPRVWqgDIU8CISBBwB/AW8KxdPADobr+eBWwEXrTL\n5xpjMoBoEYkCOojIMaCcMWabfc5vgLuxAmYAMNE+1wLgExERY4zJS72VulbGGGZvO86byw9S2rcY\n04a14a7WNa5vNn56MmyaYk2YLFEG+kyC9o9AsTxsg6xUIZDXO5gPgTFAzk0nAo0xcfbr08Dl3ZNq\nAttyfC7GLsuyX19ZfvmYkwDGmGwRSQYqAQl5rLdSV3XiXBrjfzzAlqgEejSuwpRBralS9jr6SJxO\na6XjtRMh9Sy0/Rvc+gr4V3FbnZUqSHIdMCLSHzhjjNklIt3/6DN2P4rb7zZEZDQwGqB27druvpwq\n4pxOww+7TvLmsoMY4PUBzXmgY53rm40fswtWvgCxuyCoPdw/F2q2c1udlSqI8nIHcxNwl4j0A0oC\n5UTkWyBeRKobY+JEpDpwxv58LJCzJzPILou1X19ZnvOYGBEpDgRgdfb/F2PMdGA6QHBwsD4+U7l2\nKP4CExaHsj06kfZ1K/DB0DYEVbiOvpaLZ2Dta7D3W/APhLu/gFZDwec6BgIoVUTk+l+9MWacMSbI\nGFMXq/N+vTFmOLAUGGF/bASwxH69FBgmIn4iUg9oBOywH6eliEgnsR5sP3jFMZfPNci+hgaIcjmn\n0/DvX6PpN20z4XEpTLm3FfNGd772cHFkwdZP4eN2sH+eNQP/8RBoc5+Gi/Ja7pgHMwmYLyIjgePA\nEABjTJiIzAfCgWzgMXsEGcCj/GeY8kr7C2AGMNseEJCIFWRKudT51Eyemb+XjZFn6d64ClOHtLm+\n/VqOrIeVYyEhEhr2sjrxKzdyX4WVKiSkqN0QBAcHm5CQEE9XQxUCxhjm7jzJ2ysOkpHlZMKdzRje\nsfa1jxBLjLb2aIlYZi1K2WcS3NBH92hRhZKI7DLGBLvynDqTX3mlw/EXeHP5QTYdOkuXBpV49c7m\nNK5W9uoHAmSmwZYP4Ndp4FPMmoXf6TFdlFKpK2jAKK+S7XAydc0hvth0BH+/4rx8R1P+flM9fK5l\nhJgxEPYj/DwBUmKg5WDo9RoE1Lz6sUp5IQ0Y5TVOJqbx5Nw97DmRxNDgWozp05hK/tc4r+V0KKx8\nEY5vgWot4d4voU4X91ZYqUJOA0YVedkOJ1//Gs3UNYco4ePDx/fdyJ2ta1zbwWmJsPEd2PkVlAyA\nO6ZCu4esR2NKqb+kAaOKtNDYZF5cuJ+wUyn0ahrIxLuaXdvQY6cDds+CdW9AehIEj4Qe46F0RfdX\nWqkiQgNGFUnpWQ6mrTvM9F+OUqG0L5/e35Z+Latd2wixY1usYcfxB6BOV+g7Gaq1cH+llSpiNGBU\nkbP96DnGLjpAdEIqg9sF8dIdTSlf+hrmtZw/DmsmQPgSCKgFg76G5gN12LFSuaQBo4qMC+lZTFkV\nyextx6lVsRTfjuxI10aVr35gxkXYMhV++8TqW+nxEnR5AkqUcn+llSrCNGBUoWeMYcWB07y6NIxz\nqRk8fFM+Jt8CAAAS4ElEQVRdXujdmNK+V/nn7XRay7qsnQgXT0PLIdBrog47VspFNGBUoRZ+KoWJ\nP4WxIzqRVkEBfP1QMK2Cyl/9wJM7rc2/YndBjbYwdDbU6uD+CivlRTRgVKGU5XDyr01H+GDtYQJK\nleD1Ac25r0NtSlxt++LkWOuO5cB88K+mqx0r5UYaMKrQ2R+TxJgF+4k4fYH+rarz1t0tCSh9ld0h\nsy7Bbx9bS7w4HXDzc9D1WfDzz59KK+WFNGBUoZGR7WDqz4f4cvNRqpT1Y/rf2nF782p/fdDl5V3W\nvArJJ6DpXXD7G9bilEopt9KAUYVC2Klknpu/j4jTFxjWvhbj+jUloNRV7lri9lnzWU78BoEt4e5l\nUO/m/KmwUkoDRhVsmdlOpv9i9bVUKF2CGSOC6dk08K8PungG1r0Oe761Zt73/xDaPqjLuyiVzzRg\nVIG192QSYxdafS13tKzO2/dcpa8lOwO2fwGb3oXsS9D5Mej2ApS6hlFlSimX04BRBU5qRjbv/RzJ\nzN+OEVi2JF8+GMxtzf7irsUYiFwJq8fD+Who1Bt6v6W7SirlYRowqkD55dBZxi06wKnkSwzvWIcx\nfRpTtuRf3LXEh1vBcnQDVG4Mwxda2xYrpTxOA0YVCLFJl3htaRg/h8fToEoZfvi/zgTX/YuViy+e\ngQ1vWyse+5WFPpOh/UgodpWOf6VUvtGAUR7ldBq+33mCSSsicBrDs7fdwOhu9SlZ4k865LPSYdtn\nsHmq1c/SYTTc8qIuo69UAaQBozzmyNmLjFt4gB3HEunSoBLvDGxJnUpl/vjDxkDYIlgz0ZrP0rgf\n3Pa69rMoVYBpwKh8d3no8UfroyhZ3Icp97ZicHDQn+/VEhMCq8ZBzA5rPsuAJVC/e35WWSmVCxow\nKl9dOfT41buaUbVsyT/+cNIJWPsahC4A/0C46xNoc7/OZ1GqkNCAUfkiPcvBe6sj+frX6Ksv85Jx\nwVozbOun1s/dXoCbnrI685VShYYGjHK7sFPJPDFnD0cTUnmgY21e7NuEcn809NjpsGbfr38TUs/Y\n+7O8CgFB+V9ppVSeacAot8l2OJn52zEmrYygkr8v3z3SkZsa/skOk0c2wOqX4EwY1OoE982FoHb5\nW2GllEtpwCi3+O1IAq8tDScy/gK9mlZlyqDWVCzj+78fPHsI1kyAQ6ugfG0YPBOa3Q1/1uGvlCo0\nNGCUS8WcT+OdFREsPxBHUIVSfDG8Hb2bB/7vCLG0RNj4DuycAb5loNdr0PEfUOJPOvyVUoWOBoxy\niWyHk3/9cpSP1x/GGHim1w383y1/MGEyOwN2fAm/TLE689s9DN3HgX8Vz1RcKeU2GjAqz3YdP8/E\npWEciE2mT/NqvHJnM2qUL/XfH7o8UXLta5B03Fov7PY3oWpTz1RaKeV2GjAq15IvZTFpZQTf7zhB\nZX8/Pr2/LXe0qv6/Hzz2K/z8MpzaDVWb64KUSnmJXAeMiNQCvgECAQNMN8ZME5GKwDygLnAMGGKM\nOW8fMw4YCTiAJ40xq+3ydsBMoBSwAnjKGGNExM++RjvgHDDUGHMst3VWruF0GhbtieWdFQc5n5bJ\nyK71ePa2Gyjjd8U/p4TD1lbFkcuhbA0Y8Bm0HqYTJZXyEnm5g8kGnjPG7BaRssAuEVkDPASsM8ZM\nEpGxwFjgRRFpBgwDmgM1gLUicoMxxgF8DowCtmMFTB9gJVYYnTfGNBSRYcBkYGge6qzyKPxUCq8s\nCSXk+Hna1i7PrL93oEXNgP/+0MUzsHES7JoJJUrDrROg06PgW9ojdVZKeUauA8YYEwfE2a8viMhB\noCYwAOhuf2wWsBF40S6fa4zJAKJFJAroICLHgHLGmG0AIvINcDdWwAwAJtrnWgB8IiJijDG5rbfK\nnZT0LKb+fIhvth6jfGlfpgxqxaC2Qfj45Bgdlplmzb7/9UPIugTBD8MtY7UDXykv5ZI+GBGpC9yI\ndQcSaIcPwGmsR2hghc+2HIfF2GVZ9usryy8fcxLAGJMtIslAJSDhiuuPBkYD1K5d2xVNUjZjDCsO\nnObVpWGcS83ggY61ef72xpQvnWNOi9MBe+fAhrfgQhw06Q+9JupKx0p5uTwHjIj4AwuBp40xKTnn\nO9j9KG6/2zDGTAemAwQHB+vdjYtEnbnA+EWh7DiWyA2B/vz7ofa0DMrxOMwYiFoHa16xZuDXDIZB\n/4Y6nT1XaaVUgZGngBGREljh8p0xZpFdHC8i1Y0xcSJSHThjl8cCtXIcHmSXxdqvryzPeUyMiBQH\nArA6+5UbZTmc/GvTET5aF0Vpv2K8M7Alg9sFUbyYz38+FLffmoF/dCNUqGsFS/N7dAa+Uup3eRlF\nJsAM4KAxZmqOt5YCI4BJ9vclOcrniMhUrE7+RsAOY4xDRFJEpBPWI7YHgY+vONdWYBCwXvtf3OtA\nTDIvLNhHxOkL9G9VnYl3Naeyv99/PpAcYy1GuW8ulCoPvd+xtiou7vfnJ1VKeaW83MHcBPwNOCAi\ne+2y8VjBMl9ERgLHgSEAxpgwEZkPhGONQHvMHkEG8Cj/Gaa80v4CK8Bm2wMCErFGoSk3SE7L4tON\nUXy1+SiV/f9gOf1LSVbn/bbPrUdjXZ6Am5+zQkYppf6AFLUbguDgYBMSEuLpahQaxhiW7Y9jwpJQ\nktKyGBpci/F3NCWglL2cflY67JgOm9+H9CRrCf2eE6yFKZVSRYaI7DLGBLvynDqT34sdP5fKK0vC\n2HToLK2CAvjukZY0r2F34jsdsO972PAOpMRYM+97vgrVW3m20kqpQkMDxgtlOZzM/PUY76+JpLiP\nD6/e2Yy/dapjdeIbA5ErYd3rcPYg1GgL93wO9bp5utpKqUJGA8bL/HLoLG8sC+fwmYt0b1yFSQNb\nUS3AXiL/+FZYOxFOboNKDWHwLGg2QEeGKaVyRQPGS0QnpPLGsnDWR5yhbqXSTP9bO25rZu/TEh9u\n3bEcWgn+1aD/h3DjcCj2B9saK6XUNdKAKeKS0jL5cO1hZm87jl9xH8b1bcKILnWtfVqSTsKGt62+\nFr9y0PMV6PhPXTNMKeUSGjBF2PqIeMYuPEDCxQzu71ibJ3s2omrZktZukuvftzb+AujyOHR9FkpX\n9GyFlVJFigZMEZRzdFijqv58/VB7a8XjzFT45T34dRpkXoTW90P3sVC+1tVPqpRS10kDpgi5lOng\nq81H+XRjFCV8fHipX1NGdKmLL1mw/V9WuKSegcb9rMdhupukUsqNNGCKAIfTsHBXDB+sPURccjp9\nmlfj1buaUd2/BOz7FjZNgeSTUKcrDJ0NtTt5uspKKS+gAVPI7YhO5JUloUScvkDroAA+GNqGTnUr\nQNgiqwM/8Yg1l+Wuj6B+Dx1yrJTKNxowhVTCxQzeWBbOkr2nqB5Qkk/vb0u/FoHIoVXwr7cgPhSq\nNoOh30GTOzRYlFL5TgOmkHE6Dd/tOMF7qyNJy8zmyZ6N+OctDSgVsxlmDIfYEKhYHwZ+BS0Ggk8x\nT1dZKeWlNGAKkX0nk3h5cSgHYpPpXL8Sb9zdnIYZB2HOADi2GcoFwZ0fQZv7dZKkUsrjNGAKgTMp\n6UxaGcGiPbFULevHh0PbMKBaArJmJBxeDWWqQJ/J0O4hKFHS09VVSilAA6ZAu5iRzfRNR5i++ShO\nJ/yzewMea5aB/9axsGQplAywZ9//A3zLeLq6Sin1XzRgCqDLw46nrI4k4WIG/VtVZ1xbJzX3vw1f\nLwHfstBtDHR+TDf8UkoVWBowBcyGyDO8vfwgh89cpG3t8sy+05+mkdNg7mI7WF6ATo/qsi5KqQJP\nA6aAOH4uldd++s9qx9/cWZabY79EflwMvv4aLEqpQkcDxsOSL2UxeVUEC3bFUEyE97r5cs/FWRRb\ns9jqV7n5OetRmAaLUqqQ0YDxkCyHk++2Hefj9VEkXcri8RbZ/IMFlNqx1A6WZ6Hz4xosSqlCSwMm\nnxlj+Dk8nrdXHOT4uTSG1UpknP8KAg6ttIKl6zPQ5QkNFqVUoacBk492nzjPaz+Fs+9kEndVOMGi\neiupFLcJUspZdyydHoMylTxdTaWUcgkNmHxwKP4C766OZE34ae4oHcmXNVZQNTEEpBLcOgE6jLLm\ntCilVBGiAeNGsUmXeHdVBEv3xdDfdx/bqqyg2oUwyKoOvd+BdiN0gqRSqsjSgHGDMynpfLbxCPO2\nR9Ov2Da2lV9B1UtHoHhduHMatL4Pivt5uppKKeVWGjAulJiayRebjrBw60HuMev5rfTPVMiKB/8m\n0PdLaD4QiumvXCnlHfSvnQskp2Xx9a/RLNkcwjDnCrb4bqCU8yLUuAm6TINGvcHHx9PVVEqpfKUB\nkwepGdnM3XmSFWvXMSx7CWuL/0axYk6kyV3Q5UkIaufpKiqllMdowOTChfQsvtsaTdimhQx2LGdh\nsQM4S5bCp+3freVcKtbzdBWVUsrjNGCuw7mLGczdtI/0nd8w2LmKf/icJbNsIHR8GZ/2I3VypFJK\n5VAoAkZE+gDTgGLAV8aYSfl5/ZjEVJatXkmlg98yUrZQUrK4WKMj3Pwuvk366+6RSin1Bwp8wIhI\nMeBT4DYgBtgpIkuNMeHuvK4xht0HDxO9YSbN43/iHz4nyCxWkktNh1Cy26P4V2vhzssrpVShV+AD\nBugARBljjgKIyFxgAOCWgDkbH0f4ph8ocegngrN20U4cxPo3JanTZMq3H4avbvCllFLXpDAETE3g\nZI6fY4COrr5IfMwRUr8eSB3HcW4RQ4JPZaLrD6dOr9HUrKl3K0opdb0KQ8BclYiMBkYD1K5dO1fn\nqBRYizi/auyqchvV2g+gdouuVBZxZTWVUsqrFIaAiQVq5fg5yC77nTFmOjAdIDg42OTmIsVL+NLm\nxdW5raNSSqkrFIbp5TuBRiJST0R8gWHAUg/XSSml1FUU+DsYY0y2iDwOrMYapvy1MSbMw9VSSil1\nFQU+YACMMSuAFZ6uh1JKqWtXGB6RKaWUKoQ0YJRSSrmFBoxSSim30IBRSinlFhowSiml3EKMydW8\nxAJLRM4Cx/NwispAgouqU9h4c9vBu9vvzW0H727/5bbXMcZUceWJi1zA5JWIhBhjgj1dD0/w5raD\nd7ffm9sO3t1+d7ZdH5EppZRyCw0YpZRSbqEB87+me7oCHuTNbQfvbr83tx28u/1ua7v2wSillHIL\nvYNRSinlFhowNhHpIyKRIhIlImM9XR9XEJFaIrJBRMJFJExEnrLLK4rIGhE5bH+vkOOYcfbvIFJE\neucobyciB+z3PhIpHLuxiUgxEdkjIsvsn72p7eVFZIGIRIjIQRHp7C3tF5Fn7H/zoSLyvYiULMpt\nF5GvReSMiITmKHNZe0XET0Tm2eXbRaTuNVXMGOP1X1jbABwB6gO+wD6gmafr5YJ2VQfa2q/LAoeA\nZsAUYKxdPhaYbL9uZrfdD6hn/06K2e/tADoBAqwE+nq6fdf4O3gWmAMss3/2prbPAh6xX/sC5b2h\n/VjbrEcDpeyf5wMPFeW2A92AtkBojjKXtRd4FPjCfj0MmHdN9fL0L6YgfAGdgdU5fh4HjPN0vdzQ\nziXAbUAkUN0uqw5E/lG7sfbg6Wx/JiJH+X3AvzzdnmtobxCwDrg1R8B4S9sD7D+yckV5kW+/HTAn\ngYpYW5IsA24v6m0H6l4RMC5r7+XP2K+LY03MlKvVSR+RWS7/g7wsxi4rMuxb2huB7UCgMSbOfus0\nEGi//rPfQ0379ZXlBd2HwBjAmaPMW9peDzgL/Nt+RPiViJTBC9pvjIkF3gNOAHFAsjHmZ7yg7Vdw\nZXt/P8YYkw0kA5WuVgENGC8gIv7AQuBpY0xKzveM9X9JitxQQhHpD5wxxuz6s88U1bbbimM9Mvnc\nGHMjkIr1mOR3RbX9dl/DAKyQrQGUEZHhOT9TVNv+ZzzVXg0YSyxQK8fPQXZZoSciJbDC5TtjzCK7\nOF5EqtvvVwfO2OV/9nuItV9fWV6Q3QTcJSLHgLnArSLyLd7RdrD+32eMMWa7/fMCrMDxhvb3AqKN\nMWeNMVnAIqAL3tH2nFzZ3t+PEZHiWI9gz12tAhowlp1AIxGpJyK+WJ1YSz1cpzyzR4DMAA4aY6bm\neGspMMJ+PQKrb+Zy+TB7xEg9oBGww77NThGRTvY5H8xxTIFkjBlnjAkyxtTF+t9zvTFmOF7QdgBj\nzGngpIg0tot6AuF4R/tPAJ1EpLRd557AQbyj7Tm5sr05zzUI67+nq98RebpjqqB8Af2wRlkdAV7y\ndH1c1KauWLfF+4G99lc/rGen64DDwFqgYo5jXrJ/B5HkGDEDBAOh9nufcA0dfAXlC+jOfzr5vabt\nQBsgxP7ffzFQwVvaD7wGRNj1no01YqrIth34Hqu/KQvr7nWkK9sLlAR+AKKwRprVv5Z66Ux+pZRS\nbqGPyJRSSrmFBoxSSim30IBRSinlFhowSiml3EIDRimllFtowCillHILDRillFJuoQGjlFLKLf4f\n0NpPUiDYgUoAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f0028632898>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "plt.plot(pp)\n",
    "plt.plot(qq)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### L'argument d'Euler\n",
    "\n",
    "Partant des deux énoncés\n",
    "\n",
    "1) La [série harmonique](https://fr.wikipedia.org/wiki/S%C3%A9rie_harmonique) $\\displaystyle \\sum_{n\\ge 1}\\frac1n = +\\infty$ est divergente\n",
    "\n",
    "\n",
    "2) Tout entier $n\\ge 1$ s'écrit $\\displaystyle\\prod_{i\\ge 1}p_i^{m_i}$, où les $p_i$ sont les nombres premiers, et les $m_i$ sont tous nuls sauf un nombre fini d'entre eux.\n",
    "\n",
    "On peut donc factoriser les dénominateurs de la série harmonique et écrire\n",
    "$$\\sum_{n\\ge 1}\\frac1n = \\sum_{m_1\\ge 0,m_2\\ge0,\\cdots}\\prod_{i\\ge 1}\\frac1{p_i^{m_i}}\n",
    "=\\prod_{i\\ge1}\\sum_{m_i\\ge 0}\\frac1{p_i^{m_i}}=\\prod_{i\\ge1}\\frac1{1-\\frac1{p_i}}.$$\n",
    "\n",
    "S'il n'y avait qu'un nombre fini $N$ de nombres premiers, le terme de droite serait fini, il vaudrait\n",
    "$$\n",
    "\\frac1{1-\\frac1{2}}\\frac1{1-\\frac1{3}}\\cdots\\frac1{1-\\frac1{p_N}}.$$\n",
    "Or on sait qu'il ne l'est pas, donc $N$ n'existe pas et la suite des nombres premiers est infinie.\n",
    "\n",
    "Cet argument prouve plus : on sait que si $u_n$ est une suite dans l'intervalle $[0,1[$, \n",
    "la série $\\displaystyle\\sum_n u_n$ et le produit infini $\\displaystyle \\prod_n\\frac1{1-u_n}$\n",
    "sont simultanément convergents ou divergents.\n",
    "\n",
    "Donc, la série des inverses des nombres premiers $\\displaystyle\\sum_i\\frac1{p_i}$ est divergente.\n",
    "\n",
    "Si on fait l'hypothèse que $p_n$ admet un équivalent asymptotique simple formé avec des $n^\\alpha$, $\\ln^\\beta(n)$ etc.,\n",
    "on est amené à conjecturer que la répartition des  $p_n$ est pls dense que celle de toutes les puissances\n",
    "$n^\\alpha$ pour $\\alpha>1$ (puisque la série de leurs inverses converge). De même, la série des inverses\n",
    "de $n\\ln^\\beta(n)$ converge pour $\\beta>1$. On est donc tenté de comparer $p_n$ à $n\\ln n$. Numériquement,\n",
    "ça se présente plutôt bien."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x7efffa08d2e8>]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYEAAAD8CAYAAACRkhiPAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAFl1JREFUeJzt3X2sJXd93/H39zzch322vRd77fV6beFQG5RgsjXGoNQi\noQGLln+QStQAiWjdkPwBbaQKkoqIP/pHqxZVxBKOW9JCQ2lIQJRadoEGSzFSbbJ2jZ9db8yTje1d\nr+3dvXsfztO3f8zc68vlru/1nlnfnZ33SzraOTO/M+f7O/fs+cxvZs6ZyEwkSc3U2uwCJEmbxxCQ\npAYzBCSpwQwBSWowQ0CSGswQkKQGMwQkqcEMAUlqMENAkhqss1lPvHv37ty/f/9mPb0k1dK99977\nfGbOVLW+TQuB/fv3c/Dgwc16ekmqpYj4UZXrc3eQJDWYISBJDWYISFKDGQKS1GCGgCQ1mCEgSQ1m\nCEhSg9UuBB5/9gSf+dbjPD+7uNmlSFLt1S4EDh2e5bPfOcQLJ3ubXYok1V7tQkCSVB1DQJIazBCQ\npAYzBCSpwdYNgYiYiojvRcT3I+LhiPj0Gm1uiIhjEXF/efvUmSlXklSljfyU9CLwzsycjYgu8N2I\nuCMz717V7q7MfG/1JUqSzpR1QyAzE5gt73bLW57JoiRJr40NHROIiHZE3A8cBr6dmfes0ez6iHgg\nIu6IiDdWWqUk6YzYUAhk5jAz3wzsBa6NiDetanIfsC8zfxH4Y+Dra60nIm6KiIMRcfDIkSPj1C1J\nqsCrOjsoM18C7gTevWr+8cycLadvB7oRsXuNx9+amQcy88DMTGWXyJQknaaNnB00ExG7yulp4F3A\nY6vaXBQRUU5fW673aPXlSpKqtJGzg/YAX4iINsWH+1cy87aI+B2AzLwFeD/w0YgYAPPAB8oDypKk\ns9hGzg56ALhmjfm3rJi+Gbi52tIkSWdabb8x7DhDksZXuxAojjxIkqpQuxCQJFXHEJCkBjMEJKnB\nDAFJajBDQJIazBCQpAYzBCSpwQwBSWowQ0CSGswQkKQGMwQkqcEMAUlqMENAkhqstiGQ+FvSkjSu\n2oWAvyQtSdWpXQhIkqpjCEhSgxkCktRghoAkNZghIEkNZghIUoMZApLUYIaAJDWYISBJDWYISFKD\nGQKS1GCGgCQ1mCEgSQ1W2xBIf0laksa2bghExFREfC8ivh8RD0fEp9doExHx2Yg4FBEPRMRbzky5\nEP6WtCRVprOBNovAOzNzNiK6wHcj4o7MvHtFm/cAV5a3twKfK/+VJJ3F1h0JZGG2vNstb6t3xrwP\n+GLZ9m5gV0TsqbZUSVLVNnRMICLaEXE/cBj4dmbes6rJJcBPVtx/qpwnSTqLbSgEMnOYmW8G9gLX\nRsSbTufJIuKmiDgYEQePHDlyOquQJFXoVZ0dlJkvAXcC71616Gng0hX395bzVj/+1sw8kJkHZmZm\nXm2tkqSKbeTsoJmI2FVOTwPvAh5b1ewbwIfKs4SuA45l5jOVVytJqtRGzg7aA3whItoUofGVzLwt\nIn4HIDNvAW4HbgQOAXPAb5+heiVJFVo3BDLzAeCaNebfsmI6gd+rtjRJ0plW228MS5LGZwhIUoMZ\nApLUYIaAJDWYISBJDVbbEPCnpCVpfDUMAX9LWpKqUsMQkCRVxRCQpAYzBCSpwQwBSWowQ0CSGswQ\nkKQGMwQkqcEMAUlqMENAkhrMEJCkBjMEJKnBDAFJajBDQJIarLYhkPhb0pI0rtqFQPhL0pJUmdqF\ngCSpOoaAJDWYISBJDWYISFKDGQKS1GCGgCQ1mCEgSQ1mCEhSgxkCktRg64ZARFwaEXdGxCMR8XBE\nfGyNNjdExLGIuL+8ferMlCtJqlJnA20GwO9n5n0RsR24NyK+nZmPrGp3V2a+t/oSJUlnyrojgcx8\nJjPvK6dPAI8Cl5zpwiRJZ96rOiYQEfuBa4B71lh8fUQ8EBF3RMQbK6hNknSGbWR3EAARsQ34KvDx\nzDy+avF9wL7MnI2IG4GvA1eusY6bgJsA9u3bd9pFA6S/JC1JY9vQSCAiuhQB8KXM/Nrq5Zl5PDNn\ny+nbgW5E7F6j3a2ZeSAzD8zMzJxWwf6StCRVZyNnBwXweeDRzPzMKdpcVLYjIq4t13u0ykIlSdXb\nyO6gtwMfBB6MiPvLeX8A7APIzFuA9wMfjYgBMA98INMdNpJ0tls3BDLzu6yzFyYzbwZurqooSdJr\nw28MS1KDGQKS1GCGgCQ1mCEgSQ1mCEhSgxkCktRghoAkNZghIEkNZghIUoMZApLUYLULgfJ36iRJ\nFahdCEiSqmMISFKDGQKS1GCGgCQ1mCEgSQ1mCEhSgxkCktRghoAkNZghIEkNZghIUoMZApLUYIaA\nJDWYISBJDVbbEMjc7Aokqf5qFwL+kLQkVad2IbAkcSggSeOqXQh4TRlJqk7tQmCJxwQkaXy1CwFH\nApJUndqFwBIHApI0vnVDICIujYg7I+KRiHg4Ij62RpuIiM9GxKGIeCAi3nJmyoUozw9K9wdJ0tg6\nG2gzAH4/M++LiO3AvRHx7cx8ZEWb9wBXlre3Ap8r/62eu4MkqTLrjgQy85nMvK+cPgE8Clyyqtn7\ngC9m4W5gV0TsqbzalXWdyZVLUkO8qmMCEbEfuAa4Z9WiS4CfrLj/FD8fFJVwICBJ1dlwCETENuCr\nwMcz8/jpPFlE3BQRByPi4JEjR05nFcs8JCBJ49tQCERElyIAvpSZX1ujydPApSvu7y3n/YzMvDUz\nD2TmgZmZmdOpl/AcUUmqzEbODgrg88CjmfmZUzT7BvCh8iyh64BjmflMhXWuwaGAJI1rI2cHvR34\nIPBgRNxfzvsDYB9AZt4C3A7cCBwC5oDfrr7UwtI4wN1BkjS+dUMgM7/LOsdjszhp//eqKuqVuDdI\nkqrjN4YlqcFqFwLhSaKSVJnahcASjwlI0vhqFwJLxwT87SBJGl/9QmCzC5Ckc0jtQmCJ4wBJGl/9\nQsChgCRVpn4hUPKQgCSNr3Yh4CmiklSd2oXAkvSogCSNrXYhsPyzEWaAJI2tfiGw2QVI0jmkdiGw\nxIGAJI2vdiHgRWUkqTq1C4ElniIqSeOrXQg4EJCk6tQuBJZ4iqgkja92IeDlJSWpOvULAXcHSVJl\nahcCSxwISNL4ahgCDgUkqSo1DIGCVxaTpPHVLgQ8JiBJ1aldCCxxHCBJ46tdCCwPBEwBSRpb/ULA\n/UGSVJnahcASvzEsSeOrXQg4DpCk6tQvBMoUGI02tw5JOhfULwTKsYA7gyRpfPULgXIk4JfFJGl8\n64ZARPxpRByOiIdOsfyGiDgWEfeXt09VX+bLWmUKjMwASRpbZwNt/gtwM/DFV2hzV2a+t5KK1tEq\nY8uRgCSNb92RQGb+NfDCa1DLhiwdE3AkIEnjq+qYwPUR8UBE3BERb6xonWtqLR0T8NCwJI1tI7uD\n1nMfsC8zZyPiRuDrwJVrNYyIm4CbAPbt23daTxYeE5Ckyow9EsjM45k5W07fDnQjYvcp2t6amQcy\n88DMzMxpPZ9nB0lSdcYOgYi4KMrN84i4tlzn0XHXeypLZweZAZI0vnV3B0XEl4EbgN0R8RTwR0AX\nIDNvAd4PfDQiBsA88IE8g5vpS8cERqaAJI1t3RDIzN9YZ/nNFKeQviY8O0iSquM3hiWpwWoXAq1y\nf9DQoYAkja12IbDQHwLwr29/dJMrkaT6q10IzPeKEDixMNjkSiSp/moXAi0vLylJlaldCLRbhoAk\nVaV2IWAGSFJ1ahcCl12wFYCr9uzY5Eokqf5qFwITnaLkR585vsmVSFL91S4EJEnVMQQkqcEMAUlq\nMENAkhrMEJCkBjMEJKnBah0C//5bj292CZJUa7UOgT/+zqHNLkGSaq3WIQAwu+iviUrS6ap9CLzp\nj77JXM8gkKTTUfsQALj6U99kvjdkOEr+5ocvbHY5klQb615o/mzUbsXPXV7yqk/9r+Xpz3/4AHvP\n28JFO6fYNtnhJy/MsX/31te6TEk669UyBDprhMBKH/nCwZ+b989+5Qr+5K+fBOCD113GR95xObu2\ndHn2+ALfevg5tky0+Z/f/ynXXn4+v3vD65nstphot2i3gojg2Hyf2x74Kf/4rZcxGI5YGIx4aa7H\n3vO2rFvv4mBIf5hsm6zlyy3pHBaZm3PB9gMHDuTBgz//Yb0Rf3b3j/hXX3+o4orGd9GOKV442eP9\nB/Zy+4PP8NJc/+fa7L9gCyd7Q7ZPdXj6xXkuOW+aEwsDjpxYBOCNF+/gFy7czpsv3cWDTx/jytdt\n48Gnj3Ho8CxbJtrs2TnNKJMnj5zkH/3dS7n0/C380y8e5IqZrQRw9cU7uXjnFN12i8eePcH0RJvv\nPPocH3nH5ezZNc2hw7O8eLLH33vDDK0Inju+wOW7t/JLl+7iqRfnefLILCcXB/SGyfbJDtMTbUbl\ne2T7VIcfHZ1jvj8kE7ZOtLl41zTtVjDdbXNiccCxuT7HF/rM9Ya0W8GO6S4LvSHPzy7yuh1TXLB1\ngumJNjumuiTJZKdY/3lbunRaLV6c63Fsvk8mJEkQXLhjilYLOq0WkDzx3CzPHV/gwh1TTHRaTHba\nTHZbHJ3tsdAfMtlpMTXRZqLdYsdUl5ntk2yb6rCl2+bEwoDnTiww1xty/pYJ+qMRU902C/0hC/0i\nrBf7Q4aZnFgYEMC2qc7yRsdgmEx128sbCROdFt12i+PzfU72BnTbLXZvm6TTiuV+TE+06A2SCJjv\nDxmNknYr6LRa9EcjJjstprttppZvxbo77Zf31o5GSWuNi2kMR8nswoDJbov53pBRJgnMLgzYNtVh\n13SXuf6Ql0726Q2HtFsttky0mey0GI6SUcIok/5wBBSj7KWPhIX+kNnFAf1hUW8rYLrbZstkh+lu\nm2676ENvMCJJBqOk0wr6w2Si01p+TFDUPcxkMBwRBO120GkVt8Eo6Q1HzPeGtCKKja928Zil1/iV\nrPwMW5rMcn6umL9Uz0J/xFxvwDCTyXabTrt4/7ZawWA4ohVBlv1f+vueTSLi3sw8UNn66hgCAMcX\n+jz01DEGo+TYfJ8HnnqJ/3jXD36mzc7pLsfmf/aD+G1XXMD/efLoaT/vuC7YOsHRk73K1zvdbTPM\nYrRxfL7P4BVGSk211m7Es1krWA6L+f6QndNdtky06Q9HzPWGLA5GZBYf5OeyIpiSVsTPXFkwE/qj\n0fIHf8TLIbCWV1oeUVy6dq33R6cVTHZaTHbb9AYjBqMR7RW1bJ3s0ClDazQqwqc/KgLvVH7r+sv5\n2K9duU7PT1VrtSFQ2/0TO6a6XP/63cv3/8EvXcwn33MVw3Ir+Q0XbV9elpksDootvpWWAjBWXbd4\nrtyiO7k4YNtkh1YEo8yf2TJb7akX55jstJnrDZjqFluhO6e7a269ZSbHFwYs9ofs3jbJkdlFXrd9\nkijfhK2AJw7PctcTz/PiyR5X7dnBL192HudtLbaWnz2+wNaJNj99aYGjJxf5hQu3c+GOqeX1D4Yj\nRgnd9svPfWR2kRdP9rn7yaP84t6djMot3cEwefy5E0QUb/Z3/p3XsXN6gm47OLEwYL4/ZDAsXqcf\nvzDH3vOmuXDHFCcXi37+8OhJHnr6GFfMbGX7VJc9O6fYPtllaqJFf5icXBzQaQW7tkzw0lyPwycW\nGQyTE4vFVvLTL80z3xuybbJDUoTZZKfF1skO3XaxVfniXI9MGIxG9AYjLt41zc7pLu1W0BuMWBwU\n808s9Hn967bRG45Y6A+Z74042Rvw/OwiL8z2WBgMl7fkz986QWaybapLbzBi62S7GFF0Wkx2WhAw\n2Sn+jicW+nTaLSKgPxgVW7SjpDconmc4SrZPFR/QveGIF0/2GI6SLRNFHxYGIzrl+2CqW2xZDkbJ\nYJh02sFif8TiYFjWPGSh7M/iYMgoYbFf1PfSXJ/5/pBOK5jqttk62SYIdm3psjgYsWWiTSuCCNgy\n0WF2oc/xhQHT3TbnbZ1gotNiOBpxcnFIv9zibZVbx51WEATDTILiQ3Gi02LLRIfJTqt8/ZOF/pC5\n3oCFflFjfzRa3m3abgWDYdLttFgsR4ujMqSSpB1Bt90igeFoRH+YDEfFazDRLl93oDdMhuWHe384\nYr5fjBAGo6J9BJDF/9tuO4ot93Krf+ka5FGOQIp/i/u9QfGhPD3RKV6rVrBYjv6K9/mIyU57eQQ6\n2W0t/20Wy79Hp9VaHkUNRskok/necHmja+l5u+2ir6e6JPpVe7avvWAT1HYkIElNVPVI4Oza2SVJ\nek0ZApLUYIaAJDWYISBJDWYISFKDGQKS1GCGgCQ1mCEgSQ22aV8Wi4gjwI9O8+G7gecrLKdumtz/\nJvcdmt3/JvcdXu7/ZZk5U9VKNy0ExhERB6v8xlzdNLn/Te47NLv/Te47nLn+uztIkhrMEJCkBqtr\nCNy62QVssib3v8l9h2b3v8l9hzPU/1oeE5AkVaOuIwFJUgVqFwIR8e6IeDwiDkXEJza7nipExKUR\ncWdEPBIRD0fEx8r550fEtyPiifLf81Y85pPla/B4RPz6ivm/HBEPlss+G6uvmHOWioh2RPzfiLit\nvN+kvu+KiL+MiMci4tGIeFtT+h8R/7x8zz8UEV+OiKlzue8R8acRcTgiHloxr7L+RsRkRPx5Of+e\niNi/blGZWZsb0Ab+FrgCmAC+D1y92XVV0K89wFvK6e3A/wOuBv4t8Ily/ieAf1NOX132fRK4vHxN\n2uWy7wHXUVxQ6Q7gPZvdvw2+Bv8C+G/AbeX9JvX9C8A/KacngF1N6D9wCfADYLq8/xXgt87lvgO/\nArwFeGjFvMr6C/wucEs5/QHgz9etabNflFf5Ar4N+OaK+58EPrnZdZ2Bfv4P4F3A48Cect4e4PG1\n+g18s3xt9gCPrZj/G8CfbHZ/NtDfvcBfAe9cEQJN6fvO8oMwVs0/5/tfhsBPgPMpLnV7G/D3z/W+\nA/tXhUBl/V1qU053KL5cFq9UT912By29aZY8Vc47Z5TDt2uAe4ALM/OZctGzwIXl9Kleh0vK6dXz\nz3b/AfiXwMorczel75cDR4D/XO4O+08RsZUG9D8znwb+HfBj4BngWGZ+iwb0fZUq+7v8mMwcAMeA\nC17pyesWAue0iNgGfBX4eGYeX7ksi2g/507lioj3Aocz895TtTlX+17qUOwe+FxmXgOcpNglsOxc\n7X+57/t9FEF4MbA1In5zZZtzte+nshn9rVsIPA1cuuL+3nJe7UVElyIAvpSZXytnPxcRe8rle4DD\n5fxTvQ5Pl9Or55/N3g78w4j4IfDfgXdGxJ/RjL5DsRX3VGbeU97/S4pQaEL/fw34QWYeycw+8DXg\neprR95Wq7O/yYyKiQ7G78egrPXndQuBvgCsj4vKImKA48PGNTa5pbOWR/c8Dj2bmZ1Ys+gbw4XL6\nwxTHCpbmf6A8E+By4Erge+WQ8nhEXFeu80MrHnNWysxPZubezNxP8ff8Tmb+Jg3oO0BmPgv8JCLe\nUM76VeARmtH/HwPXRcSWsuZfBR6lGX1fqcr+rlzX+yn+P73yyGKzD5KcxkGVGynOnvlb4A83u56K\n+vQOiiHgA8D95e1Gin15fwU8Afxv4PwVj/nD8jV4nBVnQgAHgIfKZTezzkGhs+kG3MDLB4Yb03fg\nzcDB8u//deC8pvQf+DTwWFn3f6U4E+ac7TvwZYrjH32KUeBHquwvMAX8BXCI4gyiK9aryW8MS1KD\n1W13kCSpQoaAJDWYISBJDWYISFKDGQKS1GCGgCQ1mCEgSQ1mCEhSg/1/13rnZ4KPfHYAAAAASUVO\nRK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f00343ece10>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot([pp[n]/(n*log(n)) for n in range(2,len(qq))])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### La fonction $\\zeta$ de Riemann\n",
    "\n",
    "La factorisation de la série harmonique est une manipulation un peu hasardeuse de séries divergentes. On peut la transformer en un argument rigoureux pour les séries convergentes (dites séries de Riemann)\n",
    "$$\\zeta(s) = \\sum_{n\\ge 1}\\frac1{n^s} <\\infty\\quad \\text{pour $s>1$.}$$\n",
    "Le raisonnement d'Euler conduit alors à la formule\n",
    "$$\\zeta(s)=\\prod_{i\\ge1}\\frac1{1-\\frac1{p_i^s}}.$$\n",
    "En fait, la série $\\zeta(s)$ converge pour $s\\in{\\mathbb C}$, pourvu que $\\Re(s)>1$. La théorie des fonctions analytiques\n",
    "permet de prouver qu'elle admet un unique prolongement analytique défini sur ${\\mathbb C}-\\{1\\}$. C'est \n",
    "[ce prolongement](https://fr.wikipedia.org/wiki/Fonction_z%C3%AAta_de_Riemann)\n",
    "qui a été étudié par Riemann. Il a montré que pour prouver le théorème des nombres premiers, il \n",
    "[suffisait de montrer](https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_des_nombres_premiers)\n",
    "que cette fonction ne s'annule pas sur la droite $\\Re(s)=1$.\n",
    "\n",
    "Remarquons au passage l'apparition de la fonction de Möbius (cf. cours précédent) dans les coefficients de l'inverse de $\\zeta$\n",
    "$$\\frac1{\\zeta(s)} = \\prod_{i\\ge1}\\left(1-\\frac1{p_i^s}\\right)=\\sum_{n\\ge 1}\\frac{\\mu(n)}{n^s}.$$\n",
    "\n",
    "Les séries de la forme\n",
    "$$A(s) = \\sum_{n\\ge 1}\\frac{a_n}{n^s}$$\n",
    "sont appelées *séries de Dirichlet*. Le produit de deux telles séries s'écrit\n",
    "$$A(s)B(s)=\\sum_{k\\ge 1}\\frac{a_k}{k^s}\\sum_{l\\ge 1}\\frac{b_l}{l^s}\n",
    "=\\sum_{n\\ge 1}\\left(\\sum_{kl=n}a_kb_l\\right)\\frac1{n^s}\n",
    "=\\sum_{n\\ge 1}\\left(\\sum_{d|n}a_db_{n/d}\\right)\\frac1{n^s}\n",
    "$$\n",
    "\n",
    "On peut en déduire la *formule d'inversion de Möbius*:\n",
    "\n",
    "Si $f$ et $g$ sont deux fonctions sur les entiers positifs reliées par\n",
    "$$f(n) = \\sum_{d|n}g(d)$$\n",
    "alors\n",
    "$$g(n) = \\sum_{d|n}\\mu(d)g\\left(\\frac{n}{d}\\right).$$\n",
    "En effet, les deux séries (formelles) \n",
    "$$F(s)=\\sum_{n\\ge 1}\\frac{f(n)}{n^s}\\quad\\text{et}\\quad G(s)=\\sum_{n\\ge 1}\\frac{g(n)}{n^s}$$\n",
    "sont reliées par (prendre $B(s)=\\zeta(s))$\n",
    "$$F(s) = G(s)\\zeta(s),\\quad {\\text d'où}\\quad G(s) = F(s)\\zeta(s)^{-1}$$\n",
    "qui équivaut à la formule d'inversion.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tests de primalité\n",
    "\n",
    "On a vu qu'il était difficile de factoriser de grands nombres, et donc de déterminer si un tel nombre est\n",
    "vraiment premier. Les tests probabilistes comme Miller-Rabin suffisent en général pour les applications pratiques,\n",
    "mais on a parfois besoin de savoir avec certitude si un nombre est premier.\n",
    "\n",
    "On sait depuis 2002 qu'il existe un [algorithme déterministe en temps polynomial](https://fr.wikipedia.org/wiki/Test_de_primalit%C3%A9_AKS), mais il reste inapplicable pour les nombres utilisés en cryptographie.\n",
    "\n",
    "Voici quelques méthodes plus anciennes, la première pour des nombres quelconques, la seconde pour les\n",
    "*nombres de Mersenne* $M_p=2^p-1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Le test de Lucas\n",
    "\n",
    "C'est la réciproque du théorème de Fermat.\n",
    "On rappelle que ce dernier est un cas particulier du théorème de Lagrange : \n",
    "dans un groupe fini, l'ordre de tout élément est un diviseur de l'ordre du groupe. \n",
    "Ainsi, si $n$ est premier,\n",
    "${\\mathbb Z}/n{\\mathbb Z}$ est un corps, et son groupe multiplicatif est d'ordre $n−1$. \n",
    "Mais si $n$ n'est pas premier, l'ordre de ce groupe est strictement inférieur à $n−1$.\n",
    "Donc, si on peut trouver un élément a d'ordre exactement n−1, n sera nécessairement premier.\n",
    "\n",
    "Pour appliquer cette idée, on factorise $n−1$ pour avoir la liste $Q$ de ses diviseurs premiers.\n",
    "On calcule ensuite pour diverses valeurs de $a$ telles que $a^{n−1}\\equiv  1 \\mod n$, les $a^{(n−1)/q} \\mod n$ pour tous les \n",
    "$q\\in Q$. \n",
    "Si pour un certain $a$ aucun n'est égal à 1, on a la preuve que n est premier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "65537\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "65536"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Exemple extrême n = F_4 = 65537\n",
    "n = 2**16+1; print(n)\n",
    "powermod(3,(n-1)//2,n) # 2 est le seul diviseur premier de n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(2, 1), (5, 1), (17, 1), (53, 2), (137, 1)]\n",
      "65421610 23778830 54996366 10089936 52636661 "
     ]
    }
   ],
   "source": [
    "# Si n-1 n'a que de petits factuers premiers, on s'en tire\n",
    "n = 65421611\n",
    "ff = factor(n-1); print(ff)\n",
    "for f in ff: print(powermod(2,(n-1)/f[0],n), end=' ')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Le test de Lucas-Lehmer.\n",
    "\n",
    "Il permet de savoir si un [nombre de Mersenne](https://fr.wikipedia.org/wiki/Nombre_de_Mersenne_premier) est premier.\n",
    "Voir [là](https://en.wikipedia.org/wiki/Lucas–Lehmer_primality_test) pour les détails.\n",
    "\n",
    "Pour prouver que $M_p=2^p-1$ est premier, on suppose qu'il possède un diviseur premier $q$ avec $q^2\\le M_p$.\n",
    "Le groupe $G$ des éléments inversibles de l'anneau ${\\mathbb Z}_q[\\sqrt{3}]$ (formé des $a+b\\alpha$ où\n",
    "$a,b\\in{\\mathbb Z}_q$ et $\\alpha=\\sqrt{3}$ est un symbole vérifiant $\\alpha^2=3$)\n",
    "est d'ordre au plus $q^2-1 \\le 2^p-2$. Si on peut trouver\n",
    "un élément $a$ d'ordre supérieur à celui de ce groupe, cela prouvera qu'un tel $q$ n'existe pas.\n",
    "\n",
    "Soient $z=2+\\sqrt{3}$ et $\\bar z=2-\\sqrt{3}$. On a $z\\bar z=1$, et la suite $s_n =z^{(2^n)}+\\bar z^{(2^n)}$\n",
    "vérifie $s_0=4$ et $s_n=s_{n-1}^2-2$. Si on suppose que  $M_p|s_{p-2}$, on a donc\n",
    "$$ z^{(2^{p-2})}+\\bar z^{(2^{p-2})} = kM_p$$\n",
    "donc $z^{(2^{p-1})}=kM_pz^{(2^{p-2})}-1$, d'où\n",
    "$$z^{(2^{p-1})}\\equiv -1\\mod q$$\n",
    "et $$\\ z^{(2^{p})}\\equiv 1\\mod q$$\n",
    "Ainsi, $z$ est d'ordre $2^p$ dans $G$. Comme l'ordre de $G$ est  $< 2^p-2$, c'est impossible.\n",
    "\n",
    "Donc, si  $M_p|s_{p-2}$, alors $M_p$ est premier.\n",
    "\n",
    "\n",
    "Le [plus grand nombre premier connu](https://primes.utm.edu/largest.html#largest)\n",
    "est en général un nombre de Mersenne."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Résidus quadratiques\n",
    "\n",
    "Puisque ${\\mathbb Z}/p{\\mathbb Z}$ est un corps, on peut diviser par tout élément non nul, et donc résoudre\n",
    "les équations du premier degré $ax+ b=0$ (en calculant les inverses par l'algorithme d'Euclide). Pour les équations du second degré, ça devient plus compliqué. On peut toujours écrire\n",
    "$$ax^2+bx+c = a\\left[ \\left(x+\\frac{b}{2a}\\right)^2-\\frac{b^2}{4a^2}+\\frac{c}{a}\\right]$$\n",
    "mais le discriminant $\\Delta =b^2-4ac$ n'a pas toujours de racine carrée modulo $p$.\n",
    "L'énoncé suivant permet de savoir si un nombre est un carré modulo $p$. On dit dans ce cas que\n",
    "c'est un *résidu quadratique* modulo $p$.\n",
    "\n",
    "\n",
    "\n",
    "## Le critère d'Euler\n",
    "\n",
    "Soit $p>2$ un nombre premier, et $a$ un entier non divisible par $p$. \n",
    "Alors, $a$ est un carré modulo $p$ si et seulement si $a^{(p-1)/2}\\equiv 1 \\mod p$.\n",
    "\n",
    "\n",
    "Remarquons que d'après Fermat, $a^{(p-1)/2}\\equiv \\pm 1 \\mod p$. On définit le <i>symbole de Legendre</i>\n",
    "par\n",
    "$$\\left(\\frac{a}{p}\\right)=\\begin{cases}1&\\text{si $a$ est un carré modulo $p$}\\\\\n",
    "                                         -1 &\\text{sinon}\n",
    "                            \\end{cases}$$\n",
    "\n",
    "Le critère d'Euler s'énonce donc\n",
    "$$\\left(\\frac{a}{p}\\right)\\equiv a^{(p-1)/2} \\mod p.$$\n",
    "\n",
    "### Preuve \n",
    "On calcule $x^{p-1}-1\\mod x^2-a$ en écrivant\n",
    "$$x^{p-1}-1 = \\left[(x^2)^{(p-1)/2}-a^{(p-1)/2}\\right] + \\left[a^{(p-1)/2}-1\\right]$$\n",
    "(ce qui revient plus simplement à poser $x^2=a$ dans $x^{p-1}-1$, le reste est donc $a^{(p-1)/2}-1$,\n",
    "qui sera 0 ssi $a$ est un carré).\n",
    "\n",
    "Si $a^{(p-1)/2}-1=0$ dans ${\\mathbb Z}/p{\\mathbb Z}$, alors $x^2-a$ divise $x^{p-1}-1 = \\prod_{c=1}^{p-1}(x-c)$\n",
    "dans ${\\mathbb Z}/p{\\mathbb Z}[x]$ et possède donc deux racines dinstinctes. Dans le cas contraire,\n",
    "le reste de la division est égal à $-2$, et $x^2-a$ n'a pas de racines modulo $p$.\n",
    "\n",
    "l'argument d'Euler prouve en fait un résultat plus général.\n",
    "Si $p = 1 + mn$, un entier $a$ non divisible par $p$ est une puissance $n$-ième modulo $p$ si (et seulement si) $a^m \\equiv 1 \\mod p$.\n",
    "\n",
    "####  Application 1\n",
    "$$ \\left(\\frac{a}{p}\\right)\\left(\\frac{b}{p}\\right)=\\left(\\frac{ab}{p}\\right),$$\n",
    "pour $a$, $b$ non divisibles par $p$.\n",
    "\n",
    "#### Application 2\n",
    "$$\\left(\\frac{-1}{p}\\right)=(-1)^{(p-1)/2}.$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## La loi de réciprocité quadratique\n",
    "\n",
    "Elle s'énonce ainsi. Si $p$ et $q$ sont deux nombres premiers impairs distincts,\n",
    "$$\\left(\\frac{p}{q}\\right)\\left(\\frac{q}{p}\\right)= (-1)^{\\frac{(p-1)(q-1)}{4}}.$$  \n",
    "\n",
    "Il en existe plus d'une centaine de preuves.\n",
    "\n",
    "### Preuve de G. Rousseau \n",
    "\n",
    "#### (J. Austral. Math. Soc. (Series A) 51 (1991), 423-425)\n",
    "C'est la plus simple. C'est une amélioration d'une variante de la cinquième preuve de Gauss, elle même due à H. Schmidt.\n",
    "\n",
    "Elle n'utilise que le théorème des restes chinois et le critère d'Euler.\n",
    "\n",
    "Considerons le groupe  $(\\mathbb{Z}/p)^\\times \\times (\\mathbb{Z}/q)^\\times = (\\mathbb{Z}/pq)^\\times$ (d'après\n",
    "le théorème des restes chinois).\n",
    "\n",
    "On a trois manières naturelles de le couper en deux comme dans le lemme de Gauss, c'est à dire en deux\n",
    "moitiés telle que les éléments de l'une soient les opposés des éléments de l'autre.\n",
    "\n",
    "\n",
    "<ol>\n",
    "<li> Prendre la première moitié de $(\\mathbb{Z}/p)^\\times$  et tout le second facteur</li>\n",
    "<li> Prendre tour le premier facteur et la moitié de $(\\mathbb{Z}/q)^\\times$</li>\n",
    "<li> Prendre la première moitié de $(\\mathbb{Z}/pq)^\\times$</li>\n",
    "</ol>\n",
    "\n",
    "Par définition, les produits de ces trois ensembles sont égaux au signe près.\n",
    "\n",
    "<p> Les valeurs de ces produits sont (en posant $P = (p-1)/2$ et $Q=(q-1)/2$):\n",
    "</p>\n",
    "\n",
    "<ol>\n",
    "<li>$(P!^{q-1}, (q-1)!^P)$</li>\n",
    "<li>$((p-1)!^Q, Q!^{p-1})$</li>\n",
    "<li>$\\left(\\frac{(p-1)!^Q P!}{q^P P!},\\frac{(q-1)!^P Q!}{p^Q Q!}\\right)$</li>\n",
    "</ol>\n",
    "\n",
    "En appliquant le théorème de Wilson à la seconde composante, \n",
    "on voit par le critère d'Euler que la différence de signe entre 1 et 3 est\n",
    "$\\left(\\frac{p}{q}\\right)$.  \n",
    "\n",
    "De même, le signe reliant 2 et 3 est $\\left(\\frac{q}{p}\\right)$.  \n",
    "\n",
    "Donc, le signe reliant 1 et 2 est\n",
    "$\\left(\\frac{p}{q}\\right) \\left(\\frac{q}{p}\\right)$.  \n",
    "\n",
    "Mais pour passer de 1 à 2, on a juste changé les signes de\n",
    "$\\frac{p-1}{2}  \\frac{q-1}{2}$ élements,\n",
    "d'où le résultat.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Le lemme de Gauss\n",
    "\n",
    "Remarquons que le cas où $p$ ou $q$ est égal à 2 n'est pas pris en compte. Le lemme suivant, utlisé par Gauss dans\n",
    "l'une de ses preuves de la loi de réciprocité, permet de répondre à la question.\n",
    "\n",
    ">Soit $p=2k+1$ un nombre premier impair, et $A=\\{a_1,\\ldots,a_k\\}$ in *demi-système* de résidus modulo $p$, c'est\n",
    "à dire que tout entier $a$ non divisible par $p$ est congru à un $\\pm a_i$.  Alors,\n",
    "$$\\left(\\frac{a}{p}\\right)=(-1)^m$$\n",
    "où $m$ est le nombre de $i$ tels que $aa_i\\equiv -a_j$ pour un $j$.\n",
    "\n",
    "Posons $j=\\sigma(i)$. Alors, $\\sigma$ est une permutation de $1,\\ldots,k$ car $aa_i\\equiv\\pm aa_j$ impliquerait\n",
    "$a_i\\equiv\\pm a_j$, ce qui contredirait l'hypothèse que $A$ est un demi-système. Donc, en multipliant\n",
    "toutes le congruences $aa_i\\equiv \\pm a_{\\sigma(i)}$, on obtient\n",
    "$$a^{(p-1)/2} a_1a_2\\cdots a_k = (-1)^m a_{\\sigma(1)}a_{\\sigma(2)}\\cdots a_{\\sigma(k)}$$\n",
    "c'est à dire $a^{(p-1)/2}=(-1)^m$.\n",
    "\n",
    "\n",
    "Pour calculer $\\left(\\frac{2}{p}\\right)$, on peut nprendre $A=\\{1,2,\\ldots,\\frac{p-1}{2}\\}$.\n",
    "Alors,\n",
    "$$1\\lt 2a_i\\le \\frac{p-1}{2}\\quad\\text{si}\\ a_i\\le \\frac{p-1}{4}$$\n",
    "et\n",
    "$$\\frac{p+1}{2}\\le 2a_i\\le p-1\\quad\\text{si}\\ \\frac{p-1}{4}\\lt a_i \\le \\frac{p-1}{2}$$\n",
    "\n",
    "Donc il y a $m=\\frac{p-1}{4}$ changements de signes si $p\\equiv 1\\ [4]$ et $m=\\frac{p+1}{4}$ si\n",
    "$p\\equiv 3\\ [4]$. Finalement\n",
    "$$\\left(\\frac{2}{p}\\right)=\\begin{cases}(-1)^{(p-1)/4}&\\text{si $\\equiv 1\\ [4]$}\\\\\n",
    "                                        (-1)^{(p+1)/4}&\\text{si $\\equiv 3\\ [4]$}\n",
    "                                        \\end{cases}\n",
    "                                        $$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}