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.}Partagez !
Diffusez cet article auprès de vos connaissances susceptibles d'être concernées.
Aidez-moi sur Facebook !
Vous appréciez cet article et souhaitez témoigner du temps que j'y ai passé pour le mettre en œuvre. C'est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.
Lisez d'autres articles !
Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira !