Introduction à la théorie des nombres/Nombres premiers et fonctions arithmétiques
Rappels d'arithmétique élémentaire
modifierDans un anneau commutatif intègre :
- Un PGCD de et est un élément (noté ou ) tel que les diviseurs communs à et soient exactement les diviseurs de . Il est donc « caractérisé[1] » par :
- .
- et sont dits premiers entre eux si [2].
- Un PPCM de et est un élément (noté ou ) tel que les multiples communs à et soient exactement les multiples de . Il est donc « caractérisé[1] » par :
- .
Autrement dit, dans , pour le préordre de divisibilité (qui sur 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).
Rappelons le principe de la preuve : pour tous nombres premiers et tout facteur premier p de , le nombre p est différent de .
Soit premier. Pour tout non divisible par , mod ou, ce qui est équivalent : pour tout , .
Le groupe multiplicatif de l'anneau est d'ordre 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
modifierMultiplicativité
modifier
Une fonction arithmétique, c'est-à-dire une application ( corps commutatif, en général ), est dite :
- multiplicative si et ;
- complètement multiplicative si l'on a même , sans hypothèse sur et .
- (« Dirac en 1 », définie par et pour tout entier ) ;
- (la fonction constante ) ;
- (l'application identité) ;
- tous les produits et puissances (même d'exposant complexe) de fonctions complètement multiplicatives, par exemple (remarque : ).
Indicatrice d'Euler
modifier
L'indicatrice d'Euler est la fonction arithmétique définie par :
pour tout entier , est le nombre d'entiers premiers avec tels que [3].
Pour tout entier , est égal :
- au nombre d'éléments du groupe des inversibles de l'anneau ;
- au nombre de générateurs d'un groupe cyclique d'ordre .
- Un élément est inversible si et seulement si , c'est-à-dire si et seulement si , donc si et seulement si et sont premiers entre eux (si d'après Bézout, et évidemment seulement si).
- Tout groupe cyclique d'ordre est isomorphe au groupe , dont les générateurs sont les éléments dont est multiple, c'est-à-dire les inversibles de l'anneau.
- D'après le théorème chinois, si et sont premiers entre eux, le morphisme d'anneaux canonique de dans est bijectif. Le morphisme de groupes obtenu par restriction, de dans , est alors bijectif.
- Pour tout nombre premier et tout , , et l'on conclut par multiplicativité de .
Remarque : n'est donc pas complètement multiplicative : par exemple, .
Faites ces exercices : Exercice 1-6. |
On démontrera en exercice l'identité remarquable (dans ce contexte, ce type de somme est toujours, implicitement, indexé par les diviseurs positifs de ).
Anneau de convolution
modifier
Le produit de convolution de deux fonctions arithmétiques et est la fonction arithmétique définie par
- .
- , d'après l'identité remarquable précédente.
- On vérifie facilement que est neutre pour , c'est-à-dire que pour toute fonction arithmétique , on a .
- Pour tout nombre complexe , la fonction « somme des puissances -ièmes des diviseurs », , peut s'écrire . En particulier la fonction « nombre de diviseurs », notée (ou parfois ), est égale à , et la fonction « somme des diviseurs », notée , est égale à . Un calcul élémentaire donne, pour premier :
- ,
- en particulier :
- et [4].
Le théorème suivant sera démontré en exercice :
Faites ces exercices : Exercice 1-5. |
L'ensemble des fonctions arithmétiques, muni de l'addition et de la convolution de Dirichlet, forme un anneau commutatif intègre[5].
Cette condition est évidemment nécessaire, pour que le nombre puisse être égal à .
Réciproquement, si , la fonction définie récursivement par et vérifie, par construction, .
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 .
- La convolée de deux fonctions multiplicatives est multiplicative. En effet, soient premiers entre eux. D'après les propriétés du PGCD (exercice 1-2) :
- .
- Toute fonction multiplicative est inversible pour (d'après le théorème précédent) et son inverse est multiplicative. En effet, si désigne la fonction multiplicative qui coïncide avec sur les puissances des nombres premiers, alors est multiplicative (d'après le point précédent) et coïncide avec sur ces puissances, donc partout, ce qui montre que donc que est multiplicative.
La complète multiplicativité n'est pas préservée par -produit ni -inverse. Par exemple, la fonction « nombre de diviseurs », , et la fonction de Möbius ci-dessous, ne sont pas complètement multiplicatives. |
Fonction de Möbius
modifier
Le calcul général ci-dessus de l' -inverse d'une fonction arithmétique telle que donne, quand on l'applique à : pour tout nombre premier ,
donc et si (par récurrence), si bien que (par multiplicativité) l'expression de pour tout est bien celle annoncée pour .
Par définition de , pour toutes fonctions arithmétiques et , on a l'équivalence , autrement dit :
Remarque : cette équivalence reste vraie si et (définies sur ) sont à valeurs dans n'importe quel groupe abélien au lieu de .
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) :
Cette égalité permit à Euler de conjecturer (1735) que , ce qu'il démontra ensuite plus élémentairement (1741). On connaît à présent les valeurs de ζ(2n) pour tout .
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 une fonction arithmétique. On définit sa série de Dirichlet génératrice, que nous noterons dans ce cours , par :
pour les 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 :
pour tous les complexes 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 et ; leurs séries de Dirichlet sont clairement la fonction constante (sur ) et la fonction . 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
modifierFaites ces exercices : Exercices 1-8 et 1-7. |
- On verra en exercice que l'écart entre deux nombres premiers consécutifs peut être arbitrairement grand, et l'on trouvera des majorations grossières de en fonction de (ce qui revient à minorer, en fonction de , le nombre de nombres premiers inférieurs ou égaux à ).
- Euler a pressenti que la série des inverses des nombres premiers diverge « comme » le logarithme de la série harmonique. En fait, (constante d'Euler-Mascheroni) et (constante de Meissel-Mertens, 1874).
Faites ces exercices : Exercice 1-9. |
On verra en exercice que cet énoncé équivaut à . 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 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 ? (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 telle que premier, . En affinant un peu la preuve, Tchebychev trouve que convient (c'est plus faible que la conjecture de Legendre ci-dessus), autrement dit :
- .
- En fait, pour tout , pour assez grand, d'après le (« grand ») théorème des nombres premiers.
Pour tout entier non nul et tout entier premier avec , il existe une infinité de nombres premiers congrus à .
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 à dans cette suite, si sa raison est , est équivalent à .
- 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 tel que est un nombre premier pour . Euler en a trouvé six : . 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 est dit diophantien s'il est l'ensemble des solutions d'une équation diophantienne avec paramètres ( ) ou, ce qui est équivalent (Hilary Putnam, 1960) s'il existe un polynôme à coefficients entiers dont est l'ensemble des valeurs strictement positives (quand toutes les variables parcourent ).
- Un ensemble d'entiers est dit récursivement énumérable s'il existe un algorithme qui, quand on lui donne , dit au bout d'un certain temps que — 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.
Notes
modifier- ↑ 1,0 et 1,1 Ici, la « caractérisation » est seulement à association près, c'est-à-dire à produit près par un inversible (si , on choisit le représentant appartenant à ; si où est un corps, on choisit, pour tout polynôme non nul, le polynôme unitaire associé).
- ↑ On définit de façon analogue le PGCD d'une famille non vide , et l'on dit que les sont premiers entre eux dans leur ensemble si ce PGCD est 1.
- ↑ Donc , et si , on peut remplacer par et/ou par .
- ↑ Remarque : pour tout , si et seulement si , ce qui a lieu pour au plus un nombre premier . En effet, si deux entiers n'ont pas le même ensemble de facteurs premiers, alors le quotient est irrationnel (il est donc même transcendant, d'après le théorème de Gelfond-Schneider).
- ↑ Cet anneau est en fait isomorphe à l'anneau des séries formelles en les indéterminées pour premier : E. D. Cashwell et C. J. Everett, « The ring of number-theoretic functions », Pacific J. Math., vol. 9, no 4, 1959, p. 975-985 [texte intégral].