Euclidean division

For proving the existence of Euclidean division, one can suppose ${\displaystyle b>0,}$ since, if ${\displaystyle b<0,}$ the equality ${\displaystyle a=bq+r}$ can be rewritten ${\displaystyle a=(-b)(-q)+r.}$ So, if the latter equality is a Euclidean division with ${\displaystyle -b>0,}$ the former is also a Euclidean division.

Given ${\displaystyle b>0}$ and ${\displaystyle a,}$ there are integers ${\displaystyle q_{1}}$ and ${\displaystyle r_{1}\geq 0}$ such that ${\displaystyle a=bq_{1}+r_{1};}$ for example, ${\displaystyle q_{1}=0}$ and ${\displaystyle r_{1}=a}$ if ${\displaystyle a\geq 0,}$ and otherwise ${\displaystyle q_{1}=a}$ and ${\displaystyle r_{1}=a-ab.}$

Let ${\displaystyle q}$ and ${\displaystyle r}$ be such a pair of numbers for which ${\displaystyle r}$ is nonnegative and minimal. If ${\displaystyle r<b.}$ we have Euclidean division. Thus, we have to prove that, if ${\displaystyle r\geq b,}$ then ${\displaystyle r}$ is not minimal. Indeed, if ${\displaystyle r\geq b,}$ one has ${\displaystyle a=b(q+1)+(r-b),}$ with ${\displaystyle 0\leq r-b<r,}$ and ${\displaystyle r}$ is not minimal

This proves the existence in all cases. This provides also an algorithm for computing the quotient and the remainder, by starting from ${\displaystyle q=0}$ (if ${\displaystyle a\geq 0}$) and adding ${\displaystyle 1}$ to it until ${\displaystyle a-bq<b.}$ However, this algorithm is not efficient, since its number of steps is of the order of ${\displaystyle a/b}$

The pair of integers r and q such that a = bq + r is unique, in the sense that there can be no other pair of integers that satisfy the same condition in the Euclidean division theorem. In other words, if we have another division of a by b, say a = bq' + r' with 0 ≤ r' < |b|, then we must have that

q' = q and r' = r.

To prove this statement, we first start with the assumptions that

0 ≤ r < |b|

0 ≤ r' < |b|

a = bq + r

a = bq' + r'

Subtracting the two equations yields

b(q – q′) = r′ – r.

So b is a divisor of r′ – r. As

|r′ – r| < |b|

by the above inequalities, one gets

r′ – r = 0,

and

b(q – q′) = 0.

Since b ≠ 0, we get that r = r′ and q = q′, which proves the uniqueness part of the Euclidean division theorem.

In Euclidean division with d as divisor, the remainder is supposed to belong to the interval [0, d) of length |d|. Any other interval of the same length may be used. More precisely, given integers ${\displaystyle m}$, ${\displaystyle a}$, ${\displaystyle d}$ with ${\displaystyle m>0}$, there exist unique integers ${\displaystyle q}$ and ${\displaystyle r}$ with ${\displaystyle d\leq r<m+d}$ such that ${\displaystyle a=mq+r}$.

In particular, if ${\displaystyle d=-\left\lfloor {\frac {m}{2}}\right\rfloor }$ then ${\displaystyle -\left\lfloor {\frac {m}{2}}\right\rfloor \leq r<m-\left\lfloor {\frac {m}{2}}\right\rfloor }$ . This division is called the centered division, and its remainder ${\displaystyle r}$ is called the centered remainder or the least absolute remainder.

This is used for approximating real numbers: Euclidean division defines truncation, and centered division defines rounding.

Given integers ${\displaystyle a}$, ${\displaystyle m}$ and ${\displaystyle R,}$ with ${\displaystyle m>0}$ and ${\displaystyle \gcd(R,m)=1,}$ let ${\displaystyle R^{-1}}$ be the modular multiplicative inverse of ${\displaystyle R}$ (i.e., ${\displaystyle 0<R^{-1}<m}$ with ${\displaystyle R^{-1}R-1}$ being a multiple of ${\displaystyle m}$), then there exist unique integers ${\displaystyle q}$ and ${\displaystyle r}$ with ${\displaystyle 0\leq r<m}$ such that ${\displaystyle a=mq+R^{-1}\cdot r}$. This result generalizes Hensel's odd division (1900).[6]

The value ${\displaystyle r}$ is the N-residue defined in Montgomery reduction.