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} \]
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 b \equiv c \pm d \pmod n \] \[ a \cdot b \equiv c \cdot d \pmod n \] \[ a^{m} \equiv b^{m} \pmod n, \quad \forall m \in \mathbb{N} \]
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.