5
$\begingroup$

Let $m$,$l$ be coprime integers where $m,l\geq 2$. For any integer $a$ and positive base $b \ (b\geq 2)$, let $ [a]_b $ denote the element of $\{0,\ldots, b-1\}$ that satisfies the equivalence $[a]_b \equiv a \bmod b$.

For any integer $n$, one can write $$ nl[l^{-1}]_m - nm[(-m)^{-1}]_l = n, $$ as Bézout's Identity yields $$ l[l^{-1}]_m - m[(-m)^{-1}]_l = 1 $$ (the existence of inverses is assured by the coprimality of $m$ and $l$).

Question: Under what conditions on $n$ does the equality $$ l[nl^{-1}]_m - m[n(-m)^{-1}]_l = n $$ hold?

Improve this question
$\endgroup$
7
  • $\begingroup$ welcom to MO !!!!!!!!!!! $\endgroup$
    – zeraoulia rafik
    Jan 10, 2018 at 20:49
  • $\begingroup$ If you really mean that $[...]_m$ is the least non-negative class representative mod m of whatever is inside the brackets, then your version of Bezout's relation is wrong: $3\times 1 - 2\times 2 $ is not equal to $1$. Now I don't know how badly you needed this to be true. $\endgroup$
    – Arnaud Mortier
    Jan 10, 2018 at 21:52
  • $\begingroup$ $[-2]^{-1} = 1$ in your comment. $\endgroup$
    – Andrey Rukhin
    Jan 10, 2018 at 22:11
  • $\begingroup$ My bad! I missed this minus sign. This is perfect then. Thanks. $\endgroup$
    – Arnaud Mortier
    Jan 10, 2018 at 22:24
  • 1
    $\begingroup$ Is "precisely when $\lfloor n\frac{l^{-1}}m \rfloor = \lfloor n\frac{m^{-1}}l \rfloor$" an acceptable answer? I think it's true.... $\endgroup$
    – Greg Martin
    Jan 10, 2018 at 22:35

4 Answers 4

Reset to default
3
$\begingroup$

Each integer number $n$ can be uniquely expressed in the form $n=lx+my$, where $0\le x\le m-1$ and $y\in \mathbb{Z}.$ This artificial numeral system is more suitable for the riven problem because for $n=lx+my$ $$l[nl^{-1}]_m - m[n(-m)^{-1}]_l = lx -m[-y]_l. $$ The last expression is equal to $n$ iff $-l<y\le 0.$ So the final answer is the set of numbers $$\{n=lx+my:0\le x\le m-1, -l<y\le 0\}.$$

Improve this answer
$\endgroup$
2
$\begingroup$

I'll use Max's notations for the sake of clarity. Notice that if $ lm $ divides $ n $ then $ K =0 $ and the condition you want to achieve always fails (unless $ n=0 $...). Hence by coprimality you may assume that $ n $ is either not a multiple of $ m $ or not a multiple of $ l $. In the first case $[l^{-1} n]_m$ cannot be $0 $ so at the end of the day the condition on $ n $ becomes $$-l <n <l+m $$ and similarly in the latter case $$-l-m<n <m $$ This is still only a sufficient condition though.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What if n is a small positive multiple of l (or -m)? Gerhard "Really, Look At Sylvester's Problem" Paseman, 2018.01.10. $\endgroup$
    – Gerhard Paseman
    Jan 10, 2018 at 23:43
  • 1
    $\begingroup$ @Arnaud: Nice observation. It can be further generalized - see update to my answer. $\endgroup$
    – Max Alekseyev
    Jan 11, 2018 at 0:36
2
$\begingroup$

Let $K=l[nl^{-1}]_m - m[-nm^{-1}]_l$. Notice that $$ K \equiv n \pmod{lm} $$ and $$ -m(l-1) \leq K \leq l(m-1). $$

Let's first assume $n\ge 0$. To guarantee that $K=n$, one needs to have $n\leq l(m-1)$ and $n-lm<-m(l-1)$, i.e. $n<m$.

Similarly, if $n<0$, then $n>-m(l-1)$ and $n+lm>l(m-1)$, i.e. $n>-l$.

Overall, the equality $K=n$ is guaranteed if $-l<n<m$.

UPDATE (generalization of Arnaud's answer) If we additionally assume that $\gcd(n,l)=g_l<l$ and $\gcd(n,m)=g_m<m$. Then the bounds become $$ lg_m-m(l-1) \leq K \leq l(m-1) - mg_l. $$ Correspondingly, the guaranteed range for $n$ extends to $$-l-mg_l < n < m + lg_m.$$

Improve this answer
$\endgroup$
6
  • $\begingroup$ Note that l and -m (and small multiples) are solutions for n. (And -l and m are not.) I think it gives an interesting split of the numbers between 1 and lm into two camps, where the sign corresponds to a solution in positive integers to al +bm =n, but shifted somehow. Also, l+1 is a solution (if l+1 less than m) as should be exactly one of -m+1 or -m-1. Gerhard "Still Checking For Sign Errors" Paseman, 2018.01.10. $\endgroup$
    – Gerhard Paseman
    Jan 10, 2018 at 22:57
  • $\begingroup$ Really? Please have one post such an $l \gt m$, because I can't find one where K is not l. Indeed I keep getting l times 1 minus m times 0 is l everytime m and l are coprime. Gerhard "Maybe L'm Doing It Wrong?" Paseman, 2018.01.10. $\endgroup$
    – Gerhard Paseman
    Jan 10, 2018 at 23:25
  • $\begingroup$ There is nothing wrong with Max's solution, the only thing is that it gives a sufficient condition rather than a characterisation. $\endgroup$
    – Arnaud Mortier
    Jan 10, 2018 at 23:36
  • $\begingroup$ @Gerhard: I see now what you meant. Sorry for confusion. Things are a bit fuzzy when $n$ is not co-prime to $lm$. $\endgroup$
    – Max Alekseyev
    Jan 10, 2018 at 23:46
  • $\begingroup$ You can add that this generalization gives the largest interval of solutions containing $0$, since the left- and right-hand sides are never solutions for $n$. $\endgroup$
    – Arnaud Mortier
    Jan 11, 2018 at 14:55
1
$\begingroup$

Note that $0,l,-m$ are solutions and $-l,m$ are not. Further, if $n \leq 0$ is a solution, then $n+ml$ is not, and similarly for $n \geq 0$ and $n-ml$. Also, for $0 \lt k \lt m$ we have $kl$ is a solution, and similarly for $-m$. Finally, if $n$ is a solution and $n+1$ is not precluded from being a solution, then $n+1$ is a solution.

This is not a proof of Greg Martin's comment, but I believe it leads to a functional and laborious proof of it, or something like it. It is my way of being unsuccinct.

Gerhard "Still Has Shades Of Sylvester" Paseman, 2018.01.10.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .