Nombres premiers

Exercice 4101. Si $p$ est un entier premier supérieur ou égal à $5$, montrer que $p^2 - 1$ est un multiple de $12$.
Exercice 4102. Montrer que si $n$ est un entier non divisible par $5$, alors $n^4\equiv1[5]$.
Exercice 4103. Justifier l'existence de $1000$ entiers consécutifs sans nombres premiers.
Exercice 4104. Soit $n \in \mathbb{N}$. \\
  1. Montrer que $\sqrt{n} \in \mathbb{Q} \iff \exists m \in \mathbb{N},\ n=m^2$. \\
  2. En déduire que $\sqrt{2} \notin \mathbb{Q}$ et $\sqrt{3} \notin \mathbb{Q}$.
Exercice 4105. Montrer que pour tout nombre premier $p$, il existe un entier naturel $n$ tel que \[ 6n^2+5n+1 \equiv 0 \pmod{p}. \]
Exercice 4106. Soient $p \in \mathbb{P}$ et $\alpha \in \mathbb{N}^*$. \\ Déterminer les diviseurs positifs de $p^\alpha$.
Exercice 4107. Soient $n > 2$ et $N$ la somme de $n$ entiers impairs consécutifs.\\ Montrer que $N$ n'est pas un nombre premier.
Exercice 4108. Montrer que le nombre entier $A = 5^{45} + 4^{30}$ est composé, c’est-à-dire non premier.
Exercice 4109. Montrer que, pour tout $n \in \mathbb{Z}$, le nombre entier $n^4-20n^2+4$ est composé, c’est-à-dire n’est pas premier.
Exercice 4110. Montrer qu’un entier $n>1$ est un nombre premier ssi il n’est divisible par aucun nombre premier inférieur ou égal à $\sqrt{n}$.
Exercice 4111. Montrer qu'un entier $n > 1$ est un nombre premier ssi il n'est divisible par aucun nombre premier inférieur ou égal à $\sqrt{n}$.
Exercice 4112. Soit $n$ un entier non nul, montrer que $42$ divise $n^{13}-n$, en utilisant le petit théorème de Fermat.
Exercice 4113. Existe-t-il des nombres premiers $p$ tels que $8p+1$ et $8p-1$ soient tous les deux premiers ?
Exercice 4114. Notons $\varphi$ l’indicatrice d’Euler.\\
  1. Montrer que si $d\mid n$ avec $n\geqslant 2$ alors $\varphi(d)$ représente le nombre d’entiers d’ordre $d$ dans $(\mathbb{Z}/n\mathbb{Z},+)$.\\
  2. En déduire que \[ \Sum_{d\mid n}\varphi(d)=n. \]
Exercice 4115. Soient \[ p_1 < p_2 < \dots \] la suite des nombres premiers, $n\in\N$ puis $I$ et $J$ deux parties de $\{1,\dots,n\}$. On pose \[ S_I=\prod_{k\in I}p_k,\qquad S_J=\prod_{k\in J}p_k. \] Montrer que $I=J\Longleftrightarrow S_I=S_J$.
Exercice 4116. Montrer que si $p$ est un nombre premier supérieur à $3$, alors \[ p^2\equiv1[24]. \]
Exercice 4117. Montrer que les nombres suivants sont composés.\\
  1. $4n^3+6n^2+4n+1$ avec $n \in \mathbb{N}^*$. \\
  2. $n^4-n^2+16$ avec $n \in \mathbb{Z}$.
Exercice 4118. Soient $a$ et $p$ deux entiers supérieurs à $2$.\\ Montrer que si $a^p-1$ est premier, alors $a=2$ et $p$ est premier.
Exercice 4119. Soit $n$ un naturel non nul.\\ Montrer qu'il existe toujours un nombre premier strictement compris entre $n$ et $n!+2$.
Exercice 4120. Pour $p \in \mathbb{P}$ et $n \in \mathbb{Z}$, on note $v_p(n)$ l'exposant de la plus grande puissance de $p$ divisant $n$.\\
  1. Montrer que $v_2(1000!)=994$. \\
  2. Plus généralement, calculer $v_p(n!)$.
Exercice 4121. Soit $p$ un nombre premier, $p > 5$. \\ Montrer que $p^2-1$ est divisible par $24$.
Exercice 4122. Montrer que l’ensemble $P$ des nombres premiers est infini. Montrer qu’il en est de même de l’ensemble des nombres premiers congrus à $3$ modulo $4$.
Exercice 4123. Trouver tous les nombres premiers $p$ tels que $p^2+2$ soit aussi premier.
Exercice 4124. Soient $a \geq 2$ et $n \geq 2$ deux entiers.\\ On suppose que $a^n - 1$ est un nombre premier.\\ Montrer que $a = 2$ et que $n$ est premier.
Exercice 4125. Décomposer le polynôme $X^4+4$ en produit de deux polynômes réels du second degré. \\ En déduire que $5$ est le seul nombre premier de la forme $n^4+4$ avec $n \in \N$.
Exercice 4126. Soient $a$ et $b$ deux nombres premiers tels que $a\neq b$. On pose $x=a^\alpha b^\beta$ avec $\alpha,\beta$ dans $\N^*$.\\ Quels sont les diviseurs de $x$ dans $\N^*$ ? Écrire la somme de ces diviseurs sous forme factorisée.\\ Trouver $x$ tel qu’il admette $12$ diviseurs de somme $195$.
Exercice 4127. Soient, pour tout $n \in \N$, \[ F_n=2^{2^n}+1. \] Montrer que les éléments de la suite $(F_n)_{n \in \N}$ sont premiers entre eux deux à deux, puis en déduire l'existence d'une infinité de nombres premiers.
Exercice 4128. Soit $n \in \mathbb{N}^*$. On pose $M_n = 2^n - 1$.
  1. Montrer que si $M_n$ est un nombre premier, alors $n$ est un nombre premier.
  2. Soit $p \geq 3$ un nombre premier. Montrer que si $q$ est un nombre premier divisant $M_p$, alors $q$ est de la forme $2kp + 1$ avec $k \in \mathbb{N}^*$.
Exercice 4129. On suppose que $n$ est un entier premier.\\
  1. Montrer que pour tout $p \in \llbracket 1,n-1 \rrbracket$, \[ p\binom{n}{p}=n\binom{n-1}{p-1} \]
  2. Montrer que $n$ divise $2^n-2$.\\
  3. En déduire que pour tout entier naturel $a$, $a^n \equiv a \quad (mod\ n)$.\\
  4. Si $a$ n'est pas multiple de $n$, écrire plus simplement la dernière congruence. Ce résultat s'appelle le petit théorème de Fermat.
Exercice 4130. On pose pour tout $n\in\N^*$, \[ F_n=2^{2^n}+1, \] les nombres de Fermat.\\
  1. Montrer que pour tous entiers naturels $n < m$, $F_n$ divise $F_m-2$.\\
  2. Montrer que pour tous entiers $n\neq m$ dans $\N$, on a $F_n\wedge F_m=1$.\\
  3. En déduire qu’il existe une infinité de nombres premiers.
Exercice 4131. Soit $p$ un nombre premier.\\
  1. Démontrer que pour tout $k\in\{1,\dots,p-1\}$, le nombre $\displaystyle \binom{p}{k}$ est divisible par $p$.\\
  2. Montrer que pour tout $a\in\Z$, $a^p-a\equiv0[p]$. \\
    1. Montrer que pour tout $n\in\N$, $n^5-n\equiv0[30]$. \\
    2. Montrer que pour tout $n\in\N$, $n^7-n\equiv0[42]$.
Exercice 4132. Soit $p$ un nombre premier.\\
  1. Montrer $\forall k \in \{1,2,\ldots,p-1\},\ p \mid \displaystyle \binom{p}{k}$. \\
  2. En déduire que $\forall n \in \mathbb{Z},\ n^p \equiv n \ [p]$.
Exercice 4133. Soit \[ E=\{4k-1 \mid k \in \mathbb{N}^*\} \]
  1. Montrer que pour tout $n \in E$, il existe $p \in \mathbb{P}\cap E$ tel que $p \mid n$. \\
  2. En déduire qu'il y a une infinité de nombres premiers $p$ tels que $p \equiv -1 \ [4]$.
Exercice 4134. Soit $p$ un nombre premier et $k \in \mathbb{N}^*$. Montrer que \[ \Sum_{x \in \mathbb{Z}/p\mathbb{Z}}x^k \] est égal à $0$ ou à $-1$. Préciser à quelle condition on obtient $0$ ou $-1$.
Exercice 4135. Soit $p \in \mathbb{N}^*$, $p \geqslant 2$. Montrer l'équivalence : \[ (p-1)! \equiv -1 \pmod{p} \Longleftrightarrow p \;\; \mathrm{ premier.} \]
Exercice 4136. Pour $n\in\mathbb{N}$, on note $F_n=2^{2^n}+1$. Montrer que les $F_n$ $(n\in\mathbb{N})$ sont premiers entre eux deux à deux.
Exercice 4137. Soit $p$ un nombre premier $(p\geqslant 2)$.\\
  1. Montrer : $\forall k\in\{1,\ldots,p-1\}$, $p\mid \binom{p}{k}$.\\
  2. En déduire que, pour tout $n\in\mathbb{Z}$, $n^p\equiv n\;[p]$.
Exercice 4138. Décomposer le polynôme $X^4+4$ en produit de deux polynômes réels du second degré.\\ En déduire que $5$ est le seul nombre premier de la forme $n^4+4$ avec $n \in \N$.
Exercice 4139. Soient $a$ et $b$ deux nombres premiers tels que $a\neq b$. On pose $x=a^\alpha b^\beta$ avec $\alpha,\beta \in \N^*$.\\ Quels sont les diviseurs de $x$ dans $\N^*$ ? Écrire la somme de ces diviseurs sous forme factorisée.\\ Trouver $x$ tel qu’il admette $12$ diviseurs de somme $195$.
Exercice 4140.
  1. Soit $d$ et $n$ dans $\N^*$, montrer que le nombre de multiples de $d$ dans $[1,n]$ est égal à $\left\lfloor \Frac{n}{d}\right\rfloor$.\\
  2. Montrer que pour tout nombre premier $p$, $\nu_p(n!)=\sum_{k\geqslant 1}\left\lfloor \Frac{n}{p^k}\right\rfloor$.\\
  3. Trouver la puissance de $2$ dans la décomposition en facteurs premiers de $1000!$.\\
  4. Montrer que l’écriture décimale de $1000!$ se termine par $249$ zéros.
Exercice 4141. \\
  1. Montrer qu'il existe une infinité de nombres premiers. \\
    1. Montrer que si un entier $n$ est congru à $3$ modulo $4$, alors il admet un facteur premier congru à $3$ modulo $4$. \\
    2. En déduire qu'il existe une infinité de nombres premiers congrus à $3$ modulo $4$.
Exercice 4142. On note $\mathcal{P}$ l'ensemble des nombres premiers.\\ Pour tout $n \in \Z$ et tout nombre premier $p$, on note $\nu_p(n)$ la valuation $p$-adique de $n$.\\
  1. Soit $a,b,k \in \N^*$.\\ Montrer que si $a^k \mid b^k$, alors $a \mid b$.\\
  2. Soit $n,k \in \N^*$.\\ Montrer que\\ \[ \parenthese{\exists m \in \N^* \;\; n=m^k} \iff \parenthese{\forall p \in \mathcal{P},\;\; \nu_p(n)\equiv 0\;[k] }. \]\\
  3. Soit $m,k,a,b \in \N^*$ tels que $a \wedge b = 1$ et $ab=m^k$.\\ Montrer qu'il existe $c,d \in \N^*$ tels que $a=c^k$ et $b=d^k$.
Exercice 4143. Soit $p \geqslant 2$ un nombre premier. \\
  1. Montrer que pour tout $k \in \llbracket 1,p-1 \rrbracket$, on a $p \mid \binom{p}{k}$. \\
  2. En déduire une autre preuve du petit théorème de Fermat : pour tout $n \geqslant 1$, $n^p \equiv n \; [p]$. \\
Exercice 4144. Soit $p$ un nombre premier et $k \in \{1,\ldots,p-1\}$. \\ Montrer que $p$ divise $\displaystyle \binom{p-1}{k} - (-1)^k$.
Exercice 4145. \\
  1. Montrer que l'ensemble des entiers de la forme $4n+1$ est stable par produit.\\
  2. Démontrer qu'il existe une infinité de nombres premiers de la forme $4n-1$.\\
  3. Démontrer qu'il existe une infinité de nombres premiers de la forme $6n-1$.
Exercice 4146. L'ensemble $\mathbb{P}$ des nombres premiers est infini.
Exercice 4147. On pose pour tout $n \in \N$, $F_n = 2^{2^n} + 1$.\\
  1. Soit $n \in \N^*$.\\ Si $2^n + 1$ est premier, montrer que $n$ est une puissance de $2$.\\
  2. Soit $n \geq 1$.\\ Montrer que $F_n - 2 = F_{n-1}(F_{n-1} - 2)$.\\ En déduire que $F_n = F_0F_1 \cdots F_{n-1} + 2$.\\
  3. En déduire que si $n < m$, alors $F_n$ et $F_m$ sont premiers entre eux.\\
  4. En déduire qu'il existe une infinité de nombres premiers.
Exercice 4148. Nombres de Fermat.\\
  1. Soit $m \in \N^*$ tel que $2^m+1$ soit premier. Montrer qu'il existe $n \in \N$ tel que $m=2^n$.\\
  2. Notons \[ F_n=2^{2^n}+1 \] Montrer que si $m \neq n$, $F_n$ et $F_m$ sont premiers entre eux.
Exercice 4149. On suppose admis le théorème de Fermat : si $p$ est un entier premier qui ne divise pas l'entier naturel $n$ alors il divise \[ n^{p-1}-1 \]
  1. Soit $\alpha$ un entier naturel non nul, $n$ un entier naturel non nul et $p$ un entier premier qui ne divise pas $n$, que peut-on dire de $(n^\alpha)^{p-1}-1$.\\
  2. Soit $\alpha$ un entier naturel non nul, $n$ et $m$ deux entiers naturels non nuls et $p$ un entier premier qui ne divise ni $m$, ni $n$, que peut-on dire de $(n^\alpha)^{p-1}-(m^\alpha)^{p-1}$.\\
  3. Si $m$ et $n$ sont des entiers premiers distincts et $N=m^{60}-n^{60}$, démontrer que $N$ est divisible par $56786730$.
Exercice 4150. On désire montrer qu'il existe une infinité de nombres premiers de la forme $4n+1$. Pour cela, on va supposer qu'il n'y a qu'un nombre fini de nombres premiers de cette forme. On les note \[ p_1,p_2,\dots,p_k \] et on pose $a=p_1p_2\cdots p_k$ et $N=a^2+1$. \\
  1. Soit $q$ un facteur premier de $N$. On suppose que $q$ est de la forme $4n+3$, où $n \in \N$. Montrer que $q$ divise $a^{4n+2}-1$ puis $a^4-1$ et enfin $a^2-1$. \\ Conclure sur ce choix de $q$.\\
  2. Justifier le fait que $N$ contient un facteur premier autre que $2$. Quel est le reste de la division d'un tel facteur premier par $4$ ?\\
  3. Ce facteur premier mis en évidence à la question précédente peut-il être un des nombres $p_1,\dots,p_k$. Conclure sur la problématique de l'énoncé.
Exercice 4151. On considère les deux propositions suivantes :\\ $(P_1)$ : Pour tout entier $n \geqslant 2$, il existe au moins un nombre premier $p$ tel que $n < p < 2n$.\\ $(P_2)$ : Pour tout entier $n \geqslant 2$, la décomposition de $n!$ en facteurs premiers comprend au moins un nombre à la puissance $1$.\\ Montrer que ces deux propriétés sont équivalentes.
Exercice 4152. Soit $p$ premier.\\ Montrer que \[ \Sum_{k=0}^{p}\binom{p}{k}\binom{p+k}{k}\equiv 2^p+1 \pmod{p^2}. \]
Exercice 4153. Soit $p$ un nombre premier impair.\\
  1. Montrer que si $p$ est une somme de deux carrés d'entiers, on a alors $p \equiv 1 \pmod{4}$. \\
  2. On suppose $p \equiv 1 \pmod{4}$.\\ Dénombrer les carrés dans $(\mathbb{Z}/p\mathbb{Z})^*$.\\
  3. En déduire qu'il existe $n \in \mathbb{Z}$ tel que $n^2 \equiv -1 \pmod{p}$. \\
  4. Démontrer qu'il existe $(a,b) \in \mathbb{Z}^2$ tels que $0 < b < \sqrt{p}$ et $\left|\Frac{bn}{p}-a\right| \leqslant \Frac{1}{\sqrt{p}}$. \\
  5. Montrer que $(bn-ap)^2+b^2=p$.
Exercice 4154. Pour tout $r\in\N^*$ et tout $n\in\N$, on appelle $\mathcal{P}$-suite de raison $r$ et de longueur $n$, tout $n$-uplet $(p_1,\dots,p_n)$ tel que pour tout $i\in\{1,\dots,n-1\}$, $p_{i+1}=p_i+r$ et les $p_1,\dots,p_n$ sont des nombres premiers.\\
  1. Soit $(p_1,\dots,p_n)$ une $\mathcal{P}$-suite de longueur $n\geqslant3$ et de raison $r$. Montrer que $r$ est pair et que $p_1>2$.\\
  2. Montrer que $n\leqslant p_1$.\\
  3. On suppose l’existence d’un nombre premier $q$ strictement inférieur à $n$ ne divisant pas $r$. On note pour tout $i\in\{1,\dots,n\}$, $r_i$ le reste de la division euclidienne de $p_i$ par $q$.\\
    1. Montrer que pour tous $(i,j)\in\{1,\dots,n\}^2$, \[ r_i=r_j\Longleftrightarrow q\mid(i-j). \]
    2. En déduire que les nombres $r_1,\dots,r_q$ sont deux à deux distincts.\\
    3. Établir l’existence de $s\in\{1,\dots,n\}$ tel que $p_s=q$.\\
    4. En déduire une contradiction. Qu’a-t-on montré ?
Exercice 4155. Un entier $n\in\N^*$ est dit parfait si la somme des diviseurs de $n$ est égale à $2n$. Dans toute la suite, pour tout $n\in\N^*$, on pose \[ \lambda_n=\sum_{1\leqslant d\leqslant n,\;d\mid n} d. \]
  1. Montrer que si $p$ est un nombre premier tel que $2^p-1$ est encore premier, alors le nombre $E_p=2^{p-1}(2^p-1)$ est un nombre parfait.\\
  2. Réciproquement, soit $n$ un nombre parfait pair. On pose $n=2^rm$ avec $r\in\N^*$ et $m\in\N^*$ impair.\\
    1. Montrer que $\lambda_n=\lambda_m(2^{r+1}-1)$. \\
    2. Montrer qu’il existe $c\in\N$ tel que $m=(2^{r+1}-1)c \quad \mathrm{et} \quad \lambda_m=2^{r+1}c$. \\
    3. Montrer que $c=1$ et que $2^{r+1}-1$ est premier.\\
    4. Montrer que $r+1$ est premier.\\
    5. En déduire que $n=2^{p-1}(2^p-1)$ pour un certain nombre premier $p$.
Exercice 4156. Soit $p$ un nombre premier.\\
  1. Soit $q$ un nombre premier qui divise $p-1$. Établir l'existence d'un élément de $\big((\mathbb{Z}/p\mathbb{Z})^*,\times\big)$ d'ordre exactement $q$.\\
  2. Soit $q$ un nombre premier et $\alpha \in \mathbb{N}^*$ tels que $q^\alpha$ divise $p-1$. Montrer l'existence d'un élément de $\big((\mathbb{Z}/p\mathbb{Z})^*,\times\big)$ d'ordre $q^\alpha$.\\
  3. En déduire que $\big((\mathbb{Z}/p\mathbb{Z})^*,\times\big)$ est cyclique.
Exercice 4157. Soit $a$ et $p$ des entiers de $\mathbb{N}^*$ tels que \[ a^{p-1}\equiv 1 \pmod{p}. \]
  1. On suppose que pour tout diviseur $d$ de $p-1$ autre que $p-1$, l'entier $a^d-1$ est premier avec $p$. Montrer que $p$ est premier.\\
  2. On suppose que $p-1$ se décompose en $p-1=rs$ avec $r \geqslant s$ et que, pour tout diviseur $t$ de $r$ autre que $1$, l'entier $a^{\frac{p-1}{t}}-1$ est premier avec $p$. Montrer que $p$ est premier.
Exercice 4158. \\
  1. Déterminer une condition nécessaire sur $m \in \mathbb{N}$ pour que le nombre $2^m+1$ soit premier.\\ On pose pour tout $n \in \mathbb{N}$, \[ F_n=2^{2^n}+1. \]
  2. Vérifier que $F_0,F_1,F_2,F_3$ et $F_4$ sont des nombres premiers. Montrer que $F_5$ est divisible par $641$.\\
  3. Prouver que si $n \neq m$, alors $F_n$ et $F_m$ sont premiers entre eux. Retrouver ainsi le théorème d'Euclide : il existe une infinité de nombres premiers.\\
  4. Si $p$ est un diviseur premier de $F_n$, établir \[ p \equiv 1 \pmod{2^{n+1}}. \] Expliquer pourquoi on en vient naturellement à essayer $641$ comme diviseur de $F_5$.
Exercice 4159. \\
  1. Montrer que tout entier $n > 6$ s'écrit comme somme de deux entiers premiers entre eux, strictement supérieurs à $1$.\\
  2. Soit $(p_n)_{n \geqslant 1}$ la suite strictement croissante des nombres premiers. Montrer que pour tout $k \geqslant 2$, on a \[ p_{k+1}+p_{k+2} \leqslant p_1p_2\cdots p_k. \]
  3. Pour $n \in \mathbb{N}^*$, on note $q_n$ le plus petit nombre premier ne divisant pas $n$. Montrer que la suite $\Frac{q_n}{n}$ tend vers $0$.
Exercice 4160. Soit $p$ un nombre premier et $n,k$ des entiers naturels.\\
  1. On suppose $n \geqslant 2$. Montrer l'équivalence entre les assertions suivantes :\\
    1. $n$ est premier.\\
    2. Pour tout $i \in \llbracket 1,n-1 \rrbracket$, $n$ divise $\binom{n}{i}$. \\
  2. On écrit $n$ et $k$ en base $p$ : \[ n=n_0+n_1p+\cdots+n_jp^j,\quad k=k_0+k_1p+\cdots+k_jp^j. \] Montrer le théorème de Lucas : \[ \binom{n}{k} \equiv \Prod_{\ell=0}^{j}\binom{n_\ell}{k_\ell} \pmod{p}. \]
  3. Montrer que le nombre de coefficients binomiaux impairs situés sur la $n$-ième ligne du triangle de Pascal est une puissance de $2$.
Exercice 4161. Soit $n \in \mathbb{N}\setminus \{0,1\}$. \\ Montrer que $n$ est le produit de ses diviseurs non triviaux si, et seulement si $n=p^3$ avec $p \in \mathbb{P}$ ou $n=p_1p_2$ avec $p_1,p_2 \in \mathbb{P}$ distincts.
Exercice 4162. Soient $a,b \in \mathbb{N}\setminus \{0,1\}$ et $ n \in \mathbb{N}^*$. On suppose que $a^n+b^n$ est un nombre premier.\\ Montrer que $n$ est une puissance de $2$.
Exercice 4163. Soit $p\in\mathbb{N}\setminus\{0,1\}$. Démontrer que $p$ est premier si et seulement si : $(p-1)!\equiv -1\;[p]$.
Exercice 4164. On note $A$ l’ensemble des nombres premiers de la forme $4k-1$, où $k \in \mathbb{N}^*$. \\ Montrer que $A$ est infini.
Exercice 4165. Soit $n \in \N^*$ et $p_n$ le $n$-ième nombre premier.\\
  1. Posons $\alpha=p_1p_2\cdots p_n+1$. Montrer que $p_{n+1}\leqslant \alpha$.\\
  2. Montrer que $p_n\leqslant \exp(2^{\,n-1})$.\\
  3. En déduire que pour tout $n\geqslant 2$, on a $\ln(\ln n)\leqslant \pi(n)\leqslant n$.
Exercice 4166. Nombres parfaits : Soit $n\in\N^*$ et $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}$ sa décomposition en facteurs premiers.\\
    1. Montrer que $n$ admet exactement $(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_r+1)$ diviseurs positifs.\\
    2. On note $\sigma(n)$ la somme des diviseurs de $n$. Montrer que $\sigma(n)=\Prod_{1\leqslant i\leqslant r}\Frac{p_i^{\alpha_i+1}-1}{p_i-1}$.\\
    3. Montrer que si $m$ et $n$ n’ont aucun facteur premier commun, $\sigma(mn)=\sigma(m)\sigma(n)$.\\
  2. On dit qu’un entier naturel non nul $n$ est parfait s’il est égal à la somme de ses diviseurs autres que lui-même (i.e. si $\sigma(n)=2n$). Si $2^p-1$ est un nombre premier, montrer que $n=2^{p-1}(2^p-1)$ est parfait.\\
  3. Réciproquement, démontrer qu’un nombre parfait pair $n$ est de la forme $2^{p-1}(2^p-1)$ où $2^p-1$ est nécessairement premier.\\
On ne sait pas s’il existe des nombres parfaits impairs.
Exercice 4167. Soit $P$ un polynôme non constant à coefficients entiers. On note : \[ \mathcal{D} = \{d \in \mathbb{N}^*,\; \exists m \in \mathbb{Z},\; d \mid P(m)\}. \] Montrer que $\mathcal{D}$ contient une infinité de nombres premiers.
Exercice 4168. Soit $p$ premier congru à $1$ modulo $4$, $p=4k+1$. On considère l'ensemble \[ S=\{(a,b,c) \in \mathbb{N}^{*2}\times \mathbb{Z},\ 4ab+c^2=p\}. \]
  1. Montrer que $S$ est non vide, fini et inclus dans $(\mathbb{N}^*)^2 \times \mathbb{Z}^*$. Prouver que $S_1=\{(a,b,c) \in S,\ a > b+c\}$ et $S_2=\{(a,b,c) \in S,\ a < b+c\}$ forment une partition de $S$. Exhiber une bijection de $S_1$ sur $S_2$.\\
  2. Montrer que \[ f:(a,b,c)\mapsto (a-b-c,b,-2b-c) \] est une involution de $S_1$. Chercher ses points fixes et en déduire que le cardinal de $S$ est congru à $2$ modulo $4$.\\
  3. Montrer que $S_3=\{(a,b,c) \in S,\ a \neq b\}$ a un cardinal divisible par $4$. En déduire que $p$ est somme de deux carrés.
Exercice 4169. \\
  1. Établir que pour tout $(a,b,c,d,x,y,z,t) \in \mathbb{Z}^8$, \[ (a^2+b^2+c^2+d^2)(x^2+y^2+z^2+t^2) \] est égal à \[ (ax+by+cz+dt)^2+(ay-bx-ct+dz)^2+(az+bt-cx-dy)^2+(at-bz+cy-dx)^2. \]
  2. Soit $p$ un nombre premier impair. Montrer qu'il existe $(a,b) \in \mathbb{Z}^2$ tel que $p$ divise $1+a^2+b^2$. \\
  3. Soit $E$ l'ensemble des entiers naturels $n \geqslant 1$ tel que $np$ soit somme de quatre carrés d'entiers. Montrer que $E$ n'est pas vide.\\ On note $m$ son plus petit élément. Montrer que $m < p$, puis que $m$ est impair.\\
  4. Supposons $1 < m$ et $mp=a^2+b^2+c^2+d^2$. En considérant les résidus de $a,b,c,d$ modulo $m$ de valeur absolue minimale, construire $m' < m$ appartenant à $E$. Conclure.\\
  5. En déduire que tout entier naturel peut s'écrire comme somme de quatre carrés.
Exercice 4170. Soit $p$ un nombre premier de Sophie Germain, c'est-à-dire un nombre premier impair tel que $q=2p+1$ soit premier. On se propose de prouver le théorème de Sophie Germain : il n'existe pas de triplet $(x,y,z) \in \mathbb{Z}^3$ tel que \[ xyz \not\equiv 0 \pmod{p} \] et \[ x^p+y^p+z^p=0. \]
  1. On raisonne par l'absurde et on suppose donné dans la suite un triplet $(x,y,z) \in \mathbb{Z}^3$ tel que $x^p+y^p+z^p=0$ et $xyz \not\equiv 0 \pmod{p}$. \\ Montrer qu'on peut supposer $\mathrm{pgcd}(x,y,z)=1$ et qu'alors $x,y,z$ sont premiers entre eux deux à deux.\\
  2. Montrer qu'il existe deux entiers $a$ et $\alpha$ tels que $y+z=a^p$ et $\Sum_{k=0}^{p-1}(-z)^{p-1-k}y^k=\alpha^p$. Établir l'existence de deux entiers $b,c$ tels que $x+y=c^p$ et $x+z=b^p$.\\
  3. Si $m \in \mathbb{Z}$ n'est pas divisible par $q$, montrer que $m^p \equiv \pm 1 \pmod{q}$. \\ En déduire qu'un et un seul des trois entiers $x,y,z$ est divisible par $q$.\\ On supposera que c'est $x$.\\
  4. Établir successivement les congruences suivantes, toutes modulo $q$ : \[ b^p+c^p-a^p \equiv 0,\quad a \equiv 0,\quad y \equiv c^p,\quad \alpha^p \equiv py^{p-1}. \] Obtenir une contradiction et conclure.
Exercice 4171. On note $\Phi_1=X-1$ et pour $n \geqslant 2$, \[ \Phi_n=\Prod_{\substack{1 \leqslant k \leqslant n\\ \mathrm{pgcd}(k,n)=1}}\left(X-\mathrm{e}^{\frac{2ik\pi}{n}}\right), \] le $n$-ième polynôme cyclotomique.\\
  1. Montrer que $\Phi_n$ est à coefficients entiers pour tout $n \in \mathbb{N}^*$.\\
  2. Que peut-on dire d'un nombre premier $p$ qui divise $\Phi_n(a)$, où $a \in \mathbb{Z}$, mais aucun des $\Phi_d(a)$, où $d$ décrit l'ensemble des diviseurs stricts de $n$ ?\\
  3. En déduire que pour $n \geqslant 1$ fixé, il existe une infinité de nombres premiers de la forme $\lambda n+1$ avec $\lambda$ entier.
Exercice 4172. Preuve d’Euler de l’infinitude des nombres premiers.\\
  1. Montrer que chaque entier $n$ est décomposable de manière unique sous la forme $n=qm^2$ où $q$ est sans facteur carré autre que $1$.\\
  2. Montrer que $\Sum_{m=1}^{+\infty}\Frac{1}{m^2}\leqslant 2$.\\
  3. Montrer que $\Sum_{q\leqslant x}\Frac{1}{q}\leqslant \prod_{p\leqslant x}\left(1+\Frac{1}{p}\right)\leqslant \exp\left(\sum_{p\leqslant x}\Frac{1}{p}\right)$.\\
  4. Justifier la minoration $\Sum_{n\leqslant x}\Frac{1}{n}\geqslant \ln x$.\\
  5. Conclure que $\Sum_{p\leqslant x}\Frac{1}{p}\geqslant \ln(\ln x)-\ln 2$ et en déduire que la série des inverses des nombres premiers diverge.
Exercice 4173. Nombres parfaits : Soit $n \in \N^*$ et $n=p_1^{\alpha_1}\cdots p_r^{\alpha_r}$ sa décomposition en facteurs premiers.\\
  1. Montrer que $n$ admet exactement $(\alpha_1+1)\cdots(\alpha_r+1)$ diviseurs positifs.\\
  2. On note $\sigma(n)$ la somme des diviseurs de $n$. Montrer que $\sigma(n)=\prod_{1\leqslant i\leqslant r}\Frac{p_i^{\alpha_i+1}-1}{p_i-1}$.\\
  3. Montrer que si $m$ et $n$ sont premiers entre eux, alors $\sigma(mn)=\sigma(m)\sigma(n)$.\\
  4. Si $2^p-1$ est premier, montrer que $n=2^{p-1}(2^p-1)$ est parfait.\\
  5. Réciproquement, démontrer qu’un nombre parfait pair est de cette forme.
Exercice 4174. Preuve d’Euler de l’infinitude de l’ensemble des nombres premiers. Elle fournit de fait un résultat en un certain sens optimal. Elle s’appuie encore sur l’unicité de la décomposition en produit de nombres premiers.\\
  1. Montrer que chaque entier $n$ est décomposable de manière unique sous la forme $n=qm^2$ où $q$ est sans facteur carré autre que $1$. En déduire l’identité $\Sum_{n\leqslant x}\Frac{1}{n}=\Sum_{q\leqslant x}\Frac{1}{q}\Sum_{m\leqslant \sqrt{x/q}}\Frac{1}{m^2}$ où la somme indexée sur $q$ est étendue à tous les entiers génériques $q$ sans facteur carré et n’excédant pas $x$.\\
  2. Montrer l’inégalité $\Sum_{m=1}^{+\infty}\Frac{1}{m^2}\leqslant 2$.\\ Indication : $\forall m\geqslant 2\;\;\Frac{1}{m^2}\leqslant \Frac{1}{m(m-1)}$.\\
  3. Montrer que $\Sum_{q\leqslant x}\Frac{1}{q}\leqslant \Prod_{p\leqslant x}\Big(1+\Frac{1}{p}\Big)\leqslant \exp\Big\{\Sum_{p\leqslant x}\Frac{1}{p}\Big\}$ où $p$ désigne un nombre premier générique.\\ Indication : on établira l’inégalité classique de convexité : $1+u\leqslant \exp(u)$.\\
  4. Justifier la minoration $\Sum_{n\leqslant x}\Frac{1}{n}\geqslant \ln x$.\\
  5. Conclure que $\Sum_{p\leqslant x}\Frac{1}{p}\geqslant \ln(\ln x)-\ln 2$ et en déduire la forme forte suivante du théorème d’Euclide :\\ la série des inverses des nombres premiers diverge.
Exercice 4175. Soient $p \geqslant 3$ premier et $t \in \mathbb{N}^*$.\\ Soient $p_1,\ldots,p_r$ des nombres premiers congrus à $1$ modulo $p^t$.\\ On pose \[ a=2p_1\cdots p_r \quad\text{et}\quad c=a^{p^{t-1}}. \]
  1. Montrer que \[ c\equiv 2\ [p]. \]
  2. Montrer que \[ m=1+c+\cdots+c^{p-1} \] et $c-1$ sont premiers entre eux.
  3. Soit $q$ un facteur premier de $m$. Montrer que \[ q\equiv 1\ [p^t]. \]
  4. En déduire qu'il existe une infinité de nombres premiers congrus à $1$ modulo $p^t$.