# Euclidean division remainder bound

It is normally stated that for any two integers $m,n \in \mathbb{Z}$ there exist $q,r \in \mathbb{Z}$ with $m=qn+r$ where $0 \leq r < n$.

Is it possible to do this with $|r|\leq \frac{|n|}{2}$ instead by allowing negative remainders?

-

## 3 Answers

It’s possible to do it with any set of remainders that is a complete residue system modulo $n$. The most obvious one is of course $\{0,1,\dots,n-1\}$; the symmetric one that you describe is probably the next most obvious and is sometimes used. Note, though, that when $n$ is even you have to make a choice: you can include one of $n/2$ and $-n/2$, but not both. The usual approach is to include $n/2$, so that for $n=6$, for example, you allow remainders of $-2,-1,0,1,2$, and $3$.

In other words, for odd $n$ you have $|r|<\dfrac{|n|}2$, or $$\frac{-|n|+1}2\le r \le \frac{|n|-1}2,$$ and for even $n$ you have $$\frac{-|n|+1}2\le r\le \frac{n}2.$$

-

Yes. Your question very nearly answers itself. $$47 \div 10 = 4 + \frac{7}{10} = 5 - \frac{3}{10}.$$ In one case $q=4$ and $r=7$; in the other, $q=5$ and $r=-3$. If one of these is more than half of $10$, then the other is less.

-

You can explicitly take $q = \left\| \frac{m}{n}\right\|$ and $r = m - n \left\| \frac{m}{n}\right\|$, where $\| \alpha \|$ denotes the nearest integer to $\alpha \in \mathbb{R}$.

Note that for any real number $x$, one has $|x - \| x \|| \leq \frac{1}{2}$. Thus, you always have

$$\left| \frac{r}{n} \right| = \left| \frac{m}{n} - \left\| \frac{m}{n} \right\| \right| \leq \frac{1}{2}$$

or $|r| \leq \frac{|n|}{2}$ as wanted.

-