# When does the following congruence identity hold?

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?

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

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

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.

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

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

• 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. Jan 10 '18 at 22:57
• 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. Jan 10 '18 at 23:25
• There is nothing wrong with Max's solution, the only thing is that it gives a sufficient condition rather than a characterisation. Jan 10 '18 at 23:36
• @Gerhard: I see now what you meant. Sorry for confusion. Things are a bit fuzzy when $n$ is not co-prime to $lm$. Jan 10 '18 at 23:46
• 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$. Jan 11 '18 at 14:55

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.