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?

$\endgroup$
7
  • $\begingroup$ welcom to MO !!!!!!!!!!! $\endgroup$ Jan 10 '18 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$ Jan 10 '18 at 21:52
  • $\begingroup$ $[-2]^{-1} = 1$ in your comment. $\endgroup$ Jan 10 '18 at 22:11
  • $\begingroup$ My bad! I missed this minus sign. This is perfect then. Thanks. $\endgroup$ Jan 10 '18 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$ Jan 10 '18 at 22:35
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\}.$$

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

$\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$ Jan 10 '18 at 23:43
  • 1
    $\begingroup$ @Arnaud: Nice observation. It can be further generalized - see update to my answer. $\endgroup$ Jan 11 '18 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.$$

$\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$ Jan 10 '18 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$ Jan 10 '18 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$ Jan 10 '18 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$ Jan 10 '18 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$ Jan 11 '18 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.