1.2  Modulus

The integer quotient of $ x$ and $ y$ may be defined as $ \lfloor x/y
\rfloor$. This formulation leads to the following characterization of the modulus function:1.2

Definition 1.2.1   (mod-def) For all $ x \in \mathbb{R}$ and $ y \in \mathbb{R}$,

$\displaystyle mod(x,y) = \left\{\begin{array}{ll}
x - \lfloor x/y \rfloor y & \mbox{if $y \neq 0$}\\
x & \mbox{if $y = 0$}. \end{array} \right.$

Notation: We shall generally use the infix notation $ x \bmod y$ for $ mod(x,y)$. For the purpose of resolving ambiguous expressions, the precedence of this operator is highr than that of addition and lower than that of multiplication.

Although $ x \bmod y$ is of interest mainly when $ x \in \mathbb{Z}$, $ y
\in \mathbb{Z}$, and $ y > 0$, the definition is less restrictive and arbitrary real arguments must be considered. The following closure properties are worth noting.

Lemma 1.2.1   (integerp-mod) For all $ m \in \mathbb{Z}$ and $ n \in \mathbb{Z}$, $ m \bmod n \in \mathbb{Z}$.

  (natp-mod-2) If $ m \in \mathbb{Z}$, $ n \in \mathbb{Z}$, and $ n > 0$, then $ m \bmod n \in \mathbb{N}$.

PROOF: By Definitions 1.2.1 and 1.1.1,

$\displaystyle m \bmod n = m - \lfloor m/n \rfloor n \geq m - (m/n)n = 0. $

In the usual case $ n > 0$, we also have an upper bound on $ m \bmod n$.

  (mod-bnd-1) If $ m \in \mathbb{Z}$, $ n \in \mathbb{Z}$, and $ n > 0$, then $ m \bmod n < n$.

PROOF: By Definitions 1.2.1 and 1.1.1,

$\displaystyle m \bmod n = m - \lfloor m/n \rfloor n < m - ((m/n)-1) n = n. $

The case $ n=1$ is trivial.

  (mod-by-1) For all $ m \in \mathbb{Z}$, $ m \mod 1 = 0$.

PROOF: By Lemmas 1.2.2 and 1.2.3, $ 0 \leq m \bmod 1 < 1$ and $ m \bmod 1 \in \mathbb{Z}$


When $ m \geq 0$, we have another upper bound on $ m \bmod n$.

  (mod-bnd-2) For all $ m \in \mathbb{N}$ and $ n \in \mathbb{Z}$,

$\displaystyle m \bmod n \leq m.$

PROOF: By Lemma 1.2.1, $ m \bmod n = m - \lfloor m/n \rfloor n$. If $ n > 0$, then $ m/n > 0$, $ \lfloor m/n \rfloor \geq 0$ by Lemma 1.1.3, and $ \lfloor m/n \rfloor n \geq 0$. If $ n<0$, then $ \lfloor m/n \rfloor \leq m/n \leq 0$, and again, $ \lfloor m/n \rfloor n \geq 0$

  (mod-does-nothing) If $ m \in \mathbb{N}$, $ n \in \mathbb{N}$, and $ m < n$, then $ m \bmod n = m$.

PROOF: Since $ 0 \leq m/n < 1$, $ \lfloor m/n \rfloor = 0$ by Definition 1.1.1. Now by Lemma 1.2.1,

$\displaystyle m = \lfloor m/n \rfloor n + m \bmod n = m \bmod n. $

Note that as a consequence of Lemmas 1.2.2, 1.2.3, and 1.2.6, $ mod$ is an idempotent operator in the sense that for $ n > 0$,

$\displaystyle (m \bmod n) \bmod n = m \bmod n.
$

This result is generalized below as Lemma 1.2.20.

We have two equivalent conditions for $ m \bmod n = 0$.

  (mod-0-fl) For all $ m \in \mathbb{Z}$ and $ n \in \mathbb{Z}$,

$\displaystyle m \bmod n = 0 \Leftrightarrow m = \lfloor m/n \rfloor n.$

PROOF: This follows immediately from Lemma 1.2.1

  (mod-0-int) Let $ m \in \mathbb{Z}$ and $ n \in \mathbb{Z}$. If $ n \neq 0$, then

$\displaystyle m \bmod n = 0 \Leftrightarrow m/n \in \mathbb{Z}.$

PROOF: By Lemma 1.2.1,

$\displaystyle m \bmod n = 0 \Leftrightarrow m = \lfloor m/n \rfloor n \Leftrightarrow m/n = \lfloor m/n \rfloor.$

The result follows from Lemma 1.1.1

  (mod-mult-n) For all $ a \in \mathbb{Z}$ and $ n \in \mathbb{Z}$, $ an \bmod n = 0$.

PROOF: If $ n = 0$, then $ an \bmod n = an = 0$. Otherwise, Lemma 1.2.8 applies. 

In the event that $ m$ is a multiple of $ n$, the following lemma may be used to identify the muliplier.

  (mod-squeeze) Let $ m \in \mathbb{Z}$ and $ n \in \mathbb{Z}$. If $ m \bmod n = 0$ and $ (a-1)n < m < (a+1)n$, then $ m = an$.

PROOF: Since $ n \neq 0$, we have $ a-1 < m/n < a+1$. By Lemma 1.2.8, $ m/n \in \mathbb{Z}$, which implies $ m/n = a$

  (m-must-be-n) Let $ m \in \mathbb{Z}$ and $ n \in \mathbb{Z}$. If $ m \bmod n = 0$ and $ 0 < m < 2n$, then $ m = n$.

PROOF: This is Lemma 1.2.10 with $ a=1$

  (mod-0-0) For all $ m \in \mathbb{Z}$, $ n \in \mathbb{Z}$, and $ p \in \mathbb{Z}$,

$\displaystyle m \bmod p = 0 \Leftrightarrow m \bmod n = 0$    and $\displaystyle \lfloor m/n \rfloor \bmod p = 0.$

PROOF: By Lemma 1.2.8,

$\displaystyle m \bmod np = 0$ $\displaystyle \Leftrightarrow$ $\displaystyle m/(np) \in \mathbb{Z}$  
  $\displaystyle \Leftrightarrow$ $\displaystyle m/n \in \mathbb{Z}$    and $\displaystyle (m/n)/p \in \mathbb{Z}$  
  $\displaystyle \Leftrightarrow$ $\displaystyle m/n \in \mathbb{Z}$    and $\displaystyle \lfloor m/n\rfloor /p \in \mathbb{Z}$  
  $\displaystyle \Leftrightarrow$ $\displaystyle m \bmod n = 0$    and $\displaystyle \lfloor m/n \rfloor \bmod p = 0. $  

We have the following generalization of Lemma 1.2.8.

  (mod-equal-int)
Let $ a \in \mathbb{Z}$, $ b \in \mathbb{Z}$, and $ n \in \mathbb{Z}$. If $ n > 0$, then

$\displaystyle a \bmod n = b \bmod n \Leftrightarrow (a-b)/n \in \mathbb{Z}.$

PROOF: By Lemma 1.2.1,

$\displaystyle a-b = \lfloor a/n \rfloor n - \lfloor b/n \rfloor n + (a \bmod n) - (b \bmod n).$

Therefore,

$\displaystyle (a-b)/n = \lfloor a/n \rfloor - \lfloor b/n \rfloor + ((a \bmod n) - (b \bmod n))/n$

and

$\displaystyle (a-b)/n \in \mathbb{Z} \Leftrightarrow ((a \bmod n) - (b \bmod n))/n \in \mathbb{Z}.$

By Lemmas 1.2.2 and 1.2.3, $ 0 \leq a \bmod n < n$ and $ 0 \leq b \bmod n < n$, and hence,

$\displaystyle ((a \bmod n) - (b \bmod n))/n \in \mathbb{Z} \Leftrightarrow a = b. $

  (mod-force-equal) Let $ a \in \mathbb{Z}$, $ b \in \mathbb{Z}$, and $ n \in \mathbb{Z}$. If $ \vert a-b\vert < n$, then

$\displaystyle a \bmod n = b \bmod n \Leftrightarrow a=b.$

PROOF: Since $ \vert(a-b)/n\vert < 1$, $ (a-b)/n \in \mathbb{Z} \Leftrightarrow a=b$. The result follows from Lemma 1.2.13

  (mod-mult) For all $ a \in \mathbb{Z}$, $ m \in \mathbb{Z}$, and $ n \in \mathbb{Z}$,

$\displaystyle (m+an) \bmod n = m \bmod n.$

PROOF: By Lemma 1.1.4,

$\displaystyle \lfloor (m+an)/n \rfloor = \lfloor m/n + a \rfloor = \lfloor m/n \rfloor + a.$

Thus, by Lemma 1.2.1,
$\displaystyle (m+an) \bmod n$ $\displaystyle =$ $\displaystyle m+an - \lfloor (m+an)/n \rfloor$  
  $\displaystyle =$ $\displaystyle m+an - \lfloor m/n \rfloor - a$  
  $\displaystyle =$ $\displaystyle m - \lfloor m/n \rfloor$  
  $\displaystyle =$ $\displaystyle m \bmod n. $  

  (mod-force) Let $ a \in \mathbb{Z}$, $ m \in \mathbb{Z}$, and $ n \in \mathbb{Z}$. If $ an \leq m < (a+1)n$, then

$\displaystyle m \bmod n = m-an.$

PROOF: By Lemmas 1.2.15 and 1.2.6,

$\displaystyle m \bmod n = (m-an) \bmod n = m-an. $

  (mod-bnd-3) Let $ a \in \mathbb{Z}$, $ m \in \mathbb{Z}$, $ n \in \mathbb{Z}$, and $ r \in \mathbb{Z}$. If $ an \leq m < an+r$, then $ m \bmod n < r$.

PROOF: By Lemmas 1.2.15 and 1.2.5,

$\displaystyle m \bmod n = (m-an) \bmod n \leq m-an < r. $

  (mod-sum) For all $ a \in \mathbb{Z}$, $ b \in \mathbb{Z}$, and $ n \in \mathbb{Z}$,

$\displaystyle (a+(b \bmod n)) \bmod n = (a+b) \bmod n.$

PROOF: By Lemma 1.2.1, $ b \bmod n = b - \lfloor b/n \rfloor n$, and hence

$\displaystyle (a + (b \bmod n)) \bmod n$ $\displaystyle =$ $\displaystyle a + (b \bmod n) - \lfloor (a+(b \bmod n))/n \rfloor n$  
  $\displaystyle =$ $\displaystyle a+b- \lfloor b/n \rfloor n - \lfloor (a+b)/n - \lfloor b/n \rfloor \rfloor n$  
  $\displaystyle =$ $\displaystyle a+b- \lfloor b/n \rfloor n - (\lfloor (a+b)/n \rfloor - \lfloor b/n \rfloor) n$  
  $\displaystyle =$ $\displaystyle a+b - \lfloor (a+b)/n \rfloor n$  
  $\displaystyle =$ $\displaystyle (a+b) \bmod n. $  

  (mod-diff) For all $ a \in \mathbb{Z}$, $ b \in \mathbb{Z}$, and $ n \in \mathbb{Z}$,

$\displaystyle (a-(b \bmod n)) \bmod n = (a-b) \bmod n.$

PROOF: By Lemma 1.2.1, $ b \bmod n = b - \lfloor b/n \rfloor n$, and hence

$\displaystyle (a - (b \bmod n)) \bmod n$ $\displaystyle =$ $\displaystyle a - (b \bmod n) - \lfloor (a-(b \bmod n))/n \rfloor n$  
  $\displaystyle =$ $\displaystyle a-b + \lfloor b/n \rfloor n - \lfloor (a-b)/n + \lfloor b/n \rfloor \rfloor n$  
  $\displaystyle =$ $\displaystyle a-b + \lfloor b/n \rfloor n - (\lfloor (a-b)/n \rfloor + \lfloor b/n \rfloor) n$  
  $\displaystyle =$ $\displaystyle a-b - \lfloor (a-b)/n \rfloor n$  
  $\displaystyle =$ $\displaystyle (a-b) \bmod n. $  

  (mod-of-mod) For all $ m \in \mathbb{Z}$, $ k \in \mathbb{Z}$, and $ n \in \mathbb{Z}$,

$\displaystyle (m \bmod kn) \bmod n = m \bmod n.$

PROOF: By Lemma 1.2.1,

$\displaystyle (m \bmod kn) \bmod n$ $\displaystyle =$ $\displaystyle (x \bmod kn) - \lfloor (x \bmod kn)/n \rfloor n$  
  $\displaystyle =$ $\displaystyle x - \left\lfloor \frac{x}{kn} \right\rfloor kn -
\left\lfloor \frac{x - \left\lfloor \frac{x}{kn} \right\rfloor kn}{n} \right\rfloor n$  
  $\displaystyle =$ $\displaystyle x - \left\lfloor \frac{x}{kn} \right\rfloor kn -
\left\lfloor \frac{x}{n} - \left\lfloor \frac{x}{kn} \right\rfloor k \right\rfloor n$  
  $\displaystyle =$ $\displaystyle x - \left\lfloor \frac{x}{kn} \right\rfloor kn -
\left(\left\lfloor \frac{x}{n} \right\rfloor - \left\lfloor \frac{x}{kn} \right\rfloor k \right)
n$  
  $\displaystyle =$ $\displaystyle x - \left\lfloor \frac{x}{n} \right\rfloor n$  
  $\displaystyle =$ $\displaystyle x \bmod n. $  

Lemma 1.2.20 is used most frequently with power-of-two moduli.

  (mod-of-mod-cor) For all $ a \in \mathbb{Z}$, $ b \in \mathbb{Z}$, and $ m \in \mathbb{Z}$, if $ a \geq b \geq 0$, then

$\displaystyle (m \bmod 2^a) \bmod 2^b = m \bmod 2^b.$

PROOF: This is the case of Lemma 1.2.20 with $ n = 2^b$ and $ k = 2^{a-b}$

  (mod-prod) For all $ k \in \mathbb{Z}$, $ m \in \mathbb{Z}$, and $ n \in \mathbb{Z}$,

$\displaystyle km \bmod kn = k(m \bmod n).$

PROOF: By Lemma 1.2.1,

$\displaystyle km \bmod kn$ $\displaystyle =$ $\displaystyle km - \left\lfloor \frac{km}{kn} \right\rfloor kn$  
  $\displaystyle =$ $\displaystyle k (m-\lfloor m/n \rfloor n)$  
  $\displaystyle =$ $\displaystyle k(m \bmod n).$  

  (mod-mod-times) For all $ a \in \mathbb{N}$, $ b \in \mathbb{N}$, and $ n \in \mathbb{N}$, if $ n > 0$, then

$\displaystyle (a \bmod n)b \bmod n = ab \bmod n.
$

PROOF: By Definition 1.2.1 and Lemma 1.1.4,

$\displaystyle (a \bmod n)b \bmod n$ $\displaystyle =$ $\displaystyle (a \bmod n)b - \left\lfloor \frac{(a \bmod n)b}{n} \right\rfloor n$  
  $\displaystyle =$ $\displaystyle \left(a - \left\lfloor\frac{a}{n}\right\rfloor n\right)b
- \left\...
...rac{\left(a - \left\lfloor\frac{a}{n}\right\rfloor n\right)b}{n}\right\rfloor n$  
  $\displaystyle =$ $\displaystyle ab - \left\lfloor\frac{a}{n}\right\rfloor nb
- \left\lfloor\frac{ab}{n} - \left\lfloor\frac{a}{n}\right\rfloor b\right\rfloor n$  
  $\displaystyle =$ $\displaystyle ab - \left\lfloor\frac{a}{n}\right\rfloor nb
- \left(\left\lfloor\frac{ab}{n}\right\rfloor - \left\lfloor\frac{a}{n}\right\rfloor b\right) n$  
  $\displaystyle =$ $\displaystyle ab - \left\lfloor\frac{ab}{n}\right\rfloor n$  
  $\displaystyle =$ $\displaystyle ab \bmod n. $  

  (mod-plus-mod, mod-times-mod) For all $ a \in \mathbb{N}$, $ b \in \mathbb{N}$, $ c \in \mathbb{N}$, and $ n \in \mathbb{N}$, if $ n > 0$ and $ a \bmod n = b \bmod n$, then

$\displaystyle (a+c) \bmod n = (b+c) \bmod n
$

and

$\displaystyle ac \bmod n = bc \bmod n.
$

PROOF: By Lemma 1.2.18,

$\displaystyle (a+c) \bmod n = ((a \bmod n)+c) \bmod n = ((b \bmod n)+c) \bmod n = (b+c) \bmod n,
$

and by Lemma 1.2.23,

$\displaystyle ac \bmod n = (a \bmod n)c \bmod n = (b \bmod n)c \bmod n = bc \bmod n. $

The next four lemmas are trivial consequences of preceding results, but are worth noting because of the frequency with which the modulus 2 occurs in our applications.

  (mod012) For all $ m \in \mathbb{Z}$, $ m \bmod 2 \in \{0,1\}$.

PROOF: By Lemmas 1.2.2 and 1.2.3, $ m \bmod 2 \in \mathbb{Z}$ and $ 0 \leq m \bmod 2 < 2$

  (mod-plus-mod-2) For all $ a \in \mathbb{Z}$ and $ b \in \mathbb{Z}$,

$\displaystyle (a+b) \bmod 2 = a \bmod 2 \Leftrightarrow b \bmod 2 = 0.$

PROOF: By Lemma 1.2.13,

$\displaystyle (a+b) \bmod 2 = a \bmod 2 \Leftrightarrow (a+b-a)/2 = b/2 \in \mathbb{Z} \Leftrightarrow b \bmod 2 = 0.$

  (mod-mod-2-not-equal) For all $ m \in \mathbb{Z}$,

$\displaystyle m \bmod 2 \neq (m+1) \bmod 2.$

PROOF: This follows from Lemma 1.2.13 and the observation that $ 1/2 \notin \mathbb{Z}$

  (mod-2*m+1-rewrite) For all $ m \in \mathbb{Z}$, $ (2m+1) \bmod 2 = 1$.

PROOF: By Lemma 1.2.1,

$\displaystyle (2m+1) \bmod 2 = 2m+1 - \lfloor (2m+1)/2 \rfloor 2 = 2m+1 - m \cdot 2 = 1. $

David Russinoff 2017-08-01