Two numbers \(a, b\) are are congruent \(\bmod k\) if they have the same remainder when divided by \(k\). This is conventionally written \[ a \equiv b \pmod k \] which implies that \[ a = n \cdot k + r \quad \text{and} \quad b = m \cdot k + r \] and similarly \[ k\ |\ (a-b), \quad a = n \cdot k + b, n \in \mathbb{Z} \]
Geometrically this can be thought of wrapping the number lines around an \(k\)-sided polygon. Values on coincident vertices are congruent modulo \(k\).
If \(x = a \pmod n\) then \(a\) is called the residue of \(x\) modulo \(n\). The complete set of all least residues is then \(\{0, 1, 2, \cdots, n\}\). This may also be noted as \(\mathbb{Z}/n\mathbb{Z}\) representing the finite set of \(\bmod n\).
For all \(a,b,c,d \in \mathbb{Z}\) and \(n \in \mathbb{Z}_{>1}\), if \(a \equiv b \pmod n\) and \(c \equiv d \pmod n\) the following also hold \[ a \pm c \equiv b \pm d \pmod n \] \[ a \cdot c \equiv b \cdot d \pmod n \] \[ a^{m} \equiv b^{m} \pmod n, \quad \forall m \in \mathbb{N} \]
Using these properties, any integer in the congerence class may be swapped for the standard representative before performing arithmetic.
Give some integer \(a\) its modular multiplicative inverse \(x\) is an integer such that \(ax \equiv 1 \pmod k\).
As an example under it can be seen that \(2 \cdot 5 \equiv 1 \pmod 9\) which implies that \(2^{-1} \equiv 5 \pmod 9\) and \(5^{-1} \equiv 2 \pmod 9\). Note: \(a^{-1}\) denotes the inverse, not reciprocal.
Not all numbers will have a modular multiplicative inverse. For example, \(3x \not \equiv 1 \pmod 9\ \forall x\). In general it can shown that \[ \begin{align*} a \in \mathbb Z \text{ is invertable} \bmod n \iff \gcd(a,n)=1 \end{align*} \] or simply:, numbers that are prime relative to the modulus are invertible, however factors are not.