For simplicity, I will denote the size, or the number of bits its value takes up, of $x$ with $|x|$.

Modular Arithmetic

Arithmetic system defined by a modulus $m$ such that any natural number $n$ is represented as its remainder $n \space (\text{mod } m)$ when integer divided by $m$.

$$ \hspace{59pt}r \equiv n\space(\text{mod }m) \iff n = km + r= \lfloor\frac{n} {m}\rfloor m +r\\ \hspace{59pt}\iff m|(n-r) \\ \hspace{121pt}\iff r \space (\text{mod } m) = n \space (\text{mod }m) $$

Two natural numbers $r$ and $n$ are said to be congruent modulo $m$ if they differ by an integer multiple of $m$ or, equivalently, they share the same remainder when divided by $m$.

Arithmetic Operations

Like standard arithmetic, modular arithmetic is equipped with the following operations.

• Addition and Subtraction. $x \pm y \text{ (mod m)}$
• Multiplication. $x \cdot y \text{ (mod m)}$
• Negation. $-x \text{ (mod m)}$
• Exponentiation. $x^d \text{ (mod m)}$ ****
• Inversion. $xx^{-1} \equiv 1\text{ (mod m)}$

Residue Classes

Equivalence classes which correspond to elements congruent to the same remainder modulo $m$.

$$ R_i = \{x \space | \space x \equiv i \text{ (mod m)} \} $$

Euclidean Algorithm