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\mathrm{\setminus }n:=\lfloor \frac{m}{n}\rfloor ,m\in \mathbb{\mathbb{Z}},n\in {\mathbb{\mathbb{Z}}}^{*},$

where  

⌊ ·⌋

is the floor function. In the mapping

$(m,n)\mapsto (q,r):=(m\mathrm{\setminus }n,m-(m\mathrm{\setminus }n)n)=(\lfloor \frac{m}{n}\rfloor ,m-\lfloor \frac{m}{n}\rfloor n),m\in \mathbb{\mathbb{Z}},n\in {\mathbb{\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

$\lfloor \frac{m}{n}+\mathrm{s}\mathrm{g}\mathrm{n}(n)\frac{1}{2}\rfloor ,m\in \mathbb{\mathbb{Z}},n\in {\mathbb{\mathbb{Z}}}^{*},$

where  

sgn (n)

is the sign function. In the mapping

$(m,n)\mapsto (q,r):=(\lfloor \frac{m}{n}+\mathrm{s}\mathrm{g}\mathrm{n}(n)\frac{1}{2}\rfloor ,m-\lfloor \frac{m}{n}+\mathrm{s}\mathrm{g}\mathrm{n}(n)\frac{1}{2}\rfloor n),m\in \mathbb{\mathbb{Z}},n\in {\mathbb{\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