Modulo Arithmetic

The supported modulo operations are addition, subtraction, and multiplication. The properties of these modulo operations are as follows:

$⟨$ Theorem A-1.2.1 $⟩$ Properties of Modulo Operations

For any integer $x$ , the following is true:

1.: Addition: $a \equiv b mod q ⟺ a + x \equiv b + x mod q$
2.: Subtraction: $a \equiv b mod q ⟺ a - x \equiv b - x mod q$
3.: Multiplication: $a \equiv b mod q ⟺ a \cdot x \equiv b \cdot x mod q$ . This equivalence holds provided that $\gcd (x, q) = 1$ . Without this assumption, only the implication $a \equiv b mod q \Rightarrow a \cdot x \equiv b \cdot x mod q$ is guaranteed.

Proof.

For any integer $x$ ,

1.

Addition:

a \equiv b mod q ⟺ a = b + 𝑘𝑞

(for some integer

k

) #

a

and

b

differ by some multiple of

q

$⟺ a + x = b + k \cdot q + x$

$⟺ a + x = b + x + k \cdot q$ $▹$ $a + x$ and $b + x$ differ by some multiple of $q$

$⟺ a + x \equiv b + x mod q$

2.

Subtraction:

a \equiv b mod q ⟺ a = b + 𝑘𝑞

(for some integer

k

)

$⟺ a - x = b + k \cdot q - x$

$⟺ a - x = b - x + k \cdot q$ $▹$ $a - x$ and $b - x$ differ by some multiple of $q$

$⟺ a - x \equiv b - x mod q$

3.

Multiplication:

a \equiv b mod q ⟺ a = b + 𝑘𝑞

(for some integer

k

)

$⟹ a \cdot x = b \cdot x + k \cdot q \cdot x$

$⟹ a \cdot x = b \cdot x + k_{x} \cdot q$ (where $k_{x} = k \cdot x$ ) $▹$ $a \cdot x$ and $b \cdot x$ differ by some multiple of $q$

$⟹ a \cdot x \equiv b \cdot x mod q$

Conversely, if $x$ and $q$ are coprime (i.e., $\gcd (x, q) = 1$ ), then $x$ has a multiplicative inverse $x^{- 1}$ modulo $q$ . From $a \cdot x \equiv b \cdot x mod q$

$⟹ a \cdot x \cdot x^{- 1} \equiv b \cdot x \cdot x^{- 1} mod q$

$⟹ a \equiv b mod q$

□

Based on the modulo operations in Theorem A-1.2.1, we can also derive the following properties of modulo arithmetic:

$⟨$ Theorem A-1.2.2 $⟩$ Properties of Modulo Arithmetic

1.

Associative:

(a \cdot b) \cdot c \equiv a \cdot (b \cdot c) mod q

2.

Commutative:

(a \cdot b) \equiv (b \cdot a) mod q

3.

Distributive:

(a \cdot (b + c)) \equiv ((a \cdot b) + (a \cdot c)) mod q

4.

Interchangeable: Congruent values are interchangeable in modulo arithmetic.

For example, suppose $(a \equiv b mod q)$ and $(c \equiv d mod q)$ . Then, $a$ and $b$ are interchangeable, and $c$ and $d$ are interchangeable in modulo arithmetic as follows:

$(a + c) \equiv (b + d) \equiv (a + d) \equiv (b + c) mod q$

$(a - c) \equiv (b - d) \equiv (a - d) \equiv (b - c) mod q$

$(a \cdot c) \equiv (b \cdot d) \equiv (a \cdot d) \equiv (b \cdot c) mod q$

The proof of Theorem A-1.2.2 is similar to that of Theorem A-1.2.1, which we leave as an exercise for the reader.

A-1.2 Modulo Arithmetic