# Introduction à la théorie des nombres/Nombres premiers et fonctions arithmétiques
## Rappels d'arithmétique élémentaire

Dans un anneau commutatif intègre $A$ :
* Un PGCD de $a$ et $b$ est un élément $d$ (noté $\operatorname {PGCD} (a,b)$ ou $a\land b$) tel que les diviseurs communs à $a$ et $b$ soient exactement les diviseurs de $d$. Il est donc « caractérisé » par :
    $\left((x\mid a)\land (x\mid b)\right)\Leftrightarrow x\mid d$.
* $a$ et $b$ sont dits premiers entre eux si $a\land b=1$.
* Un PPCM de $a$ et $b$ est un élément $m$ (noté $\operatorname {PPCM} (a,b)$ ou $a\lor b$) tel que les multiples communs à $a$ et $b$ soient exactement les multiples de $m$. Il est donc « caractérisé » par :
    $\left((a\mid x)\land (b\mid x)\right)\Leftrightarrow m\mid x$.
Autrement dit, dans $A$, pour le préordre de divisibilité (qui sur $\mathbb {N}$ est un ordre), pgcd = borne inf et ppcm = borne sup. Ils n'existent pas toujours, et même lorsqu'ils existent, on n'a pas toujours l'identité de Bézout. Pour plus de détails, voir l'exercice 1-1, ainsi que « Anneau à PGCD » et « Anneau de Bézout ».
* Lemme d'Euclide — Si un nombre premier p divise le produit de deux entiers a et b, alors p divise a ou b.
* Lemme de Gauss — Si un nombre entier a divise le produit de deux autres nombres entiers b et c, et si a est premier avec b, alors a divise c.
Gauss avait démontré le lemme d'Euclide directement (par descente infinie sur b pour a et p fixés), mais il se déduit immédiatement du lemme de Gauss, qui est vrai dans tout anneau (commutatif intègre) à PGCD.
Tout entier strictement positif peut se décomposer en un produit de nombres premiers, de façon unique (à l'ordre des facteurs près).
Rappelons que ce théorème se démontre par récurrence (pour l'unicité, on utilise le lemme d'Euclide).
Il existe une infinité de nombres premiers.
Rappelons le principe de la preuve : pour tous nombres premiers $p_{1},\dots ,p_{n}$ et tout facteur premier p de $1+p_{1}\dots p_{n}$, le nombre p est différent de $p_{1},\dots ,p_{n}$.
Soit $p$ premier. Pour tout $a\in \mathbb {Z}$ non divisible par $p$, $a^{p-1}\equiv 1$ mod $p$ ou, ce qui est équivalent : pour tout $a\in \mathbb {Z}$, $a^{p}\equiv a{\pmod {p}}$.
Le groupe multiplicatif de l'anneau $\mathbb {Z} /p\mathbb {Z}$ est d'ordre $p-1$ et l'ordre d'un élément d'un groupe (ou plus généralement, l'ordre d'un sous-groupe) divise l'ordre du groupe (théorème de Lagrange). Pour une preuve moins « savante », voir l'exercice 1-3.

## Fonctions arithmétiques
### Multiplicativité

Une fonction arithmétique, c'est-à-dire une application $f:\mathbb {N} ^{*}\to K$ ($K$ corps commutatif, en général $\mathbb {C}$), est dite :
* multiplicative si $f(1)=1$ et $a\land b=1\Rightarrow f(ab)=f(a)f(b)$ ;
* complètement multiplicative si l'on a même $f(ab)=f(a)f(b)$, sans hypothèse sur $a$ et $b$.
* $\delta _{1}$ (« Dirac en 1 », définie par $\delta _{1}(1)=1$ et $\delta _{1}(n)=0$ pour tout entier $n>1$) ;
* $\mathbf {1}$ (la fonction constante $n\mapsto 1$) ;
* $\mathrm {id}$ (l'application identité) ;
* tous les produits et puissances (même d'exposant $a$ complexe) de fonctions complètement multiplicatives, par exemple $\mathrm {id} ^{a}:n\mapsto n^{a}$ (remarque : $\mathbf {1} =\mathrm {id} ^{0}$).

### Indicatrice d'Euler

L'indicatrice d'Euler est la fonction arithmétique $\varphi$ définie par :
pour tout entier $n\geq 1$, $\varphi (n)$ est le nombre d'entiers $k$ premiers avec $n$ tels que $0<k\leq n$.
Pour tout entier $n\geq 1$, $\varphi (n)$ est égal :
* au nombre d'éléments du groupe $\left(\mathbb {Z} /n\mathbb {Z} \right)^{\times }$ des inversibles de l'anneau $\mathbb {Z} /n\mathbb {Z}$ ;
* au nombre de générateurs d'un groupe cyclique d'ordre $n$.
* Un élément ${\overline {k}}\in \mathbb {Z} /n\mathbb {Z}$ est inversible si et seulement si $\exists u\in \mathbb {Z} \quad n\mid ku-1$, c'est-à-dire si et seulement si $\exists u,v\in \mathbb {Z} \quad 1=ku+nv$, donc si et seulement si $k$ et $n$ sont premiers entre eux (si d'après Bézout, et évidemment seulement si).
* Tout groupe cyclique d'ordre $n$ est isomorphe au groupe $(\mathbb {Z} /n\mathbb {Z} ,+)$, dont les générateurs sont les éléments dont ${\overline {1}}$ est multiple, c'est-à-dire les inversibles de l'anneau.
* $\varphi$ est multiplicative ;
* si $n=\prod _{i=1}^{r}p_{i}^{k_{i}}$ (avec $p_{1},\dots ,p_{r}$ premiers distincts et $k_{1},\dots ,k_{r}\in \mathbb {N} ^{*}$) alors
    $\varphi (n)=\prod _{i=1}^{r}p_{i}^{k_{i}-1}\left(p_{i}-1\right)=n\prod _{i=1}^{r}{\left(1-{\frac {1}{p_{i}}}\right)}$.
* D'après le théorème chinois, si $a$ et $b$ sont premiers entre eux, le morphisme d'anneaux canonique de $\mathbb {Z} /(ab)\mathbb {Z}$ dans $\mathbb {Z} /a\mathbb {Z} \times \mathbb {Z} /b\mathbb {Z}$ est bijectif. Le morphisme de groupes obtenu par restriction, de $\left(\mathbb {Z} /(ab)\mathbb {Z} \right)^{\times }$ dans $\left(\mathbb {Z} /a\mathbb {Z} \times \mathbb {Z} /b\mathbb {Z} \right)^{\times }=\left(\mathbb {Z} /a\mathbb {Z} \right)^{\times }\times \left(\mathbb {Z} /b\mathbb {Z} \right)^{\times }$, est alors bijectif.
* Pour tout nombre premier $p$ et tout $k\in \mathbb {N} ^{*}$, $\varphi \left(p^{k}\right)=\left|\left(\mathbb {Z} /p^{k}\mathbb {Z} \right)^{\times }\right|=p^{k}-\left|\{j\in \{1,\dots ,p^{k}\}\mid p{\text{ divise }}j\}\right|=p^{k}-\left|\{pi\mid i\in \{1,\dots ,p^{k-1}\}\}\right|=p^{k}-p^{k-1}$, et l'on conclut par multiplicativité de $\varphi$.
Remarque : $\varphi$ n'est donc pas complètement multiplicative : par exemple, $\varphi \left(2^{2}\right)=2\neq 1^{2}=\left(\varphi (2)\right)^{2}$.
On démontrera en exercice l'identité remarquable $\sum _{d\mid n}\varphi (d)=n$ (dans ce contexte, ce type de somme est toujours, implicitement, indexé par les diviseurs positifs $d$ de $n$).

### Anneau de convolution

Le produit de convolution de deux fonctions arithmétiques $f$ et $g$ est la fonction arithmétique $f*g$ définie par
    $\forall n\in \mathbb {N} ^{*}\quad (f*g)(n)=\sum _{ab=n}f(a)g(b)=\sum _{d|n}f(d)g(n/d)$.
* $\varphi *{\bf {1}}={\rm {id}}$, d'après l'identité remarquable précédente.
* On vérifie facilement que $\delta _{1}$ est neutre pour $*$, c'est-à-dire que pour toute fonction arithmétique $f$, on a $f*\delta _{1}=\delta _{1}*f=f$.
* Pour tout nombre complexe $a$, la fonction « somme des puissances $a$-ièmes des diviseurs », $\sigma _{a}:n\mapsto \sum _{d\mid n}d^{a}$, peut s'écrire $\sigma _{a}=\mathrm {id} ^{a}*\mathbf {1}$. En particulier la fonction « nombre de diviseurs », notée $d$ (ou parfois $\tau$), est égale à $\sigma _{0}=\mathbf {1} *\mathbf {1}$, et la fonction « somme des diviseurs », notée $\sigma$, est égale à $\sigma _{1}=\mathrm {id} *\mathbf {1}$. Un calcul élémentaire donne, pour $p$ premier :
       $\sigma _{a}\left(p^{k}\right)={\begin{cases}{\frac {p^{(k+1)a}-1}{p^{a}-1}}&{\text{si }}p^{a}\neq 1\\k+1&{\text{si }}p^{a}=1\end{cases}}$,
    en particulier :
       $\mathrm {d} \left(p^{k}\right)=k+1$ et $\sigma \left(p^{k}\right)={\frac {p^{k+1}-1}{p-1}}$.
Le théorème suivant sera démontré en exercice :
L'ensemble des fonctions arithmétiques, muni de l'addition et de la convolution de Dirichlet, forme un anneau commutatif intègre.
Une fonction arithmétique $f$ est inversible pour la convolution si et seulement si $f(1)\neq 0$.
Cette condition est évidemment nécessaire, pour que le nombre $(f*g)(1)=f(1)g(1)$ puisse être égal à $\delta _{1}(1)=1$.
Réciproquement, si $f(1)\neq 0$, la fonction $g$ définie récursivement par $g(1)={\frac {1}{f(1)}}$ et $\forall n>1\quad g(n)=-{\frac {1}{f(1)}}\sum _{ab=n,~b<n}f(a)g(b)$ vérifie, par construction, $f*g=\delta _{1}$.
Dans l'anneau de convolution des fonctions arithmétiques, l'ensemble des fonctions multiplicatives est un sous-groupe du groupe des inversibles.
* Cet ensemble contient $\delta _{1}$.
* La convolée $f*g$ de deux fonctions multiplicatives est multiplicative. En effet, soient $m,n\in \mathbb {N} ^{*}$ premiers entre eux. D'après les propriétés du PGCD (exercice 1-2) :
    $(f*g)(m)(f*g)(n)=\sum _{x|m,y|n}f(x)g(m/x)f(y)g(n/y)=\sum _{x|m,y|n}f(xy)g(mn/(xy))=\sum _{z|mn}f(z)g(mn/z)=(f*g)(mn)$.
* Toute fonction multiplicative $f$ est inversible pour $*$ (d'après le théorème précédent) et son inverse $g$ est multiplicative. En effet, si $h$ désigne la fonction multiplicative qui coïncide avec $g$ sur les puissances des nombres premiers, alors $h*f$ est multiplicative (d'après le point précédent) et coïncide avec $\delta _{1}$ sur ces puissances, donc partout, ce qui montre que $h=g$ donc que $g$ est multiplicative.
* La complète multiplicativité n'est pas préservée par $*$-produit ni $*$-inverse. Par exemple, la fonction « nombre de diviseurs », $\mathrm {d} =\mathbf {1} *\mathbf {1}$, et la fonction de Möbius ci-dessous, ne sont pas complètement multiplicatives.

### Fonction de Möbius

La fonction inverse de ${\bf {1}}$ pour $*$ est notée $\mu$ et appelée la fonction de Möbius.
$\forall r\in \mathbb {N} \quad \forall p_{1},\dots ,p_{r}{\text{ premiers distincts}}\quad \forall k_{1},\dots ,k_{r}\in \mathbb {N} ^{*}$
    $\mu \left(p_{1}^{k_{1}}\dots p_{r}^{k_{r}}\right)={\begin{cases}(-1)^{r}&{\text{si tous les }}k_{i}{\text{ sont égaux à }}1\\0&{\text{sinon.}}\end{cases}}$
Le calcul général ci-dessus de l'$*$-inverse $g$ d'une fonction arithmétique $f$ telle que $f(1)\neq 0$ donne, quand on l'applique à $f=\mathbf {1}$ : pour tout nombre premier $p$,
    $g(1)=1\quad {\text{et}}\quad \forall k>0\quad g\left(p^{k}\right)=-\sum _{i=0}^{k-1}g(p^{i})$
donc $g(p)=-1$ et $g\left(p^{k}\right)=0$ si $k>1$ (par récurrence), si bien que (par multiplicativité) l'expression de $g(n)$ pour tout $n\in \mathbb {N} ^{*}$ est bien celle annoncée pour $\mu$.
Par définition de $\mu$, pour toutes fonctions arithmétiques $f$ et $g$, on a l'équivalence $g=f*\mathbf {1} \Leftrightarrow f=g*\mu$, autrement dit :
$\forall n\in \mathbb {N} ^{*}\;g(n)=\sum _{d\mid n}f(d)$ si et seulement si $\forall n\in \mathbb {N} ^{*}\;f(n)=\sum _{d\mid n}\mu (d)g(n/d)$.
De $\varphi *\mathbf {1} =\mathrm {id}$, on déduit : $\varphi =\mu *\mathrm {id}$, c.-à-d $\forall n\in \mathbb {N} ^{*}\quad \varphi (n)=\sum _{d\mid n}\mu (d){\frac {n}{d}}$.
Remarque : cette équivalence reste vraie si $f$ et $g$ (définies sur $\mathbb {N} ^{*}$) sont à valeurs dans n'importe quel groupe abélien au lieu de $\mathbb {C}$.

## Fonction zêta de Riemann et autres séries de Dirichlet

La preuve du théorème des nombres premiers (voir infra) est issue de l'étude approfondie, à l'aide de méthodes d'analyse complexe, de la fonction zêta (introduite par Euler dès 1735 pour une variable réelle et étendue par Riemann dans son mémoire de 1859) :
La fonction $\zeta$ est définie, sur le demi-plan des complexes de partie réelle $>1$, par :
    $\zeta (s):=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}$.
$\zeta (s)=\prod _{p{\text{ premier}}}{\frac {1}{1-p^{-s}}}$.
Cette série étant absolument convergente, on a
    $\zeta (s)=\lim _{k\to \infty }\sum _{j_{1},\dots ,j_{k}\in \mathbb {N} }{\frac {1}{\left(p_{1}^{j_{1}}\dots p_{k}^{j_{k}}\right)^{s}}}=\lim _{k\to \infty }\prod _{i=1}^{k}\sum _{j=0}^{\infty }p_{i}^{-js}=\prod _{i=1}^{\infty }{\frac {1}{1-p_{i}^{-s}}}$.
Cette égalité permit à Euler de conjecturer (1735) que $\zeta (2)=\pi ^{2}/6$, ce qu'il démontra ensuite plus élémentairement (1741). On connaît à présent les valeurs de ζ(2n) pour tout $n\in \mathbb {N} ^{*}$.
Signalons pour l'anecdote que la « probabilité » que k entiers choisis au hasard soient premiers entre eux dans leur ensemble est 1/ζ(k) (pour k = 2, c'est un théorème de Cesàro, de 1891).
Soit $f$ une fonction arithmétique. On définit sa série de Dirichlet génératrice, que nous noterons dans ce cours $\operatorname {DG} (f)$, par :
    $\operatorname {DG} (f)(s)=\sum _{n=1}^{\infty }{\frac {f(n)}{n^{s}}}$
pour les $s\in \mathbb {C}$ pour lesquels la série converge (s'il en existe).
Pour étudier sérieusement la théorie de ces fonctions (et de leur prolongement analytique) il faut s'attaquer à des questions de convergence plus fines que dans la théorie des fonctions holomorphes, ce que nous ne ferons pas ici. Nous nous satisferons de la propriété suivante, qui résulte simplement des propriétés du produit de Cauchy de deux séries :
La multiplication des séries de Dirichlet est compatible avec la convolution de Dirichlet, au sens suivant :
    $\operatorname {DG} (f)(s)\times \operatorname {DG} (g)(s)=\operatorname {DG} (f*g)(s)$
pour tous les complexes $s$ tels que les deux séries du côté gauche convergent et que l'une des deux converge absolument.
(Noter que la simple convergence des deux séries à gauche n'implique pas celle de la série à droite.) Ceci ressemble au lien entre convolution et multiplication dans la transformation de Fourier.
Un caractère de Dirichlet est une fonction arithmétique complètement multiplicative et périodique. Les deux plus simples sont $\delta _{1}$ et $\mathbf {1}$ ; leurs séries de Dirichlet sont clairement la fonction constante $\mathbf {1}$ (sur $\mathbb {C}$) et la fonction $\zeta$. Un autre exemple de caractère de Dirichlet est le symbole de Legendre, cf. chap. 4. Les séries associées aux caractères de Dirichlet interviennent dans la preuve du théorème de la progression arithmétique (voir infra).

## Énoncés de quelques conjectures et théorèmes célèbres sur les nombres premiers

* On verra en exercice que l'écart $p_{n+1}-p_{n}$ entre deux nombres premiers consécutifs peut être arbitrairement grand, et l'on trouvera des majorations grossières de $p_{n}$ en fonction de $n$ (ce qui revient à minorer, en fonction de $x$, le nombre $\pi (x)$ de nombres premiers inférieurs ou égaux à $x$).
* Euler a pressenti que la série des inverses des nombres premiers diverge « comme » le logarithme de la série harmonique. En fait, $\sum _{k=1}^{n}{\frac {1}{k}}-\ln n\to \gamma$ (constante d'Euler-Mascheroni) et $\sum _{p_{i}\leq n}{\frac {1}{p}}_{i}-\ln(\ln(n))\to M$ (constante de Meissel-Mertens, 1874).
          $\pi (x)\sim {\frac {x}{\ln x}}$ (Hadamard et La Vallée Poussin, 1896).
On verra en exercice que cet énoncé équivaut à $p_{n}\sim n\ln n$. Le « petit théorème des nombres premiers » (Tchebychev, 1850), qui dit seulement « est de l'ordre de » au lieu de « est équivalent », est bien plus élémentaire.
* Conjecture de Goldbach, 1741 (8e problème de Hilbert, CIM de 1900) : tout entier pair $\geq 4$ est-il somme de deux nombres premiers ?
* Nombres premiers jumeaux (fait aussi partie du 8e problème de Hilbert, ainsi que l'hypothèse de Riemann) : existe-il une infinité de nombres premiers p tels que p + 2 soit aussi premier ?
* Conjecture de Legendre : existe-t-il toujours un nombre premier entre deux carrés parfaits consécutifs ?
* Existe-t-il une infinité de nombres premiers de la forme $n^{2}+1$ ? (on sait depuis Henryk Iwaniec, 1978, qu'il y en a au moins une infinité de semi-premiers).
* « Postulat » de Bertrand : le « petit théorème des nombres premiers » permet d'affirmer qu'il existe une constante $C$ telle que $\forall n>1~\exists p$ premier, $n<p<Cn$. En affinant un peu la preuve, Tchebychev trouve que $C=2$ convient (c'est plus faible que la conjecture de Legendre ci-dessus), autrement dit :
       $p_{n+1}<2p_{n},~{\text{ou encore :}}~\pi (2n)>\pi (n)$.
    En fait, pour tout $C>1$, $\pi (Cx)-\pi (x)>0$ pour $x$ assez grand, d'après le (« grand ») théorème des nombres premiers.
Pour tout entier $n$ non nul et tout entier $m$ premier avec $n$, il existe une infinité de nombres premiers congrus à $m{\bmod {n}}$.
Version quantitative de La Vallée Poussin (qui généralise le théorème des nombres premiers) :
    le nombre de nombres premiers inférieurs ou égaux à $x$ dans cette suite, si sa raison est $n$, est équivalent à ${\frac {1}{\varphi (n)}}\times {\frac {x}{\ln x}}$.
* Théorème de Green-Tao (2004) : la suite des nombres premiers contient des suites arithmétiques arbitrairement longues.
* Formules polynomiales
** Un nombre chanceux d'Euler est un entier $p>1$ tel que $n^{2}-n+p$ est un nombre premier pour $n=1,\dots ,p-1$. Euler en a trouvé six : $p=2,3,5,11,17,41$. Il n'y en a pas d'autres (Kurt Heegner, 1952).
** Il n'existe pas de polynôme (non constant) à coefficients entiers dont toutes les valeurs à partir d'un certain rang soient premières (on le montrera dans l'exercice 1-4).
** Dixième problème de Hilbert : l'ensemble des équations diophantiennes résolubles est-il récursif, c'est-à-dire : existe-t-il un algorithme universel qui, quand on lui donne n, répond si la n-ième équation (pour une numérotation naturelle de toutes les équations) a des solutions ou pas ? Réponse : non et même pire :
Tout ensemble récursivement énumérable est diophantien.
* Un ensemble $S$ est dit diophantien s'il est l'ensemble des solutions d'une équation diophantienne avec paramètres ($S=\{x\in \mathbb {N} \mid \exists y_{1},\dots ,y_{k}\in \mathbb {N} ,P(x,y_{1},\dots ,y_{k})=0\}$) ou, ce qui est équivalent (Hilary Putnam, 1960) s'il existe un polynôme $Q$ à coefficients entiers dont $S$ est l'ensemble des valeurs strictement positives (quand toutes les variables parcourent $\mathbb {N}$).
* Un ensemble $S$ d'entiers est dit récursivement énumérable s'il existe un algorithme qui, quand on lui donne $n$, dit au bout d'un certain temps que $n\in S$ — si c'est vrai — ou tourne indéfiniment sinon.
Il existe des ensembles récursivement énumérables non récursifs donc, d'après le théorème de Matiassevitch, il existe une suite d'équations diophantiennes (dont le degré et le nombre d'inconnues sont même bornés) pour laquelle aucun algorithme ne peut répondre correctement pour chaque n à la question « la n-ième équation a-t-elle des solutions ? ».
Une retombée surprenante du théorème de Matiassevitch est (puisque l'ensemble des nombres premiers est évidemment récursivement énumérable, et même récursif) qu'il existe un polynôme Q (de degré 25, à 26 variables) dont les valeurs strictement positives sont exactement les nombres premiers.