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