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

Exercice 1-1

On se place dans un anneau commutatif intègre quelconque, et l'on ne spécifie donc les pgcd et ppcm qu'à association près ($\sim$). Démontrer que si $c\neq 0$ :

1. si $\operatorname {PGCD} (ac,bc)$ existe alors $\operatorname {PGCD} (a,b)$ existe et $\operatorname {PGCD} (ac,bc)\sim c\operatorname {PGCD} (a,b)$ ;
2. $\operatorname {PPCM} (ac,bc)$ existe si et seulement si $\operatorname {PPCM} (a,b)$ existe, et dans ce cas : $\operatorname {PPCM} (ac,bc)\sim c\operatorname {PPCM} (a,b)$ ;
3. si $\operatorname {PPCM} (a,b)$ existe alors $\operatorname {PGCD} (a,b)$ aussi (pour info : la réciproque est fausse : cf. Anneau à PGCD) et $\operatorname {PPCM} (a,b)\times \operatorname {PGCD} (a,b)\sim ab$ ;
4. si tous les PGCD de paires existent alors tous les PPCM aussi.

Solution

1. Même méthode que dans Arithmétique/PGCD#Propriétés du PGCD.
2. Voir Anneau (mathématiques)/Exercices/Exercices#Exercice 4.
3. $m:=\operatorname {PPCM} (a,b)$ divise $ab$, que l'on peut supposer non nul. Posons alors $d:=ab/m$. D'après le point 2, pour tout $n\in A$, $mn$ est un $\operatorname {PPCM} (an,bn)$. Par conséquent, $\forall n\in A\quad n\mid a,b\Leftrightarrow nb,an\mid ab\Leftrightarrow mn\mid ab\Leftrightarrow mn\mid md\Leftrightarrow n\mid d$, ce qui prouve que $d$ est un $\operatorname {PGCD} (a,b)$.
4. Même méthode (s'appuyant sur le point 1) que dans Arithmétique/PPCM#Théorème.

 

Exercice 1-2

Soient $m,n\in \mathbb {N} ^{*}$ premiers entre eux. Démontrer que l'application $\mathbb {N} ^{2}\to \mathbb {N} ,\,(x,y)\mapsto xy$ se restreint en une bijection de l'ensemble des couples $(x,y)$ tels que $x\mid m$ et $y\mid n$ dans l'ensemble des diviseurs de $mn$, en explicitant la bijection réciproque. (Cette propriété a servi, dans le cours, à démontrer que si $f$ et $g$ sont multiplicatives alors $f*g$ l'est aussi.)

Solution

Soient $A:=\{(x,y)\in \mathbb {N} ^{2}\mid x\mid m{\text{ et }}y\mid n\}$, $B:=\{z\in \mathbb {N} \mid {z\mid mn}\}$, $F:\mathbb {N} ^{2}\to \mathbb {N} ,\,(x,y)\mapsto xy$ et $G:\mathbb {N} \to \mathbb {N} ^{2},\,z\mapsto \left(z\land m,z\land n\right)$.

On a immédiatement $F(A)\subset B$ et $G(B)\subset A$, ce qui permet de considérer les restrictions $f:A\to B$ et $g:B\to A$ de $F$ et $G$. 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 $\land$ par rapport à $\lor$, dans tout anneau à PGCD (non nécessairement factoriel).

• $g\circ f=\mathrm {id} _{A}$, c'est-à-dire : si $x\mid m{\text{ et }}y\mid n$ alors $(xy)\land m=x$ et $(xy)\land n=y$.

  En effet, si $x\mid m{\text{ et }}y\mid n$ alors $x\land y\mid m\land y\mid m\land n=1$ donc

  $(xy)\land m=\left(x\lor y\right)\land m=\left(x\land m\right)\lor \left(y\land m\right)=x\lor 1=x$

  et de même, $(xy)\land n=y$.

• $f\circ g=\mathrm {id} _{B}$, c'est-à-dire : si $z\mid mn$ alors $\left(z\land m\right)\left(z\land n\right)=z$.

  En effet, $\left(z\land m\right)\land \left(z\land n\right)\mid m\land n=1$ donc

  $\left(z\land m\right)\left(z\land n\right)=\left(z\land m\right)\lor \left(z\land n\right)=z\land \left(m\lor n\right)=z\land mn=z$.

 

Exercice 1-3

Soient $p$ un nombre premier et $a$ un entier non divisible par $p$. On note ${\overline {k}}$ la classe modulo $p$ de tout entier $k$.

1. Montrer que l'application $\mathbb {Z} /p\mathbb {Z} \to \mathbb {Z} /p\mathbb {Z} ,\;x\mapsto ax$ est bijective et envoie $\{{\overline {k}}\mid 1\leq k\leq p-1\}$ sur lui-même.
2. En déduire que $\left(p-1\right)!\,a^{p-1}\equiv \left(p-1\right)!\mod p$.
3. En déduire le petit théorème de Fermat.
4. Soient $b,c\in \mathbb {Z}$. Montrer que si $b^{p}\equiv c^{p}{\bmod {p}}$, alors $b^{p}\equiv c^{p}{\bmod {p^{2}}}$.
5. Soient $p$ et $q$ deux nombres premiers distincts. Montrer que $p^{q-1}+q^{p-1}\equiv 1{\bmod {pq}}$.
6. Montrer que pour tous entiers $n$ et $m\geq 1$, $n^{m}-n$ est divisible par le produit de tous les nombres premiers $p$ tels que $p-1\mid m-1$. Donner la valeur de ce produit pour $m=5$, $7$ et $13$.
7. Montrer que pour tous entiers $m$ et $n$, $mn(m^{60}-n^{60})$ est divisible par 56 786 730.

Solution

1. L'application est bijective car la classe de $a{\bmod {p}}$ est inversible. Elle envoie $\{{\overline {k}}\mid 1\leq k\leq p-1\}$ (l'ensemble des inversibles de l'anneau $\mathbb {Z} /p\mathbb {Z}$) sur lui-même car dans tout anneau, un produit est inversible si et seulement si les deux facteurs le sont.
2. D'après la question précédente, les deux ensembles $\{{\overline {ka}}\mid 1\leq k\leq p-1\}$ et $\{{\overline {k}}\mid 1\leq k\leq p-1\}$ sont égaux, donc le produit de leurs $p-1$ éléments le sont.
3. La congruence précédente se simplifie par $\left(p-1\right)!$ car ce produit est inversible modulo $p$.
4. D'après le petit théorème de Fermat, $b^{p}\equiv c^{p}{\bmod {p}}\Rightarrow \exists k\in \mathbb {Z} \quad b=c+kp$. Or $(c+kp)^{n}\equiv c^{n}+nc^{n-1}kp{\bmod {p^{2}}}$ (par la formule du binôme), en particulier $(c+kp)^{p}\equiv c^{p}{\bmod {p^{2}}}$.
5. Modulo $p$ on a : $p^{q-1}+q^{p-1}\equiv q^{p-1}\equiv 1$. De même, modulo $q$, $p^{q-1}+q^{p-1}\equiv 1$.
6. Soit $p$ premier tel que $p-1\mid m-1$. Si $p\mid n$ alors $n^{m}\equiv 0\equiv n{\bmod {p}}$. Sinon, $n^{p-1}\equiv 1{\bmod {p}}$ donc $n^{m-1}\equiv 1{\bmod {p}}$ donc $n^{m}\equiv n{\bmod {p}}$. Le produit de ces nombres premiers $p$ est égal à 30 si $m=5$, à 42 si $m=7$ et à 2730 si $m=13$.
7. $56\,786\,730=2\times 3\times 5\times 7\times 13\times 31\times 61=\prod _{p{\text{ premier}} \atop p-1\mid 60}p$. Pour chacun de ces facteurs premiers $p$, ou bien $p$ divise $m$ ou $n$ et alors il divise $mn(m^{60}-n^{60})$, ou bien $p$ ne divise ni $m$ ni $n$ et alors, modulo $p$, $mn(m^{60}-n^{60})\equiv mn(1-1)=0$.

 

Exercice 1-4

1. Démontrer qu'il n'existe aucun polynôme $P$ 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 $P$, montrer qu'il existerait un $m=P(n_{0})>1$ et que tous les $P(n_{0}+rm)$ seraient alors divisibles par $m$.
2. Démontrer que plus généralement, si $f(n)=P(n,2^{n},3^{n},4^{n},\dots ,k^{n})$ où $P$ est un polynôme en $k$ variables à coefficients entiers, et si $\lim _{n\to +\infty }f(n)=+\infty$, alors $f(n)$ est un nombre composé pour une infinité de valeurs de $n\in \mathbb {N}$. Indication : en supposant que c'est faux, montrer qu'il existerait un nombre premier $p=f(n_{0})>k$ puis, en utilisant le petit théorème de Fermat, que tous les $f\left(n_{0}+rp(p-1)\right)$ seraient alors divisibles par $p$.

Solution

(H&W th. 21-22 ; Baker p. 5)

1. Supposons qu'il existe un tel $P$ (de coefficient dominant nécessairement positif) et soit $n_{0}$ tel que $m:=P(n_{0})$ soit $>1$. Pour tout entier $r$, on a, modulo $m$ : $n_{0}+rm\equiv n_{0}$ donc $P(n_{0}+rm)\equiv P(n_{0})\equiv 0$, c'est-à-dire que $P(n_{0}+rm)$ est divisible par $m$. Mais (puisque $\lim _{+\infty }P=+\infty$) pour tout $r$ suffisamment grand, on a de plus $P(n_{0}+rm)>m$, donc $P(n_{0}+rm)$ est composé : absurde.
2. Soient $f$ comme indiqué et soit $n_{1}$ tel que $\forall n\geq n_{1}\quad f(n)>k$. Supposons que $f(n)$ n'est composé que pour un nombre fini de valeurs de $n$. Il existe alors $n_{0}\geq n_{1}$ tel que $p:=f\left(n_{0}\right)$ soit premier. Pour tout entier $r$, on a, modulo $p$ : $n_{0}+rp(p-1)\equiv n_{0}$ et pour tout $i\in \{1,\dots ,p-1\}$ (en particulier pour $i=2,\dots ,k$) : $i^{n_{0}+rp(p-1)}=i^{n_{0}}\left(i^{p-1}\right)^{rp}\equiv i^{n_{0}}$ (d'après le petit théorème de Fermat), donc $f\left(n_{0}+rp(p-1)\right)\equiv f\left(n_{0}\right)\equiv 0$. On conclut comme précédemment.

 

Exercice 1-5

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 $F$ cet ensemble. On sait déjà que $(F,+)$ est un groupe abélien. Il reste à vérifier que :

• ✻ est commutative : Immédiat.
• ✻ est associative : $\forall n\in \mathbb {N} ^{*}\quad {\begin{cases}f*(g*h)\left(n\right)&=\sum _{ab=n}f(a)(g*h)(b)=\sum _{ab=n}f(a)\left[\sum _{cd=b}g(c)h(d)\right]=\sum _{acd=n}f(a)g(c)h(d)~;\\(f*g)*h\left(n\right)&=\sum _{bd=n}(f*g)(b)h(d)=\sum _{bd=n}\left[\sum _{ac=b}f(a)g(c)\right]h(d)=\sum _{acd=n}f(a)g(c)h(d).\end{cases}}$
• ✻ est distributive par rapport à l'addition : $\forall n\in \mathbb {N} ^{*}\quad \quad f*(g+h)\left(n\right)=\sum _{ab=n}f(a)(g(b)+h(b))=\sum _{ab=n}f(a)g(b)+\sum _{ab=n}f(a)h(b)=f*g\left(n\right)+f*h\left(n\right)$.
• δ₁ est neutre pour ✻ : vu en cours.
• L'anneau est intègre : soient $f,g\in F\setminus \{0\}$. Notons $u,v\in \mathbb {N} ^{*}$ les plus petits entiers tels que $f(u)\neq 0$ et $g(v)\neq 0$, et $n$ leur produit. Alors, dans la somme $f*g\left(n\right)=\sum _{ab=n}f(a)g(b)$, hormis le terme $f(u)g(v)\neq 0$, tous les termes sont nuls (soit parce que $a<u$, soit parce que $b<v$), donc $f*g\left(n\right)\neq 0$, donc $f*g\neq 0$.

 

Exercice 1-6

Soit $n\in \mathbb {N} ^{*}$.

1. Soit $d\in \mathbb {N} ^{*}$ un diviseur de $n$. On note $q=n/d$ et $G=\{{\overline {0}},{\overline {q}},2{\overline {q}},\dots ,(d-1){\overline {q}}\}\subset \mathbb {Z} /n\mathbb {Z}$.
   Montrer que pour tout ${\overline {r}}\in \mathbb {Z} /n\mathbb {Z}$, $d{\overline {r}}={\overline {0}}\Leftrightarrow {\overline {r}}\in G$, et en déduire que les éléments d'ordre $d$ du groupe $(\mathbb {Z} /n\mathbb {Z} ,+)$ sont les générateurs du sous-groupe $G$.
2. En déduire que $\sum _{d\mid n}\varphi (d)=n$.
3. Retrouver ce résultat par calcul direct, en considérant d'abord le cas où $n$ est une puissance d'un nombre premier, puis en utilisant que $\mathbf {1} *\varphi$ et $\mathrm {id}$ sont multiplicatives, après l'avoir justifié.

Solution

1. Soit ${\overline {r}}\in \mathbb {Z} /n\mathbb {Z}$ avec, sans perte de généralité, $0\leq r<n$. Alors :
   • $d{\overline {r}}={\overline {0}}\Leftrightarrow n\mid dr\Leftrightarrow dq\mid dr\Leftrightarrow q\mid r\Leftrightarrow r\in \{0,q,2q,\dots ,\left(d-1\right)q\}\Leftrightarrow {\overline {r}}\in G$ ;
   • ${\overline {r}}$ est donc d'ordre exactement $d$ si et seulement si, en plus d'appartenir à $G$, il engendre dans $G$ un sous-groupe d'ordre $d$, c'est-à-dire égal à $G$ tout entier.
2. D'après ce qui précède, pour tout diviseur $d$ de $n$, le nombre d'éléments de $(\mathbb {Z} /n\mathbb {Z} ,+)$ d'ordre $d$ est égal au nombre de générateurs d'un groupe cyclique d'ordre $d$, c'est-à-dire à $\varphi (d)$.
   En partitionnant $\mathbb {Z} /n\mathbb {Z}$ selon les ordres (divisant tous $n$) de ses éléments, on en déduit que $n=\sum _{d\mid n}\varphi (d)$.
3. Si $n=p^{k}$ avec $p$ premier alors $\sum _{d\mid n}\varphi (d)=\sum _{j=0}^{k}\varphi \left(p^{j}\right)=1+\sum _{j=1}^{k}\left(p^{j}-p^{j-1}\right)=p^{k}=n$. Donc $\mathbf {1} *\varphi$ et $\mathrm {id}$ coïncident sur les $p^{k}$.
   Or $\mathrm {id}$ est multiplicative (évident) et $\mathbf {1} *\varphi$ aussi (car $\mathbf {1}$ et $\varphi$ le sont). Donc $\mathbf {1} *\varphi =\mathrm {id}$.

 

Exercice 1-7

On note couramment $\left(p_{n}\right)_{n\geq 1}$ 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 »).

1. En examinant l'argument d'Euclide (qui montre que la suite $\left(p_{n}\right)$ est infinie), montrer (par récurrence) que $p_{n}\leq 2^{2^{n-1}}$.
2. Fixons $n$ et posons $t=\log _{2}\left(p_{n}\right)$.
   • En examinant les décompositions possibles en facteurs premiers pour tous les entiers de $1$ à $p_{n}$, démontrer que $p_{n}\leq \left(t+1\right)^{n}$.
   • En déduire que si $n\geq 5$ alors $t<n^{2}$ (on pourra admettre que $\forall x\geq 5\quad \log _{2}\left(x^{2}+1\right)<x$).
   • En déduire : $\forall n\in \mathbb {N} ^{*}\quad p_{n}\leq 2^{n^{2}}$.

Solution

1. (HW p. 15-16)
   • Initialisation : $p_{1}=2=2^{1}=2^{2^{1-1}}$.
   • Hérédité : supposons (hypothèse de récurrence forte) que pour $k$ de $1$ à $n$, on a $p_{k}\leq 2^{2^{k-1}}$ et montrons qu'alors, $p_{n+1}\leq 2^{2^{n}}$.
     Par le raisonnement d'Euclide, si $p$ est un facteur premier de $1+p_{1}\dots p_{n}$ alors $p\geq p_{n+1}$.
     Or $p\leq 1+p_{1}\dots p_{n}\leq 1+\prod _{k=1}^{n}2^{2^{k-1}}=1+2^{\sum _{k=1}^{n}2^{k-1}}=1+2^{2^{n}-1}\leq 2^{2^{n}}$ (car $2^{2^{n}-1}<2^{2^{n}}$).
     Par conséquent, $p_{n+1}\leq 2^{2^{n}}$.

   Remarques :

   • ou encore, en notant $\pi (x)$ le nombre de nombres premiers $\leq x$ : $\pi (x)\geq \log _{2}\log _{2}x$ (HW p. 16).
   • cette méthode prouve aussi que $p_{n+1}\leq p_{n}^{n}+1$, mais ce n'est pas suffisant pour la récurrence.

2. (Tenebaum p. 22)
   • Un entier compris entre $1$ et $p_{n}$ s'écrit de façon unique $\prod _{i=1}^{n}p_{i}^{k_{i}}$ avec $2^{k_{i}}\leq p_{i}^{k_{i}}\leq x\leq p_{n}<2^{t+1}$ donc $0\leq k_{i}\leq t$.
     Le nombre de ces entiers est $p_{n}$ et le nombre de $n$-uplets $\left(k_{1},\dots ,k_{n}\right)$ autorisés est majoré par $\left(t+1\right)^{n}$, donc $p_{n}\leq \left(t+1\right)^{n}$.
   • Autrement dit, $2^{t}\leq \left(t+1\right)^{n}$ c'est-à-dire $t\leq n\log _{2}\left(t+1\right)$. Pour $n\geq 5$, montrons par l'absurde que $t<n^{2}$.
     Si l'on avait $t\geq n^{2}$, c'est-à-dire $x:={\sqrt {t}}\geq n\geq 5$, on déduirait de l'indication que $\log _{2}\left(t+1\right)<{\sqrt {t}}$ et donc $t<n{\sqrt {t}}$, c'est-à-dire $t<n^{2}$ : contradiction.
   • Pour $n\geq 5$, on vient de montrer que $t+1\leq n^{2}$, donc $p_{n}<2^{t+1}\leq 2^{n^{2}}$.
     Pour $n$ de 1 à 4, on vérifie à la main que $p_{n}\leq 2^{n^{2}}$ : $2=2^{1},3<2^{4},5<2^{9},7<2^{16}$.

Justification de l'indication admise : soit $f(x)=\log _{2}\left(x^{2}+1\right)-x$, montrons que pour $x\geq 5$, $f(x)<0$.

$f'(x)={\frac {2x}{\left(x^{2}+1\right)\ln 2}}-1$ donc $f'(5)<0$ et à droite de 5, $f'$ est décroissante ($f''(x)={\frac {2\left(1-x^{2}\right)}{\left(x^{2}+1\right)^{2}\ln 2}}<0$ dès que $x>1$)

donc $f'<0$ donc $f$ est décroissante, or $f(5)=\ln _{2}(26)-5<0$, donc $f<0$.

 

Exercice 1-8

On veut démontrer que la suite $\left(p_{n+1}-p_{n}\right)$ n'est pas majorée.

1. Soit $m\in \mathbb {N} ^{*}$. Montrer que tous les entiers de $p_{1}\dots p_{m}+2$ à $p_{1}\dots p_{m}+p_{m}$ sont composés.
2. En déduire qu'il existe $n\in \mathbb {N} ^{*}$ tel que $p_{n+1}-p_{n}\geq p_{m}$.
3. Conclure.

Solution

1. Soit $q=p_{1}\dots p_{m}$. Tout entier $k$ entre $2$ et $p_{m}$ est divisible par l'un des nombres $p_{j}$ pour $1\leq j\leq m$, donc $q+k$ l'est aussi, mais $q+k>p_{j}$ donc $q+k$ est composé.
2. Si $p_{n}$ est le plus grand nombre premier $<q+2$, le suivant est $>q+p_{m}$, donc $p_{n+1}-p_{n}\geq (q+p_{m}+1)-(q+1)=p_{m}$.
3. On applique ce qui précède, après avoir choisi $p_{m}$ arbitrairement grand.

 

Exercice 1-9

Démontrer que les formulations (1), (2) et (3) suivantes du théorème des nombres premiers sont équivalentes :

$(1):p_{n}\sim n\ln n,\quad (2):\pi (x)\ln \pi (x)\sim x,\quad (3):\pi (x)\sim x/\ln x$.

($(2)$ est un intermédiaire technique ; la motivation est $(1)\Leftrightarrow (3)$.)

Indication pour $(2)\Leftrightarrow (3)$ : montrer que chacun des énoncés $(2)$ et $(3)$ implique $\ln(\pi (x))\sim \ln x$.

Solution

$(2)$ et $(3)$ impliquent tous deux $\ln(\pi (x))\sim \ln x$. En effet :

• si $f\sim _{a}g>0$ et si, au voisinage de $a$, $g$ « reste à l'écart » de la valeur $1$, c'est-à-dire si $1/(\ln g)$ est bornée, alors $\ln f\sim _{a}\ln g$, car $\ln f/\ln g-1=\ln(f/g)/\ln g\to 0$ ;
• Quand $t\to +\infty$, $\ln t\pm \ln \ln t\sim \ln t$ car quand $s:=\ln t\to +\infty$, $\ln s$ est négligeable devant $s$.

Par conséquent, $(2)\Leftrightarrow (3)$.

$(2)$ appliqué à $x=p_{n}$ donne $(1)$.

Réciproquement, si $(1)$, alors $\pi (x)\ln(\pi (x))\sim p_{\pi (x)}\leq x<p_{\pi (x)+1}\sim (\pi (x)+1)\ln(\pi (x)+1)\sim \pi (x)\ln(\pi (x))$, d'où (2).

 

Exercice 1-10

Démontrer :

1. $\zeta (s)\operatorname {DG} (\mu )(s)=1$ pour tout $s\in \mathbb {C}$ de partie réelle $>1$ ;
2. $\operatorname {DG} \left(\sigma _{a}\right)(s)=\zeta (s-a)\,\zeta (s)$ pour tout complexe $a$ et tout $s\in \mathbb {C}$ de partie réelle $>1+\max \left({\rm {Re}}(a),0\right)$.
   Rappel : $\sigma _{a}$ est la fonction « somme des puissances $a$-ièmes des diviseurs » : $\sigma _{a}(n)=\sum _{d\mid n}d^{a}$.

Solution

(H&W th. 291.) Remarquons d'abord que $\operatorname {DG} (\mathrm {id} ^{a})(s)=\sum _{n=1}^{\infty }{\frac {n^{a}}{n^{s}}}=\zeta (s-a)$ (pour tout complexe $s$ de partie réelle $>1+\operatorname {Re} (a)$), en particulier $\operatorname {DG} (\mathbf {1} )=\zeta$ (pour tout $s$ de partie réelle $>1$).

1. $\mu *\mathbf {1} =\delta _{1}$ donc $\operatorname {DG} (\mu )\,\zeta =\operatorname {DG} (\mu )\operatorname {DG} (\mathbf {1} )=\operatorname {DG} (\delta _{1})=$ la fonction constante $1$ (sur $\operatorname {Re} (s)>1$, ce qui prouve que $\zeta$ ne s'annule pas sur ce demi-plan).
2. De même, $\sigma _{a}=\mathrm {id} ^{a}*\mathbf {1}$ donc $\operatorname {DG} (\sigma _{a})(s)=\zeta (s-a)\zeta (s)$ (pour tout $s$ de partie réelle $>1,1+\operatorname {Re} (a)$).
   Par exemple (Baker p. 16) :
   • $\sum _{n=1}^{\infty }{\frac {d(n)}{n^{s}}}=\zeta (s)^{2}$ si $\operatorname {Re} (s)>1$ ;
   • $\sum _{n=1}^{\infty }{\frac {\sigma (n)}{n^{s}}}=\zeta (s-1)\zeta (s)$ si $\operatorname {Re} (s)>2$.

 

Exercice 1-11

Pour tout entier $k\geq 1$, on définit la fonction $J_{k}:\mathbb {N} ^{*}\to \mathbb {N} ^{*}$ par :

$J_{k}(n)$ est le nombre de $k$-uplets $\left(a_{1},\dots ,a_{k}\right)\in \{1,\dots ,n\}^{k}$ tels que $\operatorname {PGCD} \left(n,a_{1},\dots ,a_{k}\right)=1$.

1. Reconnaître $J_{1}$.
2. En partitionnant $\{1,\dots ,n\}^{k}$ selon les valeurs que prend, sur cet ensemble, l'application $\left(x_{1},\dots ,x_{k}\right)\mapsto \operatorname {PGCD} \left(n,x_{1},\dots ,x_{k}\right)$, démontrer que (pour tout $n\in \mathbb {N} ^{*}$)

   $n^{k}=\sum _{d\mid n}J_{k}(n/d)$.

3. En déduire que $J_{k}(n)=\sum _{d\mid n}(n/d)^{k}\mu (d)$ et que $J_{k}$ est multiplicative.
4. En déduire que $J_{k}(n)=n^{k}\prod _{p{\text{ premier}}\mid n}\left(1-{\frac {1}{p^{k}}}\right)$.
5. $J_{k}$ est-elle complètement multiplicative ?
6. Calculer $\operatorname {DG} \left(J_{k}\right)$, sachant que $\operatorname {DG} (\mathbf {1} )=\zeta$ (cours) et que $\operatorname {DG} (\mu )={\frac {1}{\zeta }}$ (exercice précédent).

Solution

1. $J_{1}=\varphi$, l'indicatrice d'Euler.
2. Si $\operatorname {pgcd} \left(n,x_{1},\dots ,x_{k}\right)=d$ alors $d\mid n$. Pour tout diviseur $d$ de $n$, les $\left(x_{1},\dots ,x_{k}\right)\in \{1,\dots ,n\}^{k}$ tels que $\operatorname {pgcd} \left(n,x_{1},\dots ,x_{k}\right)=d$ sont les produits par $d$ des $\left(a_{1},\dots ,a_{k}\right)\in \{1,\dots ,n/d\}^{k}$ tels que $\operatorname {pgcd} \left(n/d,a_{1},\dots ,a_{k}\right)=1$, donc il y en a $J_{k}(n/d)$. On a donc bien $n^{k}=\operatorname {card} (\{1,\dots ,n\}^{k})=\sum _{d\mid n}J_{k}(n/d)$.
3. D'après la question précédente, $\mathrm {id} ^{k}=J_{k}*\mathbf {1}$. Par inversion de Möbius, on en déduit que $J_{k}=\mathrm {id} ^{k}*\mu$, ce qui prouve à la fois que $J_{k}(n)=\sum _{d\mid n}(n/d)^{k}\mu (d)$ et que $J_{k}$ est multiplicative (puisque $\mathrm {id} ^{k}$ et $\mu$ le sont).
4. Pour $p$ premier et $s\in \mathbb {N} ^{*}$, $J_{k}\left(p^{s}\right)=\sum _{i=0}^{s}p^{(s-i)k}\mu (p^{i})=p^{sk}-p^{(s-1)k}=p^{sk}\left(1-{\frac {1}{p^{k}}}\right)$, d'où le résultat, par la multiplicativité de $J_{k}$. Remarquons au passage que cette multiplicativité et cette expression de $J_{k}\left(p^{s}\right)$ peuvent se déduire directement de la définition, sans utiliser les questions précédentes.
5. $J_{k}$ n'est pas complètement multiplicative : pour $p$ premier, $J_{k}\left(p^{2}\right)=p^{2k}-p^{k}\neq \left(p^{k}-1\right)^{2}=\left(J_{k}(p)\right)^{2}$.
6. D'après la question 3), $J_{k}=\mathrm {id} ^{k}*\mu$ donc $\operatorname {DG} \left(J_{k}\right)=\operatorname {DG} \left(\mathrm {id} ^{k}\right)\times \operatorname {DG} (\mu )$. Or $\operatorname {DG} (\mu )={\frac {1}{\zeta }}$ et $\operatorname {DG} \left(\mathrm {id} ^{k}\right)(s)=\sum _{n=1}^{\infty }{\frac {n^{k}}{n^{s}}}=\operatorname {DG} (\mathbf {1} )(s-k)=\zeta (s-k)$. Donc $\operatorname {DG} (J_{k})(s)={\frac {\zeta (s-k)}{\zeta (s)}}$ (pour $s\in \mathbb {C}$ de partie réelle $>k+1$).

 

Exercice 1-12

La fonction de von Mangoldt $\Lambda$ est définie sur $\mathbb {N} ^{*}$ par

$\Lambda (n)={\begin{cases}\ln p&{\text{si }}n=p^{m}{\text{ pour un nombre premier }}p{\text{ et un entier }}m\geq 1,\\0&{\text{sinon.}}\end{cases}}$

1. Montrer que pour tout entier $n\geq 1$, $\ln n=\sum _{d\mid n}\Lambda (d)$.
2. En déduire que $\Lambda (n)=-\sum _{d\mid n}\mu (d)\ln d$.

Solution

1. Notons $n=p_{1}^{a_{1}}\dots p_{r}^{a_{r}}$ la décomposition de $n$ en produit de facteurs premiers ($r\geq 0$, $a_{k}\in \mathbb {N} ^{*}$, $p_{k}$ premiers distincts). Alors,

   $\sum _{d\mid n}\Lambda (d)=\sum _{k=1}^{r}\sum _{m=1}^{a_{k}}\ln p_{k}=\sum _{k=1}^{r}a_{k}\ln p_{k}=\ln n$.

2. Par inversion de Möbius,

   $\Lambda (n)=\sum _{d\mid n}\mu (d)\ln(n/d)=\left(\sum _{d\mid n}\mu (d)\right)\ln n-\sum _{d\mid n}\mu (d)\ln d=-\sum _{d\mid n}\mu (d)\ln d$

   car $\sum _{d\mid n}\mu (d)=\left(\mu *\mathbf {1} \right)(n)=\delta _{1}(n)=0$ pour tout $n>1$ et $\ln 1=0$.

 

Exercice 1-13

(Exercice iii de Baker p. 17.)

On définit $f:\mathbb {N} ^{*}\to \mathbb {Q}$ par :

$f(n):={\frac {1}{n}}\sum _{0<a\leq n \atop a\land n=1}a$.

1. Montrer que $f$ n'est pas multiplicative.
2. Montrer que $\sum _{d\mid n}f(n/d)={\frac {n+1}{2}}$.
3. En déuire que $\forall n>1\quad f(n)={\frac {1}{2}}\varphi (n)$.

Solution

1. $f(2)={\frac {1}{2}}$, $f(3)=1$, $f(6)=1\neq f(2)f(3)$.
2. $\sum _{d\mid n}f(n/d)=\sum _{d\mid n}{\frac {d}{n}}\sum _{0<a\leq (n/d) \atop a\land (n/d)=1}a={\frac {1}{n}}\sum _{d\mid n}\sum _{0<b\leq n \atop b\land n=d}b={\frac {1}{n}}\sum _{0<b\leq n}b={\frac {n+1}{2}}$.
3. $f*\mathbf {1} ={\frac {\mathrm {id} +\mathbf {1} }{2}}$ donc par inversion de Möbius, $f={\frac {\mathrm {id} +\mathbf {1} }{2}}*\mu ={\frac {\varphi +\delta _{1}}{2}}$.
   Variante : $f*\mathbf {1} ={\frac {\mathrm {id} +\mathbf {1} }{2}}={\frac {\varphi *\mathbf {1} +\mathbf {1} }{2}}={\frac {\varphi +\delta _{1}}{2}}*\mathbf {1}$ donc puisque $\mathbf {1}$ est inversible pour la convolution, $f={\frac {\varphi +\delta _{1}}{2}}$.
   Par conséquent, $\forall n>1\quad f(n)={\frac {\varphi (n)+\delta _{1}(n)}{2}}={\frac {1}{2}}\varphi (n)$.

 

Exercice 1-14

1. Transcrire la formule d'inversion de Möbius dans le cas où les fonctions $f$ et $g$, au lieu d'être à valeurs dans $(\mathbb {C} ,+)$, sont à valeurs dans un groupe abélien noté multiplicativement, $(G,\times )$.
2. Pour $n\in \mathbb {N} ^{*}$, on définit le $n$-ième polynôme cyclotomique $\Phi _{n}$ comme le polynôme unitaire dont les racines sont simples et sont les racines primitives $n$-ièmes de $1$ dans $\mathbb {C}$ (les éléments du groupe $(\mathbb {C} ^{*},\times )$ dont l'ordre est exactement $n$) :
   $\Phi _{n}(X)=\prod _{0\leq k<n,~k\land n=1}\left(X-\exp \left({\frac {k\mathrm {i} 2\pi }{n}}\right)\right)$.
   Vérifier que $X^{n}-1=\prod _{d\mid n}\Phi _{d}(X)$.
3. En déduire que tous les polynômes cyclotomiques sont à coefficients entiers.
4. Déduire des questions 1 et 2 un moyen de calculer $\Phi _{n}$. Indication : prendre pour $G$ le groupe des fractions rationnelles non nulles à coefficients rationnels.
5. En considérant les degrés des polynômes en jeu dans les questions 2 et 4, retrouver deux formules connues.

Solution

1. Si $\forall n\in \mathbb {N} ^{*}\quad g(n)=\prod _{d|n}f(d)$ alors $\forall n\in \mathbb {N} ^{*}\quad f(n)=\prod _{d|n}g(n/d)^{\mu (d)}$.
2. Il suffit de regrouper selon leurs ordres multiplicatifs les racines $n$-ièmes de $1$.
3. Récurrence bien fondée : si les $\Phi _{d}(X)$ appartiennent à $\mathbb {Z} [X]$ pour tous les diviseurs stricts $d$ de $n$ alors $\Phi _{n}(X)={\frac {X^{n}-1}{\displaystyle {\prod _{d|n,~d\neq n}\Phi _{d}(X)}}}\in \mathbb {Z} [X]$, puisque le dénominateur est unitaire.
4. $\Phi _{n}(X)=\prod _{d|n}\left(X^{n/d}-1\right)^{\mu (d)}$.
5. $\sum _{d|n}\varphi (d)=n$ et $\varphi (n)=\sum _{d|n}\mu (d){\frac {n}{d}}$.

 

Exercice 1-15

Soit $n\in \mathbb {N} ^{*}$. On note $\Phi _{n}$ le $n$-ième polynôme cyclotomique (cf. exercice précédent).

1. Montrer qu'il existe un multiple $b$ de $n$ tel que $\Phi _{n}(b)\neq \pm 1$.
2. Soit alors $p$ un diviseur premier de $\Phi _{n}(b)$. Montrer que $b^{n}\equiv 1{\bmod {p}}$ puis, en notant $d$ l'ordre de $b$ dans $\left(\mathbb {Z} /p\mathbb {Z} \right)^{\times }$, montrer que :
   • si $d=n$, alors $p\equiv 1{\bmod {n}}$.
   • si $d$ est un diviseur strict de $n$, alors $p\mid n$.
3. En déduire (par un raisonnement analogue à celui d'Euclide dans le cas $n=1$) le cas particulier suivant du théorème de la progression arithmétique de Dirichlet :

   il existe une infinité de nombres premiers congrus à $1{\bmod {n}}$.

Solution

1. Si tous les multiples de $n$ avaient pour image $\pm 1$ par $\Phi _{n}$ alors $\Phi _{n}-1$ ou $\Phi _{n}+1$ aurait une infinité de racines donc serait nul. Or $\deg \Phi _{n}>0$. (Autre argument : $\Phi _{1}(-1)=-2$ et d'après le théorème de Zsigmondy, $\forall n\geq 2\quad \Phi _{n}(n)>1$.)
2. $p\mid \Phi _{n}(b)$ et $\Phi _{n}(X)\mid X^{n}-1$ donc $p\mid b^{n}-1$.
   • L'ordre de $b$ dans $\left(\mathbb {Z} /p\mathbb {Z} \right)^{\times }$ divise l'ordre $p-1$ du groupe.
   • Si $d$ est un diviseur strict de $n$ alors $\Phi _{n}$ fait partie des polynômes cyclotomiques (à coefficients entiers) dont ${\frac {X^{n}-1}{X^{d}-1}}$ est le produit. Puisque $p$ divise $\Phi _{n}(b)$, il divise donc ${\frac {b^{n}-1}{b^{d}-1}}=\sum _{k=0}^{n/d-1}b^{kd}\equiv \sum _{k=0}^{n/d-1}1^{k}{\bmod {p}}$, si bien qu'il divise $n/d$, qui lui-même divise $n$.
3. Soient $b$ et $p$ comme ci-dessus. Alors, $p$ ne divise pas $n$ (car il divise $\Phi _{n}(b)$, qui est congru ${\bmod {n}}$ à $\Phi _{n}(0)=\pm 1$). Il est donc congru à $1{\bmod {n}}$. De même, il existe un nombre premier $p_{2}\equiv 1{\bmod {pn}}$, puis un nombre premier $p_{3}\equiv 1{\bmod {p_{2}pn}}$, etc., et tous ces nombres premiers sont ipso facto distincts et congrus à $1{\bmod {n}}$.

Références :

• Jürgen Neukirch, Algebraic Number Theory, Springer, 2013 [lire en ligne], p. 64 , exercice 1,
• « Dirichlet's theorem on arithmetic progressions », sur math.stackexchange
• « Dirichlet's theorem on primes in arithmetic progression », sur math.stackexchange
• « Is there an “elementary” proof of the infinitude of completely split primes? », sur mathoverflow
• Ernst Wendt, « Elementarer Beweis des Satzes, dass in jeder unbegrenzten arithmetischen Progression $my+1$ unendlich viele Primzahlen vorkommen », J. reine angew. Math., vol. 115, 1895, p. 85-88 [texte intégral]
• Références de l'article de Wikipédia sur le théorème de la progression arithmétique, et de la page de discussion de cet article.

Remarque : pour tout $n\geq 2$, le plus petit nombre premier congru à $1{\bmod {n}}$ est strictement inférieur à $2^{\varphi (n)+1}$. Cf. R. Thangadurai et A. Vatwani, « The least prime congruent to one modulo n », Amer. Math. Monthly, vol. 118, n^o  8, 2011, p. 737-742 [texte intégral].

 

Exercice 1-16

Soit $f:\mathbb {N} ^{*}\to \mathbb {C}$ une fonction complètement multiplicative.

1. Démontrer que pour toutes fonctions arithmétiques $g$ et $h$,

   $(gf)*(hf)=(g*h)f$.

2. En déduire que $f*f=df$, pour une certaine fonction $d$ à préciser.
3. En déduire également que l'inverse de $f$ pour la convolution de Dirichlet est $\mu f$, où $\mu$ désigne la fonction de Möbius.
4. Démontrer que réciproquement, si une fonction multiplicative $g$ a pour inverse de $\mu g$ pour la convolution de Dirichlet, alors $g$ est complètement multiplicative (indication : évaluer $g$ sur les puissances de nombres premiers, en utilisant l'expression explicite de $\mu$ sur ces mêmes nombres).

Solution

(Apostol, th. 2.17 p. 36 et exercice 27 p. 49)

1. $\forall n\in \mathbb {N} ^{*}\quad \left((gf)*(hf)\right)(n)=\sum _{ab=n}g(a)f(a)h(b)f(b)=\sum _{ab=n}g(a)h(b)f(n)=(g*h)(n)f(n)$.
2. $f*f=df$ pour $d=\mathbf {1} *\mathbf {1}$, la fonction nombre de diviseurs.
3. $f*(\mu f)=({\mathbf {1} }*\mu )f=\delta _{1}f=f(1)\delta _{1}=\delta _{1}$.
4. Supposons que $(\mu g)*g=\delta _{1}$ et montrons que $g$ est complètement multiplicative.
   Puisqu'elle est supposée multiplicative, il suffit de vérifier que pour tout $p$ premier et tout $k\in \mathbb {N}$, $g\left(p^{k}\right)=\left(g(p)\right)^{k}$.
   Montrons-le par récurrence sur $k$. L'initialisation est immédiate et l'hérédité vient de :

   ${\begin{aligned}0&=\delta _{1}\left(p^{k+1}\right)=(\mu g*g)\left(p^{k+1}\right)\\&=\sum _{d\mid p^{k+1}}\mu (d)g(d)g(p^{k+1}/d)=\sum _{i=0}^{k+1}\mu (p^{i})g(p^{i})g(p^{k+1-i})\\&=g(1)g(p^{k+1})-g(p)g(p^{k})=g(p^{k+1})-g(p)g(p^{k}).\end{aligned}}$

 

Exercice 1-17

Soit $(u_{n})$ la suite d'entiers définie par :

$u_{0}=1,\quad u_{1}=2\quad {\text{et}}\quad \forall n\geq 2\quad u_{n}=4u_{n-1}-u_{n-2}$.

Montrer que le seul carré parfait de cette suite est $u_{0}=1$.

Solution

Modulo $5$, $u_{j}\equiv 1,2,2,1,2,\dots$ et $2$ n'est pas un carré. Donc si $u_{n}$ est un carré alors $n$ est un multiple de $3$, soit : $n=3k$.

$\forall j\in \mathbb {N} \quad u_{j}={\frac {r^{j}+r^{-j}}{2}}$ avec $r=2+{\sqrt {3}}$ (cf. Approfondissement sur les suites numériques/Récurrence affine d'ordre 2#Cas linéaire) donc

$u_{n}=u_{3k}={\frac {r^{3k}+r^{-3k}}{2}}={\frac {(r^{k}+r^{-k})^{3}-3(r^{k}+r^{-k})}{2}}=u_{k}(4u_{k}^{2}-3)$.

Or $u_{k}$ n'est pas divisible par $3$ car modulo $3$, $u_{j}\equiv 1,-1,1,-1,\dots$. On en déduit que $u_{k}$ et $4u_{k}^{2}-3$ sont premiers entre eux. Si leur produit $u_{3k}$ est un carré alors tous deux sont des carrés.

On a donc prouvé que si $u_{n}$ est un carré alors $3\mid n$ et $u_{n/3}$ est un carré. Par descente infinie, cela démontre que le seul carré de la suite est bien $u_{0}$.

 

Exercice 1-18

Pour tout $n\in \mathbb {N}$, on note $f(n)$ le nombre de solutions de l’équation $x^{2}=1$ dans $\mathbb {Z} /n\mathbb {Z}$.

1. Montrer que si $m$ et $n$ sont premiers entre eux, $f(mn)=f(m)f(n)$.
2. Soient $p$ un nombre premier impair et $k\in \mathbb {N} ^{*}$. Montrer que $f(p^{k})=2$.
3. Soit $k\in \mathbb {N} ^{*}$. Calculer $f(2^{k})$.

Solution

1. Conséquence immédiate du théorème des restes chinois.
2. Il y a au moins les deux solutions ${\bar {1}}$ et $-{\bar {1}}$, et ce sont les seules car $p$ ne peut pas diviser à la fois $x-1$ et $x+1$ donc si $p^{k}$ divise $x^{2}-1$, il divise l'un des deux facteurs.
3. On voit vite que $f(2)=1$ et $f(4)=2$. Pour tout $k\geq 3$, $f(2^{k})=4$. En effet, $2^{k}$ divise $x^{2}-1=(x+1)(x-1)$ si et seulement si $2^{k-1}$ divise $x+1$ ou $x-1$, et les quatre solutions modulo $2^{k}$ ($\pm {\bar {1}}$ et $\pm {\bar {1}}+{\bar {2}}^{k-1}$) sont distinctes dès que $k\geq 3$.