# 1.2  Modulus

The integer quotient of and may be defined as . This formulation leads to the following characterization of the modulus function:1.2

Definition 1.2.1   (mod-def) For all and ,

Notation: We shall generally use the infix notation for . 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 is of interest mainly when , , and , 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 and , .

PROOF: By Definitions 1.2.1 and 1.1.1,

In the usual case , we also have an upper bound on .

PROOF: By Definitions 1.2.1 and 1.1.1,

The case is trivial.

PROOF: By Lemmas 1.2.2 and 1.2.3, and

When , we have another upper bound on .

PROOF: By Lemma 1.2.1, . If , then , by Lemma 1.1.3, and . If , then , and again,

PROOF: Since , by Definition 1.1.1. Now by Lemma 1.2.1,

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

This result is generalized below as Lemma 1.2.20.

We have two equivalent conditions for .

PROOF: This follows immediately from Lemma 1.2.1

PROOF: By Lemma 1.2.1,

The result follows from Lemma 1.1.1

PROOF: If , then . Otherwise, Lemma 1.2.8 applies.

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

PROOF: Since , we have . By Lemma 1.2.8, , which implies

PROOF: This is Lemma 1.2.10 with

PROOF: By Lemma 1.2.8,

 and and and

We have the following generalization of Lemma 1.2.8.

PROOF: By Lemma 1.2.1,

Therefore,

and

By Lemmas 1.2.2 and 1.2.3, and , and hence,

PROOF: Since , . The result follows from Lemma 1.2.13

PROOF: By Lemma 1.1.4,

Thus, by Lemma 1.2.1,

PROOF: By Lemmas 1.2.15 and 1.2.6,

(mod-bnd-3) Let , , , and . If , then .

PROOF: By Lemmas 1.2.15 and 1.2.5,

PROOF: By Lemma 1.2.1, , and hence

PROOF: By Lemma 1.2.1, , and hence

PROOF: By Lemma 1.2.1,

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

PROOF: This is the case of Lemma 1.2.20 with and

PROOF: By Lemma 1.2.1,

PROOF: By Definition 1.2.1 and Lemma 1.1.4,

(mod-plus-mod, mod-times-mod) For all , , , and , if and , then

and

PROOF: By Lemma 1.2.18,

and by Lemma 1.2.23,

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.

PROOF: By Lemmas 1.2.2 and 1.2.3, and

PROOF: By Lemma 1.2.13,

PROOF: This follows from Lemma 1.2.13 and the observation that

PROOF: By Lemma 1.2.1,

David Russinoff 2017-08-01