Modular arithmetic

Another common feature of mathematics of signal processing is the need to deal with repeating sequences and periodicity. We use real numbers to model continuously repeating processes (like a point traveling continuously around a circle), but we also occasionally have discrete repeating processes, like the hours on a clock: 12:00, 1:00, 2:00, \dots, 11:00. Modular arithmetic is the math of discrete repetition.

For a positive integer \(N > 1\) (the modulus), we define for any integer \(q \in \mathbb{Z}\)

\[q \mod N \in \{0, 1, \dots, N-1\}\]

to be the remainder of \(q / N\). Equivalently:

\[k \leftarrow q \mod N \quad\quad \text{such that } a \cdot N + k = q.\]

for non-negative integer \(a \in \mathbb{N}\).

In Python code, this is implemented by

# The % symbol
q % N

# Or the numpy function np.mod
np.mod(q, N)

Examples

A few examples:

• \(3 \mod 2 = 1\)

• \(-1 \mod 4 = 3\)

• \(20 \mod 5 = 0\)

• \(10 \mod 10 = 0\)