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$.
Asked
Active
Viewed 56 times
1
-
What is $,[a,b],$ ? the lower common multiple? Better if you write directly $,l.c.m,$ , and don't mix capital and lower case letters that stand on the same category: it just makes things confusing. Oh, and what do you mean by "scope"? Perhaps an example would clear things out here. – DonAntonio Apr 09 '13 at 11:01
-
@DonAntonio $[a, b]$ is a integer interval. "scope" is mean the value of $M^{-1}$ in a interval. – Yuansheng liu Apr 09 '13 at 11:07
-
If $,[a,b],$ is an interval then $,[a,b]>m,$ doesn't make much sense, does it? Perhaps you meant $,m<a<b,$ ...? And the question still is hard to understand: if $,a<M<b,$ then unless you know more about the integers $,a,b,$ you will hardly be able to say anything about $,M^{-1},$ . What you can always say is that in any list of $,m,$ consecutive integers there will always be exactly one representative for $,M,$ and for $,M^{-1},$ – DonAntonio Apr 09 '13 at 11:09
-
@DonAntonio Corrected. I want to add some useful condition to known something about $c$ – Yuansheng liu Apr 09 '13 at 11:15
1 Answers
0
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\,$ ...
DonAntonio
- 211,718
- 17
- 136
- 287