¿El alcance de la inversa multiplicativa?

Question

En primer lugar, dejemos $c$ denotan la inversa multiplicativa de $l~ (mod~ m)$ entonces $l\times c\equiv 1~(mod~ m)$ siempre se mantiene. $l$ y $m$ son coprimos. Si conocemos $l$ y $m$ El Algoritmo de Euclides extendido puede calcular $c$ . Yo había conocido $l\in [a, b]$ , $l>m$ y quiere conocer el alcance de $c$ o $l\times c$ . O añadir cualquier condición puede confirmar el alcance de $c$ o $l\times c$ .

Answer 1

Así que ya sabemos

$$l>m\;,\;a\le l<b\;,\;\;a,b,l,m\in\Bbb Z$$

Ahora puedes hacer lo siguiente: deja que $\,k\in\Bbb Z\,\;$ ser s.t. $\;\;\,km\le l<(k+1)m\,\;$ Entonces puedes asegurarte de que también $\;km\le c<(k+1)m\,,\,\;c=l^{-1}\pmod m\,$

Por ejemplo, si tenemos

$$l=37\;,\;\;m=11\;,\;\;k=3\;\;\left(\text{ because}\;\;3\cdot 11\le 37<4\cdot 11\right)$$

entonces podemos hacer lo siguiente:

$$37=4\pmod{11}\;\wedge\;4^{-1}=3\pmod{11}\implies 3\cdot 33+3=33+3=36=37^{-1}\pmod{11}$$

y por supuesto también $\,33\le 36<44\,$ ...