Nombres premiers

Exercice 3243. 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 3244. 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 3245. 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 3246. 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 3247. Soit $n$ un entier non nul, montrer que $42$ divise $n^{13}-n$, en utilisant le petit théorème de Fermat.
Exercice 3248. 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 3249. Soit $p$ premier.\\ Montrer que \[ \Sum_{k=0}^{p}\binom{p}{k}\binom{p+k}{k}\equiv 2^p+1 \pmod{p^2}. \]
Exercice 3250. 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 3251. 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 3252. \\
  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 3253. 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 3254. Si $p$ est un entier premier supérieur ou égal à $5$, montrer que $p^2 - 1$ est un multiple de $12$.
Exercice 3255. Existe-t-il des nombres premiers $p$ tels que $8p+1$ et $8p-1$ soient tous les deux premiers ?
Exercice 3256. 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 3257. 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 3258. Montrer que si $n$ est un entier non divisible par $5$, alors $n^4\equiv1[5]$.
Exercice 3259. 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 3260. 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 3261. 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 3262. 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 3263. Montrer que si $p$ est un nombre premier supérieur à $3$, alors \[ p^2\equiv1[24]. \]
Exercice 3264. 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 3265. 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 3266. Soit $n$ un naturel non nul.\\ Montrer qu'il existe toujours un nombre premier strictement compris entre $n$ et $n!+2$.
Exercice 3267. 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 3268. 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 3269. Justifier l'existence de $1000$ entiers consécutifs sans nombres premiers.
Exercice 3270. 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 3271. Montrer que pour tout nombre premier $p$, il existe un entier naturel $n$ tel que \[ 6n^2+5n+1 \equiv 0 \pmod{p}. \]
Exercice 3272. 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 3273. Soit $p \in \mathbb{N}^*$, $p \geqslant 2$. Montrer l'équivalence : \[ (p-1)! \equiv -1 \pmod{p} \Longleftrightarrow p \;\; \mathrm{ premier.} \]
Exercice 3274. 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 3275. 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 3276. \\
  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 3277. 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 3278. \\
  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 3279. 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 3280. 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 3281. 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 3282. Soient $p \in \mathbb{P}$ et $\alpha \in \mathbb{N}^*$. \\ Déterminer les diviseurs positifs de $p^\alpha$.
Exercice 3283. Soit $p$ un nombre premier, $p > 5$. \\ Montrer que $p^2-1$ est divisible par $24$.
Exercice 3284. Soient $n > 2$ et $N$ la somme de $n$ entiers impairs consécutifs.\\ Montrer que $N$ n'est pas un nombre premier.
Exercice 3285. 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 3286. 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 3287. 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 3288. Montrer que le nombre entier $A = 5^{45} + 4^{30}$ est composé, c’est-à-dire non premier.
Exercice 3289. 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 3290. Trouver tous les nombres premiers $p$ tels que $p^2+2$ soit aussi premier.
Exercice 3291. 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 3292. 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 3293. Soit $p\in\mathbb{N}\setminus\{0,1\}$. Démontrer que $p$ est premier si et seulement si : $(p-1)!\equiv -1\;[p]$.
Exercice 3294. 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 3295. 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 3296. 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 3297.
  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 3298. \\
  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 3299. 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 3300. 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 3301. Soit $p$ un nombre premier et $k \in \{1,\ldots,p-1\}$. \\ Montrer que $p$ divise $\displaystyle \binom{p-1}{k} - (-1)^k$.
Exercice 3302. On note $A$ l’ensemble des nombres premiers de la forme $4k-1$, où $k \in \mathbb{N}^*$. \\ Montrer que $A$ est infini.
Exercice 3303. 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 3304. \\
  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 3305. L'ensemble $\mathbb{P}$ des nombres premiers est infini.
Exercice 3306. 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 3307. 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 3308. 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 3309. 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 3310. 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 3311. 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 3312. 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 3313. 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 3314. 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.