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\ne 0$ :

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

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.) Modèle:Solution

Exercice 1-3

Soient $p$ un nombre premier et $a$ un entier non divisible par $p$. On note $\bar{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 $\{\bar{k}\mid 1\le k\le p-1\}$ sur lui-même.
2. En déduire que $(p-1)!a^{p-1}\equiv (p-1)!modp$.
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}modp$, alors $b^p\equiv c^{p}mod{p}^2$.
5. Soient $p$ et $q$ deux nombres premiers distincts. Montrer que $p^{q-1}+q^{p-1}\equiv 1modpq$.
6. Montrer que pour tous entiers $n$ et $m\ge 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 Modèle:Unité.

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 $\underset{n\to +\mathrm{\infty }}{\lim }f(n)=+\mathrm{\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(n_0+rp(p-1))$ seraient alors divisibles par $p$.

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. Modèle:Solution

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=\{\bar{0},\bar{q},2\bar{q},\dots ,(d-1)\bar{q}\}\subset \mathbb{Z}/n\mathbb{Z}$.
   Montrer que pour tout $\bar{r}\in \mathbb{Z}/n\mathbb{Z}$, $d\bar{r}=\bar{0}\iff \bar{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}\phi (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 $\mathrm{𝟏}*\phi$ et $\mathrm{i}\mathrm{d}$ sont multiplicatives, après l'avoir justifié.

Exercice 1-7

On note couramment ${\left(p_n\right)}_{n\ge 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\le 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\le {(t+1)}^n$.
   • En déduire que si $n\ge 5$ alors $t<n^2$ (on pourra admettre que $\mathrm{\forall }x\ge 5{\log }_2(x^2+1)<x$).
   • En déduire : $\mathrm{\forall }n\in {\mathbb{N}}^{*}{p}_n\le 2^{n^2}$.

Exercice 1-8

Modèle:Wikipédia On veut démontrer que la suite $(p_{n+1}-p_n)$ 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\ge p_m$.
3. Conclure.

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,(2):\pi (x)\ln \pi (x)\sim x,(3):\pi (x)\sim x/\ln x$.

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

Indication pour $(2)\iff (3)$ : montrer que chacun des énoncés $(2)$ et $(3)$ implique $\ln (\pi (x))\sim \ln x$. Modèle:Solution

Exercice 1-10

Démontrer :

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

Exercice 1-11

Modèle:Wikipédia Pour tout entier $k\ge 1$, on définit la fonction $J_k:{\mathbb{N}}^{*}\to {\mathbb{N}}^{*}$ par :

$J_k(n)$ est le nombre de $k$-uplets $(a_1,\dots ,a_k)\in \{1,\dots ,n{\}}^k$ tels que $\mathrm{PGCD}(n,a_1,\dots ,a_k)=1$.

1. Reconnaître $J_1$.
2. En partitionnant $\{1,\dots ,n{\}}^k$ selon les valeurs que prend, sur cet ensemble, l'application $(x_1,\dots ,x_k)\mapsto \mathrm{PGCD}(n,x_1,\dots ,x_k)$, 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}(1-\frac{1}{p^k})$.
5. $J_k$ est-elle complètement multiplicative ?
6. Calculer $\mathrm{DG}\left(J_k\right)$, sachant que $\mathrm{DG}(\mathrm{𝟏})=\zeta$ (cours) et que $\mathrm{DG}(\mu )=\frac{1}{\zeta }$ (exercice précédent).

Exercice 1-12

Modèle:Wikipédia La fonction de von Mangoldt $\mathrm{\Lambda }$ est définie sur ${\mathbb{N}}^{*}$ par

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

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

Exercice 1-13

(Exercice iii de Baker Modèle:P..)

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

$f(n):=\frac{1}{n}\sum _{\genfrac{}{}{0ex}{}{0<a\le n}{a\wedge 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 $\mathrm{\forall }n>1f(n)=\frac{1}{2}\phi (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 $(ℂ,+)$, 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 ${\mathrm{\Phi }}_n$ comme le polynôme unitaire dont les racines sont simples et sont les racines primitives $n$-ièmes de $1$ dans $ℂ$ (les éléments du groupe $({ℂ}^{*},\times )$ dont l'ordre est exactement $n$) :
   ${\mathrm{\Phi }}_n(X)=\prod _{0\le k<n,k\wedge n=1}(X-\exp \left(\frac{k\mathrm{i}2\pi }{n}\right))$.
   Vérifier que $X^n-1=\prod _{d\mid n}{\mathrm{\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 ${\mathrm{\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.

Exercice 1-15

Soit $n\in {\mathbb{N}}^{*}$. On note ${\mathrm{\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 ${\mathrm{\Phi }}_n(b)\ne \pm 1$.
2. Soit alors $p$ un diviseur premier de ${\mathrm{\Phi }}_n(b)$. Montrer que $b^n\equiv 1modp$ puis, en notant $d$ l'ordre de $b$ dans ${(\mathbb{Z}/p\mathbb{Z})}^{\times }$, montrer que :
   • si $d=n$, alors $p\equiv 1modn$.
   • 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 à $1modn$.

Exercice 1-16

Soit $f:{\mathbb{N}}^{*}\to ℂ$ 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).

Exercice 1-17

Soit $(u_n)$ la suite d'entiers définie par :

$u_0=1,u_1=2\text{et}\mathrm{\forall }n\ge 2u_n=4u_{n-1}-u_{n-2}$.

Montrer que le seul carré parfait de cette suite est $u_0=1$. Modèle:Solution

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