Catégorie : Niveau Terminale

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.}

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

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.

Si on veut se passer de division, il est possible de calculer la racine carrée entière d’un nombre entier $n$ en utilisant des soustractions successives. Une variante est proposée ici : le nombre de départ dont on souhaite connaître la racine carrée entière est multiplié par $5$ dès le début, ce qui va faciliter le déroulement des étapes ultérieures.

Note. Cette technique évite d’avoir à gérer des multiplications par $2$ qui apparaissent dans la méthode de la potence.

Étudiez la situation sur un exemple

Soit $n = 1562$ un nombre dont on veut connaître la racine carrée entière.

Il s’agit de déterminer l’unique entier $p$ tel que $p\leq \sqrt{n} < p+1.$

Vous formez immédiatement le nombre $m = 5n =7810.$ Vous écrivez ce nombre $m$ comme une succession de tranches de $2$ chiffres, soit $m = 78\ 10.$

Première étape

Vous partez de la première tranche, $78$ en retirez successivement $5$, $15$, $25$ etc et vous stoppez juste avant de trouver un nombre strictement négatif.

Cette étape peut être formalisée dans le tableau ci-dessous :

\begin{array}{|c|c|c|c|}
\hline
78 & 73 & 58 & 33 \\
\hline
5 &  15 & 25 &\\
\hline
\end{array}

Cette étape montre que :

78 = (5+15+25) + 33.

Le nombre de soustractions effectuées est égal à $3$, soit autant de termes contenus dans la somme $5+15+25.$

En vertu des sommes formées par les termes consécutifs d’une suite arithmétique, vous avez :

\begin{align*}
5+15+25 &= 3\times \frac{5+25}{2}\\
& = \frac{3\times 30}{2}\\
&= 3\times 3\times \frac{10}{2}\\
&= 5\times 3^2.
\end{align*} 

Ainsi :

78 = 5\times 3^2 + 33.

Note. Le chiffre $3$ est le premier du résultat de la racine carrée entière cherchée.

Deuxième étape

Vous prenez le reste, à savoir $33$ et vous collez les chiffres de la tranche d’après de $m$, ce qui fournit le nombre $3310.$

Le nombre de soustractions effectuées précédemment est égal à $3$, vous collez à ce nombre $05$ ce qui fait $305.$ Puis vous allez, à partie de $3310$ retrancher $305$, $315$, $325$, $335$ etc et vous stoppez juste avant d’obtenir un nombre strictement négatif.

\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
3310 & 3005 & 2690 & 2365 & 2030& 1685 &1330 & 965& 590& 205\\
\hline
305 &  315 &  325 & 335 &345 & 355 & 365 & 375 & 385\\
\hline
\end{array}

Vu que le nombre de soustractions est égal à $9$, d’après le tableau et les sommes de termes consécutifs d’une suite arithmétique, il vient :

\begin{align*}
3310 &= (305+315+\cdots+385)+205\\
&= 9\times \frac{690}{2}+205\\
&= 9\times 69\times 5+205\\
&= (9\times 60 + 9^2)\times 5 + 205\\
&= (2\times 9\times 30 + 9^2)\times 5 + 205.
\end{align*}

Vous constatez que l’autre facteur de la multiplication par $5$ contient la fin d’une identité remarquable.

Note. Le chiffre $9$ est le deuxième du résultat de la racine carrée entière cherchée.

Comment prouve-t-on que la racine carrée entière de $1562$ est bien $39$ ?

Vous partez de la première étape, vous multipliez par $100$ et vous ajoutez $10$, ce qui fournit :

\begin{align*}
78 &= 5\times 3^2 + 33\\
7800 &= 5\times 3^2 \times 100 + 3300\\
7810 &= 5\times 3^2 \times 10^2 + 3310\\
7810 &= 5\times 30^2 + 3310.
\end{align*} 

En appliquant la deuxième étape, il vient :

\begin{align*}
7810 &= 5\times 30^2 + (2\times 9\times 30 + 9^2)\times 5 + 205\\
&= 5(30^2 + 2\times 9\times 30+9^2) + 205\\
&= 5\times 39^2 + 205.
\end{align*} 

En divisant par $5$, il vient :

1562 = 39^2 + 41.

Il est donc établi que :

1562 \geq 39^2.

Or :

\begin{align*}
39^2+41 &< 39^2+39+40\\
1562 &< 40^2.
\end{align*} 

De ces deux encadrements, vous obtenez :

\begin{align*}
39^2&\leq 1562 < 40^2\\
39 &\leq \sqrt{1562}< 40.
\end{align*} 

Autrement dit, la racine carrée entière de $1562$ est égale à $39.$

Cas où $n\leq 1999$

Soit $n$ un entier naturel inférieur ou égal à $1999$, de sorte que $5n<9995.$

En posant $m = 5n$, vous constatez que $m$ possède deux tranches de deux chiffres, autrement dit, $m = 100c+u$ où $c$ est $u$ sont deux entiers naturels inférieurs ou égaux à $99.$ Comme $m$ est un multiple de $5$, l’entier $u$ est aussi un multiple de $5$ et vaut $95$ au maximum.

La première tranche

Comme tout à l’heure, vous effectuez un certain nombre de soustractions (voire aucune), vous retranchez à $c$ les entiers $5$, $15$, $25$ juste avant de trouver un nombre strictement négatif. Tous ces entiers sont de la forme $10k-5$ avec $k$ entier supérieur ou égal à $1.$

Soit $k$ le nombre de soustractions effectuées.

Premier cas. Supposez $c\geq 5.$ Alors $k\geq 1.$

Les deux inégalités sont vérifiées :

\begin{align*}
& 5+\dots+(10k-5) \leq c\\
&c <  5+\dots+(10k+5).
\end{align*} 

Le nombre de termes de la somme $5+\dots+(10k-5)$ est égal à $k$, si bien que :

\begin{align*}
5+\dots+(10k-5) &= k\times \frac{5+10k-5}{2}\\
&=5k^2.
\end{align*}

Le nombre de termes de la somme $5+\dots+(10k-5)$ est égal à $k+1$, si bien que :

\begin{align*}
5+\dots+(10k+5) &= (k+1)\times \frac{5+10k+5}{2}\\
&= (k+1)\times \frac{10(k+1)}{2}\\
&=5(k+1)^2.
\end{align*}

Par ce procédé, pour trouvez un entier $k$ tel que :

5k^2\leq c < 5(k+1)^2.

\begin{array}{|c|c|c|c|}
\hline
c & \dots & \dots & c-5k^2 \\
\hline
5 & \dots & \dots &\\
\hline
\end{array}

Remarquez que $c<100$ si bien que $5k^2< 100$ donc $k^2<20$ d’où $k^2<25$ donc $k<5$ puis $k\leq 4.$ Ainsi $k$ est bien un chiffre.

Second cas. Supposez $c<5.$ Alors le nombre de soustractions est égal à $0$ et vous posez $k=0.$ Comme $5(k+1)^2 =20 $·K² 5, l’inégalité $5k^2\leq c < 5(k+1)^2$ est encore satisfaite.

Dans les deux cas, l’inégalité $\boxed{5k^2\leq c < 5(k+1)^2}$ est valable et $k\in\llbracket 0, 4\rrbracket$ est un chiffre.

La seconde tranche

Lorsque vous effectuez les $k$ soustractions précédentes au nombre $c$, vous obtenez un reste qui est égal à :

r = c-5k^2.

Comme $c <5(k+1)^2$ il convient de noter que $c<5(k^2+2k+1)$ donc $c-5k^2< 10k+5.$

Il s’ensuit que $\boxed{0\leq r \leq 10k+4.}$

A partir de ce reste, vous collez la deuxième tranche $u.$ Or c’est multiplier $r$ par $100$ et ajouter $u.$

Le nombre $p = 100r+u$ est ainsi obtenu.

C’est à partir de ce nombre que vous allez coller $05$ au chiffre $k$ calculé précédemment.

Concrètement, vous allez soustraire $100k+5$, $100k+15$, $100k+25$ au nombre $p$ jusqu’à vous arrêter avant de tomber sur un nombre strictement négatif.

Notez $\ell$ le nombre de soustractions effectuées.

Premier cas. Supposez que $p\geq 100k+5$, soit $p\geq 5(20k+1)$ de sorte que $\ell \geq 1.$

Alors :

\begin{align*}
& (100k+5)+\dots+(100k+10\ell-5) \leq p\\
&p <  (100k+5)+\dots+(100k+10\ell+5).
\end{align*} 

Le nombre de termes de la somme $(100k+5)+\dots+(100k+10\ell-5)$ est égal à $\ell$, si bien que :

\begin{align*}
(100k+5)+\dots+(100k+10\ell-5)  &= \ell\times \frac{100k+5+100k+10\ell-5}{2}\\
&=\ell\times \frac{200k+10\ell}{2}\\
&=\ell\times (100k+5\ell)\\
&=5\ell\times (20k+\ell).
\end{align*}

Le nombre de termes de la somme $(100k+5)+\dots+(100k+10\ell+5)$ est égal à $\ell+1$, si bien que :

\begin{align*}
(100k+5)+\dots+(100k+10\ell+5)  &= (\ell+1)\times \frac{100k+5+100k+10\ell+5}{2}\\
&=(\ell+1)\times \frac{200k+10\ell+10}{2}\\
&=(\ell+1)(100k+5\ell+5)\\
&=5(\ell+1)(20k+\ell+1).
\end{align*}

Par ce procédé, vous trouvez un entier $\ell$ tel que :

\boxed{5\ell\times (20k+\ell) \leq p < 5(\ell+1)(20k+\ell+1).}

\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
p = 100r+u & \dots & \dots & \dots & \dots& \dots &\dots & \dots& \dots&p-5\ell\times (20k+\ell)\\
\hline
100k+5 & \dots &  \dots & \dots &\dots & \dots & \dots & \dots & \dots\\
\hline
\end{array}

Second cas. Supposez que $p< 100k+5$, soit $p< 5(20k+1)$ de sorte que $\ell = 0.$ Alors, $p$ étant positif, l’inégalité $5\ell\times (20k+\ell) \leq p < 5(\ell+1)(20k+\ell+1)$ est encore valable : en effet, quand $\ell=0$ vous avez $5(\ell+1)(20k+\ell+1) = 5(20k+1).$

Le nombre $\ell$ est bien un chiffre

Raisonnez par l’absurde en supposant que $\ell \geq 10.$

Du coup :

\begin{align*}
& p\geq 50(20k+10)\\
&p  \geq 1000k+500\\
&100r+u\geq 1000k+500.

\end{align*}

Comme $95\geq u$ vous déduisez ce qui suit :

\begin{align*}
&100r+95\geq 100r+u\\
&100r+95 \geq 1000k+500.
\end{align*}

Cela fournit :

100r\geq 1000k+405.

Il a été montré précédemment que :

r\leq 10k+4.

Après multiplication par $100$, il vient :

100r\leq 1000k+400 < 1000k+405\leq 100r.

D’où la contradiction recherchée.

Donc $\ell$ est bien un chiffre.

Prouvez que la racine carrée entière de $n$ est égale à $10k+\ell$

Vous partez de l’encadrement obtenu à partir de la deuxième tranche et l’ensemble s’enchaîne :

\begin{align*}
5 (20k+\ell) &\leq p < 5(\ell+1)(20k+\ell+1)\\
5 (20k+\ell) &\leq 100r+u < 5(\ell+1)(20k+\ell+1)\\
5 (20k+\ell) &\leq 100(c-5k^2)+u < 5(\ell+1)(20k+\ell+1)\\
5 (20k+\ell) &\leq 100c-500k^2+u < 5(\ell+1)(20k+\ell+1)\\
5 (20k+\ell)+500k^2 &\leq 100c+u < 5(\ell+1)(20k+\ell+1)+500k^2\\
5 (20k+\ell)+500k^2 &\leq m < 5(\ell+1)(20k+\ell+1)+500k^2\\
5 (20k+\ell)+500k^2 &\leq 5n < 5(\ell+1)(20k+\ell+1)+500k^2\\
 \ell(20k+\ell)+100k^2 &\leq n < (\ell+1)(20k+\ell+1)+100k^2\\
(10k)^2 +2(10k) \ell + \ell^2&\leq n < (10k)^2+2(10k)(\ell+1)+(\ell+1)^2\\
(10k+\ell)^2 &\leq n < (10k+\ell+1)^2.
\end{align*}

Il en résulte que :

\boxed{10k+\ell \leq \sqrt{n} < (10k+\ell)+1.}

Ainsi la racine carrée entière de $n$ a bien été déterminée.

Prolongements

Démontrez que la méthode décrite ci-dessus reste valable pour des nombres plus grands, quitte à rajouter des tranches supplémentaires.

Soit $n$ un entier tel que $n\leq 199999$, de sorte que $5n \leq 999995.$ En découpant $m=5n$ en trois tranches de deux chiffres, vous avez $m = 10000a+100b+c$ où $a$, $b$ et $c$ sont des entiers naturels tels que $a\leq 99$, $b\leq 99$ et $c\leq 95.$

En appelant $k$ le nombre de soustractions de la première tranche, $\ell$ le nombre de soustractions de la deuxième tranche et $h$ le nombre de soustractions de la troisième tranche, démontrez que $k$, $\ell$ et $h$ sont des chiffres et que la racine carrée entière de $n$ est égale à $100k+10\ell+h.$

Généralisez alors à un entier naturel $n$ quelconque : posez encore $m=5n$ que vous découpez en $r$ tranches de deux chiffres et poursuivez.

Le but de cet article est de démontrer qu’un nombre entier $n\geq 2$ est premier, si et seulement si, pour tout entier $k$ compris entre $1$ et $n-1$, le coefficient binomial $\binom{n}{k}$ est divisible par $n.$

Visualisez le triangle de Pascal

Les premières lignes du tableau de Pascal sont les suivantes, à chaque fois est donnée la valeur du coefficient binomial $\binom{n}{k}.$

\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
&k=0&k=1&k=2 & k=3 & k=4& k=5& k=6& k=7& k=8\\
\hline
n=0&1 & \\
\hline
n=1&1 & 1\\
\hline
n=2&1 & 2 & 1\\
\hline
n=3&1 & 3 & 3 & 1\\
\hline
n=4&1 & 4 & 6 & 4 & 1\\
\hline
n=5&1 & 5 & 10 & 10 & 5& 1\\
\hline
n=6&1 & 6 & 15 & 20 & 15& 6 & 1\\
\hline
n=7&1 & 7 & 21 & 35 & 35& 21 & 7 & 1\\
\hline
n=8&1 & 8 & 28 & 56 & 70& 56 & 28 & 8&1\\
\hline
\end{array}

En prenant un numéro de ligne qui est un nombre premier, par exemple lorsque $n=7$, vous constatez que les coefficients binomiaux $7$, $21$, $35$, $35$, $21$ et $7$ sont tous des multiples de $7.$ Autrement dit :

\forall k\in\llbracket 1, 6\rrbracket, \quad 7 \left| \binom{7}{k}\right..

Par contre, en prenant $n=6$ qui n’est pas un nombre premier, vous constatez, par exemple que $20$ n’est pas un multiple de $6$, ce qui s’écrit ainsi :

6 \not\left| \binom{6}{3}\right..

Autrement dit :

\exists k\in\llbracket 1, 5\rrbracket, \quad 6 \not\left| \binom{6}{k}\right..

Le premier sens comme conséquence du lemme d’Euclide

Soit $n$ un nombre entier supérieur ou égal à $2.$ Vous supposez que $n$ est un nombre premier.

Soit $k$ un nombre entier compris entre $1$ et $n-1.$ Le coefficient binomial $\binom{n}{k}$ se calcule avec une expression comportant des factorielles :

\binom{n}{k} = \frac{n!}{k! (n-k)!}.

Vous déduisez de ce qui précède que :

n! = k! (n-k)! \binom{n}{k}.

Comme $n! = n\times (n-1)!$ il s’ensuit que $n$ divise le produit $k! (n-k)! \binom{n}{k}.$

Supposez que $n$ ne divise pas le coefficient binomial $\binom{n}{k}.$ Comme $n$ est un nombre premier qui divise le produit des deux nombres $k! (n-k)!$ et $\binom{n}{k}$ le lemme d’Euclide (vous en trouverez une démonstration dans le contenu rédigé dans l'article 126) permet d’affirmer que $n$ divise $k! (n-k)!.$ Toujours d’après le même lemme d’Euclide, $n$ divise un des facteurs noté $i$ du produit $k! (n-k)!.$ Comme $k$ est compris entre $1$ et $n-1$, tous les facteurs du produit $k! (n-k)!$ sont des nombres entiers compris entre $1$ et $n-1.$ Il s’ensuit que $i$ lui-même est un entier compris entre $1$ et $n-1.$

Or, $n$ divise $i$ avec $i$ non nul impose d’avoir $n\leq i.$ Or il a été vu que $i \leq n-1$ ce qui aboutit à une contradiction.

Par l’absurde, il a été prouvé que $n$ divise le coefficient binomial $\binom{n}{k}.$

Ainsi, pour tout entier $n$ supérieur ou égal à $2$, l’implication ci-dessous est démontrée.

\boxed{n \text{ est premier }\implies \forall k\in\llbracket 1, n-1\rrbracket, \quad n \left| \binom{n}{k}\right..}

Le sens réciproque comme conséquence de la relation de Pascal et de l’arithmétique modulaire

Visualisez la situation lorsque $n=8$

Supposez que, pour $n=8$, vous ayez :

\forall k\in\llbracket 1, n-1\rrbracket, \quad n \left| \binom{n}{k}\right..

Vous raisonnez modulo $8$ et obtenez :

\forall k\in\llbracket 1, 7\rrbracket, \quad \binom{8}{k} \equiv 0 \mod 8.

En écrivant le triangle de Pascal modulo $8$ pour les lignes $n=7$ et $n=8$ il vient :

\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
&k=0&k=1&k=2 & k=3 & k=4& k=5& k=6& k=7& k=8\\
\hline
n=7&1 &  &  &  & &  &  & \\
\hline
n=8&1 & 0 & 0 & 0 & 0& 0 & 0 & 0&1\\
\hline
\end{array}

Pour déterminer le résidu du coefficient binomial $\binom{7}{1}$ modulo $8$, vous utilisez la relation de Pascal :

\binom{7}{0}+\binom{7}{1} = \binom{8}{1}.

Ainsi :

\binom{7}{1} = \binom{8}{1} - \binom{7}{0}.

En raisonnant modulo $8$ cela donne :

\begin{align*}
\binom{7}{1} &\equiv  0 - 1 \mod 8\\
&\equiv  -1 \mod 8.
\end{align*}

En continuant ainsi, vous obtenez tous les résidus modulo $8$ de la ligne du triangle de Pascal pour $n=7$ et constatez une alternance de $1$ et de $-1.$

\begin{array}{|c|c|c|c|c|c|c|c|c|c|}
\hline
&k=0&k=1&k=2 & k=3 & k=4& k=5& k=6& k=7& k=8\\
\hline
n=7&1 & -1 & 1  & -1  &1 &-1  &1  &-1 \\
\hline
n=8&1 & 0 & 0 & 0 & 0& 0 & 0 & 0&1\\
\hline
\end{array}

Note. Vous ignorez le dernier résidu de la ligne pour $n=7$ qui est égal à $-1.$ En prenant une autre ligne, par exemple $n=9$, vous auriez trouvé à la ligne $n=8$ un résidu de $1$ et n’auriez pas pu conclure à une absurdité.

Comme $8$ n’est pas premier, il admet un diviseur propre, à savoir un nombre $d$ compris entre $2$ et $7$, tel que $d\mid 8.$

Vous vous intéressez au coefficient binomial $\binom{8}{d} = \binom{8}{2}$ et l’exprimez avec un coefficient binomial situé dans la ligne précédente du tableau de Pascal :

\begin{align*}
\binom{8}{2} &= \frac{8!}{2! 6!}\\
&=\frac{8 \times 7! }{2\times 1! 6!}\\
&=\frac{8}{2}\times \frac{7!}{1! 6!}\\
&= 4\times \binom{7}{1}.
\end{align*}

En prenant les résidus modulo $8$, vous obtenez :

\begin{align*}
\binom{8}{2} &\equiv 4\times (-1) \mod 8\\
&\equiv -4 \mod 8.
\end{align*}

Du coup, il vient :

0 \equiv-4 \mod 8.

Ceci est absurde.

Vous en déduisez qu’il est impossible que $8$ divise tous les coefficients binomiaux $\binom{8}{k}$ lorsque $k$ décrit l’intervalle d’entiers $\llbracket 1, 7\rrbracket.$

Traitez le cas général

Soit $n$ un entier supérieur ou égal à $2$, tel que :

\forall k\in\llbracket 1, n-1\rrbracket, \quad n \left| \binom{n}{k}\right..

Si $n = 2$, le nombre $n$ est un nombre premier et le résultat est démontré.

Supposez maintenant que $n\geq 3.$

Alors :

\forall k\in\llbracket 1, n-1\rrbracket, \quad \binom{n}{k} \equiv 0 \mod n.

Vous allez maintenant effectuer une récurrence limitée afin de déterminer les résidus modulo $n$ des coefficients binomiaux $\binom{n-1}{k}$ lorsque $k$ décrit l’intervalle $\llbracket 0, n-1\rrbracket.$

Pour tout entier $k\in \llbracket 0, n-1\rrbracket$ vous notez $\mathscr{P}(k)$ la propriété : « le résidu modulo $n$ du coefficient binomial $\binom{n-1}{k}$ est égal à $(-1)^k$ ».

Initialisation. Pour $k=0$, vous avez d’une part $(-1)^k = (-1)^0 = 1.$

D’autre part, $\binom{n-1}{0} = 1$ donc $\binom{n-1}{0} = (-1)^0$ ce qui donne :

\binom{n-1}{0} \equiv (-1)^0 \mod n.

La propriété $\mathscr{P}(0)$ est vérifiée.

Hérédité. Soit $k$ un entier naturel inférieur ou égal à $n-2$ tel que $\mathscr{P}(k)$ soit vérifiée.

Vous avez déjà :

\binom{n-1}{k} \equiv (-1)^k \mod n.

D’après la relation de Pascal :

\binom{n-1}{k} + \binom{n-1}{k+1} = \binom{n}{k+1}.

 \binom{n-1}{k+1} = \binom{n}{k+1} - \binom{n-1}{k}.

Comme $k+1$ est un entier supérieur ou égal à $1$ et inférieur ou égal à $n-1$, vous avez :

\binom{n}{k+1} \equiv 0 \mod n.

Du coup :

\begin{align*}
 \binom{n-1}{k+1} &\equiv 0 - (-1)^k \mod n \\
&\equiv  (-1)^{k+1} \mod n.
\end{align*}

Donc la propriété $\mathscr{P}(k+1)$ est vérifiée.

Conclusion. Par récurrence limitée, il a été établi que :

\forall k\in\llbracket 0, n-1\rrbracket, \quad\binom{n-1}{k} \equiv (-1)^k \mod n.

Supposez que $n$ ne soit pas un nombre premier.

Il existe deux diviseurs propres $d$ et $d’$ c’est-à-dire deux entiers compris entre $2$ et $n-1$ tels que $n = dd’.$

Vous exprimez le coefficient binomial $\binom{n}{d}$ de la façon suivante :

\begin{align*}
\binom{n}{d} &= \frac{n! }{d! (n-d!)}\\
&= \frac{n}{d}\times \frac{(n-1)!}{(d-1)! (n-d)!}\\
&=d' \times \binom{n-1}{d-1}.
\end{align*}

Maintenant, modulo $n$, vous avez :

\begin{align*}
0 &\equiv \binom{n}{d} \mod n\\
&\equiv d' \times \binom{n-1}{d-1} \mod n.
\end{align*}

Comme $d-1$ est compris entre $0$ et $n-1$, vous déduisez :

\binom{n-1}{d-1} \equiv (-1)^{d-1}\mod n.

Du coup :

0\equiv d'\times (-1)^{d-1}\mod n.

En multipliant ce résultat par $(-1)^{d-1}$ vous aboutissez à :

0\equiv d' \mod n.

Il en résulte que $n$ divise $d’$ qui est non nul, donc $n\leq d’ \leq n-1$ ce qui est absurde.

Donc $n$ est un nombre premier.

Ainsi, pour tout entier $n$ supérieur ou égal à $2$, l’implication ci-dessous est démontrée.

\boxed{n \text{ est premier }\impliedby \forall k\in\llbracket 1, n-1\rrbracket, \quad n \left| \binom{n}{k}\right..}

Concluez

Il a été démontré l’équivalence suivante :

\boxed{\forall n\geq 2, n \text{ est premier }\Longleftrightarrow \forall k\in\llbracket 1, n-1\rrbracket, \quad n \left| \binom{n}{k}\right..}

Prolongement

Pourriez-vous utiliser le résultat établi pour démontrer qu’un nombre entier $n\geq 2$ est premier, si et seulement si, pour tout entier $a$ premier avec $n$, $(X+a)^n\equiv X^n+a \mod n$ ?