Votre navigateur n'accepte pas le Javascript.La navigation sur ce site risque de ne pas fonctionner correctement.

364. Déterminez les nombres dont le carré vaut 1 modulo une puissance de 2

Soit $k$ un entier naturel non nul. Dans cette section, vous vous intéressez à la résolution de l’équation :

x^2\equiv 1\mod 2^k.

Traitez le cas où $k=1$

Comme $2^k = 2$ vous calculez tous les carrés modulo $2.$

\begin{array}{|c|c|c|}
\hline
x \mod 2 & 0 & 1\\
\hline
x^2 \mod 2 & 0 & 1\\
\hline
\end{array}

Vous obtenez donc :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 2) \Longleftrightarrow (x\equiv 1 \mod 2).}

Traitez le cas où $k=2$

Comme $2^2 = 4$ vous calculez tous les carrés modulo $4.$

\begin{array}{|c|c|c|c|c|}
\hline
x \mod 4 & 0 & 1 & 2 & -1\\
\hline
x^2 \mod 4 & 0 & 1 & 0 & 1\\
\hline
\end{array}

Vous obtenez donc :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 4) \Longleftrightarrow (\exists a\in\{-1,1\}, x\equiv a \mod 4).}

Traitez le cas où $k=3$

Comme $2^3 = 8$ vous calculez tous les carrés modulo $8.$

\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
x \mod 8  &-1 & 0 & 1 & 2 & 3 & 4  & 5 & 6\\
\hline
x^2 \mod 8 & 1 & 0 & 1 & 4 & 1& 0  & 1  & 4\\
\hline
\end{array}

Vous obtenez donc :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 8) \Longleftrightarrow (\exists a\in\{-1,1, 3, 5\}, x\equiv a \mod 8).}

Et après, que se passe-t-il modulo $16$ dans le cas où $k=4$ ?

Vous pourriez penser que le nombre de solutions modulo $2^4=16$ serait égal à $8$ comme le suggère cette analyse.

Analyse. Soit $x$ un nombre entier relatif tel que :

x^2\equiv 1 \mod 16.

Comme $8\mid 16$ et que $16 \mid x^2-1$ il vient $8\mid x^2-1$ et du coup :

x^2\equiv 1 \mod 8.

En appliquant le résultat précédent, vous déduisez qu’il existe $a\in\{-1, 1, 3,5\}$ tel que $x^2\equiv a \mod 8.$

Cas n°1. $x\equiv -1\mod 8.$ Il existe un entier relatif $t$ tel que $x=-1+8t.$ Si $t$ est pair, il existe un entier relatif $k$ tel que $t=2k$ et par suite $x=-1+16k$ et $x\equiv -1\mod 16.$ Si $t$ est impair, il existe un entier relatif $\ell$ tel que $t = 2\ell+1$ et par suite $x = -1+8(2\ell+1) = 7+16\ell$ et $x\equiv 7\mod 16.$

Cas n°2. $x\equiv 1\mod 8.$ En reprenant la démarche du cas précédent, vous déduisez que soit $x\equiv 1\mod 16$ soit $x\equiv 9\mod 16.$

Cas n°3. $x\equiv 3\mod 8.$ De même, vous déduisez que soit $x\equiv 3\mod 16$ soit $x\equiv 11\mod 16.$

Cas n°4. $x\equiv 5\mod 8$ en vous avez : soit $x\equiv 5\mod 16$ soit $x\equiv 13\mod 16.$

Le résultat suivant est ainsi établi :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 16) \implies (\exists a\in\{-1,1, 3, 5, 7, 9, 11, 13\}, x\equiv a \mod 16).}

Il y a huit candidats potentiels.

Synthèse. Soit $x$ un entier relatif.

Si $x\equiv -1\mod 16$, alors $x^2\equiv 1\mod 16.$

Si $x\equiv 1\mod 16$, alors $x^2\equiv 1\mod 16.$

Si $x\equiv 3\mod 16$, alors $x^2\equiv 9\mod 16.$

Si $x\equiv 5\mod 16$, alors $x^2\equiv 25\mod 16$ et $x^2\equiv 9\mod 16.$

Si $x\equiv 7\mod 16$, alors $x^2\equiv 49 \mod 16$ et $x^2\equiv 1 \mod 16.$

Si $x\equiv 9\mod 16$, alors $x\equiv -7\mod 16$ donc $x^2\equiv 49 \mod 16$ et $x^2\equiv 1 \mod 16.$

Si $x\equiv 11\mod 16$, alors $x\equiv -5\mod 16$ alors $x^2\equiv 25 \mod 16$ et $x^2\equiv 9 \mod 16.$

Si $x\equiv 13\mod 16$, alors $x\equiv -3\mod 16$ alors $x^2 \equiv 9 \mod 16.$

Parmi les 8 candidats, il n’y en a que quatre qui conviennent.

Conclusion. Par analyse-synthèse, il vient d’être démontré que :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 16) \Longleftrightarrow (\exists a\in\{-1,1, 7, 9\}, x\equiv a \mod 16).}

Le nombre de solutions modulo $16$ reste finalement égal à $4.$ Vous allez montrer que cela se généralise.

Passez au cas général en étudiant la situation pour $k\geq 3$

Dans cette section, vous supposez que $k$ est un entier supérieur ou égal à $3.$

Pour tout entier $n\geq 3$ vous notez $\mathscr{P}(n)$ la propriété suivante :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 2^n) \Longleftrightarrow (\exists a\in\left\{-1,1, -1+2^{n-1}, 1+2^{n-1}\right\}, x\equiv a \mod 2^n).}

Initialisation. Il a été démontré ci-dessus que :

\forall x\in\Z, (x^2\equiv 1\mod 8) \Longleftrightarrow (\exists a\in\{-1,1, 3, 5\}, x\equiv a \mod 8).

Comme $3 = -1+2^{3-1}$ et $5 = 1+2^{3-1}$ vous en déduisez que $\mathscr{P}(3)$ est vérifiée.

Hérédité. Soit $n$ un entier supérieur ou égal à $3.$ Supposez $\mathscr{P}(n).$

Soit $x$ un entier relatif tel que $x^2\equiv 1 \mod 2^{n+1}.$

Comme $2^n \mid 2^{n+1}$ vous déduisez $x^2\equiv 1 \mod 2^n.$ D’après l’hypothèse de récurrence, il existe un entier $a\in \left\{-1,1, -1+2^{n-1}, 1+2^{n-1}\right\}$ tel que $x\equiv a\mod 2^n.$

Cas n°1. $a\in\{-1,1\}.$ De $x\equiv a \mod 2^n$ vous déduisez l’existence d’un entier relatif $t_1$ tel que $x = a+2^n t_1.$ Si $t_1$ est pair, il existe un entier relatif $k_1$ tel que $t_1 = 2k_1$ et par suite $x=a+2^{n+1}k_1$ et $x\equiv a\mod 2^{n+1}.$

Si $t_1$ est impair il existe un entier relatif $\ell_1$ tel que $t_1 = 1+2\ell_1$ et par suite $x = a+2^n(1+2\ell_1)$ d’où $x=a+2^n+2^{n+1}\ell_1$ et $x\equiv a+2^n \mod 2^{n+1}.$

Cas n°2. $a\in\{-1+2^{n-1}, 1+2^{n-1}\}.$ Il existe $b\in\{-1,1\}$ tel que $a = b+2^{n-1}.$ Comme $x\equiv a \mod 2^n$ vous déduisez qu’il existe un entier relatif $t$ tel que $x = a+2^n t$ ce qui donne $x = b+2^{n-1}+2^n t.$ En élevant au carré, il vient :

\begin{align*}
x^2 &= b^2+2^{2n-2}+t^2\times 2^{2n}+b2^{n}+bt\times2^{n+1}+t\times 2^{2n}\\
&= b^2+2^{n+1}2^{n-3}+t^2\times 2^{n+1}2^{n-1}+b\times 2^n+bt\times 2^{n+1}+t\times 2^{n+1}2^{n-1}.
\end{align*}

Comme $n\geq 3$ tous les exposants qui apparaissent dans les puissances de $2$ sont positifs ou nuls. Modulo $2^{n+1}$ vous obtenez :

x^2\equiv b^2+b\times 2^n\mod 2^{n+1}.

Or, $b^2=1$ donc :

x^2\equiv 1+b\times 2^n\mod 2^{n+1}.

Comme $x^2\equiv 1 \mod 2^{n+1}$ vous déduisez :

\begin{align*}
1 \equiv 1+b\times 2^n \mod 2^{n+1}\\
b\times 2^n \equiv 0 \mod 2^{n+1}.
\end{align*}

Il existe un entier relatif $k$ tel que $b\times 2^n = k\times 2^{n+1}.$ En divisant par $2^n$ vous obtenez $b = 2k$ donc $b$ est pair. Or, $b\in\{-1,1\}$ d’où une contradiction. Ainsi le cas n°2 ne peut se produire.

Vous déduisez l’implication suivante :

\forall x\in\Z, (x^2\equiv 1\mod 2^{n+1}) \implies (\exists u\in\left\{-1,1, -1+2^{n}, 1+2^{n}\right\}, x\equiv u \mod 2^{n+1}).

Il reste à montrer la réciproque.

Soit $x$ un entier relatif.

S’il existe $a\in\{-1,1\}$ tel que $x\equiv a \mod 2^{n+1}$ alors $x^2\equiv a^2\mod 2^{n+1}.$ Or $a^2=1$ donc $x^2\equiv 1 \mod 2^{n+1}.$

S’il existe $a\in\{-1,1\}$ tel que $x\equiv a+2^n \mod 2^{n+1}$ alors :

\begin{align*}
x^2\equiv a^2+2^{2n}+a\times 2^{n+1} \mod 2^{n+1}\\
x^2\equiv a^2+2^{n+1}2^{n-1}+a\times 2^{n+1} \mod 2^{n+1}\\
x^2 \equiv a^2 \mod 2^{n+1}.
\end{align*} 

Comme $a^2=1$ vous obtenez encore $x^2\equiv 1 \mod 2^{n+1}.$

Vous avez démontré ce qui suit :

\forall x\in\Z, (x^2\equiv 1\mod 2^{n+1}) \impliedby (\exists u\in\left\{-1,1, -1+2^{n}, 1+2^{n}\right\}, x\equiv u \mod 2^{n+1}).

De ces deux implications, il en résulte que $\mathscr{P}(n+1)$ est vraie.

Conclusion. Par récurrence vous avez montré que pour tout entier $n$ supérieur ou égal à $3$, vous avez :

\forall x\in\Z, (x^2\equiv 1\mod 2^{n}) \Longleftrightarrow (\exists u\in\left\{-1,1, -1+2^{n-1}, 1+2^{n-1}\right\}, x\equiv u \mod 2^{n}).

Comme l’entier $k$ est supérieur ou égal à $3$, le résultat final est ainsi établi :

\boxed{\forall x\in\Z, (x^2\equiv 1\mod 2^{k}) \Longleftrightarrow (\exists a\in\left\{-1,1, -1+2^{k-1}, 1+2^{k-1}\right\}, x\equiv a \mod 2^{k}).}

363. Résolvez une équation avec congruence dans le cas linéaire

Dans le contenu rédigé dans l'article 352 une méthode permettant de résoudre une équation linéaire avec congruences a été développée.

Sera présentée ici une méthode alternative qui ne fait pas appel au $PGCD$ directement.

Soit $a$ un entier naturel non nul, $b$ un entier relatif et $n$ un entier naturel non nul.

Vous souhaitez résoudre l’équation suivante d’inconnue $x$ entière :

ax\equiv b\mod n.

Remarquez que vous pouvez remplacer $a$ et $b$ respectivement par leurs résidus modulo $n.$

Autrement dit, dans la suite, vous supposez que $a$ est un entier naturel non nul strictement inférieur à $n$, que $b$ est un entier naturel strictement inférieur à $n.$

Le théorème fondamental

Vous effectuez la division euclidienne de $n$ par $a$, il existe un quotient $q\in\N$ et un reste $r\in\N$ avec $0\leq r \leq a-1$ tels que $n = aq+r.$

Vous allez établir que l’équation $ax\equiv b\mod n$ d’inconnue $x\in\Z$ admet au moins une solution, si et seulement si, l’équation $ry \equiv -b \mod a$ d’inconnue $y\in \Z$ admet au moins une solution.

Premier sens

Soit $x\in\Z$ tel que $ax\equiv b \mod n.$

Il existe un entier relatif $k$ tel que $ax = b+ nk.$ Vous remplacez $n$ par $aq+r$ du coup :

\begin{align*}
ax &= b +(aq+r)k\\
ax &= b +aqk+rk\\
a(x-qk) - b &= rk.
\end{align*}

Cela prouve que $rk \equiv -b \mod a.$

Donc l’équation $ry \equiv -b \mod a$ d’inconnue $y\in \Z$ admet au moins une solution qui est $k.$

Second sens

Soit $y\in\Z$ tel que $ry \equiv -b \mod a.$

Il existe un entier relatif $t$ tel que $ry = -b+at.$ Vous utilisez le fait que $r = n-aq$ ce qui fournit :

\begin{align*}
(n-aq)y = -b+at\\
ny-aqy = -b+at\\
ny+b = a(t+qy).
\end{align*}

Cela prouve que $a(t+qy) \equiv b \mod n.$ Or, $t+qy\in\Z.$

Donc l’équation $ax\equiv b\mod n$ d’inconnue $x\in\Z$ admet au moins une solution qui est $t+qy.$

Déduisez une solution de l’équation $ax\equiv b\mod n$ à partir d’une solution de l’équation $ry\equiv -b\mod a$

Soit $y$ un entier relatif tel que $ry\equiv -b \mod a.$

Alors $a$ divise $ry+b.$ Donc $t = \frac{ry+b}{a}$ est un nombre entier et $ry = -b+at.$

D’après le calcul effectué à la section précédente, si vous posez $x = t+qy$, alors $x$ est un entier relatif et $ax\equiv b\mod n.$

Vous trouvez maintenant une expression de $x$ qui ne fait pas intervenir le quotient $q.$ En effet :

\begin{align*}
x &= t+qy\\
&=\frac{ry+b}{a}+\frac{aqy}{a}\\
&=\frac{(aq+r)y+b}{a}\\
&=\frac{ny+b}{a}.
\end{align*}

Vous utiliserez dans la suite :

\boxed{x=\frac{ny+b}{a}.}

En définitive, si $k$ est une solution de l’équation $ry \equiv -b \mod a$, alors $\frac{nk+b}{a}$ est une solution de l’équation $ax\equiv b\mod n.$

Note. Au passage, comme $x$ est un entier relatif, vous constatez que le nombre $a$ divise $ny+b.$ Cela peut se voir depuis le début. Comme $ry\equiv -b \mod a$ vous avez $(n-aq)y \equiv -b \mod a$ si bien que $ny\equiv -b \mod a$ et $ny+b\equiv 0 \mod a.$

Application

L’équation $143x\equiv 44 \mod 231$ d’inconnue $x\in\Z$ admet-elle au moins une solution ? Si oui, en déterminer une.

Vous appliquez le théorème fondamental précité pour le savoir.

Vous effectuez la division euclidienne de $231$ par $143.$ Comme $231 = 1\times 143+88$ Vous trouvez un reste égal à $88.$

Il s’agit maintenant de savoir si l’équation $88 y_1\equiv -44 \mod 143$ d’inconnue $y_1\in\Z$ admet au moins une solution.

Vous effectuez la division euclidienne de $143$ par $88.$ Comme $143 = 1\times 88+55$ Vous trouvez un reste égal à $55.$

Il s’agit maintenant de savoir si l’équation $55 y_2 \equiv 44 \mod 88$ d’inconnue $y_2\in\Z$ admet au moins une solution.

En divisant par $11$ cette équation est équivalente à $5y_2\equiv 4 \mod 8.$

Vous effectuez la division euclidienne de $8$ par $5.$ Comme $8 = 1\times 5+3$ Vous trouvez un reste de $3.$

Il s’agit maintenant de savoir si l’équation $3 y_3 \equiv -4 \mod 5$ d’inconnue $y_3\in\Z$ admet au moins une solution.

Vous effectuez la division euclidienne de $5$ par $3.$ Comme $5= 1\times 3+2$ Vous trouvez un reste de $2.$

Il s’agit maintenant de savoir si l’équation $2 y_4 \equiv 4 \mod 3$ d’inconnue $y_4\in\Z$ admet au moins une solution.

Vous effectuez la division euclidienne de $3$ par $2.$ Comme $3= 1\times 2+1$ Vous trouvez un reste de $1.$

Vous tombez alors sur l’équation $y_5 \equiv -4 \mod 2$ d’inconnue $y_5\in\Z$ qui admet au moins une solution, il suffit de prendre $y_5 = 0.$ Il s’ensuit que toutes les équations précitées admettent au moins une solution. Pour chacune d’entre elles, vous en calculez une.

Il vient successivement :

\begin{align*}
y_4 &= \frac{3y_5+4}{2} = \frac{4}{2} = 2
\\
y_3 &= \frac{5y_4-4}{3} = \frac{10-4}{3} = 2
\\
y_2 &= \frac{8y_3+4}{5} = \frac{16+4}{5} = 4
\\
y_1 &= \frac{143y_2-44}{88} = \frac{572-44}{88} = \frac{528}{88} = 6
\\
x&=\frac{231y_1+44}{143} = \frac{1386+44}{143}=10.
\end{align*} 

En définitive, $10$ est une solution de l’équation $143x\equiv 44 \mod 231$ d’inconnue $x\in\Z.$

Prolongement

Déterminez toutes les solutions de l’équation $143x\equiv 44 \mod 231$ d’inconnue $x\in\Z$ en les décrivant modulo $231.$

362. Les systèmes complets de congruences modulo n (2/2)

Cet exposé complète le contenu rédigé dans l'article 361.

Soit $n$ un entier naturel non nul.

Pour toute partie $A$ de $\Z$ vous direz que $A$ constitue un ensemble d’entiers non congruents modulo $n$ si et seulement si :

\forall (x,y)\in A^2,  (x \equiv y \mod n) \implies x=y.

Un système complet de congruences modulo $n$ est nécessairement un ensemble d’entiers non congruents modulo $n$

Soit $A$ un système complet de congruences modulo $n.$

Il est rappelé que l’ensemble $A$ vérifie la propriété $\mathscr{P}$ qui est : « pour tout entier relatif $x$, il existe un unique $a\in A$ tel que $x\equiv a \mod n.$ »

Soient maintenant $(x,y)\in A^2$ un couple d’éléments de $A$ tels que $x\equiv y \mod n.$

$y$ est un élément de $A$ vérifiant $x\equiv y \mod n.$

Or, $x$ est aussi un élément de $A$ tel que $x\equiv x \mod n.$

D’après la propriété $\mathscr{P}$ appliquée à $x$, vous déduisez par unicité que $x=y.$

Tout ensemble d’entiers non congruents modulo $n$ qui possède exactement $n$ éléments est un système complet de congruences modulo $n$

Soit $A$ une partie de $\Z$ comportant exactement $n$ éléments, vous les notez $a_1, \dots, a_n$ avec $a_1<\cdots<a_n.$ Supposez de plus que $A$ soit un ensemble d’entiers non congruents modulo $n.$

Soit $x$ un entier relatif fixé.

Vous raisonnez par l’absurde et supposez qu’il n’existe aucun élément $a\in A$ tel que $x\equiv a \mod n.$

Vous utilisez le fait que l’ensemble $\llbracket 0, n-1\rrbracket$ est un système complet de congruences modulo $n.$ Pour tout $i\in\llbracket 1, n\rrbracket$ il existe un unique $r_i\in\llbracket 0, n-1\rrbracket$ tel que $a_i\equiv r_i \mod n.$ De même, il existe un unique $r\in\llbracket 0,n-1\rrbracket$ tel que $x\equiv r\mod n.$

Notez que s’il existe $i\in\llbracket 1, n\rrbracket$ tel que $r = r_i$ alors $x \equiv r \equiv r_i \equiv a_i \mod n$ ce qui fournit, par transitivité de la congruence, $x\equiv a_i\mod n.$ Or, cela est une contradiction.

Par conséquent, pour tout $i\in\llbracket 1, n\rrbracket, r_i \neq r.$

L’ensemble $\{ r_i, 1\leq i\leq n\}$ est inclus dans l’ensemble $\llbracket 0,n-1\rrbracket \setminus \{r\}$ qui comporte $n-1$ éléments. Utilisant le principe des tiroirs, vous déduisez qu’il existe $(i,j)\in\llbracket 1, n\rrbracket ^2$ tel que $i<j$ et $r_i=r_j.$

Vous déduisez $a_i\equiv r_i \equiv r_j \equiv a_j \mod n$ et par transitivité $a_i\equiv a_j \mod n.$ Comme $A$ est un ensemble d’entiers non congruents modulo $n$, cela implique $a_i=a_j.$ Or $i<j$ donc $a_i < a_j$ d’où une contradiction.

Il a été démontré que :

\forall x\in \Z, \exists a\in A, x\equiv a\mod n.

Soit $x$ un entier relatif. Supposez qu’il existe $(a,a’)\in A^2$ tel que :

\begin{align*}
x\equiv a\mod n\\
x\equiv a' \mod n.
\end{align*}

Alors $a\equiv a’\mod n$ et comme $A$ est un ensemble d’entiers non congruents, vous avez $a=a’.$

Ainsi :

\forall x\in \Z, \exists !a\in A, x\equiv a\mod n.

L’ensemble $A$ est bien un système complet de congruences modulo $n.$

361. Les systèmes complets de congruences modulo n (1/2)

Soit $n$ un entier naturel non nul fixé dans tout cet exposé.

Une partie $A$ de l’ensemble $\Z$ sera qualifiée de système complet de congruences modulo $n$ si et seulement si, pour tout entier relatif $x$, il existe un unique élément $a$ de $A$ tel que $x\equiv a \mod n.$

L’exemple fondamental

Soit $x$ un entier relatif. Vous effectuez la division euclidienne de $x$ par $n.$ Il existe un quotient $q$ et un entier $r\in \llbracket 0, n-1\rrbracket$ tels que :

x = qn+r.

Du coup, vous obtenez :

x\equiv r\mod n.

Supposez qu’il existe $r’\in\llbracket 0, n-1\rrbracket$ tel que :

x\equiv r'\mod n.

Alors vous déduisez :

r\equiv r' \mod n.

Vous avez donc $n\mid r-r’$ donc il existe un entier relatif $k$ tel que $r-r’ = kn.$

Supposez que $k$ soit non nul. Alors $\vert k \vert \geq 1$ et comme $\vert r – r’\vert = \vert k \vert \times n$ vous déduisez $\vert r-r’\vert \geq n.$

Cependant, comme $r$ et $r’$ appartiennent à $\llbracket 0, n-1\rrbracket$ vous déduisez que $1-n\leq r-r’\leq n-1$ et donc $\vert r-r’\vert \leq n-1$ d’où d’une contradiction.

Donc $k=0$ et $r=r’.$ Il a été démontré que :

\forall x\in\Z, \exists! r\in\llbracket 0, n-1\rrbracket, x\equiv r\mod n.

Vous venez de démontrer dans ce paragraphe que l’ensemble $\llbracket 0, n-1\rrbracket$ est un système complet de congruences modulo $n.$

Étudiez le cardinal d’un système de congruences modulo n

Soit $A$ un système complet de congruences modulo $n.$

En raisonnant par l’absurde, supposez que $A$ possède au moins $n+1$ éléments. Vous notez ces entiers relatifs $a_1, \dots, a_{n+1}$ avec $a_1<\cdots<a_{n+1}.$

D’après le paragraphe précédent appliqué pour chaque élément précité, vous déduisez que :

\forall i\in\llbracket 1, n+1\rrbracket, \exists!r_i\in\llbracket 0, n-1\rrbracket, a_i\equiv r_i\mod n.

Les entiers $(r_i)_{1\leq i\leq n+1}$ sont au nombre de $n+1$ et ils appartiennent tous à l’ensemble $\llbracket 0, n-1\rrbracket$ qui comporte $n$ éléments. Utilisant le principe des tiroirs, vous déduisez qu’il existe un couple $(u,v)\in\llbracket 1, n+1\rrbracket^2$ tel que $u<v$ et $r_u = r_v.$ Comme $a_u \equiv r_u \mod n$ et $a_v\equiv r_v \mod n$ vous déduisez que $a_v\equiv a_u \mod n.$

D’une part, $a_v\equiv a_v \mod n$ et d’autre part $a_v\equiv a_u \mod n$ avec $a_u\neq a_v.$ Il a été montré qu’il existe un entier relatif $a_v$ et deux éléments de $A$ tels que $a_v$ leur soit congru modulo $n.$ Cela contredit le fait que $A$ soit un système complet de congruences modulo $n$ donc $A possède au maximum $n$ éléments.

Supposez en raisonnant encore par l’absurde que $A$ possède au maximum $n-1$ éléments.

Si $A$ est vide, alors $1$ doit être congru à un unique élément de $A$ modulo $1$, ce qui est impossible si $A$ ne possède aucun élément, donc $A$ n’est pas vide.

Vous notez $m$ le nombre d’éléments de $A$ vous avez $1\leq m\leq n-1.$ Vous notez les éléments de $A$ ainsi $a_1, \dots, a_{m}$ avec $a_1<\cdots<a_{m}.$

Toujours d’après le paragraphe précédent appliqué pour chaque élément précité, vous déduisez que:

\forall i\in\llbracket 1, m\rrbracket, \exists!r_i\in\llbracket 0, n-1\rrbracket, a_i\equiv r_i\mod n.

L’ensemble $R = \{r_i, 1\leq i \leq m\}$ contient au maximum $m$ éléments et c’est une partie de $\llbracket 0, n-1\rrbracket$ qui en comporte $n$ avec $n>m.$ Donc il existe un entier $r\in\llbracket 0, n-1\rrbracket$ tel que $r\notin R.$

S’il existait $i\in\llbracket 1, m\rrbracket$ tel que $r\equiv a_i \mod n$ alors $r\equiv r_i \mod n.$ Comme $r$ et $r_i$ appartiennent tous les deux à l’ensemble $\llbracket 0, n-1\rrbracket$ $\vert r-r_i\vert \leq n-1.$ Or $n$ divise $ r-r_i$ il existe un entier relatif $k$ tel que $r-r_i = kn$ ce qui implique $\vert r-r_i\vert = \vert k\vert \times n.$ Si $k$ n’est pas nul, il vient $\vert r-r_i\vert \geq n$ ce qui est absurde. Donc $k=0$ et $r=r_i$ et $r\in R$ contradiction. Donc $A$ ne peut pas posséder $n-1$ éléments au maximum.

Il en résulte que tout système complet de congruences modulo $n$ possède exactement $n$ éléments.

360. La multiplication modulo n selon la méthode de Head (2/2)

Cet exposé prolonge le contenu rédigé dans l'article 359 dont il reprend les notations.

Soit à calculer le résidu modulo $15007$ du produit $12345\times 6789.$ Vous souhaitez éviter le calcul direct du produit $12345\times 6789.$

Utilisant la méthode de Head, vous allez faire intervenir des nombres dont la valeur absolue est strictement inférieure à $30014.$

Calculez $T$ et $t$

Par définition, $T$ est égal à :

T = \left\lfloor \sqrt{15007}+\frac{1}{2}\right\rfloor.

D’une part $120^2 =14400$ et d’autre part $130^2 =16900.$ Vous avez donc l’encadrement :

120<\sqrt{15007}<130.

Reste à déterminer un encadrement plus précis. Vous calculez $125^2=15625.$ Il est donc démontré que :

120<\sqrt{15007}<125.

Vous poursuivez avec $122^2 =(120+2)^2 = 14400+480+4 =14884 $ d’où :

122<\sqrt{15007}<125.

Puis $123^2 =(122+1)^2 = 14884+122+123 =14884+200+45 =15084+45 =15129.$ d’où :

122<\sqrt{15007}<123.

Enfin, $122,5^2 =15006,25$ ce qui montre que :

122,5<\sqrt{15007}<123.

En ajoutant $\frac{1}{2}$ il vient :

123<\sqrt{15007}+\frac{1}{2}<123,5<124.

Par conséquent, $123$ est le plus grand entier inférieur ou égal à $\sqrt{10007}+\frac{1}{2}.$ Donc :

\boxed{T = 123.}

Comme $t = T^2-15007 =15129-15007=122$ vous déduisez :

\boxed{t = 122.}

Les deux premières divisions euclidiennes

Vous constatez que :

\begin{align*}
12345 &= 100\times 123+45\\
6789 &= 55\times 123+24.
\end{align*} 

Vous notez $a = 100$, $b = 45$, $c = 55$ et $d = 24$ de sorte que :

\begin{align*}
12345 &= a\times T+b\\
6789 &= c\times T+d.
\end{align*} 

Utilisant le fait que $T^2\equiv t$ modulo $15007$ vous avez :

12345\times 6789 \equiv act+(ad+bc)T+bd.

Le résidu de $ad+bc$ modulo $15007$

Vous avez :

\begin{align*}
ad+bc &= 100\times 24+45\times 55\\
&= 2400 + 2500-25\\
&=4900-25\\
&=4875.
\end{align*}

En posant $z = 4875$ vous déduisez :

12345\times 6789 \equiv act+zT+bd.

Effectuez une troisième division euclidienne

Vous calculez le produit $ac.$

\begin{align*}
ac &= 5500.
\end{align*}

Vous effectuez la division de ce nombre par $T.$

\begin{align*}
5500 &= 44\times 123 + 88.
\end{align*} 

Vous posez $e =44$ et $f = 88$ pour avoir $ac = eT+f.$

D’où :

\begin{align*}
12345\times 6789 &\equiv (eT+f)t+zT+bd\\
&\equiv ft+(et+z)T+bd.
\end{align*} 

Calculez le résidu de $et+z$ modulo $15007$

D’une part :

et = 44\times 122 = 5368.

D’autre part :

et+z = 5368 + 4875=10243.

Ce nombre ne dépasse pas $15007$ donc modulo $15007$ il vient :

et+z\equiv 10243.

En posant $v = 10243$ vous avez obtenu :

\begin{align*}
12345\times 6789 \equiv ft+vT+bd.
\end{align*} 

Effectuez une quatrième division euclidienne

Vous divisez $v$ par $T$ ce qui fournit :

\begin{align*}
10243 &= 83\times 123+34.
\end{align*}

Vous posez $g = 83$ et $h = 34$ pour avoir $v = gT+h.$

Alors modulo $15007$ vous avez :

\begin{align*}
12345\times 6789 &\equiv ft+(gT+h)T+bd\\
&\equiv ft+gT^2+hT+bd.
\end{align*} 

Or, $T^2\equiv t$ modulo $15007$ d’où :

\begin{align*}
12345\times 6789 \equiv ft+gt+hT+bd.
\end{align*} 

Concluez

Vous calculez $ft$ comme suit :

ft = 88\times 122 = 10736.

Vous calculez ensuite $gt$ et l’ajoutez à $ft.$

\begin{align*}
gt &= 83\times 122=10126\\
ft+gt &= 10736+ 10126=20862. 
\end{align*} 

Comme le résultat dépasse $15007$ vous formez le résidu de $ft+gt$ modulo $15007.$

\begin{align*}
ft+gt&\equiv 20862 - 15007\\
&\equiv 5855.
\end{align*}

Vous calculez ensuite $hT$ et l’ajoutez au résidu de $ft+gt$ modulo $15007.$

\begin{align*}
hT &= 34\times 123= 4182\\
(ft+gt)+hT &\equiv 5855 + 4182 \\
&\equiv 10037. 
\end{align*} 

Enfin, vous calculez $bd$ et l’ajoutez au résidu précédent.

\begin{align*}
bd &= 45\times 24 = 1080\\
((ft+gt)+hT)+bd &\equiv 10037 + 1080  \\
&\equiv 11117.
\end{align*} 

Finalement, modulo $15007$ vous avez :

\boxed{12345\times 6789 \equiv 11117.}

359. La multiplication modulo n selon la méthode de Head (1/2)

Dans cet article, $n$ désigne un entier naturel supérieur ou égal à $2.$

Vous notez $x$ et $y$ deux entiers naturels strictement inférieurs à $n$ dont vous souhaitez calculer le résidu modulo $n$ en manipulant des nombres entiers dont la valeur absolue est strictement inférieure à $2n.$ On dit qu’il n’y a pas de débordement.

Un premier lemme

Vous notez $T$ la partie entière du réel $\sqrt{n}+\frac{1}{2}$, c’est-à-dire :

\boxed{T = \left\lfloor \sqrt{n}+1/2 \right\rfloor.}

Notez que $1\leq \sqrt{2}+\frac{1}{2}\leq \sqrt{n} + \frac{1}{2}.$ Comme $T$ est par définition le plus grand entier inférieur ou égal à $\sqrt{n} + \frac{1}{2}$ vous déduisez que $1\leq T.$

Vous posez ensuite :

\boxed{t = T^2-n.}

D’une part :

T\leq \sqrt{n}+\frac{1}{2}.

Comme ces deux réels sont positifs, en élevant au carré, il vient :

\begin{align*}
T^2 &\leq \left(\sqrt{n}+\frac{1}{2}\right)^2\\
&\leq n+\frac{1}{4}+\sqrt{n}.
\end{align*} 

En retranchant $n$, vous déduisez :

\begin{align*}
T^2-n &\leq \frac{1}{4}+\sqrt{n}\\
t &\leq \frac{1}{4}+\sqrt{n}.
\end{align*}

Par définition de $T$, l’entier $T+1$ est strictement supérieur à $\sqrt{n} + \frac{1}{2}$ d’où :

\begin{align*}
\sqrt{n}+\frac{1}{2} & < T+1 \\
\sqrt{n}&< T+\frac{1}{2}\\
\sqrt{n}+\frac{1}{4}&< T + \frac{3}{4}.
\end{align*}

En cumulant les inégalités obtenues, vous obtenez :

t< T+\frac{3}{4}.

Or, $T+\frac{3}{4} < T+1$ du coup $t< T+1.$ Comme $t$ et $T$ sont deux entiers, il vient :

\boxed{t\leq T.}

D’autre part :

\begin{align*}
\sqrt{n} + \frac{1}{2}  &< T+1\\
\sqrt{n}-\frac{1}{2}&< T.
\end{align*}

Comme $n\geq 1$ vous avez $\sqrt{n}\geq 1$ et $\sqrt{n}-\frac{1}{2}$ est un nombre positif. En élevant au carré, il vient :

\begin{align*}
n+\frac{1}{4}-\sqrt{n} &< T^2\\
n-T^2 &< \sqrt{n}-\frac{1}{4}.
\end{align*}

Or :

\begin{align*}
\sqrt{n}-\frac{1}{2}&< T \\
\sqrt{n}&< T +\frac{1}{2}\\
\sqrt{n}-\frac{1}{4} &< T +\frac{1}{4}.
\end{align*}

En cumulant ces inégalités, vous déduisez :

\begin{align*}
n-T^2< T+\frac{1}{4}\\
-t < T+\frac{1}{4}.
\end{align*}

Comme $T+\frac{1}{4} < T+1$ vous avez :

-t< T+1.

Comme $-t$ et $T+1$ sont des entiers vous obtenez :

\boxed{-t\leq T.}

En résumé, la valeur absolue de l’entier $t$ est majorée par l’entier positif $T$, ce qui s’écrit :

\boxed{\vert t \vert \leq T.}

Deux lemmes

D’une part :

T\leq \sqrt{n}+\frac{1}{2}.

D’autre part :

T-1\leq \sqrt{n}-\frac{1}{2}.

Les entiers $T$ et $T-1$ étant positifs, par produit, il vient :

T(T-1)\leq n-\frac{1}{4}.

Du coup :

\boxed{T(T-1)< n.}

Ensuite, partant de $T\leq \sqrt{n}+\frac{1}{2}$ et en élevant au carré deux réels positifs vous avez :

T^2\leq n+\frac{1}{4}+\sqrt{n}.

Comme $8 < 9$ il vient en prenant la racine carrée $2\sqrt{2}< 3$ et donc $\frac{3+2\sqrt{2}}{4}< \frac{6}{4}$ d’où $\frac{3+2\sqrt{2}}{4}< \frac{3}{2}< 2 < n.$ Par suite :

\begin{align*}
&\frac{3+2\sqrt{2}}{4}< n\\
&\frac{1+2+2\sqrt{2}}{4}< n\\
&\left(\frac{1+\sqrt{2}}{2}\right)^2< n\\
&\frac{1+\sqrt{2}}{2}< \sqrt{n}\\
&1+\sqrt{2} < 2\sqrt{n}\\
&\sqrt{2}< 2\sqrt{n}-1\\
&2< (2\sqrt{n}-1)^2\\
&0 < (2\sqrt{n}-1)^2-2\\
&0 < 4n-4\sqrt{n}-1\\
&1+4\sqrt{n} < 4n\\
&1/4+\sqrt{n} < n\\
&n+1/4+\sqrt{n} < 2n\\
&T^2 < 2n.
\end{align*}

Le second résultat est établi :

\boxed{T^2<2n.}

Effectuez deux divisions euclidiennes

L’entier $x$ est positif et l’entier $T$ est strictement positif. Il existe un quotient $a\geq 0$ et un reste $b\in\llbracket 0, T-1\rrbracket$ tels que :

x = aT+b.

Si l’entier $a$ était strictement supérieur à $T$, alors $a$ serait supérieur ou égal à $T+1$ et par produit, $aT$ serait supérieur ou égal $T^2+T.$ Comme $b$ est positif, vous auriez $x\geq T^2+T.$ Comme $-t\leq T$ il vient $n-T^2\leq T$ et $n\leq T^2+T.$ Par cumul d’inégalités vous auriez $x\geq n$ ce qui contredit le fait que $x$ est strictement inférieur à $n.$

Par suite :

\boxed{0\leq a \leq T.}

En effectuant le même raisonnement sur l’entier $y$ vous déduisez l’existence d’un entier $c$ et d’un reste $d\in\llbracket 0, T-1\rrbracket$ tels que :

\left\{\begin{align*}
&y = cT+d\\
&0\leq c\leq T.
\end{align*}
\right.

Effectuez le produit $xy$

Vous partez des relations suivantes :

\left\{\begin{align*}
x&=aT+b\\
y&=cT+d.
\end{align*}
\right.

Après multiplication, vous avez :

\begin{align*}
xy &= acT^2+(ad+bc)T+bd\\
 &= ac(T^2-n)+(ad+bc)T+bd+nac\\
 &= act+(ad+bc)T+bd+nac.
\end{align*} 

Modulo $n$ il en résulte que :

xy\equiv act+(ad+bc)T+bd.

Obtenez le résidu de $ad+bc$ modulo $n$

Il est rappelé ce qui suit :

\left\{\begin{align*}
&0\leq a \leq T\\
&0\leq d \leq T-1.
\end{align*}
\right.

Par produit, vous obtenez :

0\leq ad \leq T(T-1) < n.

De même :

\left\{\begin{align*}
&0\leq b \leq T-1\\
&0\leq c \leq T.
\end{align*}
\right.

Par produit, vous obtenez :

0\leq bc \leq T(T-1) < n.

Par somme, le nombre $ad+bc$ appartient à l’intervalle $\llbracket 0, 2n\llbracket.$ Vous restez bien avec une valeur strictement inférieure à $2n.$

Si $ad+bc$ appartient à l’intervalle $\llbracket 0, n-1\rrbracket$ vous posez $z = ad+bc.$

Sinon, $ad+bc$ appartient à l’intervalle $\llbracket n, 2n-1\rrbracket$ et par suite $ad+bc-n$ appartient à $\llbracket 0, n-1\rrbracket$ vous posez $z = ad+bc-n.$

Dans les deux cas, vous avez un nombre $z$ appartenant à l’intervalle $\llbracket 0, n-1\rrbracket$ de sorte que, modulo $n$ la congruence suivante est vérifiée :

z\equiv ad+bc.

Modulo $n$ vous avez montré que :

xy\equiv act+zT+bd.

Effectuez une troisième division euclidienne

Il est rappelé que :

\left\{\begin{align*}
&0\leq a \leq T\\
&0\leq c \leq T.
\end{align*}
\right.

Le produit $ac$ est positif et il est inférieur ou égal à $T^2.$ Il a été vu que $T^2<2n$ vous êtes assuré de pouvoir effectuer ce produit sans dépasser $2n$ ou l’atteindre.

Une fois ce produit effectué, vous n’allez pas le réduire modulo $n$ mais vous allez effectuer la division euclidienne de $ac$ par $T.$ Il existe un quotient $e\geq 0$ et un reste $f\in\llbracket 0, T-1\rrbracket$ tels que :

ac = eT+f.

Comme $f$ est positif et comme $ac\leq T^2$ il vient :

eT\leq T^2.

Comme $T>0$ en divisant vous obtenez :

\boxed{0\leq e\leq T.}

Du coup :

\begin{align*}
xy&\equiv act+zT+bd\\
&\equiv (eT+f)t+zT+bd\\
&\equiv ft+(et+z)T+bd.
\end{align*}

Effectuez une réduction modulo $n$

Vous majorez la valeur absolue de $et$ comme suit :

\begin{align*}
\vert et\vert &\leq \vert e \vert \times \vert t \vert\\
&\leq T\times T\\
&\leq T^2.
\end{align*}

Comme $T^2<2n$ il n’y a pas de débordement. Ainsi, $et \in\llbracket 1-2n, 2n-1\rrbracket.$ Parmi les quatre nombres $et$, $et-n$, $et+n$ et $et+2n$ il y en a au moins un qui est égal au résidu de $et$ modulo $n.$

Comme $z$ est égal à son propre résidu modulo $n$, vous déduisez sans débordement la valeur du résidu $v$ modulo $n$ de $et+z.$ Il en résulte que :

\begin{align*}
xy &\equiv ft+vT+bd.
\end{align*}

Effectuez une quatrième division euclidienne

Vous divisez $v$ par $T$ il existe un quotient $g\geq 0$ et un reste $h\in\llbracket 0, T-1\rrbracket$ tels que :

v = gT+h.

Si $g>T$, alors $g\geq T+1$ et $gT\geq T^2+T$ donc $v\geq T^2+T.$ Or il a été vu que $T^2+T\geq n$ donc $v\geq n$ ce qui contredit le fait que $v\in\llbracket 0, n-1\rrbracket.$ Donc :

\boxed{0\leq g\leq T.}

Vous en déduisez que :

\begin{align*}
xy &\equiv ft+vT+bd\\
&\equiv ft+(gT+h)T+bd\\
&\equiv ft+gT^2+hT+bd\\
&\equiv ft+g(T^2-n)+hT+bd\\
&\equiv ft+gt+hT+bd.
\end{align*}

Concluez

Il a été vu que :

\begin{align*}
&0\leq f\leq T-1\\
&\vert t \vert \leq T.
\end{align*}

Par produit $\vert ft \vert$ est inférieur ou égal à $T(T-1)$ et comme $T(T-1)<n$ vous avez $\vert ft \vert < n$ ce qui prouve que le résidu modulo $n$ de $ft$ est calculable sans débordement.

De même :

\begin{align*}
&0\leq g\leq T\\
&\vert t \vert \leq T.
\end{align*}

Par produit $\vert gt \vert$ est inférieur ou égal à $T^2$ et comme $T^2<2n$ vous avez $\vert gt \vert < 2n$ ce qui prouve que le résidu modulo $n$ de $gt$ est calculable sans débordement.

En poursuivant :

0\leq h\leq T-1.

Par produit $hT$ est inférieur ou égal à $T(T-1)$ et comme $T(T-1)<n$ vous avez $hT< n$ ce qui prouve que $hT$ est déjà égal à son propre résidu modulo $n.$

Enfin, vous avez :

\begin{align*}
&0\leq b\leq T-1 \le T\\
& 0\leq d  \leq T.
\end{align*}

Par produit $bd$ est inférieur ou égal à $T(T-1)$ et comme $T(T-1)<n$ vous avez $bd< n$ ce qui prouve que $bd$ est déjà égal à son propre résidu modulo $n.$

Par somme, vous calculez le résidu modulo $n$ de $ft+gt$ modulo $n$ sans débordement, il est soit égal à $ft+gt$ soit à $ft+gt-n.$

Puis vous calculez le résidu modulo $n$ de $(ft+gt)+hT$ en effectuant la somme des deux résidus précédents quitte à soustraire une fois $n.$

En définitive, vous calculez le résidu modulo $n$ de $((ft+gt)+hT)+bd$ en effectuant la somme du résidu de $(ft+gt)+hT$ avec celle du résidu de $bd$, sans débordement, quitte à soustraire $n$ encore une fois si nécessaire.

Comme $xy\equiv ft+gt+hT+bd$ modulo $n$ vous avez bien obtenu le résidu du produit $xy$ modulo $n$ en restant toujours avec des nombres dont la valeur absolue est strictement inférieure à $2n.$

358. Un énoncé équivalent à la conjecture de Goldbach

La conjecture de Goldbach énonce que tout entier pair supérieur ou égal à $4$ peut s’écrire comme la somme de deux nombres premiers.

Vous allez démontrer que cette conjecture est équivalente à la propriété $(P)$ : « tout entier supérieur ou égal à $6$ peut s’écrire comme la somme de trois nombres premiers. »

Premier sens

Vous supposez que la conjecture de Goldbach est vraie.

Soit $n$ un entier supérieur ou égal à $6.$

Premier cas. $n$ est pair. Alors $n-2$ est un entier pair supérieur ou égal à $4.$ D’après la conjecture de Goldbach appliquée à $n-2$, il existe deux nombres premiers $p_1$ et $p_2$ tels que $n-2 = p_1+p_2.$ Du coup $n = 2+p_1+p_2$ et $n$ s’écrit comme somme de trois nombres premiers.

Second cas. $n$ est impair. Comme $n\geq 6$ vous avez même $n\geq 7.$ Ainsi $n-3\geq 4.$ Or, $n-3$ est pair. D’après la conjecture de Goldbach appliquée à $n-3$ il existe deux nombres premiers $p_1$ et $p_2$ tels que $n-3 = p_1+p_2.$ Du coup $n = 3+p_1+p_2$ et $n$ s’écrit comme somme de trois nombres premiers.

Deuxième sens

Vous supposez que la propriété $(P)$ « tout entier supérieur ou égal à $6$ peut s’écrire comme la somme de trois nombres premiers » est vraie.

Soit $n$ un entier pair supérieur ou égal à $4.$ Alors $n+2$ est un entier supérieur ou égal à $6.$ Appliquant la propriété $(P)$ à $n+2$ vous déduisez qu’il existe trois nombres premiers $p_1$, $p_2$ et $p_3$ tels que $n+2 = p_1+p_2+p_3.$ Si les trois nombres $p_1$, $p_2$ et $p_3$ sont impairs, alors leur somme $p_1+p_2+p_3$ l’est aussi, donc $n$ aussi. Mais $n$ est pair donc $n+2$ aussi, contradiction. Donc il existe $i\in\llbracket 1, 3\rrbracket$ tel que $p_i$ est pair. Comme $p_i$ est premier et que $2$ est le seul nombre premier, vous avez $p_i = 2.$ Donc vous avez :

\begin{align*}
n+2 &= p_i + \sum_{\substack{1\leq j \leq 3 \\ j\neq i}} p_j \\
&= 2 +  \sum_{\substack{1\leq j \leq 3 \\ j\neq i}} p_j.
\end{align*}

Du coup $n = \sum_{\substack{1\leq j \leq 3 \\ j\neq i}} p_j$ ce qui prouve que $n$ s’écrit comme la somme de deux nombres premiers.

357. Une version faible du théorème des nombres premiers (2/2)

Vous trouverez dans le contenu rédigé dans l'article 356 une minoration de la fonction $\pi.$

Dans cet article les notations du précédent sont reprises et vous allez démontrer la majoration suivante :

\forall n\in\N, n\geq 3 \implies \pi(n) \leq \e \frac{n}{\ln n}.

Montrez que pour tout entier $m\geq 1$ le produit $\prod_{m+1<p\leq 2m+1}p$ divise le coefficient binomial $\binom{2m+1}{m+1}$

Soient $m$ un entier supérieur ou égal à $1$ et $p$ un nombre premier tel que $m+1<p\leq 2m+1.$

Le coefficient binomial $\binom{2m+1}{m+1}$ est un nombre entier qui s’exprime avec les factorielles suivantes :

\binom{2m+1}{m+1} = \frac{(2m+1)!}{m!(m+1)!}.

Vous déduisez que :

m!(m+1)! \binom{2m+1}{m+1} = (2m+1)!.

Comme $p$ est un facteur du produit $(2m+1)!$ vous avez $p \mid (2m+1)!.$

Supposez, en raisonnant par l’absurde, que $p$ divise le produit $m! (m+1)! = 1\times\cdots\times m \times 1\times \cdots \times m \times (m+1).$ Comme $p$ est un nombre premier, d’après le lemme d’Euclide, il divise un des facteurs de ce produit. Donc il existe un entier $k$ compris entre $1$ et $m+1$ tel que $p\mid k$ donc $p\leq k.$ Or $k \leq m+1$ du coup $p\leq m+1.$ Le nombre premier $p$ étant strictement supérieur à $m+1$ vous obtenez une contradiction. Ainsi $p\nmid m!(m+1)!.$

Considérez maintenant le nombre $PGCD(p, m!(m+1)!).$ Comme il divise $p$ qui est premier, vous avez $PGCD(p, m!(m+1)!) \in\{1, p\}.$ De plus, $PGCD(p, m!(m+1)!) \mid m!(m+1)!$ et comme $p\nmid m!(m+1)!$ vous avez $PGCD(p, m!(m+1)!) \neq p$ et par suite $PGCD(p, m!(m+1)!) = 1.$

Comme $p$ divise $m!(m+1)! \binom{2m+1}{m+1}$ l’application du théorème de Gauss fournit $p\mid \binom{2m+1}{m+1}.$

Pour tout nombre premier $p$ tel que $m+1<p\leq 2m+1$ vous avez :

 p\mid \binom{2m+1}{m+1}.

S’il n’existe pas de nombre premier $p$ tel que $m+1<p\leq 2m+1$ le produit $\prod_{m+1<p\leq 2m+1}p$ est égal à $1$ par convention et il divise donc $\binom{2m+1}{m+1}.$

S’il existe au moins un nombre premier $p$ tel que $m+1<p\leq 2m+1$ il existe un entier $s\geq 1$ de sorte que $(p_k)_{1\leq k\leq s}$ soit une énumération des $s$ nombres premiers appartenant à l’intervalle $\rrbracket m+1,2m+1\rrbracket.$

Pour tout $i\in\llbracket 1, s\rrbracket$ vous avez $p_i \mid \binom{2m+1}{m+1}.$

Supposez qu’il existe deux entiers $i$ et $j$ de l’intervalle $\llbracket 1, s\rrbracket$ tels que $PGCD(p_i,p_j)\neq 1.$ Comme $PGCD(p_i,p_j) \mid p_i$ avec $p_i$ qui est premier, vous avez $PGCD(p_i,p_j) \in {1, p_i}.$ Comme il est supposé que $PGCD(p_i,p_j)\neq 1$ vous déduisez $PGCD(p_i,p_j) = p_i.$ Or $PGCD(p_i,p_j) \mid p_j$ donc $p_i \mid p_j.$ Comme $p_j$ est premier, il en résulte que $p_i\in\{1, p_j\}.$ Or $p_i\neq 1$ en tant que nombre premier donc $p_i = p_j.$ Compte tenu du fait que $(p_k)_{1\leq k \leq s}$ est une énumération des $s$ nombres premiers appartenant à l’intervalle $]m+1,2m+1]$ vous avez $i=j.$

Par contraposée, vous déduisez que les nombres de l’énumération $(p_k)_{1\leq k \leq s}$ sont deux à deux premiers entre eux. Suivant un corollaire du théorème de Gauss, vous en déduisez que :

\prod_{i=1}^s p_i \mid \binom{2m+1}{m+1}.

Autrement dit :

\boxed{\prod_{m+1 < p \leq 2m+1}p \mid \binom{2m+1}{m+1}.}

Montrez que pour tout entier $m\geq 1$ le produit $\prod_{m+1<p\leq 2m+1}p$ est inférieur ou égal à $4^m$

Soit $m$ un entier supérieur ou égal à $1.$

Vous utilisez la formule du binôme :

\begin{align*}
(1+1)^{2m+1} &= \sum_{k=0}^{2m+1}\binom{2m+1}{k} 1^k 1^{2m+1-k}\\
&=\sum_{k=0}^{2m+1}\binom{2m+1}{k}.
\end{align*}

Les coefficients binomiaux étant tous positifs vous avez la minoration :

\begin{align*}
(1+1)^{2m+1} &\geq \sum_{k=m}^{m+1}\binom{2m+1}{k}\\
&\geq \binom{2m+1}{m}+ \binom{2m+1}{m+1}.
\end{align*}

Or, par symétrie, les coefficients binomiaux $\binom{2m+1}{m}$ et $\binom{2m+1}{m+1}$ sont égaux.

Du coup :

\begin{align*}
(1+1)^{2m+1} &\geq 2 \binom{2m+1}{m}\\
2^{2m}\times 2 &\geq 2  \binom{2m+1}{m}\\
2^{2m} &\geq \binom{2m+1}{m}\\
(2^2)^{m} &\geq \binom{2m+1}{m}\\
4^{m} &\geq \binom{2m+1}{m}.
\end{align*}

Il a été montré dans la section précédente que $\prod_{m+1 < p \leq 2m+1}p \mid \binom{2m+1}{m+1}$ donc :

\prod_{m+1 < p \leq 2m+1}p \leq \binom{2m+1}{m+1}.

En combinant les inégalités précédentes, il vient $\prod_{m+1 < p \leq 2m+1}p \leq 4^m.$

En définitive :

\boxed{\forall m\in\NN, \prod_{m+1 < p \leq 2m+1}p \leq 4^m.}

Montrez que pour tout entier $n\geq 2$ le produit $\prod_{p\leq n}p$ est inférieur ou égal à $4^n$

Pour tout entier naturel $n$ supérieur ou égal à $2$, vous notez $\mathscr{P}(n)$ la propriété : « $\prod_{p\leq n}p \leq 4^n.$ »

Initialisation. Pour $n=2$ le produit $\prod_{p\leq n}p$ est égal à $\prod_{p\leq 2}p.$ Or seul $2$ est un nombre premier inférieur ou égal à $2$ donc $\prod_{p\leq 2}p = 2.$ Or $4^n = 4^2= 16$ donc l’inégalité $\prod_{p\leq 2}p \leq 4^2$ est vérifiée et $\mathscr{P}(2)$ est vraie.

Hérédité. Soit $n$ un entier naturel supérieur ou égal à $2.$ Vous supposez que $\mathscr{P}(2),\dots,\mathscr{P}(n)$ sont vraies.

Premier cas. L’entier $n+1$ est pair. Remarquez que $n+1\geq 3.$ Or $2$ est le seul nombre premier pair. Donc $n+1$ n’est pas premier. Il en résulte que :

\prod_{p\leq n+1}p = \prod_{p\leq n}p.

D’après l’hypothèse de récurrence, $\prod_{p\leq n}p \leq 4^n.$ Or $4^n\leq 4^{n+1}.$ Vous déduisez :

\prod_{p\leq n+1}p \leq 4^{n+1}.

Second cas. L’entier $n+1$ est impair. Comme $n+1\geq 3$ il existe un entier $m\geq 1$ tel que $n+1 = 2m+1.$ Vous avez :

\begin{align*}
\prod_{p\leq n+1}p &= \prod_{p\leq 2m+1}p\\
&= \left( \prod_{  p\leq m+1}p \right) \left(\prod_{ m+1<  p\leq 2m+1}p\right)\\
\end{align*}

D’après l’hypothèse de récurrence, $\prod_{ p\leq m+1}p \leq 4^{m+1}.$ Il a été démontré dans la section précédente que $\prod_{ m+1< p\leq 2m+1}p \leq 4^m.$ En combinant ces inégalités vous déduisez :

\begin{align*}
\prod_{p\leq n+1}p &\leq 4^{m+1}4^m\\
&\leq 4^{2m+1}\\
&\leq 4^{n+1}.
\end{align*}

Il est ainsi prouvé que $\mathscr(P)(n+1)$ est vraie.

Conclusion. Par récurrence forte, il a été démontré que :

\boxed{\forall n\in\N, n\geq 2 \implies \prod_{p\leq n}p \leq 4^n.}

Montrez que pour tout entier $n\geq 2$, la factorielle $\pi(n)!$ est inférieure ou égale à $4^n$

Pour tout entier naturel $n$ supérieur ou égal à $2$, vous notez $\mathscr{Q}(n)$ la propriété : « $\pi(n)! \leq \prod_{p\leq n}p.$ »

Initialisation. Pour $n=2$ la factorielle $\pi(2)!$ est égale à $1! = 1$ puisque $2$ est le seul nombre premier inférieur ou égal à $2.$ Pour la même raison $\prod_{p\leq 2}p = 2$ et vous déduisez $\pi(2)!\leq \prod_{p\leq 2}p$ et $\mathscr{Q}(2)$ est vraie.

Hérédité. Soit $n$ un entier naturel supérieur ou égal à $2.$ Vous supposez que $\mathscr{Q}(n)$ est vraie.

Premier cas. $n+1$ est un nombre premier. Dans ce cas, $\pi(n+1) = 1+\pi(n).$

\begin{align*}
\pi(n+1)! &= (1+\pi(n))!\\
&= \pi(n)! \times (1+\pi(n)).
\end{align*}

D’une part, grâce à l’hypothèse de récurrence, $\pi(n)!\leq \prod_{p\leq n}p.$

D’autre part, $\pi(n)$ désigne le nombre de nombres premiers qui sont inférieurs ou égaux à $n.$ Comme les nombres premiers inférieurs ou égaux à $n$ sont inclus dans l’ensemble $\llbracket 1, n\rrbracket$ il s’ensuit que $\pi(n)\leq n$ d’où $1+\pi(n)\leq 1+n.$

En cumulant ces résultats, vous déduisez :

\begin{align*}
\pi(n+1)! &\leq  \left(\prod_{p\leq n}p\right) \times (1+n).
\end{align*}

Comme $n+1$ est premier :

  \prod_{p\leq n+1}p =   \left(\prod_{p\leq n}p\right) \times (1+n).

Du coup :

\pi(n+1)! \leq  \prod_{p\leq n+1}p.

Second cas. $n+1$ n’est pas un nombre premier. Alors $\pi(n) =\pi(n+1)$ et $\prod_{p\leq n+1}p = \prod_{p\leq n}p.$ Comme $\pi(n)!\leq \prod_{p\leq n}p$ il vient à nouveau :

\pi(n+1)! \leq  \prod_{p\leq n+1}p.

La propriété $\mathscr{Q}(n+1)$ est donc vraie.

Conclusion. Par récurrence faible, il a été démontré que :

\forall n\in\N, n\geq 2 \implies \pi(n)!\leq \prod_{p\leq n}p.

Soit $n$ un entier naturel supérieur ou égal à $2.$

D’une part, $\pi(n)!\leq \prod_{p\leq n}p$ et d’autre part, grâce à la section précédente $\prod_{p\leq n}p \leq 4^n.$ En combinant ces inégalités, il vient $\pi(n)! \leq 4^n.$ Il vient d’être démontré que :

\boxed{\forall n\in\N, n\geq 2 \implies \pi(n)!\leq 4^n.}

Montrez que pour tout entier $n\geq 2$, $\pi(n) (\ln \pi(n) – 1) \leq n\ln 4$

Pour tout entier naturel $m$ non nul vous notez $\mathscr{R}(m)$ la propriété « $\forall x\in[0,+\infty[, \e^x\geq \frac{x^m}{m!}.$ »

Initialisation. Posez $m=1$ et considérez la fonction $f$ définie sur $[0,+\infty[$ par:

f(x) = \e^x-x.

En dérivant, il vient:

\forall x\geq 0, f'(x) = \e^x-1.

Fixez un réel $x$ positif ou nul. Comme $x\geq 0$ en appliquant la fonction exponentielle qui est croissante sur $\R$ il vient $\e^x \geq \e^0$ et $\e^x \geq 1.$ Donc $f'(x)$ est positif.

Par suite, la fonction $f$ est croissante sur $[0,+\infty[.$ Soit maintenant $x$ un réel positif ou nul. Vous avez $f(x)\geq f(0)$ donc $\e^x-x\geq 1.$ Du coup $\e^x-x > 0$ et $\e^x \geq x.$

La propriété $\mathscr{R}(1)$ est vraie.

Hérédité. Soit $m$ un entier naturel non nul tel que $\mathscr{R}(m)$ soit vraie.

Pour tout réel $x$ positif ou nul, vous définissez une fonction $g$ en posant:

g(x) = \e^x-\frac{x^{m+1}}{(m+1)!}.

En dérivant vous obtenez:

\forall x\geq0, g'(x) = \e^x-\frac{(m+1)x^m}{m!\times (m+1)} = \e^x-\frac{x^m}{m!}.

D’après l’hypothèse de récurrence, vous avez $\forall x \geq 0, g'(x)\geq 0.$

La fonction $g$ est donc croissante sur $]0,+\infty[.$ Soit $x$ un réel positif ou nul. Vous avez $g(x)\geq g(0)$ donc $\e^x-\frac{x^{m+1}}{(m+1)!}\geq 1$ et par suite $\e^x-\frac{x^{m+1}}{(m+1)!}\geq 0.$

La propriété $\mathscr{R}(m+1)$ est vraie.

Conclusion. Il a été montré par récurrence faible que:

\boxed{\forall m\in\NN, \forall x\in[0,+\infty[, \e^x\geq \frac{x^m}{m!}.}

Utilisant le résultat précédent en choisissant $x=m$, vous obtenez:

\boxed{\forall m\in\NN, \e^m\geq \frac{m^m}{m!}.}

Soit $n$ un entier supérieur ou égal à $2.$ Comme $2$ est premier, vous avez $\pi(n)\geq 1.$ Vous appliquez le résultat précédent pour $m=\pi(n)$ ce qui fournit:

\begin{align*}
&\e^{\pi (n)}\geq \frac{\pi(n)^{\pi(n)}}{\pi(n)!} \\
&\pi(n)\geq \pi(n)\ln\pi(n)-\ln (\pi(n)!) \\
&\ln (\pi(n)!) \geq \pi(n)(\ln \pi(n)-1).
\end{align*}

Or d’après la section précédente:

\begin{align*}
&\pi(n)!\leq 4^n\\
&\ln (\pi(n)!) \leq n\ln 4.
\end{align*}

En cumulant ces résultats vous avez $\pi(n)(\ln \pi(n)-1) \leq n\ln 4.$ D’où:

\boxed{\forall n\in\N, n\geq 2\implies \pi(n)(\ln \pi(n)-1) \leq n\ln 4.}

Montrez que pour tout entier $n\geq 3$, $\pi(n)\leq \e\frac{n}{\ln n}$

Pour tout réel $x$ strictement positif, vous définissez une fonction $h$ en posant:

h(x)=x(\ln x-1).

En dérivant, vous avez:

\forall x >0, h'(x) = 1\times(\ln x-1)+x\times \frac{1}{x} = \ln x.

Il en résulte que la fonction $h’$ est strictement positive sur l’intervalle $]1, +\infty[.$ Du coup, la fonction $h$ est strictement croissante sur l’intervalle $]1,+\infty[.$

Vous raisonnez maintenant par l’absurde en supposant qu’il existe un entier $n_0$ supérieur ou égal à $3$, tel que $\pi(n_0) > \e\frac{n_0}{\ln n_0}.$

Il a été démontré à la section précédente que $\forall x\in [0,+\infty[, \e^x > x.$ En particulier $\e^{n_0} > n_0$ donc $n_0 > \ln n_0$ donc $\frac{n_0}{\ln n_0} > 1$ et $\e\frac{n_0}{\ln n_0} > 1.$

Les deux réels $\pi(n_0)$ et $\e\frac{n_0}{\ln n_0}$ appartiennent donc à l’intervalle $]1, +\infty[.$ Par stricte croissance de la fonction $h$ sur cet intervalle il vient:

\begin{align*}
&h(\pi(n_0)) > h\left(\e\frac{n_0}{\ln n_0}\right)\\
&\pi(n_0)(\ln \pi(n_0)-1) >  \e\frac{n_0}{\ln n_0} \left(\ln \left(\e\frac{n_0}{\ln n_0}\right) - 1\right)\\
&\pi(n_0)(\ln \pi(n_0)-1) >  \e\frac{n_0}{\ln n_0} \left(\ln \e +\ln \left(\frac{n_0}{\ln n_0}\right) - 1\right)\\
&\pi(n_0)(\ln \pi(n_0)-1) >  \e\frac{n_0}{\ln n_0} \times \ln \left(\frac{n_0}{\ln n_0}\right).
\end{align*} 

Or, d’après le résultat de la section précédente:

 \pi(n_0)(\ln \pi(n_0)-1) \leq n_0\ln 4.

Ainsi:

\begin{align*}
&n_0 \ln 4 >  \e\frac{n_0}{\ln n_0} \times \ln \left(\frac{n_0}{\ln n_0}\right)  \\
& \ln 4 >  \frac{\e}{\ln n_0} \times \ln \left(\frac{n_0}{\ln n_0}\right)  \\
& (\ln n_0)\ln 4 > \e  \times \ln \left(\frac{n_0}{\ln n_0}\right)  \\
& (\ln n_0)\ln 4 > \e  \times \left(\ln n_0 - \ln \ln n_0\right)  \\
& (\ln n_0)\ln 4 > \e  \ln n_0 - \e \ln \ln n_0 \\
& \e \ln \ln n_0 > (\e-\ln 4)  \ln n_0   \\
& \frac{\ln \ln n_0}{\ln n_0} > \frac{\e - \ln 4}{\e}.
\end{align*}

Pour tout réel $x\in[1, +\infty[$ vous posez $u(x) = \frac{\ln x}{x}.$

En dérivant, il vient:

\forall x\geq 1, u'(x) = \frac{\frac{1}{x}\times x - \ln x}{x^2} = \frac{1-\ln x}{x^2}

Sur l’intervalle $[1, \e]$ la fonction $u’$ est positive et sur l’intervalle $[\e, +\infty[$ la fonction $u’$ est négative. Il en résulte que, sur l’intervalle $[1, +\infty[$ la fonction $u$ admet un minimum pour $x = \e.$ La valeur de ce minimum est $u(\e) = \frac{\ln \e}{\e} = \frac{1}{\e}.$

Comme $\ln n_0 \in [\ln 3,+\infty[$ avec $\ln 3 > 1$ vous avez aussi $\ln n_0 \in [1, +\infty[.$ Du coup, $u(\ln n_0)=\frac{\ln \ln n_0}{\ln n_0}$ est inférieur ou égal à $\frac{1}{\e}.$

Vous en déduisez que :

\begin{align*}
&\frac{1}{\e} > \frac{\e - \ln 4}{\e}\\
&1>\e-\ln 4\\
&\ln 4 > \e-1.
\end{align*}

Utilisant le fait que $\ln 2 < 0,694$ vous déduisez $\ln 4 < 1,388.$

D’autre part $\e > 2,718$ donc $\e-1> 1,718.$ Donc $\ln 4 < 1,388 < 1,718 < \e-1$ et $\ln 4 < \e-1$ d’où une contradiction. L’entier $n_0$ ne peut pas exister.

Finalement :

\boxed{\forall n\in\N, n\geq 3\implies \pi(n)\leq \e\frac{n}{\ln n}.}

356. Une version faible du théorème des nombres premiers (1/2)

Pour tout réel $x$, vous notez $\pi(x)$ le nombre de nombre premiers qui sont inférieurs ou égaux à $x.$

Formellement, cela se note ainsi :

\boxed{\forall x\in\R, \pi(x) = \sum_{p\leq x} 1.}

Exemple. En énumérant tous les entiers de $1$ à $10$, vous constatez que seuls $2$, $3$, $5$ et $7$ sont premiers, ce qui fournit 4 nombres premiers, donc $\pi(10) = 4.$

Le théorème des nombres premiers énonce que :

\lim_{x\to +\infty} \frac{\pi(x)}{\frac{x}{\ln x}} = 1.

Il sera démontré dans cet article une version faible, à savoir :

\forall n\in\N, n\geq 4 \implies \pi(n) \geq \frac{\ln 2}{2}\times\frac{n}{\ln n}.

Dans tout cet article, la lettre $p$ sous un symbôle de sommation désignera un nombre premier.

Valuation $p$-adique d’un entier

Étant donnés un entier $n\geq 2$ et un nombre premier $p$, vous appelez valuation $p$-adique de $n$ l’entier noté $\boxed{v_p(n)}$ égal à l’exposant de $p$ dans sa décomposition en produit de nombres premiers.

Par exemple, si vous prenez $350$, vous obtenez :

\begin{align*}
350 &= 35\times 10\\
&= 7\times 5 \times 2\times 5\\
&=2^1\times 5^2\times 7^1.
\end{align*}

Ainsi, $v_2(350)=1$, $v_5(350)=2$ et $v_7(350) = 1.$

Lorsqu’un nombre premier n’apparaît pas explicitement dans la décomposition en produit de nombres premiers, il est toujours possible d’utiliser la puissance $0.$ Comme $13^0 = 1$ vous avez :

350 = 2^1\times 5^2\times 7^1\times 13^0.

Cela permet d’écrire $v_{13}(350) = 0.$

Le $PPCM$ des premiers entiers naturels

Pour tout entier naturel $n\geq 2$, vous notez $\boxed{\Delta_n}$ le plus petit multiple commun des entiers naturels compris entre $1$ et $n.$ C’est aussi le $PPCM$ des entiers naturels compris entre $2$ et $n.$

Exemple. Vous avez :

\begin{align*}
\Delta_6 &= PPCM(1,2,3,4,5,6)\\
&= PPCM(2,3,4,5,6).
\end{align*}

Parmi les entiers naturels allant de $2$ à $6$, seuls les nombres premiers $2$, $3$ et $5$ sont utilisés. Vous avez en effet, pour chaque décomposition en produit de nombres premiers :

\begin{align*}
2 &= 2^1\times 3^0 \times 5^0\\
3 &= 2^0\times 3^1 \times 5^0\\
4 &= 2^2\times 3^0 \times 5^0\\
5 &= 2^0\times 3^0 \times 5^1\\
6 &= 2^1\times 3^1 \times 5^0.
\end{align*}

Pour obtenir le $PPCM$ de ces entiers, vous prenez la valuation $p$-adique maximale pour chaque nombre premier $p$ appartenant à $\{2,3,5\}.$

Autrement dit, pour tout $p\in\{2,3,5\}$ vous avez :

v_p(\Delta_6) = \max \{v_p(k), 2\leq k \leq 6\}.

Du coup :

\left\{\begin{align*}
v_2(\Delta_6) &= 2\\
v_3(\Delta_6) &= 1\\
v_5(\Delta_6) &= 1.
\end{align*}
\right.

Vous en déduisez que :

\boxed{\Delta_6 = 2^2\times 3^1\times 5^1 = 60.}

Montrez que pour tout nombre premier $q$ et pour tout entier $n\geq 2$ vous avez $q^{v_q(\Delta_n)}\leq n$

Soit $q$ un nombre premier et soit $n$ un entier tel que $n\geq 2.$

Vous avez $v_q(\Delta_n) = \max \{v_q(k), 2\leq k \leq n\}.$

Comme l’ensemble $\{v_q(k), 2\leq k \leq n\}$ est fini, il existe un entier $k_0$ compris entre $2$ et $n$ tel que $v_q(k_0) = \max \{v_q(k), 2\leq k \leq n\}.$

Or l’entier $k_0$ est égal au produit suivant :

k_0 = \prod_{p\leq n} p^{v_p(k_0)}. 

Premier cas. Si $q$ est inférieur ou égal à $n$, il apparaît dans le produit de $k_0$ et donc $q^{v_q(k_0)}\leq k_0.$ Or $k_0$ est inférieur ou égal à $n$ donc $q^{v_q(k_0)}\leq n.$

Il a été vu que $v_q(\Delta_n) = v_q(k_0)$ ce qui prouve le résultat suivant :

\boxed{q^{v_q(\Delta_n)} \leq n.}

Second cas. Si $q$ est strictement supérieur à $n$, alors $q$ ne peut apparaître dans aucune décomposition en facteurs premiers de $k$ où $k\in\llbracket 2, n\rrbracket$ donc $v_q(\Delta_n) = 0$ et donc $q^{v_q(\Delta_n)} = 1.$ Comme $n\geq 2$ vous déduisez que l’inégalité $q^{v_q(\Delta_n)} \leq n$ est encore valable.

Montrez que pour tout entier $n\geq2$ vous avez $\Delta_n \leq n^{\pi(n)}$

Soit $n$ un entier supérieur ou égal à $2.$ Vous notez $s=\pi(n)$ et $p_1,\dots,p_s$ les nombres premiers des décompositions en facteurs premiers de tous les entiers $k$ compris entre $2$ et $n.$

Utilisant les valuations, vous obtenez :

\forall k\in\llbracket 2, n\rrbracket, k= \prod_{i=1}^s p_i^{v_{p_i}(k)}.

Pour tout $i\in\llbracket 1, s\rrbracket$, vous avez $v_{p_i}(\Delta_n) = \max \{v_{p_i}(k), 2\leq k\leq n\}$ avec :

 \Delta_n= \prod_{i=1}^s p_i^{v_{p_i}(\Delta_n)}.

D’après le résultat établi à la précédente section :

\forall i\in\llbracket 1, s\rrbracket, p_i^{v_{p_i}(\Delta_n)} \leq n.

Du coup :

\begin{align*}
\Delta_n &\leq \prod_{i=1}^s n\\
&\leq n^s\\
&\leq n^{\pi(n)}.
\end{align*}

Il a été prouvé que :

\boxed{\forall n\geq 2, \Delta_n \leq n^{\pi(n)}.}

Déduisez-en une version faible du théorème des nombres premiers

Soit $n$ un entier supérieur ou égal à $4.$

Alors :

\begin{align*}
n&\geq 4\\
2n &\geq 4+n\\
2n-4&\geq n\\
n-2&\geq \frac{n}{2}.
\end{align*} 

Note. Cette astuce est effectuée afin de pouvoir appliquer la fonction logarithme sans faire apparaître de soustraction.

D’après le contenu rédigé dans l'article 348 vous avez $\Delta_n \geq \frac{2^n}{4}.$

Utilisant le fait que $\frac{2^n}{4} = 2^{n-2}$ vous avez $\Delta_n \geq 2^{n/2}.$

Du coup, en tenant compte de la section précédente :

\begin{align*}
2^{n/2} &\leq n^{\pi(n)} \\
\frac{n}{2}\ln 2  &\leq \pi(n) \ln n\\
\frac{\ln 2}{2}\times \frac{n}{\ln n} &\leq \pi(n).
\end{align*}

Vous avez obtenu le résultat souhaité :

\boxed{\forall n\in\N, n\geq 4 \implies  \frac{\ln 2}{2}\times\frac{n}{\ln n} \leq \pi(n).}

Prolongement

Allez lire le contenu rédigé dans l'article 357 pour obtenir une majoration de la fonction $\pi.$

354. Factorisez un entier naturel avec la méthode de Fermat

Soit $n$ un entier naturel. Il convient tout d’abord de remarquer que la racine de $n$ est inférieure ou égale à $\frac{n+1}{2}.$ En effet :

\begin{align*}
(n-1)^2 &\geq 0\\
n^2-2n+1&\geq 0\\
n^2+2n+1&\geq 4n\\
(n+1)^2 &\geq 4n\\
n+1 &\geq 2\sqrt{n}\\
\frac{n+1}{2}&\geq \sqrt{n}.
\end{align*}

Ainsi :

\boxed{\forall n\in\N, \sqrt{n}\leq \frac{n+1}{2}.}

Par définition, un entier naturel qui n’est pas premier sera qualifié de composé.

Le résultat à démontrer

Il s’agit d’établir que, pour tout entier naturel $n$ impair supérieur ou égal à $3$, vous avez l’équivalence :

\boxed{n\text{ n'est pas premier}\Longleftrightarrow \exists k\in \N \cap \left[\sqrt{n}, \frac{n+1}{2}\right[, k^2-n\text{ est le carré d'un entier.} }

Note. Ce résultat a déjà été établi dans le contenu rédigé dans l'article 296. Une démonstration plus succincte est présentée dans cet article.

Démontrez le sens $\implies$

Soit $n$ un entier naturel impair composé supérieur ou égal à $3.$ Il existe deux entiers naturels $a$ et $b$ compris entre $2$ et $n-1$ tels que $n=ab.$

Si $a$ est pair, alors $2\mid a.$ Comme $a\mid n$ vous déduisez par transitivité que $2\mid n$ donc $n$ est pair ce qui est absurde. De même si $b$ est pair, il vient $2\mid b$ puis $b\mid n$ donc $2\mid n$ du coup $n$ est pair, contradiction. Donc $a$ et $b$ sont impairs.

Le quotient de la division euclidienne de $a$ par $2$ est donc égal à $1.$ De même, le quotient de la division euclidienne de $b$ par $2$ est égal à $1.$ Il existe deux entiers naturels $a’$ et $b’$ tels que $a = 2a’+1$ et $b = 2b’+1$ d’où $a+b = 2(a+a’+1)$ ce qui prouve que $a+b$ est pair. Ainsi $\frac{a+b}{2}$ est un entier naturel. Utilisant le même raisonnement, $a – b = 2(a’-b’)$ donc $a-b$ est un entier relatif pair et $\frac{a-b}{2}$ est un entier relatif.

Vous posez maintenant $k = \frac{a+b}{2}.$ Il a été vu que $k\in\N.$

Comme $a>1$ et comme $b>1$, le produit $(a-1)(b-1)$ est strictement positif. En développant, vous obtenez :

\begin{align*}
&(a-1)(b-1)> 0\\
&ab-a-b+1 > 0\\
&ab+1 > a+b\\
&n+1 > a+b\\
&\frac{n+1}{2} > k.
\end{align*}

Maintenant, $k^2-n$ est le carré d’un entier relatif. En effet :

\begin{align*}
k^2-n &= \left(\frac{a+b}{2}\right)^2-ab\\
&= \frac{a^2+2ab+b^2}{4}-\frac{4ab}{4}\\
&= \frac{a^2-2ab+b^2}{4}\\
&=\left(\frac{a-b}{2}\right)^2.
\end{align*}

Comme un carré est positif, il vient $k^2-n \geq 0$ puis $k^2\geq n$ et enfin $k\geq \sqrt{n}$ ce donne le résultat.

Démontrez le sens $\impliedby$

Soit $n$ un entier naturel impair supérieur ou égal à $3.$ Vous supposez qu’il existe un entier naturel $k$ tel que :

\left\{\begin{align*}
&\sqrt{n}\leq k < \frac{n+1}{2}\\
&k^2-n\text{ est le carré d'un entier}.
\end{align*}
\right.

Comme $n\geq 1$ il vient $\sqrt{n}\geq 1$ donc $k\geq 1.$

Il existe un entier relatif $u$ tel que $k^2-n=u^2 = (\vert u \vert)^2.$ En posant $\ell = \vert u \vert$ il vient :

\begin{align*}
k^2-n&=\ell^2\\
k^2-\ell^2 &=n\\
(k+\ell)(k-\ell) &= n.
\end{align*}

Comme $2k < n+1$ vous déduisez ce qui suit :

\begin{align*}
2k<  n+1\\
-n < -2k+1\\
k^2-n < k^2-2k+1\\
\ell^2<(k-1)^2.
\end{align*} 

Comme $\ell$ et $k-1$ sont positif, vous déduisez $\ell < k-1$ donc $1< k-\ell.$

Ainsi, l’entier $k-\ell$ est supérieur ou égal à $2$ et divise $n.$

Si $n$ était premier, alors $k-\ell = n.$ L’égalité $(k+\ell)(k-\ell) = n$ s’écrit $n(k+\ell) = n$ d’où $k+\ell =1.$ Comme $k$ est supérieur ou égal à $1$ il vient $\ell = 0$ donc $n = k^2$ donc $k$ divise $n.$ Si $k=1$ alors $n =1$ ce qui contredit le fait que $n$ est premier. Si $k=n$ alors $n = n^2$ d’où $n=1$ après simplification par $n$ ce qui est absurde.

Donc $n$ est composé.

Application : factorisez $2279$

Cherchez d’abord le plus petit carré parfait qui soit supérieur ou égal à $2279.$

Comme $40^2 = 1600$ et comme $50^2=2500$ vous prenez $45^2=2025.$

Ce nombre étant strictement inférieur à $2279$ vous calculez le carré suivant.

\begin{align*}
46^2&= 2025+45+46\\
&= 2025+91\\
&= 2116.
\end{align*} 

Vous poursuivez :

\begin{align*}
47^2&= 2116+46+47\\
&= 2116+93\\
&= 2209.
\end{align*} 

Vous continuez :

\begin{align*}
48^2&= 2209+47+48\\
&= 2209+95\\
&= 2304.
\end{align*} 

Comme $48^2 \geq 2279$ vous évaluez la différence suivante :

\begin{align*}
48^2- 2279 &= 2304-2279\\
&=104-79\\
&=99-74\\
&=25\\
&=5^2.
\end{align*}

Ainsi $2279$ va être factorisé comme suit :

\begin{align*}
2279 &= 48^2-5^2\\
&=(48+5)(48-5)\\
&=53\times 43.
\end{align*}

Application : factorisez $10541$

Vous avez $100^2 =10000$ ce qui vous amène à calculer le carré parfait suivant.

\begin{align*}
101^2&= 10000+100+101\\
&= 10000+201\\
&= 10201.
\end{align*} 

Comme $10201< 10541$ vous poursuivez.

\begin{align*}
102^2&= 10201+101+102\\
&= 10201+203\\
&= 10404.
\end{align*} 

Comme $10404< 10541$ vous poursuivez.

\begin{align*}
103^2&= 10404+102+103\\
&= 10404+205\\
&= 10605.
\end{align*} 

Etant donné que $10609\geq 10541$ vous calculez la différence suivante :

\begin{align*}
103^2-10541 &= 10609-10541\\
&=109-41\\
&=99-31\\
&=68.
\end{align*} 

Comme $68$ n’est pas un carré parfait, vous calculez la prochaine différence :

\begin{align*}
104^2-10541 &= (103^2-10541) + (103+104)\\
&=68+207\\
&=275.
\end{align*} 

Comme $275$ n’est pas un carré parfait, vous calculez la prochaine différence :

\begin{align*}
105^2-10541 &= (104^2-10541) + (104+105)\\
&=275+209\\
&=484\\
&=22^2.
\end{align*} 

Ainsi, $10541$ est factorisable et :

\begin{align*}
10541 &= 105^2-22^2\\
&=(105+22)(105-22)\\
&=127\times 83.
\end{align*}

Prolongement

Vous êtes invité à lire le contenu rédigé dans l'article 295 qui détaille un autre exemple.