En raison de limitations techniques, la typographie souhaitable du titre, « Exercice : Nombres premiers et fonctions arithmétiques Introduction à la théorie des nombres/Exercices/Nombres premiers et fonctions arithmétiques », n'a pu être restituée correctement ci-dessus.
Soient premiers entre eux. Démontrer que l'application se restreint en une bijection de l'ensemble des couples tels que et dans l'ensemble des diviseurs de , en explicitant la bijection réciproque. (Cette propriété a servi, dans le cours, à démontrer que si et sont multiplicatives alors l'est aussi.)
Solution
Soient , , et .
On a immédiatement et , ce qui permet de considérer les restrictions et de et . Pour montrer que ces deux restrictions sont des bijections réciproques l'une de l'autre, on peut utiliser la décomposition des entiers en facteurs premiers, mais le raisonnement suivant est plus général car il n'utilise que la distributivité de par rapport à , dans tout anneau à PGCD (non nécessairement factoriel).
Soient un nombre premier et un entier non divisible par . On note la classe modulo de tout entier .
Montrer que l'application est bijective et envoie sur lui-même.
En déduire que .
En déduire le petit théorème de Fermat.
Soient . Montrer que si , alors .
Soient et deux nombres premiers distincts. Montrer que .
Montrer que pour tous entiers et , est divisible par le produit de tous les nombres premiers tels que . Donner la valeur de ce produit pour , et .
Montrer que pour tous entiers et , est divisible par 56 786 730.
Solution
L'application est bijective car la classe de est inversible. Elle envoie (l'ensemble des inversibles de l'anneau ) sur lui-même car dans tout anneau, un produit est inversible si et seulement si les deux facteurs le sont.
D'après la question précédente, les deux ensembles et sont égaux, donc le produit de leurs éléments le sont.
La congruence précédente se simplifie par car ce produit est inversible modulo .
D'après le petit théorème de Fermat, . Or (par la formule du binôme), en particulier .
Modulo on a : . De même, modulo , .
Soit premier tel que . Si alors . Sinon, donc donc . Le produit de ces nombres premiers est égal à 30 si , à 42 si et à 2730 si .
. Pour chacun de ces facteurs premiers , ou bien divise ou et alors il divise , ou bien ne divise ni ni et alors, modulo , .
Démontrer qu'il n'existe aucun polynôme non constant à coefficients entiers dont toutes les valeurs à partir d'un certain rang soient des nombres premiers. Indication : en supposant qu'il existe un tel , montrer qu'il existerait un et que tous les seraient alors divisibles par .
Démontrer que plus généralement, si où est un polynôme en variables à coefficients entiers, et si , alors est un nombre composé pour une infinité de valeurs de . Indication : en supposant que c'est faux, montrer qu'il existerait un nombre premier puis, en utilisant le petit théorème de Fermat, que tous les seraient alors divisibles par .
Solution
(H&W th. 21-22 ; Baker p. 5)
Supposons qu'il existe un tel (de coefficient dominant nécessairement positif) et soit tel que soit . Pour tout entier , on a, modulo : donc , c'est-à-dire que est divisible par . Mais (puisque ) pour tout suffisamment grand, on a de plus , donc est composé : absurde.
Soient comme indiqué et soit tel que . Supposons que n'est composé que pour un nombre fini de valeurs de . Il existe alors tel que soit premier. Pour tout entier , on a, modulo : et pour tout (en particulier pour ) : (d'après le petit théorème de Fermat), donc . On conclut comme précédemment.
Démontrer que l'ensemble des fonctions arithmétiques, muni de l'addition et de la convolution de Dirichlet, forme un anneau commutatif intègre.
Solution
Notons cet ensemble. On sait déjà que est un groupe abélien. Il reste à vérifier que :
✻ est commutative : Immédiat.
✻ est associative :
✻ est distributive par rapport à l'addition : .
δ1 est neutre pour ✻ : vu en cours.
L'anneau est intègre : soient . Notons les plus petits entiers tels que et , et leur produit. Alors, dans la somme , hormis le terme , tous les termes sont nuls (soit parce que , soit parce que ), donc , donc .
Soit un diviseur de . On note et . Montrer que pour tout , , et en déduire que les éléments d'ordre du groupe sont les générateurs du sous-groupe .
En déduire que .
Retrouver ce résultat par calcul direct, en considérant d'abord le cas où est une puissance d'un nombre premier, puis en utilisant que et sont multiplicatives, après l'avoir justifié.
Solution
Soit avec, sans perte de généralité, . Alors :
;
est donc d'ordre exactement si et seulement si, en plus d'appartenir à , il engendre dans un sous-groupe d'ordre , c'est-à-dire égal à tout entier.
D'après ce qui précède, pour tout diviseur de , le nombre d'éléments de d'ordre est égal au nombre de générateurs d'un groupe cyclique d'ordre , c'est-à-dire à . En partitionnant selon les ordres (divisant tous ) de ses éléments, on en déduit que .
Si avec premier alors . Donc et coïncident sur les . Or est multiplicative (évident) et aussi (car et le sont). Donc .
On note couramment la suite des nombres premiers, rangés par ordre strictement croissant.
On va en donner deux majorations faciles (plus grossières même que celle du « petit théorème des nombres premiers »).
En examinant l'argument d'Euclide (qui montre que la suite est infinie), montrer (par récurrence) que .
Fixons et posons .
En examinant les décompositions possibles en facteurs premiers pour tous les entiers de à , démontrer que .
En déduire que si alors (on pourra admettre que ).
En déduire : .
Solution
(HW p. 15-16)
Initialisation : .
Hérédité : supposons (hypothèse de récurrence forte) que pour de à , on a et montrons qu'alors, . Par le raisonnement d'Euclide, si est un facteur premier de alors . Or (car ). Par conséquent, .
Remarques :
ou encore, en notant le nombre de nombres premiers : (HW p. 16).
cette méthode prouve aussi que , mais ce n'est pas suffisant pour la récurrence.
Un entier compris entre et s'écrit de façon unique avec donc . Le nombre de ces entiers est et le nombre de -uplets autorisés est majoré par , donc .
Autrement dit, c'est-à-dire . Pour , montrons par l'absurde que . Si l'on avait , c'est-à-dire , on déduirait de l'indication que et donc , c'est-à-dire : contradiction.
Pour , on vient de montrer que , donc . Pour de 1 à 4, on vérifie à la main que : .
Justification de l'indication admise : soit , montrons que pour , .
donc et à droite de 5, est décroissante ( dès que )
En partitionnant selon les valeurs que prend, sur cet ensemble, l'application , démontrer que (pour tout )
.
En déduire que et que est multiplicative.
En déduire que .
est-elle complètement multiplicative ?
Calculer , sachant que (cours) et que (exercice précédent).
Solution
, l'indicatrice d'Euler.
Si alors . Pour tout diviseur de , les tels que sont les produits par des tels que , donc il y en a . On a donc bien .
D'après la question précédente, . Par inversion de Möbius, on en déduit que , ce qui prouve à la fois que et que est multiplicative (puisque et le sont).
Pour premier et , , d'où le résultat, par la multiplicativité de . Remarquons au passage que cette multiplicativité et cette expression de peuvent se déduire directement de la définition, sans utiliser les questions précédentes.
n'est pas complètement multiplicative : pour premier, .
D'après la question 3), donc . Or et . Donc (pour de partie réelle ).
Transcrire la formule d'inversion de Möbius dans le cas où les fonctions et , au lieu d'être à valeurs dans , sont à valeurs dans un groupe abélien noté multiplicativement, .
Pour , on définit le -ième polynôme cyclotomique comme le polynôme unitaire dont les racines sont simples et sont les racines primitives -ièmes de dans (les éléments du groupe dont l'ordre est exactement ) : . Vérifier que .
En déduire que tous les polynômes cyclotomiques sont à coefficients entiers.
Déduire des questions 1 et 2 un moyen de calculer . Indication : prendre pour le groupe des fractions rationnelles non nulles à coefficients rationnels.
En considérant les degrés des polynômes en jeu dans les questions 2 et 4, retrouver deux formules connues.
Solution
Si alors .
Il suffit de regrouper selon leurs ordres multiplicatifs les racines -ièmes de .
Soit . On note le -ième polynôme cyclotomique (cf. exercice précédent).
Montrer qu'il existe un multiple de tel que .
Soit alors un diviseur premier de . Montrer que puis, en notant l'ordre de dans , montrer que :
si , alors .
si est un diviseur strict de , alors .
En déduire (par un raisonnement analogue à celui d'Euclide dans le cas ) le cas particulier suivant du théorème de la progression arithmétique de Dirichlet :
il existe une infinité de nombres premiers congrus à .
Solution
Si tous les multiples de avaient pour image par alors ou aurait une infinité de racines donc serait nul. Or . (Autre argument : et d'après le théorème de Zsigmondy, .)
et donc .
L'ordre de dans divise l'ordre du groupe.
Si est un diviseur strict de alors fait partie des polynômes cyclotomiques (à coefficients entiers) dont est le produit. Puisque divise , il divise donc , si bien qu'il divise , qui lui-même divise .
Soient et comme ci-dessus. Alors, ne divise pas (car il divise , qui est congru à ). Il est donc congru à . De même, il existe un nombre premier , puis un nombre premier , etc., et tous ces nombres premiers sont ipso facto distincts et congrus à .
Ernst Wendt, « Elementarer Beweis des Satzes, dass in jeder unbegrenzten arithmetischen Progression unendlich viele Primzahlen vorkommen », J. reine angew. Math., vol. 115, 1895, p. 85-88 [texte intégral]
Remarque : pour tout , le plus petit nombre premier congru à est strictement inférieur à . Cf. R. Thangadurai et A. Vatwani, « The least prime congruent to one modulo n », Amer. Math. Monthly, vol. 118, no 8, 2011, p. 737-742 [texte intégral].
Démontrer que pour toutes fonctions arithmétiques et ,
.
En déduire que , pour une certaine fonction à préciser.
En déduire également que l'inverse de pour la convolution de Dirichlet est , où désigne la fonction de Möbius.
Démontrer que réciproquement, si une fonction multiplicative a pour inverse de pour la convolution de Dirichlet, alors est complètement multiplicative (indication : évaluer sur les puissances de nombres premiers, en utilisant l'expression explicite de sur ces mêmes nombres).
Supposons que et montrons que est complètement multiplicative. Puisqu'elle est supposée multiplicative, il suffit de vérifier que pour tout premier et tout , . Montrons-le par récurrence sur . L'initialisation est immédiate et l'hérédité vient de :