## Congruence

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}
\]

## Residue

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\).

## Algebraic Properties

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}
\]

## Multiplicative inverse

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.