Integer division

This article page is a stub, please help by expanding it.

Integer division (or Euclidean division) is an operation on integers defined as

$m\backslash n:=\left\lfloor {\frac {m}{n}}\right\rfloor ,\quad m\in \mathbb {Z} ,n\in \mathbb {Z} ^{*},$

where 

⌊ ·⌋

is the floor function. In the mapping

$(m,n)\mapsto (q,r):=\left(m\backslash n,\,m-(m\backslash n)\,n\right)=\left(\left\lfloor {\frac {m}{n}}\right\rfloor ,m-\left\lfloor {\frac {m}{n}}\right\rfloor n\right),\quad m\in \mathbb {Z} ,n\in \mathbb {Z} ^{*},$

given by the division algorithm, the integer quotient 

q ∈ ℤ

, with 

0   ≤   r < | n |

as the remainder.

Least absolute remainder

The least absolute remainder integer division (or nearest integer division) is an operation on integers defined as

$\left\lfloor {\frac {m}{n}}+{\rm {sgn}}(n)\,{\frac {1}{2}}\right\rfloor ,\quad m\in \mathbb {Z} ,n\in \mathbb {Z} ^{*},$

where 

sgn (n)

is the sign function. In the mapping

$(m,n)\mapsto (q,r):=\left(\left\lfloor {\frac {m}{n}}+{\rm {sgn}}(n)\,{\frac {1}{2}}\right\rfloor ,m-\left\lfloor {\frac {m}{n}}+{\rm {sgn}}(n)\,{\frac {1}{2}}\right\rfloor n\right),\quad m\in \mathbb {Z} ,n\in \mathbb {Z} ^{*},$

given by the [least absolute remainder] division algorithm, the nearest integer quotient 

q ∈ ℤ

, with 

−  ⌊   | n | /2⌋   ≤   r < | n |  −  ⌊   | n | /2⌋

as the least absolute remainder.

Examples

The allowed least absolute remainders  mod ±2 are  { − 1, 0} :   (7, 2) maps to  (4, 7  −  4  ×  2) = (4,  − 1) , i.e.  7 = 4  ×  2 + ( − 1) ;   ( − 7, 2) maps to  ( − 3,  − 7  −  ( − 3)  ×  2) = ( − 3,  − 1) , i.e.   − 7 = ( − 3)  ×  2 + ( − 1) ;   (7,  − 2) maps to  ( − 4, 7  −  ( − 4)  ×  ( − 2)) = ( − 4,  − 1) , i.e.  7 = ( − 4)  ×  ( − 2) + ( − 1) ;   ( − 7,  − 2) maps to  (3,  − 7  −  3  ×  ( − 2) = (3,  − 1) , i.e.   − 7 = 3  ×  ( − 2) + ( − 1) .

The allowed least absolute remainders  mod ±256 are  { − 128, ...,  − 1, 0, 1, ..., 127} :   (128, 256) maps to  (1, 128  −  1  ×  256) = (1,  − 128) , i.e.  128 = 1  ×  256 + ( − 128) ;   ( − 128, 256) maps to  0,  − 128  −  0  ×  256) = (0,  − 128) , i.e.   − 128 = 0  ×  256 + ( − 128) ;   (128,  − 256) maps to  ( − 1, 128  −  ( − 1)  ×  ( − 256)) = ( − 1,  − 128) , i.e.  128 = ( − 1)  ×  ( − 256) + ( − 128) ;   ( − 128,  − 256) maps to  (0,  − 128  −  0  ×  ( − 256) = (0,  − 128) , i.e.   − 128 = 0  ×  ( − 256) + ( − 128) .

See also

• Euclidean algorithm
• Divisors
• Prime factorization