Introduction à la théorie des nombres/Nombres premiers et fonctions arithmétiques

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Rappels d'arithmétique élémentaire

Dans un anneau commutatif intègre $A$ :

PGCD, PPCM

• 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 ».

Début d'un lemme

Lemme d'Euclide, Lemme de Gauss

• 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.

Fin du lemme

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.

Début d’un théorème

Théorème fondamental de l'arithmétique

Tout entier strictement positif peut se décomposer en un produit de nombres premiers, de façon unique (à l'ordre des facteurs près).

Fin du théorème

Rappelons que ce théorème se démontre par récurrence (pour l'unicité, on utilise le lemme d'Euclide).

Début d’un théorème

Théorème d'Euclide sur les nombres premiers

Il existe une infinité de nombres premiers.

Fin du théorème

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}$.

Début d’un théorème

Petit théorème de Fermat

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}}$.

Fin du théorème

Démonstration

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é

Définition

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$.

Début de l'exemple

Exemples de fonctions complètement multiplicatives

• $\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}$).

Fin de l'exemple

Indicatrice d'Euler

Définition

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$.

Début d’un théorème

Théorème

Pour tout entier $n\geq 1$, $\varphi (n)$ est égal :

1. 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}$ ;
2. au nombre de générateurs d'un groupe cyclique d'ordre $n$.

Fin du théorème

Démonstration

1. 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).
2. 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.

 

Corollaire

1. $\varphi$ est multiplicative ;
2. 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émonstration

1. 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.
2. 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}$.

Faites ces exercices : Exercice 1-6.

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

Définition

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)$.

Début de l'exemple

Exemples

• $\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}}$.

Fin de l'exemple

Le théorème suivant sera démontré en exercice :

Faites ces exercices : Exercice 1-5.

Début d’un théorème

Théorème

L'ensemble des fonctions arithmétiques, muni de l'addition et de la convolution de Dirichlet, forme un anneau commutatif intègre.

Fin du théorème

Début d’un théorème

Théorème

Une fonction arithmétique $f$ est inversible pour la convolution si et seulement si $f(1)\neq 0$.

Fin du théorème

Démonstration

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}$.

 

Début d’un théorème

Théorème

Dans l'anneau de convolution des fonctions arithmétiques, l'ensemble des fonctions multiplicatives est un sous-groupe du groupe des inversibles.

Fin du théorème

Démonstration

• 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

Définition

La fonction inverse de ${\bf {1}}$ pour $*$ est notée $\mu$ et appelée la fonction de Möbius.

Début d’un théorème

Théorème

$\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}}$

Fin du théorème

Démonstration

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 :

Corollaire

$\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)$.

Début de l'exemple

Exemple

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}}$.

Fin de l'exemple

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) :

Définition

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}}}$.

Début d’un théorème

Théorème

$\zeta (s)=\prod _{p{\text{ premier}}}{\frac {1}{1-p^{-s}}}$.

Fin du théorème

Démonstration

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}}}$.

 

Pour information

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).

Définition

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 :

Propriété

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

Faites ces exercices : Exercices 1-8 et 1-7.

• 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).

Début d’un théorème

Théorème des nombres premiers

$\pi (x)\sim {\frac {x}{\ln x}}$   (Hadamard et La Vallée Poussin, 1896).

Fin du théorème

Faites ces exercices : Exercice 1-9.

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.

Problèmes de Landau

(Congrès international des mathématiciens de 1912) :

• 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.

Début d’un théorème

Théorème de la progression arithmétique

(Dirichlet, 1841)

Pour tout entier $n$ non nul et tout entier $m$ premier avec $n$, il existe une infinité de nombres premiers congrus à $m{\bmod {n}}$.

Fin du théorème

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 :

Début d’un théorème

Solution du dixième problème de Hilbert

(Iouri Matiassevitch, 1970)

Tout ensemble récursivement énumérable est diophantien.

Fin du théorème

Explications

• 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.