The scope of the multiplicative inverse?

Question

First, Let $c$ denote the multiplicative inverse of $l~ (mod~ m)$, then $l\times c\equiv 1~(mod~ m)$ always hold. $l$ and $m$ are coprime. If we known $l$ and $m$, Extended Euclid's Algorithm can calculate $c$. I had known $l\in [a, b]$, $l>m$, and want to known the scope of $c$ or $l\times c$. Or add any condition can confirm the scope of $c$ or $l\times c$.

Answer 1

So we already know

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

You can do as follows now: let $\,k\in\Bbb Z\,\;$ be s.t. $\;\;\,km\le l<(k+1)m\,\;$ , then you can make sure that also $\;km\le c<(k+1)m\,,\,\;c=l^{-1}\pmod m\,$

For example, if we have

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

then we can do as follows:

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

and of course also $\,33\le 36<44\,$ ...