Exercise 4.1.12 (Expression for the least positive residue of $a$ modulo $m$)

Question

For any integers $a$ and $m\geq 2$, prove that $a - m\lfloor a/m \rfloor$ is the least non-negative residue of $a$ modulo $m$. Write a similar expression for the least positive residue of $a$ modulo $m$.

Richard Ganaye · Accepted Answer

\begin{proof}

\begin{enumerate}
\item[(a)]
The Euclidean division of $a$ by $m \geq 2$ gives
$$a = q m + r,\qquad 0 \leq r < m,$$
where the remainder $r$ is the least non-negative residue of $a$ modulo $m$.

Then $\frac{a}{m} = q + \frac{r}{m}$, where $0 \leq \frac{r}{m} < 1$, thus $q = \lfloor a/m floor$ and 
$$r = a - m\lfloor a/m floor$$
is the least non-negative residue of $a$ modulo $m$.

\item[(b)] We write
$$a = q' m +s, \qquad 0 < s \leq m,$$
where $s$ is the least positive residue of $a$ modulo $m$.
Then $\frac{a}{m} = q' + \frac{s}{m}$,  where $0 < \frac{s}{m} \leq 1$. Thus 
\begin{align*}
  q' &< \frac{a}{m} - \leq q' + 1 ,\
 -q' - 1 & \leq -\frac{a}{m} < - q'.
\end{align*}
Therefore $-q' - 1  = \lfloor  -\frac{a}{m}  floor $, and $q' =  -1 -  \lfloor  -\frac{a}{m} floor$, so
$$ s= a +  m ( 1+  \lfloor  -a/m floor)$$
is the least positive residue of $a$ modulo $m$.
\end{enumerate}
\end{proof}
Check:
\begin{verbatim}
sage: a, m = 143, 7
sage: a + m * (1 + floor(-a/m))
3
sage: a, m = 140, 7
sage: a + m * (1 + floor(-a/m))
7
\end{verbatim}

Exercise 4.1.12 (Expression for the least positive residue of $a$ modulo $m$)

Answers

Comments

Exercise 4.1.12 (Expression for the least positive residue of $a$ modulo $m$)

Answers

Comments

Add answer