5 Modular math

Two integers are equivalent in modular math if their remainders (after being divided by an integer $n$ ) are the same. Such two integers are called ``congruent modulo n''. For example $5 \mod 2 = 1$ and $1 \mod 2 = 1$ , This means that 5 and 1 are ``congruent modulo 2''. In symbols, we can say that $5 \equiv 1 (\mod 2)$ . This should be read as $(5 \equiv 1) (\mod 2)$ .

Given a modulo-n environment, and given that $0 \le i < n$ , there is an infinite number integers that are congruent modulo n. Namely, the set of $[i]_n = \{x\vert i\in \mathbb{I},x = a + i\times n\}$ is called the equivalence class of $a$ . For example, the equivalence class of 2 congruent to 3 is $[2]_3 = \{\ldots,...-4, -1, 2, 5, \ldots\}$ . Another notation is $[a]_n = \hat{a}$ , module-n is assumed in the ``hat'' notation. The equivalence class of the integer $a$ is also called the congruence class or reside class of $a$ modulo $n$ .

Modular mathematics is congruent with respect to the addition and multiplication operators. This means that $\forall a, a', b, b' \in \mathbb{I}: (a \equiv a') (\mod n) \wedge (b \equiv b... ...b) \equiv (a' + b') (\mod n)) \wedge ((a \cdot b) \equiv (a' \cdot b')(\mod n))$ .

In computer programming, modular math is used all the time. This is because of the fixed width representation of integers. For example, let consider 16-bit integer. The value $1$ and $65537$ are both represented as 0000 0000 0000 0001 in binary.

The more interesting case is how signed numbers are represented. Given that we have using 16-bit integers, we are still using modulo 65536 operators. However, $-1 \equiv 65535 (\mod 65536)$ , $-2 \equiv 65534 (\mod 65536)$ and etc. This is why -1 as a signed 16-bit integer has the same binary representation as 65535 as an unsigned 16-bit integer.

Also interestingly, 2's complement can be used as negation. This is because the negation operator can be defined as follows: $-x = 0-x$ . In modulo-65536 mathematics, $0 \equiv 65536 (\mod 65536)$ . Consequently, the negation of a value $x$ is $-x \equiv 0-x \equiv 65536-x (\mod (65536)$ (because modular mathematics is congruent with respect to addition and subtraction). The two's complement of $x$ can be defined as ``bitwise not of $x$ plus 1'', but it is also simply $(65535-x)+1 = 65536-x$ . Hence, two's complement (n-bit) and negation are modulo-$2^n$ congruent.