Nombres premiers

Exercice 3172. 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 3173. 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 3174. 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 3175. 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 3176. Soit $n$ un entier non nul, montrer que $42$ divise $n^{13}-n$, en utilisant le petit théorème de Fermat.
Exercice 3177. 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 3178. Soit $p$ premier.\\ Montrer que \[ \Sum_{k=0}^{p}\binom{p}{k}\binom{p+k}{k}\equiv 2^p+1 \pmod{p^2}. \]
Exercice 3179. 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 3180. 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 3181. \\
  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 3182. 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 3183. Si $p$ est un entier premier supérieur ou égal à $5$, montrer que $p^2 - 1$ est un multiple de $12$.
Exercice 3184. Existe-t-il des nombres premiers $p$ tels que $8p+1$ et $8p-1$ soient tous les deux premiers ?
Exercice 3185. 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 3186. 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 3187. Montrer que si $n$ est un entier non divisible par $5$, alors $n^4\equiv1[5]$.
Exercice 3188. 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 3189. 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 3190. 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 3191. 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 3192. Montrer que si $p$ est un nombre premier supérieur à $3$, alors \[ p^2\equiv1[24]. \]
Exercice 3193. 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 3194. 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 3195. Soit $n$ un naturel non nul.\\ Montrer qu'il existe toujours un nombre premier strictement compris entre $n$ et $n!+2$.
Exercice 3196. 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 3197. 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 3198. Justifier l'existence de $1000$ entiers consécutifs sans nombres premiers.
Exercice 3199. 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 3200. Montrer que pour tout nombre premier $p$, il existe un entier naturel $n$ tel que \[ 6n^2+5n+1 \equiv 0 \pmod{p}. \]
Exercice 3201. 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 3202. Soit $p \in \mathbb{N}^*$, $p \geqslant 2$. Montrer l'équivalence : \[ (p-1)! \equiv -1 \pmod{p} \Longleftrightarrow p \;\; \mathrm{ premier.} \]
Exercice 3203. 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 3204. 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 3205. \\
  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 3206. 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 3207. \\
  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 3208. 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 3209. 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 3210. 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 3211. Soient $p \in \mathbb{P}$ et $\alpha \in \mathbb{N}^*$. \\ Déterminer les diviseurs positifs de $p^\alpha$.
Exercice 3212. Soit $p$ un nombre premier, $p > 5$. \\ Montrer que $p^2-1$ est divisible par $24$.
Exercice 3213. Soient $n > 2$ et $N$ la somme de $n$ entiers impairs consécutifs.\\ Montrer que $N$ n'est pas un nombre premier.
Exercice 3214. 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 3215. 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 3216. 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 3217. Montrer que le nombre entier $A = 5^{45} + 4^{30}$ est composé, c’est-à-dire non premier.
Exercice 3218. 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 3219. Trouver tous les nombres premiers $p$ tels que $p^2+2$ soit aussi premier.
Exercice 3220. 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 3221. 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 3222. Soit $p\in\mathbb{N}\setminus\{0,1\}$. Démontrer que $p$ est premier si et seulement si : $(p-1)!\equiv -1\;[p]$.
Exercice 3223. 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 3224. 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 3225. 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 3226.
  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 3227. \\
  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 3228. 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 3229. 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 3230. Soit $p$ un nombre premier et $k \in \{1,\ldots,p-1\}$. \\ Montrer que $p$ divise $\displaystyle \binom{p-1}{k} - (-1)^k$.
Exercice 3231. On note $A$ l’ensemble des nombres premiers de la forme $4k-1$, où $k \in \mathbb{N}^*$. \\ Montrer que $A$ est infini.
Exercice 3232. 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 3233. \\
  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 3234. L'ensemble $\mathbb{P}$ des nombres premiers est infini.
Exercice 3235. 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 3236. 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 3237. 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 3238. 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 3239. 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 3240. 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 3241. 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 3242. 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 3243. 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.